jexp/depth and breadth first traversals.adoc

## depth and breadth first traversals.adoc

      
    Raw
  

              depth and breadth first traversals.adoc
            
          
    Combining depth- and breadth-first traversals in a single cypher query


Answering a Stackoverflow question


My graph is a tree structure with root and end nodes, and a line of nodes between them with -[:NEXT]-> relationships from one to the next. Some nodes along that path also have -[:BRANCH]-> relationships to other root nodes, and through them to other lines of nodes.


What Cypher query will return an ordered list of the nodes on the path from beginning to end, with any BRANCH relationships being included with the records for the nodes that have them?


It’s not a technical diagram, but the basic structure looks like this, with each node depicted as a black circle. In this case, I would would want every node depicted here.


/*
    //setup
    [source,cypher]
    ----
    foreach (r in range (0,10) | MERGE (n:Path { id:r }) MERGE (n)-[:NEXT]→(m:Path { id:n.id+1 }))
    foreach (r in [2,4] | MERGE (n:Path {id:r})-[:BRANCH]→(m) )
    ----
*/


MERGE (n:Path { id:0 })
MERGE (n)-[:NEXT]->(:Path { id:1 })-[:NEXT]->(_2:Path { id:2 })-[:NEXT]->(:Path { id:3 })
                      -[:NEXT]->(_4:Path { id:4 })-[:NEXT]->(:Path { id:5 })-[:NEXT]->(:Path { id:6 })
MERGE (_2)-[:BRANCH]->(:Branched)
MERGE (_4)-[:BRANCH]->(:Branched)


You can match the path along the NEXT relationship and optionall match branching BRANCH relationships.
Order the results by path length and you’re done.


MATCH p=(root { id:0 })-[:NEXT*0..]->(leaf)  OPTIONAL
MATCH (leaf)-[:BRANCH]->(branched)
RETURN leaf, branched, length(p) AS l
ORDER BY l ASC