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}