原始图边表的格式很简单:| node_x | node_y | strength |,其中“node_x” ->“node_y”是具有权重“weight”的直接边。
思路是,如果在探索路径的任何点上,我们发现其子节点中有目标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到4的路径时,对节点2的路径探索应该停止。
总之,如果节点已经有直接边连接目标节点,我不想发现该节点的路径。这意味着在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显然经过了良好的优化,因此我想更深入地研究它。