source: josm/trunk/src/org/openstreetmap/josm/data/osm/NodeGraph.java@ 19064

Last change on this file since 19064 was 19064, checked in by GerdP, 3 weeks ago

see #21881 Add a check for loops in directional waterways

  • fix @since xxx
  • adapt unit test
  • Property svn:eol-style set to native
File size: 15.4 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.data.osm;
3
4import java.util.ArrayDeque;
5import java.util.ArrayList;
6import java.util.Collection;
7import java.util.Collections;
8import java.util.Comparator;
9import java.util.Deque;
10import java.util.HashMap;
11import java.util.HashSet;
12import java.util.LinkedHashMap;
13import java.util.LinkedHashSet;
14import java.util.List;
15import java.util.Map;
16import java.util.Map.Entry;
17import java.util.Optional;
18import java.util.Set;
19import java.util.TreeMap;
20import java.util.stream.Collectors;
21import java.util.stream.Stream;
22
23import org.openstreetmap.josm.tools.Pair;
24import org.openstreetmap.josm.tools.Utils;
25
26/**
27 * A directed or undirected graph of nodes. Nodes are connected via edges represented by NodePair instances.
28 *
29 * @since 12463 (extracted from CombineWayAction)
30 */
31public class NodeGraph {
32
33 /**
34 * Builds a list of pair of nodes from the given way.
35 * @param way way
36 * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order.
37 * if {@code false} each pair of nodes will occur twice (the pair and its inverse copy)
38 * @return a list of pair of nodes from the given way
39 */
40 public static List<NodePair> buildNodePairs(Way way, boolean directed) {
41 List<NodePair> pairs = new ArrayList<>();
42 for (Pair<Node, Node> pair : way.getNodePairs(false)) {
43 pairs.add(new NodePair(pair));
44 if (!directed) {
45 pairs.add(new NodePair(pair).swap());
46 }
47 }
48 return pairs;
49 }
50
51 /**
52 * Builds a list of pair of nodes from the given ways.
53 * @param ways ways
54 * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order.<br>
55 * if {@code false} each pair of nodes will occur twice (the pair and its inverse copy)
56 * @return a list of pair of nodes from the given ways
57 */
58 public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
59 List<NodePair> pairs = new ArrayList<>();
60 for (Way w : ways) {
61 pairs.addAll(buildNodePairs(w, directed));
62 }
63 return pairs;
64 }
65
66 /**
67 * Builds a new list of pair nodes without the duplicated pairs (including inverse copies).
68 * @param pairs existing list of pairs
69 * @return a new list of pair nodes without the duplicated pairs
70 */
71 public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
72 List<NodePair> cleaned = new ArrayList<>();
73 for (NodePair p : pairs) {
74 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
75 cleaned.add(p);
76 }
77 }
78 return cleaned;
79 }
80
81 /**
82 * Create a directed graph from the given node pairs.
83 * @param pairs Node pairs to build the graph from
84 * @return node graph structure
85 */
86 public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
87 NodeGraph graph = new NodeGraph();
88 for (NodePair pair : pairs) {
89 graph.add(pair);
90 }
91 return graph;
92 }
93
94 /**
95 * Create a directed graph from the given ways.
96 * @param ways ways to build the graph from
97 * @return node graph structure
98 */
99 public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
100 NodeGraph graph = new NodeGraph();
101 for (Way w : ways) {
102 graph.add(buildNodePairs(w, true));
103 }
104 return graph;
105 }
106
107 /**
108 * Create an undirected graph from the given node pairs.
109 * @param pairs Node pairs to build the graph from
110 * @return node graph structure
111 */
112 public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
113 NodeGraph graph = new NodeGraph();
114 for (NodePair pair : pairs) {
115 graph.add(pair);
116 graph.add(pair.swap());
117 }
118 return graph;
119 }
120
121 /**
122 * Create an undirected graph from the given ways, but prevent reversing of all
123 * non-new ways by fixing one direction.
124 * @param ways Ways to build the graph from
125 * @return node graph structure
126 * @since 8181
127 */
128 public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
129 NodeGraph graph = new NodeGraph();
130 for (Way w : ways) {
131 graph.add(buildNodePairs(w, false));
132 }
133 return graph;
134 }
135
136 /**
137 * Create a nearly undirected graph from the given ways, but prevent reversing of all
138 * non-new ways by fixing one direction.
139 * The first new way gives the direction of the graph.
140 * @param ways Ways to build the graph from
141 * @return node graph structure
142 */
143 public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways) {
144 boolean dir = true;
145 NodeGraph graph = new NodeGraph();
146 for (Way w : ways) {
147 if (!w.isNew()) {
148 /* let the first non-new way give the direction (see #5880) */
149 graph.add(buildNodePairs(w, dir));
150 dir = false;
151 } else {
152 graph.add(buildNodePairs(w, false));
153 }
154 }
155 return graph;
156 }
157
158 private final Set<NodePair> edges;
159 private int numUndirectedEdges;
160 /** The number of edges that were added. */
161 private int addedEdges;
162 private final Map<Node, List<NodePair>> successors = new LinkedHashMap<>();
163 private final Map<Node, List<NodePair>> predecessors = new LinkedHashMap<>();
164
165 /**
166 * Constructs a lookup table from the existing edges in the graph to enable efficient querying.
167 * This method creates a map where each node is associated with a list of nodes that are directly connected to it.
168 *
169 * @return A map representing the graph structure, where nodes are keys, and values are their direct successors.
170 * @since 19062
171 */
172 public Map<Node, List<Node>> createMap() {
173 final Map<Node, List<Node>> result = new HashMap<>(Utils.hashMapInitialCapacity(edges.size()));
174
175 for (NodePair edge : edges) {
176 result.computeIfAbsent(edge.getA(), k -> new ArrayList<>()).add(edge.getB());
177 }
178
179 return result;
180 }
181
182 /**
183 * See {@link #prepare()}
184 */
185 protected void rememberSuccessor(NodePair pair) {
186 List<NodePair> l = successors.computeIfAbsent(pair.getA(), k -> new ArrayList<>());
187 if (!l.contains(pair)) {
188 l.add(pair);
189 }
190 }
191
192 /**
193 * See {@link #prepare()}
194 */
195 protected void rememberPredecessors(NodePair pair) {
196 List<NodePair> l = predecessors.computeIfAbsent(pair.getB(), k -> new ArrayList<>());
197 if (!l.contains(pair)) {
198 l.add(pair);
199 }
200 }
201
202 /**
203 * Replies true if {@code n} is a terminal node of the graph. Internal variables should be initialized first.
204 * @param n Node to check
205 * @return {@code true} if it is a terminal node
206 * @see #prepare()
207 */
208 protected boolean isTerminalNode(Node n) {
209 if (successors.get(n) == null) return false;
210 if (successors.get(n).size() != 1) return false;
211 if (predecessors.get(n) == null) return true;
212 if (predecessors.get(n).size() == 1) {
213 NodePair p1 = successors.get(n).get(0);
214 NodePair p2 = predecessors.get(n).get(0);
215 return p1.equals(p2.swap());
216 }
217 return false;
218 }
219
220 protected void prepare() {
221 Set<NodePair> undirectedEdges = new LinkedHashSet<>();
222 successors.clear();
223 predecessors.clear();
224
225 for (NodePair pair : edges) {
226 if (!undirectedEdges.contains(pair) && !undirectedEdges.contains(pair.swap())) {
227 undirectedEdges.add(pair);
228 }
229 rememberSuccessor(pair);
230 rememberPredecessors(pair);
231 }
232 numUndirectedEdges = undirectedEdges.size();
233 }
234
235 /**
236 * Constructs a new {@code NodeGraph}.
237 */
238 public NodeGraph() {
239 edges = new LinkedHashSet<>();
240 }
241
242 /**
243 * Add a node pair.
244 * @param pair node pair
245 */
246 public void add(NodePair pair) {
247 addedEdges++;
248 edges.add(pair);
249 }
250
251 /**
252 * Add a list of node pairs.
253 * @param pairs collection of node pairs
254 */
255 public void add(Iterable<NodePair> pairs) {
256 for (NodePair pair : pairs) {
257 add(pair);
258 }
259 }
260
261 /**
262 * Return the edges containing the node pairs of the graph.
263 * @return the edges containing the node pairs of the graph
264 */
265 public Collection<NodePair> getEdges() {
266 return Collections.unmodifiableSet(edges);
267 }
268
269 /**
270 * Return the terminal nodes of the graph.
271 * @return the terminal nodes of the graph
272 */
273 protected Set<Node> getTerminalNodes() {
274 return getNodes().stream().filter(this::isTerminalNode).collect(Collectors.toCollection(LinkedHashSet::new));
275 }
276
277 private List<NodePair> getConnectedPairs(Node node) {
278 List<NodePair> connected = new ArrayList<>();
279 connected.addAll(Optional.ofNullable(successors.get(node)).orElseGet(Collections::emptyList));
280 connected.addAll(Optional.ofNullable(predecessors.get(node)).orElseGet(Collections::emptyList));
281 return connected;
282 }
283
284 protected List<NodePair> getOutboundPairs(NodePair pair) {
285 return getOutboundPairs(pair.getB());
286 }
287
288 protected List<NodePair> getOutboundPairs(Node node) {
289 return Optional.ofNullable(successors.get(node)).orElseGet(Collections::emptyList);
290 }
291
292 /**
293 * Return the graph's nodes.
294 * @return the graph's nodes
295 */
296 public Collection<Node> getNodes() {
297 Set<Node> nodes = new LinkedHashSet<>(2 * edges.size());
298 for (NodePair pair : edges) {
299 nodes.add(pair.getA());
300 nodes.add(pair.getB());
301 }
302 return nodes;
303 }
304
305 protected boolean isSpanningWay(Collection<NodePair> way) {
306 return numUndirectedEdges == way.size();
307 }
308
309 protected List<Node> buildPathFromNodePairs(Deque<NodePair> path) {
310 return Stream.concat(path.stream().map(NodePair::getA), Stream.of(path.peekLast().getB()))
311 .collect(Collectors.toList());
312 }
313
314 /**
315 * Tries to find a spanning path starting from node {@code startNode}.
316 * <p>
317 * Traverses the path in depth-first order.
318 *
319 * @param startNode the start node
320 * @return the spanning path; empty list if no path is found
321 */
322 protected List<Node> buildSpanningPath(Node startNode) {
323 if (startNode != null) {
324 Deque<NodePair> path = new ArrayDeque<>();
325 Set<NodePair> dupCheck = new HashSet<>();
326 Deque<NodePair> nextPairs = new ArrayDeque<>(getOutboundPairs(startNode));
327 while (!nextPairs.isEmpty()) {
328 NodePair cur = nextPairs.removeLast();
329 if (!dupCheck.contains(cur) && !dupCheck.contains(cur.swap())) {
330 while (!path.isEmpty() && !path.peekLast().isPredecessorOf(cur)) {
331 dupCheck.remove(path.removeLast());
332 }
333 path.addLast(cur);
334 dupCheck.add(cur);
335 if (isSpanningWay(path))
336 return buildPathFromNodePairs(path);
337 nextPairs.addAll(getOutboundPairs(path.peekLast()));
338 }
339 }
340 }
341 return Collections.emptyList();
342 }
343
344 /**
345 * Tries to find a path through the graph which visits each edge (i.e.
346 * the segment of a way) exactly once.<p>
347 * <b>Note that duplicated edges are removed first!</b>
348 *
349 * @return the path; {@code null}, if no path was found
350 */
351 public List<Node> buildSpanningPath() {
352 prepare();
353 if (numUndirectedEdges > 0 && isConnected()) {
354 // Try to find a path from each "terminal node", i.e. from a
355 // node which is connected by exactly one undirected edge (or
356 // two directed edges in the opposite direction) to the graph. A
357 // graph built up from way segments is likely to include such
358 // nodes, unless the edges build one or more closed rings.
359 // We order the nodes to start with the best candidates, but
360 // it might take very long if there is no valid path as we iterate over all nodes
361 // to find out.
362 Set<Node> nodes = getTerminalNodes();
363 nodes = nodes.isEmpty() ? getMostFrequentVisitedNodesFirst() : nodes;
364 return nodes.stream()
365 .map(this::buildSpanningPath)
366 .filter(path -> !path.isEmpty())
367 .findFirst().orElse(null);
368 }
369 return null;
370 }
371
372 /**
373 * Tries to find a path through the graph which visits each edge (i.e.
374 * the segment of a way) exactly once. If the graph was build from overlapping
375 * ways duplicate edges were removed already. This method will return null if
376 * any duplicated edge was removed.
377 *
378 * @return List of nodes that build the path; an empty list if no path or duplicated edges were found
379 * @since 15573 (return value not null)
380 */
381 public List<Node> buildSpanningPathNoRemove() {
382 List<Node> path = null;
383 if (edges.size() == addedEdges)
384 path = buildSpanningPath();
385 return path == null ? Collections.emptyList() : path;
386 }
387
388 /**
389 * Find out if the graph is connected.
390 * @return {@code true} if it is connected
391 */
392 private boolean isConnected() {
393 Collection<Node> nodes = getNodes();
394 if (nodes.isEmpty())
395 return false;
396 Deque<Node> toVisit = new ArrayDeque<>();
397 HashSet<Node> visited = new HashSet<>();
398 toVisit.add(nodes.iterator().next());
399 while (!toVisit.isEmpty()) {
400 Node n = toVisit.pop();
401 if (!visited.contains(n)) {
402 for (NodePair pair : getConnectedPairs(n)) {
403 if (n != pair.getA())
404 toVisit.addLast(pair.getA());
405 if (n != pair.getB())
406 toVisit.addLast(pair.getB());
407 }
408 visited.add(n);
409 }
410 }
411 return nodes.size() == visited.size();
412 }
413
414 /**
415 * Sort the nodes by number of appearances in the edges.
416 * @return set of nodes which can be start nodes in a spanning way
417 */
418 private Set<Node> getMostFrequentVisitedNodesFirst() {
419 if (edges.isEmpty())
420 return Collections.emptySet();
421 // count the appearance of nodes in edges
422 Map<Node, Integer> counters = new HashMap<>();
423 for (NodePair pair : edges) {
424 Integer c = counters.get(pair.getA());
425 counters.put(pair.getA(), c == null ? 1 : c + 1);
426 c = counters.get(pair.getB());
427 counters.put(pair.getB(), c == null ? 1 : c + 1);
428 }
429 // group by counters
430 TreeMap<Integer, Set<Node>> sortedMap = new TreeMap<>(Comparator.reverseOrder());
431 for (Entry<Node, Integer> e : counters.entrySet()) {
432 sortedMap.computeIfAbsent(e.getValue(), x -> new LinkedHashSet<>()).add(e.getKey());
433 }
434 LinkedHashSet<Node> result = new LinkedHashSet<>();
435 for (Entry<Integer, Set<Node>> e : sortedMap.entrySet()) {
436 if (e.getKey() > 4 || result.isEmpty()) {
437 result.addAll(e.getValue());
438 }
439 }
440 return Collections.unmodifiableSet(result);
441 }
442
443}
Note: See TracBrowser for help on using the repository browser.