Cypher query to find all paths with same relationship type

Question

I'm struggling to find a single clean, efficient Cypher query that will let me identify all distinct paths emanating from a start node such that every relationship in the path is of the same type when there are many relationship types.

Here's a simple version of the model:

CREATE (a), (b), (c), (d), (e), (f), (g),
       (a)-[:X]->(b)-[:X]->(c)-[:X]->(d)-[:X]->(e),
       (a)-[:Y]->(c)-[:Y]->(f)-[:Y]->(g)

In this model (a) has two outgoing relationship types, X and Y. I would like to retrieve all the paths that link nodes along relationship X as well as all the paths that link nodes along relationship Y.

I can do this programmatically outside of cypher by making a series of queries, the first to retrieve the list of outgoing relationships from the start node, and then a single query (submitted together as a batch) for each relationship. That looks like:

START n=node(1) 
MATCH n-[r]->() 
RETURN COLLECT(DISTINCT TYPE(r)) as rels;

followed by:

START n=node(1) 
MATCH n-[:`reltype_param`*]->() 
RETURN p as path;

The above satisfies my need, but requires at minimum 2 round trips to the server (again, assuming I batch together the second set of queries in one transaction).

A single-query approach that works, but is horribly inefficient is the following single Cypher query:

START n=node(1) 
MATCH p = n-[r*]->() WHERE 
   ALL (x in RELATIONSHIPS(p) WHERE TYPE(x) = TYPE(HEAD(RELATIONSHIPS(p)))) 
RETURN p as path;

That query uses the ALL predicate to filter the relationships along the paths enforcing that each relationship in the path matches the first relationship in the path. This, however, is really just a filter operation on what it essentially a combinatorial explosion of all possible paths --- much less efficient than traversing a relationship of a known, given type first.

I feel like this should be possible with a single Cypher query, but I have not been able to get it right.

Eve Freeman Eve Freeman · Accepted Answer · 2014-01-01T23:19:46

Here's a minor optimization, at least non-matching the paths will fail fast:

MATCH n-[r]->() 
WITH distinct type(r) AS t 
MATCH p = n-[r*]->() 
WHERE type(r[-1]) = t // last entry matches
RETURN p AS path

This is probably one of those things that should be in the Java API if you want it to be really performant, though.

Cypher query to find all paths with same relationship type

1 Answers