Простой алгоритм поиска по графику в SQL (PostgreSQL)

Question

Я реализовал график узлов в PostgreSQL (не дерево)

структура таблицы в этом формате

id | node1  | node2 
--------------------
1  |   1    |   2
2  |   1    |   3
3  |   4    |   1
4  |   5    |   1
5  |   1    |   6

Это показывает отношения между узлом 1и узлы, к которым он подключен.

Моя проблема

... заключается в том, что мне нужна функция или метод, чтобы найти конкретный путь к узлу в sql.

Я хочучтобы вызвать функцию, подобную SELECT getGraphPath (startnode, targetnode), и это отобразит путь в любой форме (строки или строки)

например, SELECT getGraphPath (1,18) дает:

[1]-->[3]-->[17]-->[18]
[1]-->[4]-->[10]-->[18]

или даже строк:

Result  |
--------
1
3
17
18

Я также хотел бы знать, как пройти по графику, используя поиск в ширину и поиск в глубину.

Answer 1

Примерно так:

with recursive graph_cte (node1, node2, start_id) 
as
( 
  select node1, node2, id as start_id
  from graphs
  where node1 = 1 -- alternatively elect the starting element using where id = xyz
  union all
  select nxt.node1, nxt.node2, prv.start_id
  from graphs nxt
    join graph_cte prv on nxt.node1 = prv.node2
)
select start_id, node1, node2
from graph_cte
order by start_id;

(требуется PostgreSQL 8.4 или выше)

Answer 2

SQL не лучше всего подходит для манипулирования графиками и поиска путей.Возможно, вам лучше загрузить график на процедурный язык и использовать алгоритм Флойд-Варшалла или Алгоритм Джонсона , чтобы найти путь между узлами.

Однако, если вы действительно должны использовать SQL, то я предлагаю вам взять копию SQL Джо Селко для умных , в которой есть целая глава, посвященная графам в SQL.

Answer 3

Вы можете напрямую использовать базу данных графиков для решения вашей проблемы: https://launchpad.net/oqgraph -> graph как механизм хранения mysql

Answer 4

Это не совсем оптимально для памяти, но работает и с циклическими графами:

with recursive graph_cte (node1, node2, path) 
as
( 
  select node1, node2, ARRAY[node1] as path
  from graph
  where node1 = 4 -- start node
  union all
  select nxt.node1, nxt.node2, array_append(prv.path, nxt.node1)
  from graph nxt, graph_cte prv
  where nxt.node1 = prv.node2
  and nxt.node1 != ALL(prv.path)
)
select array_append(path, node2)
from graph_cte
where node2 = 6 -- goal node
limit 1;

Он основан на ранее принятом ответе, но отслеживает путь. Он должен немедленно прекратить поиск, как только найдет целевой узел.