Neo4j: Cypher : All Simple Paths

[lassewesth]

@ssingaraju: 'Hi :

With the below set up, How do we extract all simple paths between David-Emil with no duplicated (revisited) hops. Is there a allSimplePaths function in Cypher much similar to allShortestPaths.

Thank you in advance.

Graph Setup:
(1) {"name":"David"}
(2) {"name":"Emil"}
(3) {"name":"Anders"}
(4) {"name":"Bossman"}
(5) {"name":"Cesar"}
(1)-[:KNOWS]->(3)
(2)-[:KNOWS]->(1)
(3)-[:KNOWS]->(4)
(3)-[:BLOCKS]->(5)
(4)-[:KNOWS]->(2)
(4)-[:BLOCKS]->(1)
(5)-[:KNOWS]->(2)

(1)-[:KNOWS]->(2)

start d=node(1), e=node(2)
match p = allShortestPaths( d-[*..15]->e )
return nodes(p)
+------------------------------------------------+
| nodes(p) |
+------------------------------------------------+
| [Node[1]{name->"David"},Node[2]{name->"Emil"}] |
+------------------------------------------------+
1 row
0 ms

You can modify and query this graph by entering statements in the input field at the bottom.
For some syntax help hit the button. If you want to share your graph, just do it with

start d=node(1), e=node(2)
match p = d-[*..15]->e
return nodes(p)
+----------------------------------------------------------------------------------------------------------------------------------------------+
| nodes(p) |
+----------------------------------------------------------------------------------------------------------------------------------------------+
| [Node[1]{name->"David"},Node[3]{name->"Anders"},Node[4]{name->"Bossman"},Node[2]{name->"Emil"}] |
| [Node[1]{name->"David"},Node[3]{name->"Anders"},Node[4]{name->"Bossman"},Node[2]{name->"Emil"},Node[1]{name->"David"},Node[2]{name->"Emil"}] |
| [Node[1]{name->"David"},Node[3]{name->"Anders"},Node[4]{name->"Bossman"},Node[1]{name->"David"},Node[2]{name->"Emil"}] |
| [Node[1]{name->"David"},Node[3]{name->"Anders"},Node[5]{name->"Cesar"},Node[2]{name->"Emil"}] |
| [Node[1]{name->"David"},Node[3]{name->"Anders"},Node[5]{name->"Cesar"},Node[2]{name->"Emil"},Node[1]{name->"David"},Node[2]{name->"Emil"}] |
| [Node[1]{name->"David"},Node[2]{name->"Emil"}] |
| [Node[1]{name->"David"},Node[2]{name->"Emil"},Node[1]{name->"David"},Node[3]{name->"Anders"},Node[4]{name->"Bossman"},Node[2]{name->"Emil"}] |
| [Node[1]{name->"David"},Node[2]{name->"Emil"},Node[1]{name->"David"},Node[3]{name->"Anders"},Node[5]{name->"Cesar"},Node[2]{name->"Emil"}] |
+----------------------------------------------------------------------------------------------------------------------------------------------+
8 rows
0 ms'

[lassewesth]

---

valueCount: 1
strings:

• "This issue was migrated from "
• ""
  values:
• https://github.com/neo4j/community/issues/606

[lassewesth]

@systay: Thanks so much for writing this down.

TL;DR;

It should be possible to write:
MATCH p = simplePaths(d-[*..15]->e)

The returned paths cannot contain loops (i.e. a node cannot occur more than once in any returned path).

[raananraz]

Hi,
What exactly was the solution here? looking for the exact same thing.
Using version 2.

[ecbftw]

This still appears to be a missing capability from Neo4j. After quite a bit of searching, I've found numerous people who want this kind of feature, such as:
https://stackoverflow.com/questions/40060000/cypher-all-paths-without-loops
https://stackoverflow.com/questions/47198226/how-to-avoid-cycle-or-loop-in-path-neo4j-cypher
While it is possible to use the solutions above on small graphs, they are very inefficient, since they use Cypher to generate all possible paths with loops and then filter out the loop variants. You can't run this on even a small graph that has loops without putting a cap on the path length.

I realize that finding all non-loop paths is not going to be terribly efficient either, but some problems can only be solved this way. I have a fairly small graph where I am testing this kind of search without any cap on path length. I can do it very quickly in browser-based JavaScript code using BFS and a hash table for each partial path. But with the same graph in Cypher, there's basically no way to do this efficiently (that I have found).

I haven't found a function in apoc or in algo for this task. Since this is the one task I wanted to use neo4j for, I'll probably have to ditch it if there isn't an efficient way to do it.

[boggle]

This is being worked on for Cypher 10 and GQL.