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}