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
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)
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?
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.
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.
I got a little bit lost and I had no time to understand it all right now... So I just trust your description here
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.
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 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]
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?
. Do you have the queries in order to generate your sample data?
