Traverse relationship type until the node with another relationship type has been found

Hello, I have a following model:


Now starting from Client X I would like to traverse the sponsorship tree UNTIL:

  1. either the max number of hops (maxHops) has been reached OR
  2. the whole tree has been traversed (up to Root), meaning there is no outgoing HAS_SPONSOR relationship from Root node OR
  3. the Client Y node is traversed where Client Y has an outgoing HAS_LEADER relationship.

The result should be a SINGLE longest path containing at most maxHops nodes.
I tried to use apoc.path.expand but no luck, since I do not know how to configure condition #3.

Thanks for any help.

I think the following will work. I tested it with all three scenarios. Pure cypher, but it is not very elegant. This seems to be a better candidate for a traversal algorithm. Maybe someone will help you with that. My solution may be more of an academic exercise than a practical solution. Maybe it will work and perform satisfactorily for your environment.

Basically, I queried for all three scenarios and merged them with 'union' clauses. Since they are mutually exclusive, you should get back just one path. The value of '10' is your maxHops. The values of 9, are maxHop - 1. The literal values of 'item' returned was just for me to see which union clause returned the result. You can remove that of course.

match (n:Client) where id(n) = 0
call {
with n
match p = (n)-[:HAS_SPONSOR1..9]->(m:Client)
where not any (i in nodes(p) where exists ((i)-[:HAS_LEADER]->(:Client)))
and not exists ((m)-[:HAS_SPONSOR]->(:Client))
return p as path, 1 as item
with n
match p = (n)-[:HAS_SPONSOR
where not any (i in nodes(p) where exists ((i)-[:HAS_LEADER]->(:Client)))
return p as path, 2 as item
with n
match p = (n)-[:HAS_SPONSOR*1..9]->(m:Client)
where exists ((m)-[:HAS_LEADER]->(:Client))
return p as path, 3 as item
return path, item

BTW- it seems like the '*' symbols used in the variable length path descriptions don't get rendered correctly. The seem to start and stop the text from being rendered in italics.

Thank you for the quick reply and the effort you took.
Much appreciated.
There are a few problems with your proposed solution:

  • maxHops are dynamic, so it is not possible to do variable length relationship traversal, like you did
  • the correct number of items (Clients) in the path needs to be returned. Your path is correct but it is longer than it should
  • and what I forgot to emphasize: In case Root is found, stop with traversal but not include Root, but if a node with HAS_LEADER relationship is found, stop with the traversal, but include that node.

I came up with this query (no subqueries and unions)

WITH 2 AS maxHops
MATCH p=(c:Client{login:"c1"})-[hds:HAS_SPONSOR*0..]->(s:Client) 
WHERE s.type="Root" OR 
LENGTH(p)>=maxHops  OR 
EXISTS ((s)-[:HAS_LEADER]->())
RETURN [n IN NODES(p) WHERE n.type <> "Root"| n] AS list LIMIT 1

The last line is to take out Root if it exists. The other 2 conditions are fine.
Hope it would be of help to somebody else.