CODEWITHSUNDEEP
algorithmneo4jshortest-path
Boas Enkler
Boas Enkler

Reputation: 12557

Graph Modelling in neo4j for shortest path based on date/time?

I want to model a Graph to do pathfinding.

In the simplest scenario I've

Stations and Rides

So my Graph looks like this

Station A -> Ride -> Station B
Station B -> Ride -> station C

Now When I Search From A To C I could to some path searching for example with the dijkstra algorithm.

But now the rides are date related. I thought about grouping them under date nodes For Departure and arrival like this (I would represent the date as a unix timestamp, just for better readbility it is a date below)

Station A -> 01/01/2016 -> Ride -> 01/01/2016 -> Station B
Station B -> 01/01/2016 -> Ride -> 01/02/2016 -> station C

This way I could start the lookup from the specific datenode of the start station.

First Question:

Is this a good idea?

Second Question:

There is still the time problem. So that the second ride must occur AFTER the first ride. I'm not sure how to handle this. Is there a way to do this with a cipher query?

Upvotes: 0

Views: 128

Answers (1)

stdob--
stdob--

Reputation: 29172

1) I would use this model:

(a:Station {title:'Station A'})-[:Ride]->
    (r:Ride { title:'Ride from A to B', 
              departure: '01/01/2016', 
              arrival: '01/01/2016'
    })
-[:Ride]->(b:Station {title:'Station B'});

(b:Station {title:'Station B'})-[:Ride]->
    (r:Ride { title:'Ride from B to C', 
              departure: '01/01/2016', 
              arrival: '01/02/2016'
    })
-[:Ride]->(c:Station {title:'Station C'})

2) And about query:

MATCH (A:Station {title:'Station A'})
MATCH (C:Station {title:'Station C'})
  WITH (A)-[:Ride*]->(C) as trips
  UNWIND trips as trip
    WITH filter( ride in nodes(trip) WHERE ride:Ride ) as rides
      WHERE size(rides) <= 3 AND
            all( 
                 i in range(0, size(rides) - 2) 
                 WHERE rides[i]['arrival'] < rides[i+1]['departure'] 
            ) 
RETURN 
  rides,
  reduce( resistance = 0, n in rides | resistance + n.resistance ) as resistance,
  ( rides[size(rides)-1]['arrival'] - rides[0]['departure'] ) as duration
ORDER BY resistance ASC, duration ASC
SKIP 0 LIMIT 5 // <== get the first five of the best routes

Upvotes: 1

Related Questions