Apache TinkerPop•16mo ago

Route from origin to destination between two datetimes

Hey, I'm attempting to create a graph DB that will allow me to efficiently find a route from origin to destination between two times stamps. I've created two different graph DBs were different levels of success. I have one graph that has AirportDay vertices and Flight edges between them. This was my first attempt, and while it worked, since the Flights were edges I was not able to guarantee that the next flight in the route took off before the previous one landed. This caused me to create my second graph, which is Flights as vertices and a connects_to edge to connect Flights to other Flights. This one works very well (besides inserting into the DB but that's not too big of a problem). I have a few questions 1. Are these optimal designs for this type of problem, I'm sure someone has had this problem before, I tried following this blog (https://maxdemarzi.com/2017/05/24/flight-search-with-neo4j/) but couldn't get it to work 2. Why does my second query output paths that go through the destination? For example it output this path for when my origin was MIA and destination is ATL. I want this query to stop once it hits ATL... 1912MIA20230612 -> 0957ATL20230612 -> 2455DEN20230612

maxdemarzi

Max De Marzi

Flight Search with Neo4j

I think I am going to take the opportunity to explain why I love graphs in this blog post. I’m going to try to explain why looking at problems from the graph point of view opens you up to cre…

2 Replies

terrabl•16mo ago

Here is my query for each one AirportDay + Flight

    paths = (g.V().hasLabel('AirportDay').has('airport', origin).has('date', gte(start_datestamp))
             .as_('a')
             .repeat(
        __.outE('flight').as_('fl')
        .inV().hasLabel('AirportDay').has('date', lte(end_datestamp))
        .where(P.gte('a')).by('date')
        .simplePath()
    )
             .until(
        __.has('airport', destination).has('date', lte(end_datestamp)).or_().loops().is_(4)
    )
             .has('airport', destination).has('date', lte(end_datestamp))  # ensure the destination is reached
             .path()
             .by('airport')
             .by(
                __.valueMap('flight_id', 'start_timestamp', 'end_timestamp'))  # Retrieve flight_id, start_timestamp and end_timestamp
             .toList())

    paths = (g.V().hasLabel('AirportDay').has('airport', origin).has('date', gte(start_datestamp))
             .as_('a')
             .repeat(
        __.outE('flight').as_('fl')
        .inV().hasLabel('AirportDay').has('date', lte(end_datestamp))
        .where(P.gte('a')).by('date')
        .simplePath()
    )
             .until(
        __.has('airport', destination).has('date', lte(end_datestamp)).or_().loops().is_(4)
    )
             .has('airport', destination).has('date', lte(end_datestamp))  # ensure the destination is reached
             .path()
             .by('airport')
             .by(
                __.valueMap('flight_id', 'start_timestamp', 'end_timestamp'))  # Retrieve flight_id, start_timestamp and end_timestamp
             .toList())

Flights + connect_to

    paths = (g.V().hasLabel('Flight').has('origin', origin).has('start_timestamp', gte(start_timestamp))
             .emit(__.has('destination', destination).has('end_timestamp', lte(end_timestamp)))
             .repeat(
                 __.outE('connects_to').inV().has('end_timestamp', lte(end_timestamp)).simplePath()
             )
             .until(__.has('destination', destination).has('end_timestamp', lte(end_timestamp)).or_().loops().is_(3))
             .has('destination', destination).has('end_timestamp', lte(end_timestamp))
             .path().by(T.id)
             .toList())

    paths = (g.V().hasLabel('Flight').has('origin', origin).has('start_timestamp', gte(start_timestamp))
             .emit(__.has('destination', destination).has('end_timestamp', lte(end_timestamp)))
             .repeat(
                 __.outE('connects_to').inV().has('end_timestamp', lte(end_timestamp)).simplePath()
             )
             .until(__.has('destination', destination).has('end_timestamp', lte(end_timestamp)).or_().loops().is_(3))
             .has('destination', destination).has('end_timestamp', lte(end_timestamp))
             .path().by(T.id)
             .toList())

Anyone know why this query

 paths = (g.V().hasLabel('Flight').has('origin', origin).has('start_timestamp', gte(start_timestamp))
             .emit(__.has('destination', destination).has('end_timestamp', lte(end_timestamp)))
             .repeat(
                 __.outE('connects_to').inV().has('end_timestamp', lte(end_timestamp)).simplePath()
             )
             .until(__.has('destination', destination).has('end_timestamp', lte(end_timestamp)).or_().loops().is_(3))
             .has('destination', destination).has('end_timestamp', lte(end_timestamp))
             .path().by(T.id)
             .toList())

 paths = (g.V().hasLabel('Flight').has('origin', origin).has('start_timestamp', gte(start_timestamp))
             .emit(__.has('destination', destination).has('end_timestamp', lte(end_timestamp)))
             .repeat(
                 __.outE('connects_to').inV().has('end_timestamp', lte(end_timestamp)).simplePath()
             )
             .until(__.has('destination', destination).has('end_timestamp', lte(end_timestamp)).or_().loops().is_(3))
             .has('destination', destination).has('end_timestamp', lte(end_timestamp))
             .path().by(T.id)
             .toList())

Would return a path that goes through the destinaton? and then back to the destination?

spmallette•16mo ago

Would return a path that goes through the destinaton? and then back to the destination?

i'm not sure. at a quick glance, i would expect simplePath() to filter away any of those sorts of paths so i'm not sure why you would see that behavior. i think we'd need some sample data like @KelvinL requested on this SO post that I assume is related to this question here in discord: https://stackoverflow.com/q/76741481/1831717 - i think we'd need to see an example that produced that sort of situation in order to tell you what was happening..

Stack Overflow

Gremlin: Get All Routes from point A to point B with Day as the onl...

I'm attempting to create a route optimizer, the end state will eventually optimize the routes based on certain parameters, right now I'm just trying to get a graph DB set up and a query that can ge...

Gaming

Programming

Route from origin to destination between two datetimes