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}