我有一个edges我的 PostgreSQL 数据库中的表代表了一个directed图表,有两列:节点来源 and node_to(值是节点的 id)。
给定单个节点(初始节点)我希望能够遍历整个图表,但是在一个无向的 way.
我的意思是,例如下图:
(a->b)
(c->b)
(c->d)
If 初始节点 is a, b, c, or d,无论如何,我会得到[a, b, c, d].
我使用了以下 SQL 查询(基于http://www.postgresql.org/docs/8.4/static/queries-with.html ):
WITH RECURSIVE search_graph(uniq, depth, path, cycle) AS (
SELECT
CASE WHEN g.node_from = 'initial_node' THEN g.node_to ELSE g.node_from END,
1,
CASE WHEN g.node_from = 'initial_node' THEN ARRAY[g.node_from] ELSE ARRAY[g.node_to] END,
false
FROM edges g
WHERE 'initial_node' in (node_from, node_to)
UNION ALL
SELECT
CASE WHEN g.node_from = sg.uniq THEN g.node_to ELSE g.node_from END,
sg.depth + 1,
CASE WHEN g.node_from = sg.uniq THEN path || g.node_from ELSE path || g.node_to END,
g.node_to = ANY(path) OR g.node_from = ANY(path)
FROM edges g, search_graph sg
WHERE sg.uniq IN (g.node_from, g.node_to) AND NOT cycle
)
SELECT * FROM search_graph
它工作得很好......直到我遇到一个有 12 个节点在各个方向上全部连接在一起的情况(对于每一对,我都有 (a->b) 和 (b->a)),这使得查询循环无限期地。 (将 UNION ALL 更改为 UNION 并不能消除循环。)
有没有人有任何建议来处理这个问题?
Cheers,
Antoine.