Neo4 Hierarchy Traversal

Question

I've got some hierarchical data stored in neo4j and need a query to find all children of a parent node for a particular user. The basic scenario is:

(Root Task {control: 1})
    (Child Task 2 {control: 2})
    (Child Task 3 {control: 3})
        (Child Task 4 {control: 4})

The child tasks have a :CHILD_OF relationship to the parent. So this is all fine, and I'm able to get the children of a parent. Using the following query I would get Child Task 4 returned.

MATCH (rootTask:Task {control: 3}), (user:User {control: 60})
,(childTask:Task)-[:CHILD_OF*]->(rootTask)
WHERE (user)-[:LINKED_TO]->(childTask)
RETURN childTask

The problem comes in with the need for a user to re-arrange the structure, but only for himself. So I introduced a new relationship, which contains a reference to the user. CHILD_OF_<usercontrol> is added and if it exists it should take preference over the CHILD_OF relationship.

So if user 60 decides the (Child Task 4) task should fall under the (Root Task) and not (Child Task 3), there are two links created:

MERGE (Level 4 task)-[:CHILD_OF]->(Child Task 3)
MERGE (Level 4 task)-[:CHILD_OF_60]->(Root Task)

His view is now basically:

(Root Task {control: 1})
    (Child Task 2 {control: 2})
    (Child Task 3 {control: 3})
    (Child Task 4 {control: 4})

So now when I ask for children of (Child Task 3), for user 60 I don't want (Child Task 4) returned.

Using the previous query and adding the user specific relationship and an additional constraint to not return a child task if it has a user specific link to an unbound task almost works, expect it will return children of (Child Task 4) because they only have a CHILD_OF relationship that gets linked to. The logic to exclude childTask's that have a user specific link is also flawed because it might actually point to the same parent.

MATCH (rootTask:Task {control: 3}), (user:User {control: 60})
,(childTask:Task)-[:CHILD_OF|CHILD_OF_60*]->(rootTask)
WHERE (user)-[:LINKED_TO]->(childTask) 
AND NOT (childTask)-[:CHILD_OF_60]-(:Task)
RETURN childTask

The essence of the logic I need is just if relationship CHILD_OF_60 exists for a task follow that relationship and ignore the default CHILD_OF relationship.

---

Test data

MERGE (ruan :User {control: 50, fullname: 'Ruan'})
MERGE (amber :User {control: 60, fullname: 'Amber'})
MERGE (task1 :Task {control: 1, subject: 'Root Task:'})
MERGE (task2 :Task {control: 2, subject: 'Child of Root:'})
MERGE (task3 :Task {control: 3, subject: 'User properties'})
MERGE (task4 :Task {control: 4, subject: 'User parent links'})
MERGE (task5 :Task {control: 5, subject: 'Hierarchy Traversal'})
MERGE (task6 :Task {control: 6, subject: 'Parent'})
MERGE (task7 :Task {control: 7, subject: 'Child'})
MERGE (task8 :Task {control: 8, subject: 'Query1'})
MERGE (task2)-[:CHILD_OF]->(task1)
MERGE (task3)-[:CHILD_OF]->(task2)
MERGE (task4)-[:CHILD_OF]->(task2)
MERGE (task5)-[:CHILD_OF]->(task2)
MERGE (task6)-[:CHILD_OF]->(task5)
MERGE (task7)-[:CHILD_OF]->(task5)
MERGE (task8)-[:CHILD_OF]->(task7)
MERGE (ruan)-[:LINKED_TO]->(task1)
MERGE (ruan)-[:LINKED_TO]->(task2)
MERGE (ruan)-[:LINKED_TO]->(task3)
MERGE (ruan)-[:LINKED_TO]->(task4)
MERGE (ruan)-[:LINKED_TO]->(task5)
MERGE (ruan)-[:LINKED_TO]->(task6)
MERGE (ruan)-[:LINKED_TO]->(task7)
MERGE (ruan)-[:LINKED_TO]->(task8)
MERGE (amber)-[:LINKED_TO]->(task1)
MERGE (amber)-[:LINKED_TO]->(task2)
MERGE (amber)-[:LINKED_TO]->(task3)
MERGE (amber)-[:LINKED_TO]->(task4)
MERGE (amber)-[:LINKED_TO]->(task5)
MERGE (amber)-[:LINKED_TO]->(task6)
MERGE (amber)-[:LINKED_TO]->(task7)
MERGE (amber)-[:LINKED_TO]->(task8)
MERGE (task2)-[:CHILD_OF]->(task1)
MERGE (task3)-[:CHILD_OF]->(task2)
MERGE (task4)-[:CHILD_OF]->(task2)
MERGE (task5)-[:CHILD_OF]->(task2)
MERGE (task6)-[:CHILD_OF]->(task5)
MERGE (task7)-[:CHILD_OF]->(task5)
MERGE (task8)-[:CHILD_OF]->(task7)
MERGE (task5)-[:CHILD_OF_60]->(task1)
MERGE (task3)-[:CHILD_OF_60]->(task1)

Answer 1

This was a fun one to work on. I've made up a GraphGist here to demonstrate my suggestion:

http://graphgist.neo4j.com/#!/gists/54d8b5ef8cfb85197aa4

But I'll put the solution here as well:

MATCH
  (rootTask:Task { control: 1 }),
  path=(childTask:Task)-[:CHILD_OF|CHILD_OF_60*1..]->rootTask,
  (user:User { control: 60 })-[:LINKED_TO]->childTask
WITH childTask, path AS the_path, path
UNWIND nodes(path) AS node
OPTIONAL MATCH node-[:CHILD_OF_60]->(otherParent:Task)
WITH childTask, the_path, collect(otherParent IS NULL OR otherParent IN nodes(the_path))[0..-1] AS otherParentResults
WHERE ALL(result IN otherParentResults WHERE result)
RETURN DISTINCT childTask

Basically I'm getting the path, checking to see if the leaf node has another parent via the CHILD_OF_60 relationship, and then returning the child if it doesn't have another parent or if the otherParent isn't in the ancestry path.

I'd feel more comfortable with this solution if it were backed by automated tests, but give it a try! ;)

Also, as a rule I try not to make variable relationship names. You may want to consider having an optional user_id property on your CHILD_OF relationships. Alternatively you might have something like a CHILD_OF_FOR_USER relationship type which has a user_id property.

EDIT: I've edited the query above and the GraphGist to take care of child nodes with moved ancestors in the path to the root node