Graphs in the Real World - Graph Databases - page 137

...
}
Here we define two expanders—one for DELIVERY_ROUTE relationships, another for
CONNECTED_TO relationships—and the traversal that will find the two legs of our route.
This traversal terminates whenever it encounters a node with no incoming DELIV
ERY_ROUTE relationships. Because each delivery base is at the root of a delivery route
tree, we can infer that a node without any incoming DELIVERY_ROUTE relationships
represents a delivery base in our graph.
The constructor for ParcelRouteCalculator accepts the current database instance.
From this it obtains the location index, which it stores in a member variable.
Each route calculation engine maintains a single instance of this route calculator. This
instance is capable of servicing multiple requests. For each route to be calculated, the
client calls the calculator's calculateRoute() method, passing in the names of the start
and end points, and the interval for which the route is to be calculated:
public Iterable < Node > calculateRoute ( String start ,
String end ,
Interval interval )
{
TraversalDescription deliveryBaseFinder =
createDeliveryBaseFinder ( interval );
Path upLeg = findRouteToDeliveryBase ( start , deliveryBaseFinder );
Path downLeg = findRouteToDeliveryBase ( end , deliveryBaseFinder );
Path topRoute = findRouteBetweenDeliveryBases (
upLeg . endNode (),
downLeg . endNode (),
interval );
return combineRoutes ( upLeg , downLeg , topRoute );
}
calculateRoute() first obtains a deliveryBaseFinder for the specified interval, which
it then uses to find the routes for the two legs. Next, it finds the route between the delivery
bases at the top of each leg, these being the last nodes in each leg's path. Finally, it
combines these routes to generate the final results.
The createDeliveryBaseFinder() helper method creates a traversal description con‐
figured with the supplied interval:
private TraversalDescription createDeliveryBaseFinder ( Interval interval )
{
return DELIVERY_BASE_FINDER . expand ( DELIVERY_ROUTE_EXPANDER ,
new InitialBranchState . State < Interval >( interval , interval ) );
}