How can I get all paths to node?

[jasperblondin]

Hello!

There is a graph of the following form.

Nodes:

• Lesson
• Skill

Relations:

• Lesson requires some skills: (:Lesson)-[:REQUIRES]->(:Skill)
• Lesson provide only one skill: (:Skill)-[:PROVIDED_BY]->(:Lesson)

How can I get all longest paths (chains of lessons) to selected lesson?

Example model:

Summary

`merge (l1:Lesson {id: "L1"})
merge (l2:Lesson {id: "L2"})
merge (l3:Lesson {id: "L3"})
merge (l4:Lesson {id: "L4"})
merge (l5:Lesson {id: "L5"})
merge (l6:Lesson {id: "L6"})
merge (l7:Lesson {id: "L7"})
merge (l8:Lesson {id: "L8"})
merge (l9:Lesson {id: "L9"})

merge (s1:Skill {id: "S1"})
merge (s2:Skill {id: "S2"})
merge (s3:Skill {id: "S3"})
merge (s4:Skill {id: "S4"})
merge (s5:Skill {id: "S5"})
merge (s6:Skill {id: "S6"})
merge (s7:Skill {id: "S7"})
merge (s8:Skill {id: "S8"})
merge (s9:Skill {id: "S9"})

merge (l1)-[:REQUIRES]->(s1)
merge (l1)-[:REQUIRES]->(s2)
merge (l1)-[:REQUIRES]->(s3)

merge (s1)-[:PROVIDED_BY]->(l2)
merge (s1)-[:PROVIDED_BY]->(l3)
merge (s2)-[:PROVIDED_BY]->(l4)
merge (s3)-[:PROVIDED_BY]->(l5)
merge (s3)-[:PROVIDED_BY]->(l6)

merge (l3)-[:REQUIRES]->(s4)
merge (l4)-[:REQUIRES]->(s5)
merge (l4)-[:REQUIRES]->(s6)
merge (l5)-[:REQUIRES]->(s6)
merge (l6)-[:REQUIRES]->(s7)

merge (s4)-[:PROVIDED_BY]->(l7)
merge (s5)-[:PROVIDED_BY]->(l7)
merge (s6)-[:PROVIDED_BY]->(l8)
merge (s7)-[:PROVIDED_BY]->(l9)

merge (l9)-[:REQUIRES]->(s3)`

According to this example model for lesson "L1" I want to get paths:

• L2, L1
• L7, L3, L1
• L7, L4, L1
• L8, L4, L1
• L8, L5, L1
• L8, L5, L9, L6, L1

[ameyasoft]

If I understand correctly, here is my solution:

Step: 1 Created data

merge (a:Lesson {lesson: "L1"})
merge (a1:Lesson {lesson: "L2"})
merge (a2:Lesson {lesson: "L3"})
merge (a3:Lesson {lesson: "L4"})
merge (a4:Lesson {lesson: "L5"})
merge (a5:Lesson {lesson: "L6"})

merge (b:Skill {skill: "SK1"})
merge (b1:Skill {skill: "SK2"})
merge (b2:Skill {skill: "SK3"})
merge (b3:Skill {skill: "SK4"})

merge (a)-[:REQUIRES]->(b)
merge (a)-[:REQUIRES]->(b2)
merge (a)-[:REQUIRES]->(b3)

merge (b)-[:PROVIDED_BY]->(a1)
merge (b2)-[:PROVIDED_BY]->(a2)
merge (b3)-[:PROVIDED_BY]->(a3)

Cypher query:
match (a:Lesson)-[]-(b:Skill)-[]-(c:Lesson)
with distinct a.lesson as lesson, collect(distinct c.lesson) as lessons
with lesson, lessons where size(lessons) > 1
return lesson, lessons
type or paste code here

Result:

[jasperblondin]

Thank you for the attention!
I have updated the task description.

[Bennu]

Hi @jasperblondin !

