1

I'm learning Neo4J.

I understand how to make depth-first searches for nodes, but in my case, I want to serialize all nodes, but traverse one branch completely, then move to the next branch, and so on.

Given these nodes:

N1 { order: 1 }
  N2 { order: 1 }
    N4 { order: 1 }
      N5 { order: 1 }
      N6 { order: 2 }
  N3 { order: 2 }
    N7 { order: 1 }

The relationship between the nodes is a directed one named part_of. E.i. N2-[part_of]->N1.

I would like the list to be serialized in this order: N1 N2 N4 N5 N6 N3 N7.

What's the most efficient way of doing this?

Thanks in advance.

// E

6
  • 2
    Show more of your data model. How is the hierarchy represented - e.g., are there relationships between the nodes?
    – cybersam
    Nov 25, 2019 at 19:33
  • 1
    Also, what is the significance of the order properties?
    – cybersam
    Nov 26, 2019 at 1:43
  • Order is the ordering of the nodes on the same level.
    – ekampp
    Nov 26, 2019 at 6:15
  • I have added an example of a relationship. This is indicative of all of the relationships. Hope this clarifies.
    – ekampp
    Nov 26, 2019 at 6:19
  • 1
    Shouldn't N2 and N3 have different order values?
    – cybersam
    Nov 26, 2019 at 8:06

1 Answer 1

0

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
3
  • Hey @Pablissimo, thanks for the feedback on why this is a bad approach. I appreciate that! I will give the solution a good look.
    – ekampp
    Feb 10, 2020 at 9:45
  • There are two things that seem rough: (1) "stable ordering by your order property for a laugh" and (2) "Just because you can, doesn't mean you should".
    – ekampp
    Feb 10, 2020 at 9:46
  • The stable ordering should be possible - you sort by your order property, then have to fall back to something reliable (like node ID). In my example that's not happening - if two nodes shared an order within a set of siblings then they can be traversed in any order (and indeed it might break the DFS traversal entirely). The bigger problem is really that this has to pull all paths from root to children into memory up front, then do the DFS. The Graph Algorithms version is a streaming algorithm - it'll work on bigger graphs.
    – Pablissimo
    Feb 10, 2020 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.