Cypher query to find the longest path using neo4j 3.1.0 version

4
votes

Can anybody send the Cypher query to find LONGEST PATH between two nodes using neo4j 3.1.0 version.

2
neo4jcypher
Do you mean the longest simple path (i.e., without any cycles)? If you want to include cycles, then all paths that have a cycle could be considered to have infinite length. – cybersam

2 Answers

6
votes

The graph algorithm to find the longest path is not implemented.

Here is a Cypher query that gets all paths and sorts them by size:

// get the nodes
MATCH (a:Node), (b:Node)
WHERE ID(a) = 14 AND ID(b) = 7
WITH a,b
// match all paths
MATCH p=(a)-[*]-(b)
// return the longest
RETURN p, length(p) ORDER BY length(p) DESC LIMIT 1

However, without any restrictions on the query, this might not work on large graphs. Finding the longest path in an undirected graph is expensive: https://en.wikipedia.org/wiki/Longest_path_problem

And without restrictions on the query (direction and relationship type) the query will look for all undirected paths.

You should restrict your path query or try two solve your problem without the longest path.

1
votes

If you are looking for the longest path between nodes where each node in the chain has the same relationship to the next then see Achieving longestPath Using Cypher which shows:

MATCH p=(parent:Entity)-[:HAS_CHILD*1..10]->(child:Person)
WHERE size((child)-[:HAS_CHILD]->()) = 0
RETURN child;

However I am using:

MATCH (parent:Entity)-[:HAS_CHILD*1..10]->(child:Person)
WHERE NOT (child)-[r:HAS_CHILD]->()
RETURN child;

If anyone can comment on performance or any other aspect please do!

I also discovered an undocumented feature which will return the child when it is also the parent (as in only one node):

MATCH (parent:Entity)-[:HAS_CHILD*0..]->(child:Person)
WHERE NOT (child)-[r:HAS_CHILD]->()
RETURN child;