Quick request just because I feel a bit lazy . Do you have the queries in order to generate your sample data?

Bennu

[jasperblondin]

Hi!

Of course. See the description above.
I will duplicate it below.

merge (l1:Lesson {id: "L1"})
merge (l2:Lesson {id: "L2"})
merge (l3:Lesson {id: "L3"})
merge (l4:Lesson {id: "L4"})
merge (l5:Lesson {id: "L5"})
merge (l6:Lesson {id: "L6"})
merge (l7:Lesson {id: "L7"})
merge (l8:Lesson {id: "L8"})
merge (l9:Lesson {id: "L9"})

merge (s1:Skill {id: "S1"})
merge (s2:Skill {id: "S2"})
merge (s3:Skill {id: "S3"})
merge (s4:Skill {id: "S4"})
merge (s5:Skill {id: "S5"})
merge (s6:Skill {id: "S6"})
merge (s7:Skill {id: "S7"})
merge (s8:Skill {id: "S8"})
merge (s9:Skill {id: "S9"})

merge (l1)-[:REQUIRES]->(s1)
merge (l1)-[:REQUIRES]->(s2)
merge (l1)-[:REQUIRES]->(s3)

merge (s1)-[:PROVIDED_BY]->(l2)
merge (s1)-[:PROVIDED_BY]->(l3)
merge (s2)-[:PROVIDED_BY]->(l4)
merge (s3)-[:PROVIDED_BY]->(l5)
merge (s3)-[:PROVIDED_BY]->(l6)

merge (l3)-[:REQUIRES]->(s4)
merge (l4)-[:REQUIRES]->(s5)
merge (l4)-[:REQUIRES]->(s6)
merge (l5)-[:REQUIRES]->(s6)
merge (l6)-[:REQUIRES]->(s7)

merge (s4)-[:PROVIDED_BY]->(l7)
merge (s5)-[:PROVIDED_BY]->(l7)
merge (s6)-[:PROVIDED_BY]->(l8)
merge (s7)-[:PROVIDED_BY]->(l9)

merge (l9)-[:REQUIRES]->(s3)

[Bennu]

Hi @jasperblondin !

Assuming you don't wanna use any APOC function.

MATCH p = (i:Lesson {id : 'L1'})-[:REQUIRES|PROVIDED_BY*]->(f:Lesson)
where not (f)-[:REQUIRES]->()
return [n in nodes(p) where n:Lesson | n.id]

Bennu

PS: Lemme know if it works on trickier cases. Yes I know, we all hate corner cases.

[jasperblondin]

Thank you for the quick response!

The code works fine. But there is one "corner case"
It is necessary to exclude repetition of nodes (loops). In other words, the route does not have to go through the same node twice. This is only for nodes labeled "Lesson"!
To reproduce the problem, you just need to add a pair of relations to the existing graph:

match (l9:Lesson {id: "L9"})
match (s8:Skill {id: "S8"})
merge (l9)-[:REQUIRES]->(s8)

and

match (s8:Skill {id: "S8"})
match (l1:Lesson {id: "L1"})
merge (s8)-[:PROVIDED_BY]->(l1)

[poornima]

In your modification, you have connected L9 back to L1 which means L1 can be completed only by skills attained through L9 but L9 can be completed only by skills attained through L1. Is this right? This is why L1 is now appearing twice in the list and once it appears the second time, it now traverses along other paths until the condition where not (f)-[:REQUIRES]->() can be met i.e. it is looking for a terminal node. the results do not look right. There is a ["L1", "L4", "L7"] result but also a ["L1", "L6", "L9", "L1", "L4", "L7"]. See how the same path gets inserted in there?

[jasperblondin]

poornima:

In your modification, you have connected L9 back to L1 which means L1 can be completed only by skills attained through L9 but L9 can be completed only by skills attained through L1. Is this right?

Almost.
The word "only" is superfluous here.
My example is oversimplified.
There are many other connections and ways to achieve a skill.

