BestFirstRouter.java (2404B) download
1package osm.routing.strategy;
2
3import java.util.HashSet;
4import java.util.Map;
5import java.util.PriorityQueue;
6import java.util.Queue;
7import java.util.Set;
8
9import osm.geo.Point;
10import osm.routing.RoutingEdge;
11import osm.routing.RoutingGraph;
12import osm.routing.RoutingNode;
13import osm.routing.RoutingStrategy;
14import 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 */
23public 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}