You by now have probably discovered the algo.dfs.stream
function in the Neo4j Graph Algorithms plugin, which sort-of gets you half-way there:
MATCH (startNode: Node { name: 'N1' } )
CALL algo.dfs.stream('Node', 'PART_OF', 'BOTH', id(startNode))
YIELD nodeIds
UNWIND nodeIds as nodeId
WITH algo.asNode(nodeId) as n
RETURN n
The trouble is that algo.dfs.stream
doesn't let you control the order nodes are traversed amongst siblings - your best bet is probably to do this in application code, where writing a DFS is pretty trivial.
However I spent the past couple hours hacking about on a pure Cypher approach that does perform a depth-first search with stable ordering by your order
property for a laugh. I heartily implore you to not using this code, for several reasons:
- I'm pretty sure it's got at least an O(n^2) complexity in the number of nodes in the tree
- A lot of costly work is done up-front calculating paths as a single batch, whereas your own traversal code could be stream-based - this won't work on large graphs
- 'Just because you can, doesn't mean you should'
But it seems a waste to not post it somewhere so here we are.
Assuming some test data to match your sample:
MERGE (n1: Node { order: 1, name: 'N1' })
MERGE (n2: Node { order: 1, name: 'N2' })
MERGE (n3: Node { order: 2, name: 'N3' })
MERGE (n4: Node { order: 1, name: 'N4' })
MERGE (n5: Node { order: 1, name: 'N5' })
MERGE (n6: Node { order: 2, name: 'N6' })
MERGE (n7: Node { order: 1, name: 'N7' })
MERGE (n2)-[:PART_OF]->(n1)
MERGE (n4)-[:PART_OF]->(n2)
MERGE (n5)-[:PART_OF]->(n4)
MERGE (n6)-[:PART_OF]->(n4)
MERGE (n3)-[:PART_OF]->(n1)
MERGE (n7)-[:PART_OF]->(n3)
The following will yield the DFS traversal, where nodes amongst siblings are selected by sorting on the order
property of the node.
MATCH (root: Node { name: 'N1' }), pathFromRoot=shortestPath((root)<-[:PART_OF*]-(leaf: Node)) WHERE NOT ()-[:PART_OF]->(leaf)
WITH nodes(pathFromRoot) AS pathFromRootNodes
WITH pathFromRootNodes, reduce(pathString = "", pathElement IN pathFromRootNodes | pathString + '/' + right("00000" + toString(pathElement.order), 6)) AS orderPathString ORDER BY orderPathString
WITH reduce(concatPaths = [], p IN collect(pathFromRootNodes) | concatPaths + p) AS allPaths
WITH reduce(distinctNodes = [], n IN allPaths | CASE WHEN n IN distinctNodes THEN distinctNodes ELSE distinctNodes + n end) AS traversalOrder
RETURN [x in traversalOrder | x.name]
I won't explain line by line, but the gist is:
- We build the set of paths from the root to each leaf node
- For each path we construct a synthetic key that combines the
order
property at each node in such a way that that sorting the paths by this key yields the order in which we'd reach each leaf node
- This is probably the most important bit - we pad the 'order' property so that we can just use lexical ASCII sorting on the paths to yield a traversal order
- We flatten the list of sorted paths and de-duplicate the nodes within to get the traversal order
order
properties?N2
andN3
have differentorder
values?