我有以下问题:我正在尝试发现从源节点(node_s)到目标节点(node_t)的所有可能路径。
带有图边的原始表格的格式很简单:| 节点_x | 节点_y | 实力 | ,其中“node_x”->“node_y”是直接边,边的强度为“权重”。
这个想法是,如果在探索路径期间的任何时候,我们发现其子节点中的一个节点具有目标node_t,我们记录该路径并停止从该节点探索路径,否则继续探索。
简单的解决方案是使用 PostgreSQL 的递归 CTE,它构造图的传递闭包:
WITH RECURSIVE transitive_closure (source, target, weight, path_string) AS
(
--non-recurive term
SELECT b.node_x, b.node_y, b.strength, b.node_x || '.' || b.node_y || '.' AS path_string
FROM best_path b
WHERE b.node_x = node_s --source_node
UNION
--recurive term
SELECT tc.source, b.node_y, least(tc.weight,b.strength), tc.path_string || b.node_y || '.' AS path_string
FROM best_path AS b JOIN transitive_closure AS tc ON b.node_x = tc.target
WHERE tc.path_string NOT LIKE '%' || b.node_y || '.%'
)
SELECT *
FROM transitive_closure tc
WHERE tc.target = node_t --target_node
上面的代码将从源节点node_s发现所有可能的路径。只有在传递闭包构造之后,我才能选择从源节点到目标节点的所需路径行(参见最后一个 SELECT 语句)。
例子:
best_path 表有以下数据:
node_x | node_y | strength
--------+--------+----------
1 | 2 | 1
1 | 3 | 1
2 | 4 | 1
2 | 5 | 1
3 | 6 | 1
3 | 7 | 1
4 | 8 | 1
4 | 9 | 1
5 | 10 | 1
5 | 11 | 1
询问:
找到从源节点 = 1 到目标节点 = 4 的路径
结果:
source | target | strength | path_string
--------+--------+----------+------------
1 | 2 | 1 | 1.2.
1 | 3 | 1 | 1.3.
1 | 4 | 1 | 1.2.4.
1 | 5 | 1 | 1.2.5.
1 | 6 | 1 | 1.3.6.
1 | 7 | 1 | 1.3.7.
1 | 8 | 1 | 1.2.4.8.
1 | 9 | 1 | 1.2.4.9.
1 | 10 | 1 | 1.2.5.10.
1 | 11 | 1 | 1.2.5.11.
这不是我需要的。由于已经有从节点 2 到节点 4(目标)的直接边,我不需要路径 1.2.5.、1.2.4.8.、1.2.4.9.、1.2.5.10.、1.2.5.11.,路径探索对于节点 2,应该在发现从 2 到 4 的路径时停止。
总而言之,如果节点已经具有到目标节点的直接边缘,我不想发现节点的路径。这意味着在 CTE 的递归术语中,我希望有一些条件可以说明以下内容,伪代码如下:
WITH RECURSIVE transitive_closure (source, target, weight, path_string) AS
(
--non-recurive term (as before)
SELECT b.node_x, b.node_y, b.strength, b.node_x || '.' || b.node_y || '.' AS path_string
FROM best_path b
WHERE b.node_x = node_s --source_node
UNION
--recurive term
SELECT tc.source, b.node_y, least(tc.weight,b.strength), tc.path_string || b.node_y || '.' AS path_string
FROM best_path AS b JOIN transitive_closure AS tc ON b.node_x = tc.target
WHERE tc.path_string NOT LIKE '%' || b.node_y || '.%'
AND b.node_y = node_t
--will select only rows with direct edge to target
UNION (second union is not allowed in CTE)
SELECT those rows which do not have direct edge to target
AND which parents did not contribute to constructing the query above.
i.e. b.node_x = tc.target where there is no direct edge between b.node_x to node_t
)
作为查找从源节点 = 1 到目标节点 = 4 的路径的查询的结果,我想要以下内容:
source | target | strength | path_string
--------+--------+----------+------------
1 | 2 | 1 | 1.2.
1 | 3 | 1 | 1.3.
1 | 4 | 1 | 1.2.4.
1 | 6 | 1 | 1.3.6.
1 | 7 | 1 | 1.3.7.
在此先感谢您的帮助!
我已经尝试了很多方法:例如 FROM/WHERE 子句中的条件,尝试将 CTE 传递给函数,但没有成功。
任何建议将不胜感激。
我有自己的递归函数,可以实现我想要的,但是,在大量数据上它非常慢;而且 PostgreSQL 的 CTE 显然优化得很好,所以我想深入研究一下。