persolijn

an efficient router for busses
Log | Files | Refs

BestFirstRouter.java (2404B)

      1 package osm.routing.strategy;
      2 
      3 import java.util.HashSet;
      4 import java.util.Map;
      5 import java.util.PriorityQueue;
      6 import java.util.Queue;
      7 import java.util.Set;
      8 
      9 import osm.geo.Point;
     10 import osm.routing.RoutingEdge;
     11 import osm.routing.RoutingGraph;
     12 import osm.routing.RoutingNode;
     13 import osm.routing.RoutingStrategy;
     14 import osm.routing.RoutingGraph.Route;
     15 
     16 /**
     17  * A base class for implementing routing algorithms between two points on a
     18  * graph.
     19  *
     20  * @param <N> The type of nodes in the graph.
     21  * @param <P> The type of points representing locations in the graph.
     22  */
     23 public class BestFirstRouter<N extends RoutingNode<N>, E extends RoutingEdge<N>, P> implements RoutingStrategy<N, E> {
     24     /**
     25      * Finds the optimal route between the start node and a collection of target
     26      * nodes.
     27      *
     28      * @param targets The target nodes and their distances.
     29      * @param start   The starting node.
     30      * @param offset  The offset value.
     31      * @return A list representing the optimal route from the start to a target
     32      *         node.
     33      */
     34     @Override
     35     public Route<N> route(RoutingGraph<N, E> graph, Map<N, Long> targets, N start, long offset) {
     36         Queue<N> openNodes = new PriorityQueue<>(RoutingNode.scoreComparator());
     37         Set<N> closedNodes = new HashSet<>();
     38 
     39         double bestProgress = 0;
     40 
     41         openNodes.add(start);
     42         closedNodes.add(start);
     43 
     44         start.setScore(0L);
     45 
     46         while (!openNodes.isEmpty()) {
     47             N current = openNodes.poll();
     48 
     49             double currentProgress = graph.getProgress(targets, start, offset, current);
     50             if (currentProgress > bestProgress)
     51                 graph.onProgress(bestProgress = currentProgress, start, targets.keySet());
     52 
     53             if (graph.isTarget(targets, current)) {
     54                 N[] history = graph.getHistory(current);
     55                 return new Route<>(current, history, Point.distance(history));
     56             }
     57 
     58             graph.forNeighbor(current, edge -> {
     59                 N next = edge.getDestination();
     60 
     61                 if (closedNodes.contains(next))
     62                     return;
     63 
     64                 long totalWeight = current.getScore() + graph.getCost(current, edge);
     65 
     66                 next.setParent(current);
     67                 next.setScore(totalWeight);
     68 
     69                 closedNodes.add(next);
     70                 openNodes.add(next);
     71             });
     72         }
     73         return null;
     74     }
     75 
     76 }