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

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)

创建一个 index/constraint

你可以尝试类似的方法（过滤掉所有出现两次节点的路径）

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);

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

Answer 2

感谢 Michael hunger。

在 NEO4J 4.0.7 中，不再支持过滤器和提取，必须使用 列表理解。密码语句是这样的（过滤掉一个节点出现两次的所有路径）：

MATCH p=({ i: "A" })-[:r*]-({ i: "C" }) 
WHERE NONE (n IN nodes(p) 
            WHERE size([x IN nodes(p) 
                              WHERE n = x]) > 2 )
return [n IN nodes(p) | n._id]

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

Finding cypher paths that don't visit the same node twice

neo4j

cypher