001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.data.osm; 003 004import java.util.ArrayDeque; 005import java.util.ArrayList; 006import java.util.Collection; 007import java.util.Collections; 008import java.util.Comparator; 009import java.util.Deque; 010import java.util.HashMap; 011import java.util.HashSet; 012import java.util.LinkedHashMap; 013import java.util.LinkedHashSet; 014import java.util.List; 015import java.util.Map; 016import java.util.Map.Entry; 017import java.util.Optional; 018import java.util.Set; 019import java.util.TreeMap; 020import java.util.stream.Collectors; 021import java.util.stream.Stream; 022 023import org.openstreetmap.josm.tools.Pair; 024import org.openstreetmap.josm.tools.Utils; 025 026/** 027 * A directed or undirected graph of nodes. Nodes are connected via edges represented by NodePair instances. 028 * 029 * @since 12463 (extracted from CombineWayAction) 030 */ 031public class NodeGraph { 032 033 /** 034 * Builds a list of pair of nodes from the given way. 035 * @param way way 036 * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order. 037 * if {@code false} each pair of nodes will occur twice (the pair and its inverse copy) 038 * @return a list of pair of nodes from the given way 039 */ 040 public static List<NodePair> buildNodePairs(Way way, boolean directed) { 041 List<NodePair> pairs = new ArrayList<>(); 042 for (Pair<Node, Node> pair : way.getNodePairs(false)) { 043 pairs.add(new NodePair(pair)); 044 if (!directed) { 045 pairs.add(new NodePair(pair).swap()); 046 } 047 } 048 return pairs; 049 } 050 051 /** 052 * Builds a list of pair of nodes from the given ways. 053 * @param ways ways 054 * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order.<br> 055 * if {@code false} each pair of nodes will occur twice (the pair and its inverse copy) 056 * @return a list of pair of nodes from the given ways 057 */ 058 public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) { 059 List<NodePair> pairs = new ArrayList<>(); 060 for (Way w : ways) { 061 pairs.addAll(buildNodePairs(w, directed)); 062 } 063 return pairs; 064 } 065 066 /** 067 * Builds a new list of pair nodes without the duplicated pairs (including inverse copies). 068 * @param pairs existing list of pairs 069 * @return a new list of pair nodes without the duplicated pairs 070 */ 071 public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) { 072 List<NodePair> cleaned = new ArrayList<>(); 073 for (NodePair p : pairs) { 074 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) { 075 cleaned.add(p); 076 } 077 } 078 return cleaned; 079 } 080 081 /** 082 * Create a directed graph from the given node pairs. 083 * @param pairs Node pairs to build the graph from 084 * @return node graph structure 085 */ 086 public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) { 087 NodeGraph graph = new NodeGraph(); 088 for (NodePair pair : pairs) { 089 graph.add(pair); 090 } 091 return graph; 092 } 093 094 /** 095 * Create a directed graph from the given ways. 096 * @param ways ways to build the graph from 097 * @return node graph structure 098 */ 099 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}