Neo4j Cypher: topological sort in addition to regular sort?

Question

Say I have a tree of nodes that looks like this:

Where the numbers correspond to some value I generally want to sort by. (It could be time, it could be some kind of score, whatever.)

If I return them sorted by just that number, I'd of course get this sort:

1, 2, 3, 4, 5, 6, 7, 8, 9

That's generally fine, but in addition to this sort, I want to apply the constraint that parents always sort before their children. So what I really want is this sort:

3, 2, 1, 4, 5, 6, 7, 8, 9

You can see this looks almost the same; we've just flipped the order of 1, 2, 3 to 3, 2, 1.

Is there a way to achieve this sort with a Neo4j Cypher query?

—

Here's a live console example with this tree to play with:

http://console.neo4j.org/r/l9mav2

Here's my query so far:

MATCH path=( ({i: 3}) <-[:parent*0..]- (node) )
RETURN node, node.i, LENGTH(path)

I'm just not sure how to use this info:

• If I ORDER BY node.i, I get the first sort.

• If I ORDER BY LENGTH(path), it's too aggressive. E.g. 9 before 5, 6, 7, 8.

• Combining the two, in either order, doesn't work either.

Is this possible? Thanks!

Answer 1

This feels a little hacky, but maybe it will work, depending on how predictable the size of your tree is:

MATCH path=(root:Node { i: 3 })<-[:parent*0..]-(node:Node)
WITH nodes(path)[-1] as n,[x IN nodes(path)| x.i] AS o
ORDER BY o[0], coalesce(o[1], -1), coalesce(o[2], -1), coalesce(o[3], -1) // and so forth
RETURN n

Where the -1 in the coalesce is definitely lower than any possible values in the .i property.

Here's another idea using the properties of string comparison to our advantage:

MATCH path=(root:Node { i: 3 })<-[:parent*0..]-(node:Node)
WITH nodes(path)[-1] AS n,[x IN nodes(path)| x.i] AS o, 
     reduce(maxLen=0, p IN root<-[:parent*]-()|CASE WHEN maxLen < length(p)
                                                   THEN length(p)
                                                   ELSE maxLen END ) AS maxLen
ORDER BY reduce(acc='', x IN range(0,maxLen)|acc+coalesce(str(o[x]), ''))
RETURN n,reduce(acc='', x IN range(0,maxLen)|acc+coalesce(str(o[x]), ''))

You can either get the max path length as shown, or just make maxLen a really high number.

Answer 2

You can just combine the two values to represent your sort order, just giving the parents a higher precendence:

MATCH path =((root:Node { i: 3 })<-[:parent*0..]-(node:Node))
RETURN node, node.i, LENGTH(path)
ORDER BY LENGTH(path)+ node.id *10

http://console.neo4j.org/r/ijeqlv

returns

+--------------------------------------+
| node         | node.i | LENGTH(path) |
+--------------------------------------+
| Node[3]{i:3} | 3      | 0            |
| Node[2]{i:2} | 2      | 1            |
| Node[1]{i:1} | 1      | 2            |
| Node[4]{i:4} | 4      | 1            |
| Node[5]{i:5} | 5      | 2            |
| Node[6]{i:6} | 6      | 2            |
| Node[7]{i:7} | 7      | 2            |
| Node[8]{i:8} | 8      | 3            |
| Node[9]{i:9} | 9      | 1            |
+--------------------------------------+
9 rows
32 ms

Answer 3

I don't have experience with Neo4j, but if I understand correctly, the following algorithm, in words, fits your description. Best of luck!

Start at the root node and copy the root into the sorted list as your next value. Choosing among the root's children, choose the "next root" as the smallest of the root's children. Replace the root by the "next root", and move all of the "next root's" children up a level. Repeat until the graph is empty.

Ex:

Sorted = {}
           3
        /  |  \
       2   4   9
       |  /|\
       1 5 6 7
             |
             8
Sorted = {3}
       2
     / | \
    1  4  9
      /|\
     5 6 7
         |
         8
Sorted = {3,2}
       1
       | \
       4  9
      /|\
     5 6 7
         |
         8
Sorted = {3,2,1}
         4  
      / / \  \
     5 6   7  9
           |
           8
Sorted = {3,2,1,4}
          5  
        / | \
       6  7  9
          |
          8
Sorted = {3,2,1,4,5}
         6  
        /  \
       7    9
       |
       8
Sorted = {3,2,1,4,5,6}
         7  
        /  \
       8    9
Sorted = {3,2,1,4,5,6,7}
          8  
          |
          9
Sorted = {3,2,1,4,5,6,7,8}
          9
Sorted = {3,2,1,4,5,6,7,8,9}