Neo4j Bus Route Application Modeling

Question

My question is I have one graph with lot of nodes representing stops of buses. How should I include bus information like which buses available between nodes.

I am thinking of creating a buses relationship between nodes that will have info of all the buses between two nodes and a relationship property marking distance between two stops.

      buses[500A,182A],distance:500m     buses[121B,542W,222A,111Z],distance:400m

Like A------------------------------------------------------->B----------------------------------------------------------->C

So how I will find out the bus or busses( If no direct path is available) to reach M from A?

First I will find out the path (a neo4j query) , how to reach M from A .

Say my path is

buses[11A],distance:1000m    buses[11A],distance:250m   buses[13B,100A],distance:2000m

A----------------------------------------->L----------------------------------->N------------------------------------------->M

The problem is I how to programmatically check whether a direct bus to M is available or not , or I how to interchange the bus in between.

According to above scenario I can go A to N through 11A then from N to M by taking either 13B or 100A.

I have to do that programmatically.

I want to retrieve all possible paths between two stations and total distance of a path along with bus information.

Do you want to minimize distance or the number of transfers? — Nicole White
I want to get all possible routes with bus interchange info alonng with total dstancce of each path. — Mahtab Alam

Nicole White Nicole White · Accepted Answer · 2015-01-03T00:32:20

Your model needs to be more graphy-y. That is, I don't think you should have an array property on the relationship between Stop nodes with the bus information. Rather, the buses should be nodes themselves with a relationship to indicate which stops they stop at. Consider the following example data:

CREATE (a:Stop {name:'A'}),
       (b:Stop {name:'B'}),
       (c:Stop {name:'C'}),
       (d:Stop {name:'D'}),

       (a)-[:NEXT {distance:1}]->(b),
       (b)-[:NEXT {distance:2}]->(c),
       (c)-[:NEXT {distance:3}]->(d),

       (b1:Bus {id:1}),
       (b2:Bus {id:2}),
       (b3:Bus {id:3}),

       (b1)-[:STOPS_AT]->(a),
       (b1)-[:STOPS_AT]->(b),
       (b2)-[:STOPS_AT]->(a),
       (b2)-[:STOPS_AT]->(b),
       (b2)-[:STOPS_AT]->(c),
       (b3)-[:STOPS_AT]->(b),
       (b3)-[:STOPS_AT]->(c),
       (b3)-[:STOPS_AT]->(d);

The graph now looks like this:

model

With this model, it's easy to find an itinerary that minimizes the number of transfers and also returns all the necessary transfer information, if applicable. For example, all shortest itineraries (shortest in terms of # of transfers) from A to D:

MATCH (a:Stop {name:'A'}), (d:Stop {name:'D'})
MATCH p = allShortestPaths((a)-[:STOPS_AT*]-(d))
RETURN EXTRACT(x IN NODES(p) | CASE WHEN x:Stop THEN 'Stop ' + x.name
                                    WHEN x:Bus THEN 'Bus ' + x.id
                               ELSE '' END) AS itinerary

Three routes were found, which all have one transfer:

Stop A, Bus 2, Stop C, Bus 3, Stop D
Stop A, Bus 1, Stop B, Bus 3, Stop D
Stop A, Bus 2, Stop B, Bus 3, Stop D

Of course, you can return this information however you want with the EXTRACT() function.

Another example. Find an itinerary from A to C:

MATCH (a:Stop {name:'A'}), (c:Stop {name:'C'})
MATCH p = allShortestPaths((a)-[:STOPS_AT*]-(c))
RETURN EXTRACT(x IN NODES(p) | CASE WHEN x:Stop THEN 'Stop ' + x.name
                                    WHEN x:Bus THEN 'Bus ' + x.id
                               ELSE '' END)

One route was found, and there are no transfers:

Stop A, Bus 2, Stop C

Please let me know if this answers your question.

EDIT: To get the distance:

MATCH (a:Stop {name:'A'}), (d:Stop {name:'D'})
MATCH route = allShortestPaths((a)-[:STOPS_AT*]-(d)),
      stops = (a)-[:NEXT*]->(d)
RETURN EXTRACT(x IN NODES(route) | CASE WHEN x:Stop THEN 'Stop ' + x.name
                                        WHEN x:Bus THEN 'Bus ' + x.id
                                   ELSE '' END) AS itinerary,
       REDUCE(d = 0, x IN RELATIONSHIPS(stops) | d + x.distance) AS distance


                           itinerary  distance
Stop A, Bus 1, Stop B, Bus 3, Stop D         6
Stop A, Bus 2, Stop B, Bus 3, Stop D         6
Stop A, Bus 2, Stop C, Bus 3, Stop D         6

Neo4j Bus Route Application Modeling

3 Answers