3

質問・例・期待値

ストリーム ネットワークを表す有向グラフのStrahler 数またはStrahler ストリーム次数を決定する必要があります。クエリを使用して前方および後方にWITH RECURSIVE情報を取得できますが、ストラーラー数を決定するには別のことを行う必要があるようです。

たとえば、ここに 10 の支流と 1 つの流出口を持つ 19 セグメントのストリーム ネットワークがあります。各セグメントの上流部分は、ノード ID で表されます。

stream_nodes

そして、セグメントが によって接続されているテーブル構造の同じデータto_node。これは流域の排水口では null です。

CREATE TABLE streams (
  node integer PRIMARY KEY,
  to_node integer REFERENCES streams(node),
  expected_order integer
);
INSERT INTO streams(node, to_node, expected_order) VALUES
(1, NULL, 4),
(2, 1, 4),
(3, 2, 3),
(4, 2, 3),
(5, 4, 3),
(6, 3, 2),
(7, 3, 2),
(8, 5, 2),
(9, 5, 2),
(10, 6, 1),
(11, 6, 1),
(12, 7, 1),
(13, 7, 1),
(14, 8, 1),
(15, 8, 1),
(16, 9, 1),
(17, 9, 1),
(18, 4, 1),
(19, 1, 1);

Strahler 数の期待される結果 ( expected_order) は、次のように視覚化されます。

expected_stream_order

3 つのルールがあります ( GRASS 7.0 マニュアルから):

  1. ノードに子がない場合、ストラー次数は 1 です。
  2. ノードにストラーラー最大次数iの支流が 1 つだけあり、他のすべての支流の次数が i より小さい場合、次数はiのままです。
  3. ノードに最大次数iの支流が 2 つ以上ある場合、ノードのストラー次数はi + 1 です。

私が見つけた/試したこと

この問題を解決するために掘り下げて発見したことから、この計算はSQLで実行できるということです（ただし、「SQLスクリプト」はMS SQL Server用に書かれていると思います）。しかし、PostgreSQL 9.1 でできることは見つかりませんでした。

私が行った最善の試みの 1 つは、各ノードから上流ノードの数を数えることです。これにより、支流 (1 次) が正しく識別されますが、他のノードは識別されません。

WITH RECURSIVE search_graph AS (
  SELECT node AS start_node, node
  FROM streams
  -- Connect downstream towards outlet(s)
  UNION ALL
  SELECT sg.start_node, n.node
  FROM streams n
  JOIN search_graph sg ON n.to_node = sg.node
)
SELECT start_node, count(sg.node) as upstream_nodes, expected_order
FROM search_graph sg
JOIN streams s ON sg.start_node = s.node
GROUP BY start_node, expected_order
ORDER BY upstream_nodes DESC, start_node;

 start_node | upstream_nodes | expected_order
------------+----------------+----------------
          1 |             19 |              4
          2 |             17 |              4
          4 |              9 |              3
          3 |              7 |              3
          5 |              7 |              3
          6 |              3 |              2
          7 |              3 |              2
          8 |              3 |              2
          9 |              3 |              2
         10 |              1 |              1
         11 |              1 |              1
         12 |              1 |              1
         13 |              1 |              1
         14 |              1 |              1
         15 |              1 |              1
         16 |              1 |              1
         17 |              1 |              1
         18 |              1 |              1
         19 |              1 |              1
(19 rows)

アイデアは、適切に設定されたウィンドウ フレーム範囲でnth_value(value any, nth integer) ウィンドウ関数を使用することです。ただし、これを設定する方法、または Strahler 番号を識別するように設定できるかどうかはわかりません。もう 1 つの [あまり面白くない] アイデアは、Strahler 数ごとに反復を手動で実行することです。これは、実世界のデータに対して 5 ～ 8 次 (反復) であると予想されます。これはステートメントで実行できます。しかし、より良いアイデアは大歓迎です。DO

4

1 に答える 1