001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.data.osm; 003 004import java.util.ArrayList; 005import java.util.Collection; 006import java.util.Collections; 007import java.util.LinkedHashMap; 008import java.util.LinkedHashSet; 009import java.util.LinkedList; 010import java.util.List; 011import java.util.Map; 012import java.util.Optional; 013import java.util.Set; 014import java.util.Stack; 015 016import org.openstreetmap.josm.tools.Pair; 017 018/** 019 * A directed or undirected graph of nodes. 020 * @since 12463 (extracted from CombineWayAction) 021 */ 022public class NodeGraph { 023 024 /** 025 * Builds a list of pair of nodes from the given way. 026 * @param way way 027 * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order. 028 * if {@code false} each pair of nodes will occur twice (the pair and its inversed copy) 029 * @return a list of pair of nodes from the given way 030 */ 031 public static List<NodePair> buildNodePairs(Way way, boolean directed) { 032 List<NodePair> pairs = new ArrayList<>(); 033 for (Pair<Node, Node> pair: way.getNodePairs(false /* don't sort */)) { 034 pairs.add(new NodePair(pair)); 035 if (!directed) { 036 pairs.add(new NodePair(pair).swap()); 037 } 038 } 039 return pairs; 040 } 041 042 /** 043 * Builds a list of pair of nodes from the given ways. 044 * @param ways ways 045 * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order. 046 * if {@code false} each pair of nodes will occur twice (the pair and its inversed copy) 047 * @return a list of pair of nodes from the given ways 048 */ 049 public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) { 050 List<NodePair> pairs = new ArrayList<>(); 051 for (Way w: ways) { 052 pairs.addAll(buildNodePairs(w, directed)); 053 } 054 return pairs; 055 } 056 057 /** 058 * Builds a new list of pair nodes without the duplicated pairs (including inversed copies). 059 * @param pairs existing list of pairs 060 * @return a new list of pair nodes without the duplicated pairs 061 */ 062 public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) { 063 List<NodePair> cleaned = new ArrayList<>(); 064 for (NodePair p: pairs) { 065 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) { 066 cleaned.add(p); 067 } 068 } 069 return cleaned; 070 } 071 072 public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) { 073 NodeGraph graph = new NodeGraph(); 074 for (NodePair pair: pairs) { 075 graph.add(pair); 076 } 077 return graph; 078 } 079 080 public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) { 081 NodeGraph graph = new NodeGraph(); 082 for (Way w: ways) { 083 graph.add(buildNodePairs(w, true /* directed */)); 084 } 085 return graph; 086 } 087 088 /** 089 * Create an undirected graph from the given node pairs. 090 * @param pairs Node pairs to build the graph from 091 * @return node graph structure 092 */ 093 public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) { 094 NodeGraph graph = new NodeGraph(); 095 for (NodePair pair: pairs) { 096 graph.add(pair); 097 graph.add(pair.swap()); 098 } 099 return graph; 100 } 101 102 /** 103 * Create an undirected graph from the given ways, but prevent reversing of all 104 * non-new ways by fix one direction. 105 * @param ways Ways to build the graph from 106 * @return node graph structure 107 * @since 8181 108 */ 109 public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) { 110 NodeGraph graph = new NodeGraph(); 111 for (Way w: ways) { 112 graph.add(buildNodePairs(w, false /* undirected */)); 113 } 114 return graph; 115 } 116 117 public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways) { 118 boolean dir = true; 119 NodeGraph graph = new NodeGraph(); 120 for (Way w: ways) { 121 if (!w.isNew()) { 122 /* let the first non-new way give the direction (see #5880) */ 123 graph.add(buildNodePairs(w, dir)); 124 dir = false; 125 } else { 126 graph.add(buildNodePairs(w, false /* undirected */)); 127 } 128 } 129 return graph; 130 } 131 132 private final Set<NodePair> edges; 133 private int numUndirectedEges; 134 private final Map<Node, List<NodePair>> successors = new LinkedHashMap<>(); 135 private final Map<Node, List<NodePair>> predecessors = new LinkedHashMap<>(); 136 137 protected void rememberSuccessor(NodePair pair) { 138 if (successors.containsKey(pair.getA())) { 139 if (!successors.get(pair.getA()).contains(pair)) { 140 successors.get(pair.getA()).add(pair); 141 } 142 } else { 143 List<NodePair> l = new ArrayList<>(); 144 l.add(pair); 145 successors.put(pair.getA(), l); 146 } 147 } 148 149 protected void rememberPredecessors(NodePair pair) { 150 if (predecessors.containsKey(pair.getB())) { 151 if (!predecessors.get(pair.getB()).contains(pair)) { 152 predecessors.get(pair.getB()).add(pair); 153 } 154 } else { 155 List<NodePair> l = new ArrayList<>(); 156 l.add(pair); 157 predecessors.put(pair.getB(), l); 158 } 159 } 160 161 protected boolean isTerminalNode(Node n) { 162 if (successors.get(n) == null) return false; 163 if (successors.get(n).size() != 1) return false; 164 if (predecessors.get(n) == null) return true; 165 if (predecessors.get(n).size() == 1) { 166 NodePair p1 = successors.get(n).get(0); 167 NodePair p2 = predecessors.get(n).get(0); 168 return p1.equals(p2.swap()); 169 } 170 return false; 171 } 172 173 protected void prepare() { 174 Set<NodePair> undirectedEdges = new LinkedHashSet<>(); 175 successors.clear(); 176 predecessors.clear(); 177 178 for (NodePair pair: edges) { 179 if (!undirectedEdges.contains(pair) && !undirectedEdges.contains(pair.swap())) { 180 undirectedEdges.add(pair); 181 } 182 rememberSuccessor(pair); 183 rememberPredecessors(pair); 184 } 185 numUndirectedEges = undirectedEdges.size(); 186 } 187 188 /** 189 * Constructs a new {@code NodeGraph}. 190 */ 191 public NodeGraph() { 192 edges = new LinkedHashSet<>(); 193 } 194 195 /** 196 * Add a node pair. 197 * @param pair node pair 198 */ 199 public void add(NodePair pair) { 200 if (!edges.contains(pair)) { 201 edges.add(pair); 202 } 203 } 204 205 /** 206 * Add a list of node pairs. 207 * @param pairs list of node pairs 208 */ 209 public void add(Collection<NodePair> pairs) { 210 for (NodePair pair: pairs) { 211 add(pair); 212 } 213 } 214 215 protected Set<Node> getTerminalNodes() { 216 Set<Node> ret = new LinkedHashSet<>(); 217 for (Node n: getNodes()) { 218 if (isTerminalNode(n)) { 219 ret.add(n); 220 } 221 } 222 return ret; 223 } 224 225 protected List<NodePair> getOutboundPairs(NodePair pair) { 226 return getOutboundPairs(pair.getB()); 227 } 228 229 protected List<NodePair> getOutboundPairs(Node node) { 230 return Optional.ofNullable(successors.get(node)).orElseGet(Collections::emptyList); 231 } 232 233 protected Set<Node> getNodes() { 234 Set<Node> nodes = new LinkedHashSet<>(2 * edges.size()); 235 for (NodePair pair: edges) { 236 nodes.add(pair.getA()); 237 nodes.add(pair.getB()); 238 } 239 return nodes; 240 } 241 242 protected boolean isSpanningWay(Stack<NodePair> way) { 243 return numUndirectedEges == way.size(); 244 } 245 246 protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) { 247 List<Node> ret = new LinkedList<>(); 248 for (NodePair pair: path) { 249 ret.add(pair.getA()); 250 } 251 ret.add(path.peek().getB()); 252 return ret; 253 } 254 255 /** 256 * Tries to find a spanning path starting from node <code>startNode</code>. 257 * 258 * Traverses the path in depth-first order. 259 * 260 * @param startNode the start node 261 * @return the spanning path; null, if no path is found 262 */ 263 protected List<Node> buildSpanningPath(Node startNode) { 264 if (startNode != null) { 265 Stack<NodePair> path = new Stack<>(); 266 Stack<NodePair> nextPairs = new Stack<>(); 267 nextPairs.addAll(getOutboundPairs(startNode)); 268 while (!nextPairs.isEmpty()) { 269 NodePair cur = nextPairs.pop(); 270 if (!path.contains(cur) && !path.contains(cur.swap())) { 271 while (!path.isEmpty() && !path.peek().isPredecessorOf(cur)) { 272 path.pop(); 273 } 274 path.push(cur); 275 if (isSpanningWay(path)) return buildPathFromNodePairs(path); 276 nextPairs.addAll(getOutboundPairs(path.peek())); 277 } 278 } 279 } 280 return Collections.emptyList(); 281 } 282 283 /** 284 * Tries to find a path through the graph which visits each edge (i.e. 285 * the segment of a way) exactly once. 286 * 287 * @return the path; null, if no path was found 288 */ 289 public List<Node> buildSpanningPath() { 290 prepare(); 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 all ways are closed. 296 // In the worst case this loops over all nodes which is very slow for large ways. 297 // 298 Set<Node> nodes = getTerminalNodes(); 299 nodes = nodes.isEmpty() ? getNodes() : nodes; 300 for (Node n: nodes) { 301 List<Node> path = buildSpanningPath(n); 302 if (!path.isEmpty()) 303 return path; 304 } 305 return null; 306 } 307}