Repeating Pattern With Terminating Condition

Neo4j Graph Platform
, ,
1

The Graph:

biker_routes
biker_routes1457×589 77.9 KB

Facts:
A cyclist starts at the far left of the image above. They read the plan to know where to go. A plan is composed of legs. Legs are composed of landmarks. A cyclist completes a leg by traveling from the beginning landmark to the ending landmark. A plan is complete when a cyclist travels all legs in the plan. A plan may have an infinite number of legs. Additionally, two plans may be contiguous if the ending landmark of the first plan is the same as the beginning landmark of the second plan. The number of contiguous plans is also infinite.

The Question:
If a cyclist starts at the first leg of an arbitrarily selected plan, then how many plans can a cyclist follow to travel a specified maximum distance.

I'm having trouble coming up with a cypher match pattern that depicts a variable length path comprised of contiguous legs (legs are contiguous, technically, not plans).

I've done something like:

match (:Plan)-[:DEPICTS]->(start:Leg)
with start
match path = (start)-[:ENDS*..]->(:Landmark)<-[:BEGINS*..]-(:Leg)
return path

I have also tried the following, which returns all of the components that have this pattern instead of only returning the components with (start:Leg) as the root.

match (:Plan)-[:DEPICTS]->(start:Leg)
with start
match path = (:Leg)-[:ENDS*..]->(:Landmark)<-[:BEGINS*..]-(:Leg)
return path

This does not return a full path, instead it stops at the first pattern match.

  • Neo4j 4.1.1 Enterprise
  • Neo4j.Driver-4.2
2

Hi @captainrdubb,

Can you try this query and tell m if it's what you expected?

match (p:Plan)-[:DEPICTS]->(start:Leg)
with p, start
MATCH path =(start:Leg)-[:FOLLOWED_BY*0..]->(leg:Leg)
WHERE NOT (leg)-[:FOLLOWED_BY]->()
with p, nodes(path) as legs
UNWIND legs as leg
MATCH (l1:Landmark)<-[:BEGINS]-(leg)-[:ENDS]->(l2:Landmark)
MATCH (l1)-[r:ROAD]-(l2)
with p, legs, sum(r.km) as dist
where dist > 150 //define limit here
return p, legs, dist

Bennu

3

Thanks for the response! This is really close! There is good news and bad news.

The Bad News: It looks like the query is missing contiguous legs where two legs do NOT have a FOLLOWED_BY relationship, because they do not belong to the same Plan. However the legs share a Landmark, which allows the cyclist to end the last Leg of a Plan and begin the first Leg of a new Plan, because of the shared Landmark.

The Good News: I can create a new relationship, with a name something like "TRANSITIONS_TO" which is a lot like FOLLOWED_BY, except we know that the two legs are not part of the same plan.

@Bennu Thank you so much!