找到所有对最短路径（APSP）

Question

我必须找到一个子网与其他未通过网络和 TGW 连接的子网之间的 APSP。例如，在我的例子中，对于给定的关系，任何子网到其他子网之间不存在最短路径。

我的数据

CREATE 
(s1:Subnet{name:"sub1"}),
(s2:Subnet{name:"sub2"}),
(s3:Subnet{name:"sub3"}),
(s4:Subnet{name:"sub4"}),
(n1:Network{name:"net1"}),
(s1)-[:SUB_OF]-> (n1),
(s3)-[:SUB_OF]-> (n1),
(s2)-[:SUB_OF]-> (n1),
(s4)-[:SUB_OF]-> (n1),
(s5:Subnet{name:"sub5"}),
(s6:Subnet{name:"sub6"}),
(s7:Subnet{name:"sub7"}),
(s8:Subnet{name:"sub8"}),
(n2:Network{name:"net2"}),
(t1:TGW{name:"tg1"}),
(t2:TGW{name:"tg2"}),
(s5)-[:SUB_OF]-> (n2),
(s6)-[:SUB_OF]-> (n2),
(s7)-[:SUB_OF]-> (n2),
(s8)-[:SUB_OF]-> (n2),
(s5)-[:CONNECT_TO]->(t1),
(t1)-[:CONNECT_TO]->(s3),
(s4)-[:CONNECT_TO]->(t2),
(t2)-[:CONNECT_TO]->(s8);

我的图形投影

MATCH (src:Subnet)-[r:SUB_OF | CONNECT_TO]->(trg:Network|TGW)
RETURN gds.graph.project(
  'cypherGraph10',
  src,
  trg,
  {relationshipType: type(r)},
  {undirectedRelationshipTypes: [type(r)]
})

这并没有给我答案

CALL gds.allShortestPaths.stream('cypherGraph10') YIELD sourceNodeId, targetNodeId, distance
WHERE gds.util.isFinite(distance) AND sourceNodeId <> targetNodeId
WITH gds.util.asNode(sourceNodeId) AS source, gds.util.asNode(targetNodeId) AS target, distance
WHERE NONE(n IN [source, target] WHERE n:Network|TGW)
RETURN source.name AS source, target.name AS target, distance
ORDER BY distance DESC, source ASC, target ASC

Answer 1

您有 2 个问题：

1. CONNECT_TO

   的源是

   Subnet

   或

   TGW

   ，但您的投影查询仅查找

   Subnet

   源节点。

   所以，你应该改变：
   MATCH (src:Subnet)-[r:SUB_OF | CONNECT_TO]->(trg:Network|TGW) 至：
   MATCH (src:Subnet|TGW)-[r:SUB_OF | CONNECT_TO]->(trg:Network|TGW)
2. 您的最终查询是使用源节点和目标节点进行过滤，但您显然希望使用路径内部的节点（如果有）进行过滤。所以你没有正确过滤。但是，

   gds.allShortestPaths.stream

    不会返回路径中的任何内部节点。要解决此问题，您可以插入对 Cypher 函数 

   allShortestPaths 的调用（是的，它与 GDS 过程具有相同的名称，并且有点令人困惑）以获取完整路径，而不仅仅是其源节点和目标节点.

   CALL gds.allShortestPaths.stream('cypherGraph10') YIELD sourceNodeId, targetNodeId, distance
   WHERE gds.util.isFinite(distance) AND sourceNodeId <> targetNodeId
   WITH gds.util.asNode(sourceNodeId) AS source, gds.util.asNode(targetNodeId) AS target
   MATCH p = allShortestPaths((source)-[*]-(target))
   WHERE NONE(n IN NODES(p)[1..-1] WHERE n:Network|TGW)
   RETURN source.name AS source, target.name AS target, LENGTH(p) AS distance
   ORDER BY distance DESC, source ASC, target ASC