Graph.java (10417B) download
1package osm.protobuf;
2
3import java.util.Collection;
4import java.util.HashMap;
5import java.util.HashSet;
6import java.util.Map;
7import java.util.Map.Entry;
8import java.util.NoSuchElementException;
9import java.util.Set;
10import java.util.function.Consumer;
11import java.util.stream.Collector;
12import java.util.stream.Collector.Characteristics;
13
14import osm.common.Container;
15import osm.common.ContainerCollector;
16import osm.common.Edge;
17import osm.geo.Point;
18import osm.message.Entity;
19import osm.message.Node;
20import osm.message.Way;
21import osm.routing.RoutingGraph;
22
23/**
24 * Represents a graph used for routing on OpenStreetMap data. Implements the
25 * {@link Container} and {@link RoutingGraph} interfaces.
26 */
27public class Graph implements Container<Graph, Entity>, RoutingGraph<Node, Edge> {
28 /**
29 * Constant representing the nanosecond unit.
30 */
31 public static final double NANO = 1e-9;
32
33 /**
34 * The default speed for the router, in meters per second.
35 */
36 public static final double DEFAULT_SPEED = 60 / 3.6;
37
38 /**
39 * Constant representing the additional distance range when searching for nodes.
40 */
41 public static final double DISTANCE_RANGE = 5; // adding 5km to the result
42
43 /**
44 * Constant representing the multiplier for the additional distance range.
45 */
46 public static final double DISTANCE_RANGE_MULTIPLIER = 1.25; // adding 25% to result
47
48 /**
49 * Returns a {@link Collector} that accumulates elements into a {@link Graph}.
50 *
51 * @param points The collection of points to center the graph around.
52 * @return A {@link Collector} for accumulating elements into a {@link Graph}.
53 */
54 public static Collector<Entity, ?, Graph> asCollector(Collection<Point> points) {
55 Point center = Point.center(points);
56
57 long diameter = points.stream()
58 .mapToLong(center::distanceTo)
59 .max()
60 .orElseThrow();
61
62 long range = Math.round(DISTANCE_RANGE + DISTANCE_RANGE_MULTIPLIER * diameter);
63
64 return new ContainerCollector<>(() -> new Graph(points, center, range),
65 Set.of(Characteristics.CONCURRENT, Characteristics.UNORDERED));
66 }
67
68 private final Collection<Point> points;
69 private final Point center;
70 private final long range;
71
72 public final Map<Long, Node> nodes = new HashMap<>();
73 public final Map<Long, Way> ways = new HashMap<>();
74 public final Map<Node, Set<Edge>> neighbors = new HashMap<>();
75 public final Map<Point, Node> pointNode = new HashMap<>();
76 public final Map<Point, Long> pointDistance = new HashMap<>();
77
78 /**
79 * Constructs a {@link Graph} with the specified points, center, and range.
80 *
81 * @param points The collection of points in the graph.
82 * @param center The center point of the graph.
83 * @param range The range around the center within which nodes are considered.
84 */
85 public Graph(Collection<Point> points, Point center, long range) {
86 this.points = points;
87 this.center = center;
88 this.range = range;
89 }
90
91 /**
92 * Combines this graph with another graph, updating its nodes and neighbors.
93 *
94 * @param other The other graph to combine with.
95 * @return The combined graph.
96 */
97 @Override
98 public void fold(Graph other) {
99 nodes.putAll(other.nodes);
100 for (Entry<Node, Set<Edge>> neigh : other.neighbors.entrySet())
101 neighbors.computeIfAbsent(neigh.getKey(), k -> new HashSet<>())
102 .addAll(neigh.getValue());
103 }
104
105 /**
106 * Finalizes the graph by connecting ways and determining the closest nodes to
107 * each point.
108 */
109 @Override
110 public void finish() {
111 ways.forEach((i, w) -> connectWay(w));
112
113 for (Node node : nodes.values()) {
114 if (!neighbors.containsKey(node))
115 continue;
116
117 for (Point p : points) {
118 if (!pointNode.containsKey(p) || node.distanceTo(p) < pointDistance.get(p)) {
119 pointNode.put(p, node);
120 pointDistance.put(p, node.distanceTo(p));
121 }
122 }
123 }
124
125 System.out.printf("nodes: \t\t%d\nneighbors: \t%d\n", nodes.size(), neighbors.size());
126 }
127
128 /**
129 * Connects the nodes of a way by creating edges between consecutive nodes.
130 *
131 * @param w The way to connect.
132 */
133 protected void connectWay(Way w) {
134 Node previous = null;
135
136 for (long currentID : w.children) {
137 if (!nodes.containsKey(currentID))
138 continue;
139
140 Node current = nodes.get(currentID);
141
142 if (previous != null) {
143 long dist = current.distanceTo(previous);
144
145 neighbors.computeIfAbsent(previous, k -> new HashSet<>())
146 .add(new Edge(current, dist, (double) dist / w.speedForwards));
147
148 neighbors.computeIfAbsent(current, k -> new HashSet<>())
149 .add(new Edge(previous, dist, (double) dist / w.speedBackwards));
150 }
151
152 previous = current;
153 }
154 }
155
156 /**
157 * Accumulates an entity into the graph by adding nodes and ways based on their
158 * distance to the graph center.
159 *
160 * @param element The entity to accumulate.
161 */
162 @Override
163 public void accumulate(Entity element) {
164 if (element instanceof Node node) {
165 if (node.distanceTo(center) < range)
166 nodes.put(node.getID(), node);
167 } else if (element instanceof Way way) {
168 ways.put(way.getID(), way);
169 }
170 }
171
172 /**
173 * Retrieves a node from the graph based on its point location.
174 *
175 * @param point The point location of the node to retrieve.
176 * @return The node corresponding to the specified point.
177 */
178 public Node getNode(Point point) {
179 return pointNode.get(point);
180 }
181
182 /**
183 * Retrieves a node from the graph using its ID.
184 *
185 * @param id The ID of the node to retrieve.
186 * @return The node with the specified ID.
187 * @throws NoSuchElementException If the node with the given ID is not found.
188 */
189 public Node getNode(long id) throws NoSuchElementException {
190 if (!nodes.containsKey(id))
191 throw new NoSuchElementException(String.format("node `%d` not found", id));
192
193 return nodes.get(id);
194 }
195
196 /**
197 * Calculates the cost of moving from the current node to the next node.
198 *
199 * @param current The current node.
200 * @param next The next node to move to.
201 * @return The cost of moving from the current node to the next node.
202 */
203 @Override
204 public long getCost(Node current, Edge next) {
205 double time = next.getTime()
206 + Math.abs(Point.getAngle(current.getParent(), current, next.getDestination())) / Math.PI * 30;
207 return Math.round(next.getDistance() / DEFAULT_SPEED * 0.2 + time * 0.8);
208 }
209
210 /**
211 * Gets the closest distance from a node to a set of target nodes.
212 *
213 * @param targets The target nodes and their distances.
214 * @param node The node for which to find the closest distance.
215 * @return The closest distance from the node to any of the target nodes.
216 */
217 @Override
218 public long getClosestDistance(Map<Node, Long> targets, Node node) {
219 return targets.entrySet().stream()
220 .map(e -> e.getKey().distanceTo(node) + e.getValue())
221 .min(Long::compare)
222 .orElseThrow();
223 }
224
225 /**
226 * Called when progress is made during the route calculation.
227 *
228 * @param progress The progress made, represented as a percentage.
229 * @param start The starting node.
230 * @param targets The target nodes.
231 */
232 @Override
233 public void onProgress(double progress, Node start, Collection<Node> targets) {
234 System.out.printf("%s -> %s %6.2f%% [%s>%s]\r",
235 start, targets,
236 progress * 100,
237 "=".repeat((int) Math.round(progress * 50)),
238 " ".repeat((int) Math.round((1 - progress) * 50)));
239 }
240
241 /**
242 * Checks if a node is a target node.
243 *
244 * @param targets The target nodes and their distances.
245 * @param node The node to check.
246 * @return {@code true} if the node is a target node, {@code false} otherwise.
247 */
248 @Override
249 public boolean isTarget(Map<Node, Long> targets, Node node) {
250 return targets.containsKey(node);
251 }
252
253 /**
254 * Calculates a heuristic value for a node based on its distance to target
255 * nodes.
256 *
257 * @param targets The target nodes and their distances.
258 * @param node The node for which to calculate the heuristic.
259 * @return The heuristic value for the given node.
260 */
261 @Override
262 public long getHeuristic(Map<Node, Long> targets, Node node) {
263 long dist = targets.entrySet().stream()
264 .map(e -> e.getKey().distanceTo(node) + e.getValue())
265 .min(Long::compare)
266 .orElseThrow();
267
268 return Math.round(0.5 * dist / DEFAULT_SPEED);
269 }
270
271 /**
272 * Gets the distance from the start node to a given node.
273 *
274 * @param start The start node.
275 * @param node The node for which to calculate the distance.
276 * @return The distance from the start node to the given node.
277 */
278 @Override
279 public long getStartDistance(Node start, Node node) {
280 return start.distanceTo(node);
281 }
282
283 /**
284 * Iterates over the neighbors of a node and applies the provided consumer
285 * function.
286 *
287 * @param node The node for which to iterate over neighbors.
288 * @param consumer The consumer function to apply to each neighbor.
289 */
290 @Override
291 public void forNeighbor(Node node, Consumer<Edge> consumer) {
292 // System.out.printf("%s: %s\n", node, neighbors.get(node.getID()));
293
294 if (!neighbors.containsKey(node))
295 return;
296
297 neighbors.get(node).forEach(n -> {
298 consumer.accept(n);
299 });
300 }
301
302 /**
303 * Creates an array to store the history of a node with the given size.
304 *
305 * @param size The size of the history array.
306 * @return An array capable of storing the history of a node.
307 */
308 @Override
309 public Node[] createHistoryArray(int size) {
310 return new Node[size];
311 }
312}