Depth-first traversal, sorting, and listing

Neo4j Graph Platform Cypher
1

Hey there.

I have this node tree:

N1
  N2
    N4
    N5
  N3
    N6

Where nodes are bound together with N2-[:part_of]->N1

I would like to traverse the tree depth-first, so a flat list of the tree would look like this:

N1
N2
N4
N5
N3
N6

Additional information:

  • Stock Neo4J version 3.5.12
  • I'm using neo4jrb, but I'm happy to drop down to native Cypher to get this done

All input and suggestions appreciated. Thanks.

2

You can use algo.dfs.stream:

match (n1:Test {name:"n1"})
CALL algo.dfs.stream("Test", "PART_OF", "INCOMING", id(n1),{}) yield nodeIds
unwind nodeIds as nodeId
return algo.asNode(nodeId).name as station

In DFS, the result would be different depending on which child node is traversed first. So in your example, because N2 and N3 both are children of N1, you will get different results if you traverse N2 first or N3 first.

3 Likes
3

Hi Shan.

Thanks a lot for your response!

Can I bother you for a little more information, perhaps?

I would love it, if I could control that sorting a little more. What if I add a position property to the nodes, which sorts siblings part_of the same parent node?

Something like this:

N1 { position: 1 }
  N2 { position: 1 }
    N4 { position: 1 }
    N5 { position: 2 }
  N3 { position: 2 }
    N6 { position: 1 }
4

No problem @emk.
I don't think you can control the order of children in algo.dfs. You might be able to do it in java. Not sure though,

5

Thanks. I guess I will have to look at resorting the list after it has been generated. Thanks a bunch for your help!

1 Like
6

Just to note, Cypher variable-length relationship patterns should use depth-first traversals (excepting usage of shortestPath() in the match).

So if we create your test graph like so:

CREATE (N1:Node:Root {name:'N1'})-[:REL]->(N2:Node {name:'N2'})-[:REL]->(N4:Node {name:'N4'})
CREATE (N2)-[:REL]->(N5:Node {name:'N5'})
CREATE (N1)-[:REL]->(N3:Node {name:'N3'})-[:REL]->(N6:Node {name:'N6'})

Then a simple Cypher query with a variable length relationship should return the tree in depth first order:

MATCH (N1:Root)-[:REL*0..]->(node)
RETURN node.name

results in:

╒═══════════╕
│"node.name"│
╞═══════════╡
│"N1"       │
├───────────┤
│"N2"       │
├───────────┤
│"N4"       │
├───────────┤
│"N5"       │
├───────────┤
│"N3"       │
├───────────┤
│"N6"       │
└───────────┘

Though just as shan says, dfs traversal here doesn't allow for determining the order of children explored when multiple children are present, so N5 may come before N4, and N3 could be explored before N2, completely reordering the results.

2 Likes
7

Hi Andrew.

Thanks for pitching in. This is really interesting. This is not what I'm seeing when I'm running the query on my db. Do you know of a way that I can debug this?

8

As mentioned the ordering may be different depending on which children are visited first. Can you confirm you're working with the same graph and using the same query, and show us what results you get back?

9

Hey Andrew.

It seems that this works when doing the query directly on the neo4j web interface. But doing it through the Ruby library seems to change the outcome. I will have to investigate that some more.

Regarding sorting, is there a way to make the sorting deterministic?

10

Yes, but you do need to ORDER BY on something that can enforce the ordering you want. If you have a path variable for the pattern, you can ORDER BY length(path) to ensure that nodes encountered first are returned before those that come last, but that won't work so well when it's a tree or otherwise has separate branches.

You could try using APOC path expanders to perform your traversal, these use dfs by default. Unsure if your ruby driver would change the ordering.

1 Like