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

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? EDIT: 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.

Accepted Answer

How about

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

see also this graph-gist: http://gist.neo4j.org/?9042990

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

Solution

Problem