RoutingGraph.java (6430B) download
1package osm.routing;
2
3import java.util.Collection;
4import java.util.Map;
5import java.util.function.Consumer;
6import java.util.stream.Stream;
7
8/**
9 * Represents a routing graph, consisting of nodes and edges, and provides
10 * functionality for route calculation.
11 *
12 * @param <N> The type of nodes in the graph.
13 * @param <E> The type of edges connecting the nodes.
14 */
15public interface RoutingGraph<N extends RoutingNode<N>, E extends RoutingEdge<N>> {
16
17 /**
18 * Represents a route in a routing graph, consisting of a target node, a path,
19 * and the length of the route.
20 *
21 * @param <N> The type of nodes in the route.
22 */
23 public static class Route<N> {
24 private final N target;
25 private final N[] path;
26 private final long length;
27
28 /**
29 * Constructs a Route object.
30 *
31 * @param target The target node of the route.
32 * @param path The array of nodes representing the path from the source to the
33 * target.
34 * @param length The length of the route.
35 */
36 public Route(N target, N[] path, long length) {
37 this.target = target;
38 this.path = path;
39 this.length = length;
40 }
41
42 /**
43 * Gets the target node of the route.
44 *
45 * @return The target node.
46 */
47 public N getTarget() {
48 return target;
49 }
50
51 /**
52 * Checks if the route has a valid path.
53 *
54 * @return True if the route has a path, false otherwise.
55 */
56 public boolean hasPath() {
57 return path != null;
58 }
59
60 /**
61 * Gets the array of nodes representing the path from the source to the target.
62 *
63 * @return The array of nodes in the path.
64 */
65 public N[] getPath() {
66 return path;
67 }
68
69 /**
70 * Gets the length of the route.
71 *
72 * @return The length of the route.
73 */
74 public long getLength() {
75 return length;
76 }
77 }
78
79 /**
80 * Calculates the progress between the start and the current node.
81 *
82 * @param targets The target nodes and their distances.
83 * @param start The starting node.
84 * @param offset The offset value.
85 * @param current The current node.
86 * @return The progress between the start and current node as a percentage.
87 */
88 default double getProgress(Map<N, Long> targets, N start, long offset, N current) {
89 double startDistance = offset + getStartDistance(start, current);
90 return startDistance / (startDistance + getClosestDistance(targets, current));
91 }
92
93 /**
94 * Gets the size of the history for a given node.
95 *
96 * @param node The node for which to calculate the history size.
97 * @return The size of the history for the given node.
98 */
99 default int getHistorySize(N node) {
100 int size = 0;
101
102 for (N c = node; c != null; c = c.getParent())
103 size++;
104
105 return size;
106 }
107
108 /**
109 * Retrieves the history of a node, including itself and its ancestors.
110 *
111 * @param node The node for which to retrieve the history.
112 * @return A list representing the history of the given node.
113 */
114 default N[] getHistory(N node) {
115 N[] path = createHistoryArray(getHistorySize(node));
116
117 for (int i = path.length - 1; i >= 0; i--) {
118 path[i] = node;
119
120 node = node.getParent();
121 }
122
123 return path;
124 }
125
126 /**
127 * Retrieves the reverse history of a node, starting from itself and going to
128 * its ancestors.
129 *
130 * @param node The node for which to retrieve the reverse history.
131 * @return A stream representing the reverse history of the given node.
132 */
133 default Stream<N> getReverseHistory(N node) {
134 return Stream.iterate(node, RoutingNode::hasParent, RoutingNode::getParent);
135 }
136
137 /**
138 * Creates an array to store the history of a node with the given size.
139 *
140 * @param size The size of the history array.
141 * @return An array capable of storing the history of a node.
142 */
143 N[] createHistoryArray(int size);
144
145 /**
146 * Calculates a heuristic value for a node based on its distance to target
147 * nodes.
148 *
149 * @param targets The target nodes and their distances.
150 * @param node The node for which to calculate the heuristic.
151 * @return The heuristic value for the given node.
152 */
153 long getHeuristic(Map<N, Long> targets, N node);
154
155 /**
156 * Calculates the cost of moving from the current node to the next node.
157 *
158 * @param current The current node.
159 * @param next The next node to move to.
160 * nodes.
161 * @return The cost of moving from the current node to the next node.
162 */
163 long getCost(N current, E next);
164
165 /**
166 * Iterates over the neighbors of a node and applies the provided consumer
167 * function.
168 *
169 * @param node The node for which to iterate over neighbors.
170 * @param consumer The consumer function to apply to each neighbor.
171 */
172 void forNeighbor(N node, Consumer<E> consumer);
173
174 /**
175 * Gets the closest distance from a node to a set of target nodes.
176 *
177 * @param targets The target nodes and their distances.
178 * @param node The node for which to find the closest distance.
179 * @return The closest distance from the node to any of the target nodes.
180 */
181 long getClosestDistance(Map<N, Long> targets, N node);
182
183 /**
184 * Called when progress is made during the route calculation.
185 *
186 * @param progress The progress made, represented as a percentage.
187 */
188 void onProgress(double progress, N start, Collection<N> targets);
189
190 /**
191 * Checks if a node is a target node.
192 *
193 * @param targets The target nodes and their distances.
194 * @param node The node to check.
195 * @return {@code true} if the node is a target node, {@code false} otherwise.
196 */
197 boolean isTarget(Map<N, Long> targets, N node);
198
199 /**
200 * Gets the distance from the start node to a given node.
201 *
202 * @param start The start node.
203 * @param node The node for which to calculate the distance.
204 * @return The distance from the start node to the given node.
205 */
206 long getStartDistance(N start, N node);
207}