Max De Marzi

If you have never watched Firefly, then stop whatever you are doing and get to it, you can come back and read this post later. Ok good, now where were we. Firefly. The series is set a few hundred years from now, after people begin to terraform a new star system and it follows the adventures of the renegade crew of Serenity, a “Firefly-class” spaceship whose work consists of cargo runs or smuggling while failing to stay out of trouble. There is no faster than light travel in this series, so ships can’t just “warp” where ever they want. Instead they travel about from planets and moons, exchanging cargo, refueling and trying to make a living. We are going to model “The Verse” of Firefly in Neo4j, and see how we can find routes to move our illicit cargo from one place to another.

You can see a video of what The Verse looks like here. We are going to add some Stations to our Planets and Moons. These represent space stations, space ports, landing areas, and anywhere a ship would land to pick up and drop off cargo. An example of this in the series is Eavesdown Docks, where the crew picked up Simon Tam (the doctor), Derrial Book (the preacher), and Lawrence Dobson (spoiler alert: the undercover agent) as paying passengers. We’re also going to add nodes labeled “Docking” which represent the event of a ship arriving and then departing a Station. These Dockings are connected and follow the route a ship will take. We can see the arrival, departure and transit times. Our cargo can go from one place to another in a single ship, if it happens to take it all the way there, but more likely it will change hands at various Stations along the way. These are represented by the Transhipment relationship which also has a transit time property that tells us how long it takes to unload, transport and reload cargo from one station to another. Transhipments can only happen within a Planet, Moon, or between the Moons and Planets orbiting each other.

Using Arrows our model looks like this:

Let’s say we want to transport River Tam in a stasis pod from the planet Londinium to the Ariopolis moon orbiting the planet Ariel and it looks like routes between them go via the planet Sihnon. If you recall a set of past blog posts modeling and traversing flights, you may remember we can do this in Neo4j by creating a Traversal Description. We can start at Londinium and find all the outgoing paths until we get to Ariopolis. We can also start at Ariopolis and find all the incoming paths until we get to Londinium. But wouldn’t it be better to start at both Londinium and Ariopolis and try to meet in the middle? Of course it would, but for this we need to describe a special Traversal Description in Neo4j called a Bidirectional Traversal Description.

A BidirectionalTraversalDescription can take two Traversal Descriptions. One for the start side of our traversal and one for the end side of the traversal. However it can also take a single traversal description and mirror them. Following the normal way from the start and the reverse way from the end. I want to show you a slightly complicate example, so we’ll use the mirroredSides.

One thing I didn’t show you in the previous traversal examples is that our traversal can keep a state. We will use the state to keep track of the time in our traversal and avoid time traveling into the past when traversing normally or into the future when traversing in reverse. It takes two parameters, in our case this will be the earliest time we want to depart, and the latest time we want to arrive.

 
InitialBranchState.State<Long> ibs = new InitialBranchState.State<>(
                    (Long)input.get("departure_long"), 
                    (Long)input.get("arrival_long")
            );

We are following paths from both ends, what happens when they meet in the middle at some node? We need to evaluate that path and make sure it is valid. We do not want any Docking nodes with departure and arrival dates outside our limits, so we’ll create a Route Evaluator with those parameters.

 
RouteEvaluator routeEvaluator = new RouteEvaluator(
                    (Long)input.get("departure_long"), 
                    (Long)input.get("arrival_long")
            );

Below we can see the evaluate function in our RouteEvaluator which eliminates any paths that violate our constraints:

 
  public Evaluation evaluate(Path path) {
        for (Node node: path.nodes()) {
            Long nodeDeparture = (Long)node.getProperty("departure", departure);
            Long nodeArrival = (Long)node.getProperty("arrival", arrival);

            if (nodeDeparture < departure || nodeArrival > arrival) {
                return Evaluation.EXCLUDE_AND_PRUNE;
            }
        }
        return Evaluation.INCLUDE_AND_CONTINUE;
    }

