CODEWITHSUNDEEP
neo4jcyphershortest-path
David Kleiman
David Kleiman

Reputation: 41

neo4j shortest path in between node

I have to find the shortest path between two nodes that include a specific type of node in the path.

have the following cypher:

Match p = shortestpath((E1:Entity{seq:"123"}) –[*]-(E2:Entity{seq:"456"})))
Where any(x in nodes(path) where x:T)
Return path

T: label, can be millions of nodes dbgraph size: 4gb

The problem is that it only works when the hops are limited up to 5, and that is not enough.

Any idea on how to rewrite this for optimization? When 6 or more hops it crashes.

Upvotes: 4

Views: 462

Answers (1)

InverseFalcon
InverseFalcon

Reputation: 30407

The main problem with this kind of query is that there's no way to truncate paths during traversal...you'll only know that the path isn't valid when it finally ends at E2, since that's the only point at which you can determine that none of the nodes in an path is a :T node.

The only way I know that might optimize a bit is to ensure that all expansions stop when E2 is reached, since the query as it is now will find all paths, even those that expand past E2, as there could be a path that goes through E2, hits a :T node, then eventually returns.

Unfortunately that optimization can't be done with Cypher. The latest versions of APOC Procedures (APOC 3.3.0.2 for Neo4j 3.3.x or APOC 3.2.3.6 for Neo4j 3.2.x) have enhanced the path expander procedures to work with end nodes, and we can configure the expansion to terminate when an end node is reached, so we can stop needless expansion (this assumes that paths that pass through E2 and then return are not valid).

MATCH (E1:Entity{seq:"123"}), (E2:Entity{seq:"456"})
CALL apoc.path.expandConfig(E1, {terminatorNodes:[E2]}) YIELD path
WITH path
WHERE any(x in nodes(path) where x:T)
RETURN path
ORDER BY length(path) ASC
LIMIT 1

While this may help somewhat (at least where the E2 node blocks off expansion to a larger portion of the graph), an unbounded variable-length traversal without any restrictions on the type and with the any() predicate is not going to perform well in most cases for the reasons cited above, especially in the cases where no such path exists.

Upvotes: 1

Related Questions