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; 020 021import org.openstreetmap.josm.tools.Pair; 022 023/** 024 * A directed or undirected graph of nodes. 025 * @since 12463 (extracted from CombineWayAction) 026 */ 027public class NodeGraph { 028 029 /** 030 * Builds a list of pair of nodes from the given way. 031 * @param way way 032 * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order. 033 * if {@code false} each pair of nodes will occur twice (the pair and its inversed copy) 034 * @return a list of pair of nodes from the given way 035 */ 036 public static List<NodePair> buildNodePairs(Way way, boolean directed) { 037 List<NodePair> pairs = new ArrayList<>(); 038 for (Pair<Node, Node> pair: way.getNodePairs(false /* don't sort */)) { 039 pairs.add(new NodePair(pair)); 040 if (!directed) { 041 pairs.add(new NodePair(pair).swap()); 042 } 043 } 044 return pairs; 045 } 046 047 /** 048 * Builds a list of pair of nodes from the given ways. 049 * @param ways ways 050 * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order. 051 * if {@code false} each pair of nodes will occur twice (the pair and its inversed copy) 052 * @return a list of pair of nodes from the given ways 053 */ 054 public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) { 055 List<NodePair> pairs = new ArrayList<>(); 056 for (Way w: ways) { 057 pairs.addAll(buildNodePairs(w, directed)); 058 } 059 return pairs; 060 } 061 062 /** 063 * Builds a new list of pair nodes without the duplicated pairs (including inversed copies). 064 * @param pairs existing list of pairs 065 * @return a new list of pair nodes without the duplicated pairs 066 */ 067 public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) { 068 List<NodePair> cleaned = new ArrayList<>(); 069 for (NodePair p: pairs) { 070 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) { 071 cleaned.add(p); 072 } 073 } 074 return cleaned; 075 } 076 077 public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) { 078 NodeGraph graph = new NodeGraph(); 079 for (NodePair pair: pairs) { 080 graph.add(pair); 081 } 082 return graph; 083 } 084 085 public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) { 086 NodeGraph graph = new NodeGraph(); 087 for (Way w: ways) { 088 graph.add(buildNodePairs(w, true /* directed */)); 089 } 090 return graph; 091 } 092 093 /** 094 * Create an undirected graph from the given node pairs. 095 * @param pairs Node pairs to build the graph from 096 * @return node graph structure 097 */ 098 public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) { 099 NodeGraph graph = new NodeGraph(); 100 for (NodePair pair: pairs) { 101 graph.add(pair); 102 graph.add(pair.swap()); 103 } 104 return graph; 105 } 106 107 /** 108 * Create an undirected graph from the given ways, but prevent reversing of all 109 * non-new ways by fix one direction. 110 * @param ways Ways to build the graph from 111 * @return node graph structure 112 * @since 8181 113 */ 114 public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) { 115 NodeGraph graph = new NodeGraph(); 116 for (Way w: ways) { 117 graph.add(buildNodePairs(w, false /* undirected */)); 118 } 119 return graph; 120 } 121 122 public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways) { 123 boolean dir = true; 124 NodeGraph graph = new NodeGraph(); 125 for (Way w: ways) { 126 if (!w.isNew()) { 127 /* let the first non-new way give the direction (see #5880) */ 128 graph.add(buildNodePairs(w, dir)); 129 dir = false; 130 } else { 131 graph.add(buildNodePairs(w, false /* undirected */)); 132 } 133 } 134 return graph; 135 } 136 137 private final Set<NodePair> edges; 138 private int numUndirectedEges; 139 /** counts the number of edges that were added */ 140 private int addedEdges; 141 private final Map<Node, List<NodePair>> successors = new LinkedHashMap<>(); 142 private final Map<Node, List<NodePair>> predecessors = new LinkedHashMap<>(); 143 144 protected void rememberSuccessor(NodePair pair) { 145 List<NodePair> l = successors.computeIfAbsent(pair.getA(), k -> new ArrayList<>()); 146 if (!l.contains(pair)) { 147 l.add(pair); 148 } 149 } 150 151 protected void rememberPredecessors(NodePair pair) { 152 List<NodePair> l = predecessors.computeIfAbsent(pair.getB(), k -> new ArrayList<>()); 153 if (!l.contains(pair)) { 154 l.add(pair); 155 } 156 } 157 158 protected boolean isTerminalNode(Node n) { 159 if (successors.get(n) == null) return false; 160 if (successors.get(n).size() != 1) return false; 161 if (predecessors.get(n) == null) return true; 162 if (predecessors.get(n).size() == 1) { 163 NodePair p1 = successors.get(n).get(0); 164 NodePair p2 = predecessors.get(n).get(0); 165 return p1.equals(p2.swap()); 166 } 167 return false; 168 } 169 170 protected void prepare() { 171 Set<NodePair> undirectedEdges = new LinkedHashSet<>(); 172 successors.clear(); 173 predecessors.clear(); 174 175 for (NodePair pair: edges) { 176 if (!undirectedEdges.contains(pair) && !undirectedEdges.contains(pair.swap())) { 177 undirectedEdges.add(pair); 178 } 179 rememberSuccessor(pair); 180 rememberPredecessors(pair); 181 } 182 numUndirectedEges = undirectedEdges.size(); 183 } 184 185 /** 186 * Constructs a new {@code NodeGraph}. 187 */ 188 public NodeGraph() { 189 edges = new LinkedHashSet<>(); 190 } 191 192 /** 193 * Add a node pair. 194 * @param pair node pair 195 */ 196 public void add(NodePair pair) { 197 addedEdges++; 198 edges.add(pair); 199 } 200 201 /** 202 * Add a list of node pairs. 203 * @param pairs list of node pairs 204 */ 205 public void add(Collection<NodePair> pairs) { 206 for (NodePair pair: pairs) { 207 add(pair); 208 } 209 } 210 211 protected Set<Node> getTerminalNodes() { 212 Set<Node> ret = new LinkedHashSet<>(); 213 for (Node n: getNodes()) { 214 if (isTerminalNode(n)) { 215 ret.add(n); 216 } 217 } 218 return ret; 219 } 220 221 private List<NodePair> getConnectedPairs(Node node) { 222 List<NodePair> connected = new ArrayList<>(); 223 connected.addAll(Optional.ofNullable(successors.get(node)).orElseGet(Collections::emptyList)); 224 connected.addAll(Optional.ofNullable(predecessors.get(node)).orElseGet(Collections::emptyList)); 225 return connected; 226 } 227 228 protected List<NodePair> getOutboundPairs(NodePair pair) { 229 return getOutboundPairs(pair.getB()); 230 } 231 232 protected List<NodePair> getOutboundPairs(Node node) { 233 return Optional.ofNullable(successors.get(node)).orElseGet(Collections::emptyList); 234 } 235 236 protected Set<Node> getNodes() { 237 Set<Node> nodes = new LinkedHashSet<>(2 * edges.size()); 238 for (NodePair pair: edges) { 239 nodes.add(pair.getA()); 240 nodes.add(pair.getB()); 241 } 242 return nodes; 243 } 244 245 protected boolean isSpanningWay(Collection<NodePair> way) { 246 return numUndirectedEges == way.size(); 247 } 248 249 protected List<Node> buildPathFromNodePairs(Deque<NodePair> path) { 250 List<Node> ret = new ArrayList<>(path.size() + 1); 251 for (NodePair pair : path) { 252 ret.add(pair.getA()); 253 } 254 ret.add(path.peekLast().getB()); 255 return ret; 256 } 257 258 /** 259 * Tries to find a spanning path starting from node <code>startNode</code>. 260 * 261 * Traverses the path in depth-first order. 262 * 263 * @param startNode the start node 264 * @return the spanning path; empty list if no path is found 265 */ 266 protected List<Node> buildSpanningPath(Node startNode) { 267 if (startNode != null) { 268 Deque<NodePair> path = new ArrayDeque<>(); 269 Set<NodePair> dupCheck = new HashSet<>(); 270 Deque<NodePair> nextPairs = new ArrayDeque<>(); 271 nextPairs.addAll(getOutboundPairs(startNode)); 272 while (!nextPairs.isEmpty()) { 273 NodePair cur = nextPairs.removeLast(); 274 if (!dupCheck.contains(cur) && !dupCheck.contains(cur.swap())) { 275 while (!path.isEmpty() && !path.peekLast().isPredecessorOf(cur)) { 276 dupCheck.remove(path.removeLast()); 277 } 278 path.addLast(cur); 279 dupCheck.add(cur); 280 if (isSpanningWay(path)) 281 return buildPathFromNodePairs(path); 282 nextPairs.addAll(getOutboundPairs(path.peekLast())); 283 } 284 } 285 } 286 return Collections.emptyList(); 287 } 288 289 /** 290 * Tries to find a path through the graph which visits each edge (i.e. 291 * the segment of a way) exactly once. 292 * <p><b>Note that duplicated edges are removed first!</b> 293 * 294 * @return the path; null, if no path was found 295 */ 296 public List<Node> buildSpanningPath() { 297 prepare(); 298 if (numUndirectedEges > 0 && isConnected()) { 299 // try to find a path from each "terminal node", i.e. from a 300 // node which is connected by exactly one undirected edges (or 301 // two directed edges in opposite direction) to the graph. A 302 // graph built up from way segments is likely to include such 303 // nodes, unless the edges build one or more closed rings. 304 // We order the nodes to start with the best candidates, but 305 // it might take very long if there is no valid path as we iterate over all nodes 306 // to find out. 307 Set<Node> nodes = getTerminalNodes(); 308 nodes = nodes.isEmpty() ? getMostFrequentVisitedNodesFirst() : nodes; 309 for (Node n : nodes) { 310 List<Node> path = buildSpanningPath(n); 311 if (!path.isEmpty()) 312 return path; 313 } 314 } 315 return null; 316 } 317 318 /** 319 * Tries to find a path through the graph which visits each edge (i.e. 320 * the segment of a way) exactly once. If the graph was build from overlapping 321 * ways duplicate edges were removed already. This method will return null if 322 * any duplicated edge was removed. 323 * 324 * @return List of nodes that build the path; an empty list if no path or duplicated edges were found 325 * @since 15573 (return value not null) 326 */ 327 public List<Node> buildSpanningPathNoRemove() { 328 List<Node> path = null; 329 if (edges.size() == addedEdges) 330 path = buildSpanningPath(); 331 return path == null ? Collections.emptyList() : path; 332 } 333 334 /** 335 * Find out if the graph is connected. 336 * @return true if it is connected. 337 */ 338 private boolean isConnected() { 339 Set<Node> nodes = getNodes(); 340 if (nodes.isEmpty()) 341 return false; 342 Deque<Node> toVisit = new ArrayDeque<>(); 343 HashSet<Node> visited = new HashSet<>(); 344 toVisit.add(nodes.iterator().next()); 345 while (!toVisit.isEmpty()) { 346 Node n = toVisit.pop(); 347 if (!visited.contains(n)) { 348 for (NodePair pair : getConnectedPairs(n)) { 349 if (n != pair.getA()) 350 toVisit.addLast(pair.getA()); 351 if (n != pair.getB()) 352 toVisit.addLast(pair.getB()); 353 } 354 visited.add(n); 355 } 356 } 357 return nodes.size() == visited.size(); 358 } 359 360 /** 361 * Sort the nodes by number of appearances in the edges. 362 * @return set of nodes which can be start nodes in a spanning way. 363 */ 364 private Set<Node> getMostFrequentVisitedNodesFirst() { 365 if (edges.isEmpty()) 366 return Collections.emptySet(); 367 // count appearance of nodes in edges 368 Map<Node, Integer> counters = new HashMap<>(); 369 for (NodePair pair : edges) { 370 Integer c = counters.get(pair.getA()); 371 counters.put(pair.getA(), c == null ? 1 : c + 1); 372 c = counters.get(pair.getB()); 373 counters.put(pair.getB(), c == null ? 1 : c + 1); 374 } 375 // group by counters 376 TreeMap<Integer, Set<Node>> sortedMap = new TreeMap<>(Comparator.reverseOrder()); 377 for (Entry<Node, Integer> e : counters.entrySet()) { 378 sortedMap.computeIfAbsent(e.getValue(), LinkedHashSet::new).add(e.getKey()); 379 } 380 LinkedHashSet<Node> result = new LinkedHashSet<>(); 381 for (Entry<Integer, Set<Node>> e : sortedMap.entrySet()) { 382 if (e.getKey() > 4 || result.isEmpty()) { 383 result.addAll(e.getValue()); 384 } 385 } 386 return result; 387 } 388 389}