We’ll implement a PathExpander (here called a RouteExpander), but we’ll leave that off for now and finish creating our traversal description and bidirectional traversal description. Our traversal description will keep track of the relationships it has seen in each path and make sure we don’t end up chasing our own tails by keeping them unique:

 
RouteExpander routeExpander = new RouteExpander(
                (long)input.get("arrival_long"),
                (long)input.get("time_limit"));

TraversalDescription td = db.traversalDescription()
                    .breadthFirst()
                    .expand(routeExpander, ibs)
                    .uniqueness(Uniqueness.RELATIONSHIP_PATH);

BidirectionalTraversalDescription bidirtd = db.bidirectionalTraversalDescription()
                    .mirroredSides(td)
                    .collisionEvaluator(routeEvaluator);

Notice we are doing this traversal breadthFirst in true bidirectional search fashion, but we could have gone depthFirst as well. Ok, so let’s get back to the RouteExpander. Here is where all the magic happens. We’ll take the arrival time in our constructor along with a stopTime. In any graph you can run into an explosion of possible paths, so we are using stopTime to add a time limit to our path finding which guarantees our path exploration won’t take more than X milliseconds. We are traveling from Planets and Moons to other Planets and Moons, but we can’t just drop cargo off randomly, we are using Stations located on those planets and moons, so as a first step we’ll find those in our path. Once we get to a Station, we can check the Dockings connected to it, or we can transfer to another station. If we did transfer, then we need to add our transfer time to the arrival time of the previous Docking to know where in time we are. Finally we’ll find Dockings that don’t arrive too late, and are departing after our current time. We also need to do the same in reverse. So let’s take a look at it in the normal direction:

 
public class RouteExpander implements PathExpander<Long> {
    private long arrival;
    private long stopTime;

    public RouteExpander(long arrival, long stopTime) {
        this.arrival = arrival;
        this.stopTime = System.currentTimeMillis() + stopTime;
    }

