查找两次不访问同一节点的密码路径

Question

我正在寻找图形中两个节点之间的路径,但我的图形中有一个循环,所以我得到了不合需要的路径.我希望这里有人可以帮助我思考一个合理的补救措施.

这是我的图表:

A
|
2
|
C-3-D
|   |
|   4
5   |
|   E
|   |
|   6
|   |
F-7-G

字母是节点,数字是边(关系).

CREATE (a {i: "A"})
CREATE (c {i: "C"})
CREATE (d {i: "D"})
CREATE (e {i: "E"})
CREATE (f {i: "F"})
CREATE (g {i: "G"})
CREATE a-[:r {i:2}]->c-[:r {i:3}]->d-[:r {i:4}]->e-[:r {i:6}]->g
CREATE c-[:r {i:5}]->f-[:r {i:7}]->g;

我正在寻找A和C之间的路径,我只希望有一条路,但有三条路!

neo4j-sh (?)$ MATCH p=({i: "a"})-[:r*]-({i: "c"}) return EXTRACT(n IN NODES(p) | n.i);
+-------------------------------+
| EXTRACT(n IN NODES(p) | n.i)  |
+-------------------------------+
| ["A","C"]                     |
| ["A","C","D","E","G","F","C"] |
| ["A","C","F","G","E","D","C"] |
+-------------------------------+

neo4j-sh (?)$ MATCH p=({i: "a"})-[:r*]-({i: "c"}) return EXTRACT(n IN RELATIONSHIPS(p) | n.i);
+--------------------------------------+
| EXTRACT(n IN RELATIONSHIPS(p) | n.i) |
+--------------------------------------+
| [2]                                  |
| [2,3,4,6,7,5]                        |
| [2,5,7,6,4,3]                        |
+--------------------------------------+

从图表的角度来看,这是有道理的,因为路径没有两次访问同一个边缘,但从节点的角度来看,这是一个痛苦,因为C显然被访问了两次.

一种想法是使用allShortestPaths尝试最短路径,但是只会通过返回最短长度路径来过滤结果,这与避免两次通过同一节点不同.例如,路线A-> G有两条路径:

"A" -> "G" : [[2, 5, 7], [2, 3, 4, 6]]

但是当我使用allShortestPaths时,我只得到三跳路径[2,5,7].

是否有一种合理的方式来应用限制,以便我只获得每个节点只访问过一次的路径？

Answer 1

我认为你应该使用shortestPath或allShortestPaths,如下所示:

MATCH p=shortestPath((:Label1 {i: "a"})-[:r*]-(:Label2 {i: "c"})) 
RETURN EXTRACT(n IN NODES(p) | n.i);

确保为.创建索引/约束 :Label(i)

你可以试试这样的东西(过滤出节点出现两次的所有路径)

MATCH p=({ i: "A" })-[:r*]-({ i: "C" })
WHERE NONE (n IN nodes(p) 
            WHERE size(filter(x IN nodes(p) 
                              WHERE n = x))> 1)
RETURN EXTRACT(n IN RELATIONSHIPS(p)| n.i);

索引提示是对现实世界数据集的优化