How to find patterns that include other patterns in order (with Neo4j, Cypher)

Question

I am trying to find patterns that include other sub patterns.

I have a graph with Stop and Stoptime nodes and 4 different types of relationships: WALK_TO, GET_ON_THE_BUS, CONTINUE and GET_OFF_THE_BUS. WALK_TOhas distance and speed properties. Other relationships have time properties that I use to calculate the shortest path in time instead of the length of the path. xStop is a physical entity: a bus stop or a train station. xStoptime has the route info, arrival and departure time of the vehicle to the related stop.

I am trying to find paths from a departure point to a destination point. I split the path into a couple patterns;

start=(dep:xStop {name:'Departure'})-[:WALK_TO]->(:xStop)-[:GET_ON_THE_BUS]->(s:xStoptime)
end = (dest:xStop {name:'Destination'})<-[:WALK_TO]-(:xStop)<-[:GET_OFF_THE_BUS]-(e:xStoptime)

This gives me the ability to filter the relationships of both the start and end legs of the trip.

Now, the middle of trip can be a direct or an indirect trip. If it is a direct trip then:

direct=(:xStoptime)-[:CONTINUE*]->(:xStoptime)

Problem is with the indirect trips: the ones you have to make a transfer to another vehicle. I have 2 different transfer patterns:

t1=(:xStoptime)-[:GET_OFF_THE_BUS]->(a:xStop)-[:WALK_TO]->(b:xStop)-[:Dp]->(:xStoptime)
t2=(c:xStoptime)-[:GET_OFF_THE_BUS]->(:xStop)-[:GET_ON_THE_BUS]->(d:xStoptime) where not c.name=d.name

I want to find paths m

m=(s)-[*]->(e)

where m follows the pattern: direct, zero or more transfers with t1 or t2 , direct.

The reason that I am not using Cypher's shortest path is all relationships have properties on them and I want to calculate multiple costs based on those properties.

Any one can help? How do I write the Cypher query for this?

Can you describe your data model more completely? For example, what is the purpose of the D, A, R and Dp relationships? This question is very hard to follow otherwise. You should probably also change the names of those relationship types (at least when posing this question), so that the patterns can be easier to understand. — cybersam
Sure. I'm editing my post to include the explanation of relationships. — melis
If you're going to allow more than one repeat of either transfer pattern (basically, zero, one, or more than one), then Cypher won't be much help; it can do variable-length paths of a single relationship type, but not variable-length iterated patterns (yet). — Tore Eschliman
@cybersam I updated the names of the relationship and explained the graph model a little bit more. — melis
@ToreEschliman Do you have a suggestion like tweaking the graph model or something else? I could use a different perspective to solve the problem. — melis

cybersam cybersam · Accepted Answer · 2016-10-06T02:19:53

A different data model our data model might work better for you. For example, here is an alternate one (with some but not necessarily all the properties you need).

Alternate data model

(A) A walk between stops 1 and 4:

(:Stop {id: 1})-[:WALK {distance: 0.5, speed: 3}]->(:Stop {id: 4})

(B) A ride (on bus route 9) between stops 1 and 4:

(:Stop {id: 1})-[:RIDE {rte: 9, dep: 15, arr: 26}]->(:Stop {id: 4})

(C) A "direct" ride between stops 1, 2, and 4 (always on route 8):

(:Stop {id: 1})-[:RIDE {rte: 8, dep: 12, arr: 34}]->
  (:Stop {id: 2})-[:RIDE {rte: 8, dep: 56, arr: 88}]->(:Stop {id: 4})

(D) A "transfer" ride between stops 1, 2, and 4 (changing route at stop 2):

(:Stop {id: 1})-[:RIDE {rte: 8, dep: 12, arr: 34}]->
  (:Stop {id: 2})-[:RIDE {rte: 4, dep: 57, arr: 89}]->(:Stop {id: 4})

(E) A "transfer" ride between stops 1, 2, 3, and 4 (walking between stops 2 and 3):

(:Stop {id: 1})-[:RIDE {rte: 8, dep: 12, arr: 34}]->
  (:Stop {id: 2})-[:WALK {distance: 0.1, speed: 3}]->
    (:Stop {id: 3})-[:RIDE {rte: 5, dep: 66, arr: 92}]->(:Stop {id: 4})

Example

If we create paths A through E above, like this:

CREATE (a:Stop {id: 1}), (b:Stop {id: 2}), (c:Stop {id: 3}), (d:Stop {id: 4}),
(a)-[:WALK {distance: 0.5, speed: 3}]->(d),
(a)-[:RIDE {rte: 9, dep: 15, arr: 26}]->(d),
(a)-[:RIDE {rte: 8, dep: 12, arr: 34}]->(b),
(b)-[:RIDE {rte: 4, dep: 57, arr: 89}]->(d),
(b)-[:RIDE {rte: 8, dep: 56, arr: 88}]->(d),
(b)-[:WALK {distance: 0.1, speed: 3}]->(c)-[:RIDE {rte: 5, dep: 66, arr: 92}]->(d);

Then the following query may do what you want. It will return paths B through E. Its pattern requires a RIDE relationship at the start, followed by 0 or more RIDE or WALK relationships:

MATCH p=(a:Stop {id: 1})-[:RIDE]->(:Stop)-[:WALK|RIDE*0..]->(:Stop)-[:RIDE]->(b:Stop {id: 2})
RETURN p;

Note that there is no need for the query to actually test for a transfer, since you wanted "zero or more transfers".

Also, if you actually wanted the last relationship to always be a RIDE (that is different than the starting RIDE), you can change the query to: MATCH p=(a:Stop {id: 1})-[:RIDE]->(:Stop)-[:WALK|RIDE*0..]->(:Stop)-[:RIDE]->(b:Stop {id: 4}) RETURN p;. That will only return paths C through E.

How to find patterns that include other patterns in order (with Neo4j, Cypher)

1 Answers

Alternate data model

Example