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