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}