如何在流网络的有向图上确定Strahler数 [英] How to determine Strahler number on a directed graph for a stream network
问题描述
我需要确定 Strahler编号 或表示流网络的有向图的>"Strahler流顺序" .我可以使用WITH RECURSIVE查询来向前和向后推导信息，但是似乎我需要做一些不同的事情来确定Strahler数字.
I need to determine a Strahler number or Strahler stream order for a directed graph representing a stream network. I can derive information forwards and backwards using WITH RECURSIVE queries, but it seems I need to do something different to determine the Strahler number.
例如，这是一个19段的流网络，具有10个支流和一个出口.每个网段的上游部分由节点ID表示.
For example, here is a 19 segment stream network with 10 tributaries and one outlet. The upstream portion of each segment is represented by a node ID.
和表结构中的相同数据，其中段通过to_node连接，对于盆地出口为空.
And the same data in a table structure, where the segments are connected by to_node, which is null for the basin outlet.
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)在此处显示:
The expected result (expected_order) for the Strahler numbers is visualized here:
有3条规则(来自 GRASS 7.0手册):
- 如果节点没有子节点，则Strahler阶为1.
- 如果该节点只有一个支流，且其支流具有Strahler最高阶 i ，而所有其他支流的阶次都小于i，则该阶仍为 i . li>
- 如果节点有两个或更多支流，且其支流的最大顺序为 i ，则该节点的Strahler顺序为 i + 1.
- if the node has no children, it's Strahler order is 1.
- if the node has one and only one tributary with Strahler greatest order i, and all other tributaries have order less than i, then the order remains i.
- if the node has two or more tributaries with greatest order i, then the Strahler order of the node is i + 1.
我发现/尝试过的东西
What I've found / tried
From what I have found in digging to solve this problem is that this calculation can be done with SQL (except I think their "SQL script" is written for MS SQL Server). However, I haven't found something that can be done with PostgreSQL 9.1.
我最好的尝试之一是计算每个节点的上游节点数，以正确识别支流(一阶)，但不能识别其他支流:
One of the best attempts I have is to count the number of upstream nodes from each node, which correctly identifies the tributaries (1st order), but not others:
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编号.另一个[不太令人兴奋]的想法是为每个Strahler编号手动运行迭代，对于我的真实数据，我希望该迭代在5到8个顺序(迭代)之间.这可以通过 DO语句完成.但是，最好的主意是最好的.
An idea is to use a nth_value(value any, nth integer) window function with an appropriately set window frame range. However, I'm not sure how to set this up, or if it can be set up to identify Strahler numbers. Another [less exciting] idea is to manually run iterations for each Strahler number, which I expect to be between five and eight orders (iterations) for my real world data. This can be done with a DO statement. But any better ideas would be most welcome.
推荐答案
我遇到了CTE的限制.递归CTE不能进行左联接.刚刚结束了它的功能.
I hit a limitation with CTE. Recursive CTE can't do LEFT JOIN to itself. Just ended up doing it in function.
实时测试: https://www.db-fiddle.com/f/8z58LCVhD62YvkeJjriW8d/5
create or replace function strahler(_parent int) returns table(
node int, strahler_order int
)
as
$$
select
s.node,
case
-- If the node is a leaf (has no children), its Strahler number is one.
when count(st.*) = 0 then
1
when count(st.*) >= 2 then
case
-- If the node has one child with Strahler number i,
-- and all other children have Strahler numbers less than i,
-- then the Strahler number of the node is i again.
when min(st.strahler_order) < max(st.strahler_order) then
max(st.strahler_order)
-- If the node has two or more children with Strahler number i,
-- and no children with greater number,
-- then the Strahler number of the node is i + 1.
when min(st.strahler_order) = max(st.strahler_order) then
max(st.strahler_order) + 1
end
end
from streams s
left join lateral strahler(s.node) st on true
where _parent = 0 or s.to_node = _parent
group by s.node
$$ language 'sql';
select st.node, s.expected_order, st.strahler_order
from strahler(0) st
join streams s on st.node = s.node
order by st.node;
测试:
select st.node, s.expected_order, st.strahler_order
from strahler(0) st
join streams s on st.node = s.node
order by st.node;
输出:
| node | expected_order | strahler_order |
| ---- | -------------- | -------------- |
| 1 | 4 | 4 |
| 2 | 4 | 4 |
| 3 | 3 | 3 |
| 4 | 3 | 3 |
| 5 | 3 | 3 |
| 6 | 2 | 2 |
| 7 | 2 | 2 |
| 8 | 2 | 2 |
| 9 | 2 | 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 |
这是原始计划
实时测试: https://www.db-fiddle.com/f/8z58LCVhD62YvkeJjriW8d/1
with recursive search_graph as (
select node as start_node, node
from streams
union all
select sg.start_node, n.node
from streams n
join search_graph sg on n.to_node = sg.node
)
, get_kids as
(
select
s.node as kid,
count(sg.*) - 1 as kid_kids,
s.expected_order
from streams s
join search_graph sg on s.node = sg.start_node
group by s.node, s.expected_order
order by kid_kids
)
, order_safe as
(
select
row_number() over(s) eo,
gk.kid,
gk.kid_kids,
gk_kid.to_node as parent,
gk_p.kid_kids as siblings
from get_kids gk
left join streams gk_kid on gk.kid = gk_kid.node
left join get_kids gk_p on gk_kid.to_node = gk_p.kid
window s as (order by gk_p.kid_kids /* siblings */, gk_kid.to_node /* parent */)
)
select * from order_safe;
输出:
| eo | kid | kid_kids | parent | siblings |
| --- | --- | -------- | ------ | -------- |
| 1 | 11 | 0 | 6 | 2 |
| 2 | 10 | 0 | 6 | 2 |
| 3 | 12 | 0 | 7 | 2 |
| 4 | 13 | 0 | 7 | 2 |
| 5 | 15 | 0 | 8 | 2 |
| 6 | 14 | 0 | 8 | 2 |
| 7 | 17 | 0 | 9 | 2 |
| 8 | 16 | 0 | 9 | 2 |
| 9 | 6 | 2 | 3 | 6 |
| 10 | 7 | 2 | 3 | 6 |
| 11 | 9 | 2 | 5 | 6 |
| 12 | 8 | 2 | 5 | 6 |
| 13 | 5 | 6 | 4 | 8 |
| 14 | 18 | 0 | 4 | 8 |
| 15 | 3 | 6 | 2 | 16 |
| 16 | 4 | 8 | 2 | 16 |
| 17 | 19 | 0 | 1 | 18 |
| 18 | 2 | 16 | 1 | 18 |
| 19 | 1 | 18 | | |
最初的计划是按照安全顺序评估每个节点(将由eo字段协助)，从同级数较少的节点开始，直到同级数较多的节点.然后在将要评估的每个节点上，还将检查其直接子节点(递归CTE将对其自身进行LEFT JOIN)，然后执行必要的Strahler的三个条件.但是，CTE有一个局限性，递归CTE不能对自己进行LEFT JOIN.
The original plan is to evaluate each node in safe order (will be facilitated by eo field), start at nodes with fewer siblings, up to nodes with many siblings. Then on each node that will be evaluated, will also check its immediate children (recursive CTE will do a LEFT JOIN to itself), then perform the necessary Strahler's three conditions. However, CTE has a limitation, recursive CTE can't do LEFT JOIN to itself.
这篇关于如何在流网络的有向图上确定Strahler数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
