Cypher: All paths without loops

Question

I have trouble to get all possible paths between to nodes without loops. I use neo4j 3.0.4. I prepared an example but first of all a short explanation. I have nodes from A to Z. These nodes can be connected in each way. I want to get all possible paths without loops, meaning a specific node is not visited more than once.

Here the example:

CREATE (newNode {name:'A'})
RETURN newNode;

CREATE (newNode {name:'B'})
RETURN newNode;

CREATE (newNode {name:'C'})
RETURN newNode;

CREATE (newNode {name:'D'})
RETURN newNode;

CREATE (newNode {name:'E'})
RETURN newNode;

CREATE (newNode {name:'Z'})
RETURN newNode;


MATCH (n1), (n2)
WHERE n1.name = 'A' AND n2.name = 'B'
CREATE
    (n1)-[r:CONNECTED_TO]->(n2)
RETURN n1, n2, r;

MATCH (n1), (n2)
WHERE n1.name = 'A' AND n2.name = 'C'
CREATE
    (n1)-[r:CONNECTED_TO]->(n2)
RETURN n1, n2, r;

MATCH (n1), (n2)
WHERE n1.name = 'B' AND n2.name = 'C'
CREATE
    (n1)-[r:CONNECTED_TO]->(n2)
RETURN n1, n2, r;

MATCH (n1), (n2)
WHERE n1.name = 'C' AND n2.name = 'D'
CREATE
    (n1)-[r:CONNECTED_TO]->(n2)
RETURN n1, n2, r;

MATCH (n1), (n2)
WHERE n1.name = 'D' AND n2.name = 'E'
CREATE
    (n1)-[r:CONNECTED_TO]->(n2)
RETURN n1, n2, r;

MATCH (n1), (n2)
WHERE n1.name = 'E' AND n2.name = 'Z'
CREATE
    (n1)-[r:CONNECTED_TO]->(n2)
RETURN n1, n2, r;

MATCH (n1), (n2)
WHERE n1.name = 'D' AND n2.name = 'Z'
CREATE
    (n1)-[r:CONNECTED_TO]->(n2)
RETURN n1, n2, r;

MATCH (n1), (n2)
WHERE n1.name = 'D' AND n2.name = 'A'
CREATE
    (n1)-[r:CONNECTED_TO]->(n2)
RETURN n1, n2, r;

MATCH (n1), (n2)
WHERE n1.name = 'B' AND n2.name = 'A'
CREATE
    (n1)-[r:CONNECTED_TO]->(n2)
RETURN n1, n2, r;


MATCH p=(from{name:'A'}), (to{name:'Z'}), 
path = (from)-[r*]->(to)
RETURN path

If I run the last query, I will get also paths like A->B->A->C->D->Z. I want to avoid this loop A->B->A. The allShortestPaths does not work for me because it will just provide the paths with the fewest hops. But I want to get all paths without loops, the number of hops is not relevant. It will be necessary to limit the result or the path length because the query is very expensive.

path = (from)-[r*20]->(to)

But that is not the solution to avoid the loops because they can occur also in short paths.

EDIT1: Ok, now I come up with a possible solution for this:

MATCH (from{name:'A'}), (to{name:'Z'}), 
path = (from)-[:CONNECTED_TO*]->(to)
WHERE NONE (n IN NODES(path) WHERE SIZE(FILTER(x IN NODES(path) WHERE n = x))> 1)
RETURN path, LENGTH(path) as length
ORDER BY length;

This query seems to work, but I assume that it is very expensive. Can someone offer a better solution?

Tore Eschliman Tore Eschliman · Accepted Answer · 2016-10-15T17:41:36

Your filter will fail out slightly faster if you change it to this:

WHERE ALL(x IN NODES(path) WHERE SINGLE(y IN NODES(path) WHERE y = x))

But I don't believe you'll find a fundamentally more efficient way. Usually your options are pretty limited when your question contains the words "all paths" and your sample has an unbounded relationship :)

Cypher: All paths without loops

1 Answers