Cypher: Depth First Search on Paths by Relationship Type

Question

I have a tree setup where each relationship can have a 'left' or 'right' relationship type to the next node. The nodes are all the same type except for the terminal node.

How would I sort the paths so I get them in depth-first search ordering always taking the left relationships first? I know I can pull the paths and probably do this in my own code. But is there a way to do it using Cypher?

Something like: match path=(n)-[r*]->(n:Terminal) order by lefts first return path

Chip Allen Chip Allen · Accepted Answer · 2016-06-29T09:09:11

I appear to have found a way using a combination of reduce and extract. I'm not sure if this is the most efficient way, but it works.

First, build 2 pieces of info for each relationship in the path and combine them into a string.

Index of the relationship in the path
Then using a case statement I choose '1' for left, '2' for right

Second, combine each relationship string with reduce into one long string for all relationships in the path to get something like 011121 for the first path. Sorting this string orders by depth first since it effectively orders by level and then left/right.

match 
    p=(n)-[r*]->(terminal_node) 
    where n.id = 'root node id'
with
    p,
    terminal_node,
    extract(
        r IN relationships(p) | 
        REDUCE(
            c=-1, 
            indx in range(0, size(relationships(p))-1) | 
            case when relationships(p)[indx] = r then indx else c end 
        ) + case when type(r) = 'LEFT' then '1' else '2' end
    ) as rel_index_and_order
return 
    p, 
    terminal_node,
    REDUCE(s='', r in rel_index_and_order | s+r ) as path_sort
order by path_sort

Cypher: Depth First Search on Paths by Relationship Type

1 Answers