cancel
Showing results for 
Search instead for 
Did you mean: 

Depth first search doesn't give all the possible paths

Hello everyone,

I have a graph composed of 2126 nodes and 5175 relationships.
My purpose is to find all the paths, from a given node ("NODE1"), without any redundancy.
I've used the following query to achieve my goal :

MATCH (p : Town{name:"NODE1"})
CALL apoc.path.expandConfig(p, {uniqueness:'NODE_GLOBAL', bfs : FALSE}) YIELD path
WITH path, p, last(nodes(path)) as subgraph
WHERE p.name <> subgraph.name
RETURN nodes(path), length(path) AS len
ORDER BY len DESC

At first sight, it seems to work very well, but examining ahead the results shows the two following errors :

  • 1 There is redundancy in some paths (some nodes are sometimes present twice in a given path unless the option "uniqueness:NODE_GLOBAL" is present)

  • 2 The worst : all the possible paths are not present... It seems that the depth-first works well for the 2 or 3 first paths (NODE1 -> NODE2 -> STOP ; NODE1 -> NODE3 -> NODE4 -> STOP; NODE1 -> NODE5 -> NODE6 -> NODE7 -> ... ; ...) but once the algorithm starts to go really deeper (path of 245 nodes from NODE1), it looks like it is not able anymore to come back to NODE1 to start again its search from nearest nodes.

It is really strange as we don't have any error message or java heap space alert...

Could you please advice ?

Many thanks in advance,

Best regards,
Nathalie

0 REPLIES 0
Nodes 2022
Nodes
NODES 2022, Neo4j Online Education Summit

On November 16 and 17 for 24 hours across all timezones, you’ll learn about best practices for beginners and experts alike.