Graphs in the Real World - Graph Databases - page 138

This traversal description is built by expanding the ParcelRouteCalculator 's static
DELIVERY_BASE_FINDER traversal description using the DELIVERY_ROUTE_EXPANDER .
The branch state for the expander is initialized at this point with the interval supplied
by the client. This enables us to use the same base traversal description instance ( DE
LIVERY_BASE_FINDER ) for multiple requests. This base description is expanded and
parameterized for each request.
Properly configured with an interval, the traversal description is then supplied to fin
dRouteToDeliveryBase() , which looks up a starting node in the location index, and
then executes the traversal:
private Path findRouteToDeliveryBase ( String startPosition ,
TraversalDescription deliveryBaseFinder )
{
Node startNode = locationIndex . get ( "name" , startPosition ). getSingle ();
return deliveryBaseFinder . traverse ( startNode ). iterator (). next ();
}
That's the two legs taken care of. The last part of the calculation requires us to find the
shortest path between the delivery bases at the top of each of the legs. calculate
Route() takes the last node from each leg's path, and supplies these two nodes together
with the client-supplied interval to findRouteBetweenDeliveryBases() . Here's the
implementation of findRouteBetweenDeliveryBases() :
private Path findRouteBetweenDeliveryBases ( Node deliveryBase1 ,
Node deliveryBase2 ,
Interval interval )
{
PathFinder < WeightedPath > routeBetweenDeliveryBasesFinder =
GraphAlgoFactory . dijkstra (
CONNECTED_TO_EXPANDER ,
new InitialBranchState . State < Interval >( interval , interval ),
COST_EVALUATOR );
return routeBetweenDeliveryBasesFinder
. findSinglePath ( deliveryBase1 , deliveryBase2 );
}
Rather than use a traversal description to find the shortest route between two nodes,
this method uses a shortest weighted path algorithm from Neo4j's graph algorithm li‐
brary—in this instance, we're using the Dijkstra algorithm (see “Path-Finding with
Dijkstra's Algorithm” on page 164 for more details of the Dijkstra algorithm). This algo‐
rithm is configured with ParcelRouteCalculator 's static CONNECTED_TO_EXPANDER ,
which in turn is initialized with the client-supplied branch state interval. The algorithm
is also configured with a cost evaluator (another static member), which simply identifies
the property on a relationship representing that relationship's weight or cost. A call to
findSinglePath on the Dijkstra path finder returns the shortest path between the two
delivery bases.