查找不两次访问同一节点的密码路径 [英] Finding cypher paths that don't visit the same node twice

问题描述

我正在寻找图中两个节点之间的路径，但我的图中有一个循环，所以我得到了不希望的路径.我希望这里有人能帮我想出一个明智的补救办法.

I'm looking for the paths between two nodes in a graph, but my graph has a loop in it and so I'm getting paths back that are undesirable. I'm hoping that someone here can help me think out a sensible remedy.

这是我的图表:

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

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

The letters are nodes, and the numbers are edges (relationships).

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 之间的路径，我只希望有一个，但有 三个！

I'm looking for paths between A and C, and I'd only expect there to be one, but there are three!

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 显然被访问了两次.

That makes sense from a graph perspective because the path isn't visiting the same edge twice, but from a node perspective it's a pain because C clearly is visited twice.

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

One thought was to try shortest paths, using allShortestPaths, however that only appears to filter the result by returning just the shortest length paths, which isn't the same as avoiding passing through the same node twice. For example the route A->G has two paths:

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

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

but when I use allShortestPaths I only get the three hop path [2,5,7].

是否有一种明智的方法来应用限制，以便我只能获得每个节点仅被访问一次的路径?

Is there a sensible way of applying a restriction so that I only get paths where each node is only visited once?

推荐答案

我认为你应该使用 shortestPath 或 allShortestPaths，像这样:

I think you should use shortestPath or allShortestPaths, like this:

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

确保为 :Label(i)

您可以尝试类似的操作(过滤掉节点出现两次的所有路径)

you can try something like that (filter out all paths where a node appears twice)

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

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

the index hint was an optimization for a real world dataset

这篇关于查找不两次访问同一节点的密码路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！