[poornima]

Understood. Here's a modification using @Bennu 's original solution without using APOC, this is to ensure a Lesson like L1 which is an anchor and has both requires and provided by relationships in the same node is not visited twice -

MATCH p = (f:Lesson)<-[*]-(i:Lesson {id : 'L1'})<-[]-()
WHERE NOT (f)-[]->()
return [n in nodes(p) where n:Lesson | n.id]

It is more efficient to use relationship names I think, but just in case a lesson is connected to another lesson or a terminal node (or the first ever lesson) is connected using a relationship other than REQUIRES, I omitted specific names.

[Bennu]

I knew it long before posting the solution. There's one way to avoid it but I'm not on my computer right now (yes I know, 'why is he answering then?')

Meanwhile, can the solution use Apoc functions?
If you aim for performance as well you/we may need them.

Bennu

PS: How can you have cycles on ur use case?

[jasperblondin]

Bennu:

Meanwhile, can the solution use Apoc functions?

Any rational decisions are welcome!

[Bennu]

Hi @jasperblondin !

I got a little bit lost and I had no time to understand it all right now... So I just trust your description here

jasperblondin:

It is necessary to exclude repetition of nodes (loops). In other words, the route does not have to go through the same node twice. This is only for nodes labeled "Lesson"!

So try this,

MATCH p = (i:Lesson {id : 'L1'})-[:REQUIRES|PROVIDED_BY*]->(f:Lesson)
where not (f)-[:REQUIRES]->()
and NONE (n IN nodes(p) 
            WHERE n:Lesson and size([x IN nodes(p) 
                              WHERE x:Lesson and n = x])> 1)
return [n in nodes(p) where n:Lesson | n.id]

Is it the answer you were expenting for this use case?

If it does, please add a Beerware license to it.

Bennu

PS: You may not need the x:Lesson in the 2nd internal where.

[poornima]

Great solution! 🙂 I also found "where n.id" doesn't work well.. it needs to say "where n.id is not null". No problems with "where n:Lesson".

[jasperblondin]

Also I got a message about the deprecated method.

But this is not so important.

[jasperblondin]

I will describe the task in more detail.
Some group of teachers create lessons. Each lesson provides a specific skill. But, also, the lesson requires the student to already have a certain set of skills (to access the lesson).
Theoretically, a situation is possible when a certain lesson L1 of one of the teachers provides skill S1, but at the same time requires skill S2. At the same time, a certain lesson L2 of another teacher provides the skill S2, but at the same time requires the skill S1. It turns out a loop. Therefore, I need to truncate such a chain until the loop appears (before repeating the lesson). I can do this after fetching the data. But if there is an opportunity to do this at the fetching stage, it will be great.

PS: Sorry for my English

[jasperblondin]

Both solutions work very well.
But after checking them on real data, I ran into a problem related to the fact that I incorrectly described the task and built a test case.
Each of the lessons will always contain a list of required skills (at least one). Thus, the condition for ending the chain should be as follows: the chain ends if, for its last lesson, each required skill is not provided by any other lesson.

I tried to rewrite the condition:

where not (f)-[:REQUIRES]->()

like this:

where not (f)-[:REQUIRES]->(:Skill)-[:PROVIDED_BY]->()

But my attempts were unsuccessful

[Bennu · Accepted solution]

@jasperblondin

oh god I'll enjoy that beer.

I let the previous case still valid. Remove S4 to L7 dependency.

MATCH p = (i:Lesson {id : 'L1'})-[:REQUIRES|PROVIDED_BY*]->(f:Lesson)
where (
          (not (f)-[:REQUIRES]->())
          OR
          not exists((f)-[:REQUIRES]->()-[:PROVIDED_BY]->())
     )
and NONE (n IN nodes(p) 
            WHERE n:Lesson and size([x IN nodes(p) 
                              WHERE x:Lesson and n = x])> 1)
return [n in nodes(p) where n:Lesson | n.id]

