How to avoid cycle or loop in path Neo4j Cypher

Question

I have a problem when i use the path variables.

For example my hierarchy looks like

A-[Knows]-> B   
B-[Knows]-> C  
C-[Knows]-> D  
D-[Knows]-> E  
C-[Knows]-> F  
F-[Knows]-> G  
G-[Knows]-> B 

My query is MATCH p = (x)<-[Knows*]->(y) Return p

The relation direction have to be bidirectional. Toy problem is like A,B but in real application, i don't know direction of relations.

So there is a cycle and loop. The path start to find from A to C. But after finding C, next steps, cycle is happened.

How to avoid the loop or how to ignore it, how to remove from actual path or how to stop when the path end in B. I don't need to find second B to C.

Expected result :

A->B->C->D->E
A->B->C->F->G->B  // that is enough. The query must be stopped.

Actual result :

A->B->C->D->E
A->B->C->F->G->B->C->F->G->B..... loop trouble.

Answer 1

How can we verify that the path includes a cycle?

A simple way in clear cypher it is to count the number of unique nodes of the path and compare it with the path length increased by one:

MATCH path = (x)-[:KNOWS*]-(y)
  UNWIND NODES(path) AS n
    WITH path, 
         SIZE(COLLECT(DISTINCT n)) AS testLength 
    WHERE testLength = LENGTH(path) + 1
RETURN path

You can simplify the query using the collection functions from the APOC library.

For example:

MATCH path = (x)-[:KNOWS*]-(y)
      WHERE SIZE(apoc.coll.toSet(NODES(path))) > LENGTH(path) + 1
RETURN path

Or we can simplify:

MATCH path = (x)-[:KNOWS*]-(y) 
      WHERE apoc.coll.duplicates(NODES(path)) = []
RETURN path

Answer 2

Firstly, to avoid loops, cypher has the following mecanism : in a pattern, you can only traverse once a relationship.

The problem of your query is that you are searching all the paths between all your nodes (that's why it takes some times).

If you only want to search the shortespath between two node, you can use the cypher's shortespath function : MATCH p = shortestpath((x)-[Knows*]-(y)) RETURN p.

Moreover, if you now the ending node, you should tell it to cypher :

MATCH p = shortestpath((x)-[Knows*]-(y)) 
WHERE x.name = 'A' AND y.name = 'B'
RETURN p

Cheers