    @Override
    public Iterable<Relationship> expand(Path path, BranchState<Long> branchState) {
        // Stop if we are over our time limit
        if (System.currentTimeMillis() < stopTime) {

            // We will start at a Moon or Planet, but need to get to a station
            if ( path.endNode().hasLabel(Labels.Moon) || path.endNode().hasLabel(Labels.Planet)) {
                return path.endNode().getRelationships(
                        Direction.INCOMING, RelationshipTypes.LOCATED_AT);
            }

            // When we reach a station, we need to continue to its dockings or other stations via transhipment.
            if ( path.endNode().hasLabel(Labels.Station)) {

                // If we transfered here, our new times should be our arrival + transit time
                if (path.lastRelationship().isType(RelationshipTypes.TRANSHIPMENT)) {
                    Node lastDocking = null;
                    Iterator<Node> iterator = path.reverseNodes().iterator();
                    while (iterator.hasNext()) {
                        lastDocking = iterator.next();
                        if (lastDocking.hasLabel(Labels.Docking)) { break;}
                    }

                    Long previousArrival = (long)lastDocking.getProperty("arrival");
                    previousArrival += (long)path.lastRelationship().getProperty("transit_time");
                    branchState.setState(previousArrival);
                }

                return path.endNode().getRelationships(
                        RelationshipTypes.HAS_DOCKING,
                        RelationshipTypes.TRANSHIPMENT);
            }

            // Ignore any Dockings that arrive too late.
            Long lastArrival = (long)path.endNode().getProperty("arrival", arrival);
            if ( lastArrival <= arrival ) {

                // Ignore any Transits that we cannot catch due to time.
                Long lastDeparture = branchState.getState();
                Long departure = (Long) path.endNode().getProperty("departure", lastDeparture);

                if (departure >= lastDeparture) {
                    branchState.setState(departure);
                    return path.endNode().getRelationships(
                            RelationshipTypes.CONNECTED_TO,
                            RelationshipTypes.HAS_DOCKING);
                }
            }
        }
        return Collections.emptyList();
    }

In the reverse method we do the same but in reverse (surprise!). You can see the full code for this class on github.

Now we can finally call traverse on our bidirectional traversal passing in our startingPoint and endingPoint (which are planet and moon nodes). For each path we find, we’ll collect the nodes along the route and the time into a result map. Notice I am using getAllProperties. This is a fairly recent addition to the API and highly recommended instead of getting one property at a time. We need the departure and arrival dates from the Docking nodes, not the Station or Planet/Moon where we may end up, so getting those looks a little funny:

 
for (org.neo4j.graphdb.Path position : bidirtd.traverse(startingPoint, endingPoint)) {
                HashMap<String, Object> result = new HashMap<>();
                ArrayList<Map> steps = new ArrayList<>();
                for (Node node : position.nodes()) {
                    Map<String, Object> vsidInfo = node.getAllProperties();
                    vsidInfo.put("label", node.getLabels().iterator().next().name());
                    steps.add(vsidInfo);
                }

                result.put("steps", steps);
                result.put("departure_date", steps.get(2).get("departure_date"));
                result.put("arrival_date", steps.get(steps.size() - 3).get("arrival_date"));
                result.put("travel_time", (long)steps.get(steps.size() - 3).get("arrival")
                        - (long)steps.get(2).get("departure"));
                results.add(result);
            }

We’ll take all our results and sort them using a RouteComparator which will choose the shortest path first, then the ones with the shortest travel time, earliest arrival, departure docking code and finally arrival docking code for the sort order. You can see that RouteComparator class on github as well.

Finally we’ll take the top X paths, based on a recordLimit parameter.

 
return Response.ok().entity(
                objectMapper.writeValueAsString(
                        results.subList(0,
                                Math.min(results.size(), recordLimit)
                        ))).build();

Once we configure our extension and create some sample data we can query it like this:

 
:POST /v1/service/query {
        "from":"Londinium", 
        "to":"Sihnon", 
        "departure_date":"11/06/2215", 
        "arrival_date": "12/04/2215" }

Finally we can see our results:

 
[
  {
    "departure_date": "11/06/2215 12:00 PM",
    "steps": [
      {
        "name": "Londinium",
        "label": "Planet"
      },
      {
        "name": "Aldik",
        "label": "Station"
      },
      {
        "code": "d1",
        "arrival": 7758072000,
        "departure_date": "11/06/2215 12:00 PM",
        "departure": 7758158400,
        "label": "Docking",
        "arrival_date": "11/05/2215 12:00 PM"
      },
      {
        "code": "d2",
        "arrival": 7758244800,
        "departure_date": "11/08/2215 12:00 PM",
        "departure": 7758331200,
        "label": "Docking",
        "arrival_date": "11/07/2215 12:00 PM"
      },
      {
        "name": "Lirerim",
        "label": "Station"
      },
      {
        "name": "Sihnon",
        "label": "Planet"
      }
    ],
    "arrival_date": "11/07/2215 12:00 PM",
    "travel_time": 86400
  }
]

Which looks like:

If you want to see the complete source code, it’s on github as usual. Take a look at some of the tests for more complicated traversals.

You may not need to smuggle contraband across solar systems any time soon, but hopefully you can relate the example to something you are working on. The Traversal Framework is a pretty powerful tool in Neo4j, learn it and you’ll be able to kill problems with your brain.

Every Firefly fan has something they love about the show. I’m going to wrap up this blog post with my favorite scene from Firefly.

Simon: I’m trying to put this as delicately as I can… How do I know you won’t kill me in my sleep?
Mal: You don’t know me, son, so let me explain this to you once: If I ever kill you, you’ll be awake. You’ll be facing me, and you’ll be armed.
Simon: Are you always this sentimental?
Mal: I had a good day.
Simon: You had the Alliance on you, criminals and savages… Half the people on the ship have been shot or wounded including yourself, and you’re harboring known fugitives.
Mal: Well, we’re still flying.
Simon: That’s not much.
Mal: It’s enough.