Как определить число Strahler на ориентированном графе для потоковой сети
Вопрос / пример / ожидаемые значения
Мне нужно определить число Strahler или порядок потока Strahler для ориентированного графа, представляющего сеть потока. Я могу получать информацию вперед и назад, используя WITH RECURSIVE запросы, но, кажется, мне нужно сделать что-то другое, чтобы определить число Strahler.
Например, здесь есть сеть из 19 сегментов с 10 притоками и одним выходом. Восходящая часть каждого сегмента представлена идентификатором узла.
И те же данные в структуре таблицы, где сегменты связаны to_node, который является нулевым для выхода бассейна.
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);
Ожидаемый результат (expected_order) для чисел Strahler визуализируется здесь:
Существует три правила (из руководства GRASS 7.0):
- если узел не имеет дочерних элементов, его порядок по Strahler равен 1.
- если узел имеет один и только один приток с наивысшим порядком Стратлера i, а все остальные притоки имеют порядок меньше i, то порядок остается i.
- если узел имеет два или более притоков с наибольшим порядком i, то порядок Стралера по узлу равен i + 1.
Что я нашел / попробовал
Что я нашел в копании, чтобы решить эту проблему, так это то, что эти вычисления могут быть выполнены с помощью SQL (за исключением того, что я думаю, что их "сценарий SQL" написан для MS SQL Server). Тем не менее, я не нашел что-то, что можно сделать с PostgreSQL 9.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. Другая [менее захватывающая] идея состоит в том, чтобы вручную запускать итерации для каждого числа Стратлера, которое, как я ожидаю, должно составлять от пяти до восьми порядков (итераций) для моих данных реального мира. Это можно сделать с помощью DO заявление. Но любые лучшие идеи будут приветствоваться.
0 ответов
Я столкнулся с ограничением CTE. Рекурсивный CTE не может сделать LEFT JOIN сам по себе. Просто закончил делать это в функции.
Живой тест: https://www.db-fiddle.com/f/8z58LCVhD62YvkeJjriW8d/0
create or replace function strahler(_parent int) returns table(node int, sn 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.sn) < max(st.sn) then
max(st.sn)
-- 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.sn) = max(st.sn) then
max(st.sn) + 1
end
end as sn
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.*, s.expected_order
from strahler(0) st
join streams s on st.node = s.node
order by st.node;
Выход:
| node | sn | expected_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 выполнит ЛЕВОЕ СОЕДИНЕНИЕ с самим собой), затем выполнит три необходимых условия Strahler. Однако у CTE есть ограничение, рекурсивный CTE не может выполнить LEFT JOIN сам по себе.