B

PS: I wonder if the community forum accepts GIF's

[jasperblondin]

Bennu:

Remove S4 to L7 dependency.

I have already fixed my mistake.
Hope no one would notice. But you are very careful
The current model looks like this:

merge (l1:Lesson {id: "L1"})
merge (l2:Lesson {id: "L2"})
merge (l3:Lesson {id: "L3"})
merge (l4:Lesson {id: "L4"})
merge (l5:Lesson {id: "L5"})
merge (l6:Lesson {id: "L6"})
merge (l7:Lesson {id: "L7"})
merge (l8:Lesson {id: "L8"})

merge (s1:Skill {id: "S1"})
merge (s2:Skill {id: "S2"})
merge (s3:Skill {id: "S3"})
merge (s4:Skill {id: "S4"})
merge (s5:Skill {id: "S5"})
merge (s6:Skill {id: "S6"})
merge (s7:Skill {id: "S7"})
merge (s8:Skill {id: "S8"})
merge (s9:Skill {id: "S9"})

merge (l1)-[:REQUIRES]->(s1)
merge (l1)-[:REQUIRES]->(s2)
merge (l1)-[:REQUIRES]->(s3)

merge (s1)-[:PROVIDED_BY]->(l2)
merge (s1)-[:PROVIDED_BY]->(l3)
merge (s2)-[:PROVIDED_BY]->(l4)
merge (s3)-[:PROVIDED_BY]->(l5)
merge (s3)-[:PROVIDED_BY]->(l6)

merge (l2)-[:REQUIRES]->(s4)
merge (l2)-[:REQUIRES]->(s9)
merge (l3)-[:REQUIRES]->(s4)
merge (l4)-[:REQUIRES]->(s5)
merge (l4)-[:REQUIRES]->(s6)
merge (l5)-[:REQUIRES]->(s6)
merge (l6)-[:REQUIRES]->(s7)

merge (s6)-[:PROVIDED_BY]->(l7)
merge (s7)-[:PROVIDED_BY]->(l8)

merge (l7)-[:REQUIRES]->(s8)
merge (l8)-[:REQUIRES]->(s3)

merge (s9)-[:PROVIDED_BY]->(l1)

Your code works well. But somehow it doesn't return me one of the possible routes: ["L1", "L2"].
Please clarify, does your code cut the loops or completely exclude them from the result?

[Bennu]

Hi,

They are removed. Technically ["L1", "L2"] can't be because L2 requires S9 and S9 it's just provided by L1.

'The dog that bites it's own tail'

B

[jasperblondin]

Bennu:

They are removed. Technically ["L1", "L2"] can't be because L2 requires S9 and S9 it's just provided by L1.

In theory, there might be a situation in which the loop is longer. For example, ["L1", "S21", "L21", "S22", "L22", "S23", "L23", "S24", "L1"].
The student may have skill S22 (obtained through another lesson L99), so he should be able to follow route ["L99", "S22", "L22", "S23", "L23", "S24", "L1"] to the required lesson (the skill that this lesson provides). And we are depriving him of this opportunity.

PS: I understand that it looks strange. But people sometimes do illogical things. Even teachers creating lessons.

[Bennu]

Well,

I don't have L99 on my DB so It's hard too see this scenario on my mind. Nothing a good functional requirement can't solve

B

[ameyasoft]

match (a:Lesson)-[:REQUIRES]->(b:Skill)
with distinct a.id as lesson, collect(distinct b.id) as skls

match (c:Skill)-[:PROVIDED_BY]->(d:Lesson)
where c.id in skls
with lesson, skls, collect(distinct d.id) as lessons 
return lesson as Lesson, apoc.coll.sort(skls) as requiredSkills, apoc.coll.sort(lessons) as lessonsProvideSkills, size(lessons) as totalLessons order by totalLessons desc

Result:

[poornima]

This is a very interesting use case! Great way to get to learn neo4j!!! 😉