Neo4j Pathfinder with road type prefference

Hi All, Today I would like to post on how the graph database (Neo4j) can be used for path finding. As you know that in the real world there are so many type of road for example private road, normal road or toll. Since we have these type of choices then we shall be allowed to choose which road preference we would to travel from start point to end point. As you know that path finding algorithm A* or Djikstra always calculate for shortest path between nodes, So the question is how do we manage the road preference using the same algorithm. We know that there will be distance between each point in the graph. The algorithm will calculate this distance to pop out the shortest one. So the idea is to manage the preference by manipulating the distance calculated which we can setup multiplier to the non-preferred road type thus will give the total accumulated distance between nodes higher than the preferred one. I have the road network path as below, I try to demonstrated that we would like to travel from Balikpapan Center to Ace Hardware. There are some ways to travel but here I would like to show you 2 scenarios. The first one is to travel with the preference going with the shortest distance. The red line give you the path that the algorithm shall go. The second one is to travel with the preference going by toll road that is represented by blue line.

The algorithm that I would like to use in this sample is djikstra. To create the path finding algorithm in the Neo4j is just like the code below

public void run() {
    if (template != null) {

        PathFinder pathFinder = GraphAlgoFactory.dijkstra(new MeExpander(), new MyCostCalc());
        WeightedPath path = pathFinder.findSinglePath(template.getNode(0),template.getNode(9));
        if (path != null) {
            for (Node n : path.nodes()) {
                  System.out.print(" " + n.getProperty("name"));
            }
        }
        System.out.println("");
     }
 }

Djikstra algorithm creation get 2 parameters which is the first is the expander and cost estimation. To manage the road preference we can re-implement the calculation by implementing the Cost Evaluator class. Back to the scenario, The code below is the implementation for the 1st scenario.

public class MyCostCalc implements CostEvaluator {

  public Double getCost(Relationship relationship, Direction direction) {
       Double a = Double.valueOf(relationship.getProperty("distance").toString());
       return a;
  }

}

We can read above code that I don’t do anything to the distance gathered between nodes. Just return it as it is. But it is different with the code written below (For scenario 2), I do manage the distance gathered and do the trick. I multiply (*4) the distance for the road categorized as normal so that every time the traverser travelling through normal road then it will multiply the distance in result that algorithm will see it is longer distance as the impact the road preferred will have smaller distance.

public class TollPreffCostCalc implements CostEvaluator {
     public Double getCost(Relationship relationship, Direction direction) {
          Double a = Double.valueOf(relationship.getProperty("distance").toString());
          if(relationship.getProperty("type").toString().equals("normal")){
                  a = Double.valueOf(relationship.getProperty("distance").toString())*4;
     }
     return a;
 }

So, I hope you can get the idea of this sample. I think this is the most simple trick to be adopt in order to manage road preference in the path finding. This trick is just to trick the algorithm either djikstra or A* to return the preferred road by manipulating the distance traveled. Ho you enjoy.