Changeset 19062 in josm

Timestamp:

2024-04-27T08:58:28+02:00 (9 months ago)

Author:

GerdP

Message:

fix #21881: Add a check for loops in directional waterways
Patch by gaben, slightly modified

• implements Tarjan algorithm to find strongly connected components
• new preference validator.CycleDetector.directionalWaterways contains the list of waterway values which should be checked

Location:

trunk

Files:

• src/org/openstreetmap/josm/data/algorithms (added)
• src/org/openstreetmap/josm/data/algorithms/Tarjan.java (added)
• src/org/openstreetmap/josm/data/algorithms/package-info.java (added)
• src/org/openstreetmap/josm/data/osm/NodeGraph.java (modified) (24 diffs)
• src/org/openstreetmap/josm/data/osm/WaySegment.java (modified) (2 diffs)
• src/org/openstreetmap/josm/data/validation/OsmValidator.java (modified) (2 diffs)
• src/org/openstreetmap/josm/data/validation/tests/CycleDetector.java (added)
• src/org/openstreetmap/josm/gui/history/HistoryLoadTask.java (modified) (3 diffs)
• test/data/regress/21881 (added)
• test/data/regress/21881/CycleDetector_test_wikipedia.osm (added)
• test/data/regress/21881/not_consecutive.osm (added)
• test/unit/org/openstreetmap/josm/data/validation/tests/CycleDetectorTest.java (added)

trunk/src/org/openstreetmap/josm/data/osm/NodeGraph.java

@@ -22 +22 @@
 
 import org.openstreetmap.josm.tools.Pair;
+import org.openstreetmap.josm.tools.Utils;
 
 /**
- * A directed or undirected graph of nodes.
+ * A directed or undirected graph of nodes. Nodes are connected via edges represented by NodePair instances.
+ *
  * @since 12463 (extracted from CombineWayAction)
  */
@@ -33 +35 @@
      * @param way way
      * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order.
-     *                 if {@code false} each pair of nodes will occur twice (the pair and its inversed copy)
+     *                 if {@code false} each pair of nodes will occur twice (the pair and its inverse copy)
      * @return a list of pair of nodes from the given way
      */
     public static List<NodePair> buildNodePairs(Way way, boolean directed) {
         List<NodePair> pairs = new ArrayList<>();
-        for (Pair<Node, Node> pair: way.getNodePairs(false /* don't sort */)) {
+        for (Pair<Node, Node> pair : way.getNodePairs(false)) {
             pairs.add(new NodePair(pair));
             if (!directed) {
@@ -50 +52 @@
      * Builds a list of pair of nodes from the given ways.
      * @param ways ways
-     * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order.
-     *                 if {@code false} each pair of nodes will occur twice (the pair and its inversed copy)
+     * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order.<br>
+     *                 if {@code false} each pair of nodes will occur twice (the pair and its inverse copy)
      * @return a list of pair of nodes from the given ways
      */
     public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
         List<NodePair> pairs = new ArrayList<>();
-        for (Way w: ways) {
+        for (Way w : ways) {
             pairs.addAll(buildNodePairs(w, directed));
         }
@@ -63 +65 @@
 
     /**
-     * Builds a new list of pair nodes without the duplicated pairs (including inversed copies).
+     * Builds a new list of pair nodes without the duplicated pairs (including inverse copies).
      * @param pairs existing list of pairs
      * @return a new list of pair nodes without the duplicated pairs
@@ -69 +71 @@
     public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
         List<NodePair> cleaned = new ArrayList<>();
-        for (NodePair p: pairs) {
+        for (NodePair p : pairs) {
             if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
                 cleaned.add(p);
@@ -77 +79 @@
     }
 
+    /**
+     * Create a directed graph from the given node pairs.
+     * @param pairs Node pairs to build the graph from
+     * @return node graph structure
+     */
     public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
         NodeGraph graph = new NodeGraph();
-        for (NodePair pair: pairs) {
+        for (NodePair pair : pairs) {
             graph.add(pair);
         }
@@ -85 +92 @@
     }
 
+    /**
+     * Create a directed graph from the given ways.
+     * @param ways ways to build the graph from
+     * @return node graph structure
+     */
     public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
         NodeGraph graph = new NodeGraph();
-        for (Way w: ways) {
-            graph.add(buildNodePairs(w, true /* directed */));
+        for (Way w : ways) {
+            graph.add(buildNodePairs(w, true));
         }
         return graph;
@@ -100 +112 @@
     public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
         NodeGraph graph = new NodeGraph();
-        for (NodePair pair: pairs) {
+        for (NodePair pair : pairs) {
             graph.add(pair);
             graph.add(pair.swap());
@@ -109 +121 @@
     /**
      * Create an undirected graph from the given ways, but prevent reversing of all
-     * non-new ways by fix one direction.
+     * non-new ways by fixing one direction.
      * @param ways Ways to build the graph from
      * @return node graph structure
@@ -116 +128 @@
     public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
         NodeGraph graph = new NodeGraph();
-        for (Way w: ways) {
-            graph.add(buildNodePairs(w, false /* undirected */));
+        for (Way w : ways) {
+            graph.add(buildNodePairs(w, false));
         }
         return graph;
     }
 
+    /**
+     * Create a nearly undirected graph from the given ways, but prevent reversing of all
+     * non-new ways by fixing one direction.
+     * The first new way gives the direction of the graph.
+     * @param ways Ways to build the graph from
+     * @return node graph structure
+     */
     public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways) {
         boolean dir = true;
         NodeGraph graph = new NodeGraph();
-        for (Way w: ways) {
+        for (Way w : ways) {
             if (!w.isNew()) {
                 /* let the first non-new way give the direction (see #5880) */
@@ -131 +150 @@
                 dir = false;
             } else {
-                graph.add(buildNodePairs(w, false /* undirected */));
+                graph.add(buildNodePairs(w, false));
             }
         }
@@ -138 +157 @@
 
     private final Set<NodePair> edges;
-    private int numUndirectedEges;
-    /** counts the number of edges that were added */
+    private int numUndirectedEdges;
+    /** The number of edges that were added. */
     private int addedEdges;
     private final Map<Node, List<NodePair>> successors = new LinkedHashMap<>();
     private final Map<Node, List<NodePair>> predecessors = new LinkedHashMap<>();
 
+    /**
+     * Constructs a lookup table from the existing edges in the graph to enable efficient querying.
+     * This method creates a map where each node is associated with a list of nodes that are directly connected to it.
+     *
+     * @return A map representing the graph structure, where nodes are keys, and values are their direct successors.
+     * @since xxx
+     */
+    public Map<Node, List<Node>> createMap() {
+        final Map<Node, List<Node>> result = new HashMap<>(Utils.hashMapInitialCapacity(edges.size()));
+
+        for (NodePair edge : edges) {
+            result.computeIfAbsent(edge.getA(), k -> new ArrayList<>()).add(edge.getB());
+        }
+
+        return result;
+    }
+
+    /**
+     * See {@link #prepare()}
+     */
     protected void rememberSuccessor(NodePair pair) {
         List<NodePair> l = successors.computeIfAbsent(pair.getA(), k -> new ArrayList<>());
@@ -151 +190 @@
     }
 
+    /**
+     * See {@link #prepare()}
+     */
     protected void rememberPredecessors(NodePair pair) {
         List<NodePair> l = predecessors.computeIfAbsent(pair.getB(), k -> new ArrayList<>());
@@ -158 +200 @@
     }
 
+    /**
+     * Replies true if {@code n} is a terminal node of the graph. Internal variables should be initialized first.
+     * @param n Node to check
+     * @return {@code true} if it is a terminal node
+     * @see #prepare()
+     */
     protected boolean isTerminalNode(Node n) {
         if (successors.get(n) == null) return false;
@@ -175 +223 @@
         predecessors.clear();
 
-        for (NodePair pair: edges) {
+        for (NodePair pair : edges) {
             if (!undirectedEdges.contains(pair) && !undirectedEdges.contains(pair.swap())) {
                 undirectedEdges.add(pair);
@@ -182 +230 @@
             rememberPredecessors(pair);
         }
-        numUndirectedEges = undirectedEdges.size();
+        numUndirectedEdges = undirectedEdges.size();
     }
 
@@ -203 +251 @@
     /**
      * Add a list of node pairs.
-     * @param pairs list of node pairs
-     */
-    public void add(Collection<NodePair> pairs) {
-        for (NodePair pair: pairs) {
+     * @param pairs collection of node pairs
+     */
+    public void add(Iterable<NodePair> pairs) {
+        for (NodePair pair : pairs) {
             add(pair);
         }
     }
 
+    /**
+     * Return the edges containing the node pairs of the graph.
+     * @return the edges containing the node pairs of the graph
+     */
+    public Collection<NodePair> getEdges() {
+        return Collections.unmodifiableSet(edges);
+    }
+
+    /**
+     * Return the terminal nodes of the graph.
+     * @return the terminal nodes of the graph
+     */
     protected Set<Node> getTerminalNodes() {
         return getNodes().stream().filter(this::isTerminalNode).collect(Collectors.toCollection(LinkedHashSet::new));
@@ -230 +290 @@
     }
 
-    protected Set<Node> getNodes() {
+    /**
+     * Return the graph's nodes.
+     * @return the graph's nodes
+     */
+    public Collection<Node> getNodes() {
         Set<Node> nodes = new LinkedHashSet<>(2 * edges.size());
-        for (NodePair pair: edges) {
+        for (NodePair pair : edges) {
             nodes.add(pair.getA());
             nodes.add(pair.getB());
@@ -240 +304 @@
 
     protected boolean isSpanningWay(Collection<NodePair> way) {
-        return numUndirectedEges == way.size();
+        return numUndirectedEdges == way.size();
     }
 
@@ -249 +313 @@
 
     /**
-     * Tries to find a spanning path starting from node <code>startNode</code>.
-     *
+     * Tries to find a spanning path starting from node {@code startNode}.
+     * <p>
      * Traverses the path in depth-first order.
      *
@@ -260 +324 @@
             Deque<NodePair> path = new ArrayDeque<>();
             Set<NodePair> dupCheck = new HashSet<>();
-            Deque<NodePair> nextPairs = new ArrayDeque<>();
-            nextPairs.addAll(getOutboundPairs(startNode));
+            Deque<NodePair> nextPairs = new ArrayDeque<>(getOutboundPairs(startNode));
             while (!nextPairs.isEmpty()) {
                 NodePair cur = nextPairs.removeLast();
@@ -281 +344 @@
     /**
      * Tries to find a path through the graph which visits each edge (i.e.
-     * the segment of a way) exactly once.
-     * <p><b>Note that duplicated edges are removed first!</b>
+     * the segment of a way) exactly once.<p>
+     * <b>Note that duplicated edges are removed first!</b>
      *
-     * @return the path; null, if no path was found
+     * @return the path; {@code null}, if no path was found
      */
     public List<Node> buildSpanningPath() {
         prepare();
-        if (numUndirectedEges > 0 && isConnected()) {
-            // try to find a path from each "terminal node", i.e. from a
-            // node which is connected by exactly one undirected edges (or
-            // two directed edges in opposite direction) to the graph. A
+        if (numUndirectedEdges > 0 && isConnected()) {
+            // Try to find a path from each "terminal node", i.e. from a
+            // node which is connected by exactly one undirected edge (or
+            // two directed edges in the opposite direction) to the graph. A
             // graph built up from way segments is likely to include such
             // nodes, unless the edges build one or more closed rings.
@@ -325 +388 @@
     /**
      * Find out if the graph is connected.
-     * @return true if it is connected.
+     * @return {@code true} if it is connected
      */
     private boolean isConnected() {
-        Set<Node> nodes = getNodes();
+        Collection<Node> nodes = getNodes();
         if (nodes.isEmpty())
             return false;
@@ -351 +414 @@
     /**
      * Sort the nodes by number of appearances in the edges.
-     * @return set of nodes which can be start nodes in a spanning way.
+     * @return set of nodes which can be start nodes in a spanning way
      */
     private Set<Node> getMostFrequentVisitedNodesFirst() {
         if (edges.isEmpty())
             return Collections.emptySet();
-        // count appearance of nodes in edges
+        // count the appearance of nodes in edges
         Map<Node, Integer> counters = new HashMap<>();
         for (NodePair pair : edges) {

trunk/src/org/openstreetmap/josm/data/osm/WaySegment.java

@@ -3 +3 @@
 
 /**
- * A segment consisting of 2 consecutive nodes out of a way.
+ * A segment consisting of two consecutive nodes out of a way.
  */
 public final class WaySegment extends IWaySegment<Node, Way> {
@@ -37 +37 @@
             endIndex--;
         }
-        throw new IllegalArgumentException("Node pair is not part of way!");
+        throw new IllegalArgumentException("The node pair is not consecutive part of the way!");
     }
 

trunk/src/org/openstreetmap/josm/data/validation/OsmValidator.java

@@ -45 +45 @@
 import org.openstreetmap.josm.data.validation.tests.ConnectivityRelations;
 import org.openstreetmap.josm.data.validation.tests.CrossingWays;
+import org.openstreetmap.josm.data.validation.tests.CycleDetector;
 import org.openstreetmap.josm.data.validation.tests.DirectionNodes;
 import org.openstreetmap.josm.data.validation.tests.DuplicateNode;
@@ -155 +156 @@
         SharpAngles.class, // 3800 .. 3899
         ConnectivityRelations.class, // 3900 .. 3999
-        DirectionNodes.class, // 4000-4099
+        DirectionNodes.class, // 4000 .. 4099
         RightAngleBuildingTest.class, // 4100 .. 4199
+        CycleDetector.class, // 4200 .. 4299
     };
 

trunk/src/org/openstreetmap/josm/gui/history/HistoryLoadTask.java

@@ -10 +10 @@
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Iterator;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -16 +17 @@
 
 import org.openstreetmap.josm.data.osm.Changeset;
+import org.openstreetmap.josm.data.osm.ChangesetCache;
 import org.openstreetmap.josm.data.osm.OsmPrimitive;
 import org.openstreetmap.josm.data.osm.PrimitiveId;
@@ -230 +232 @@
             OsmServerChangesetReader changesetReader = new OsmServerChangesetReader();
             List<Long> changesetIds = new ArrayList<>(ds.getChangesetIds());
+            Iterator<Long> iter = changesetIds.iterator();
+            while (iter.hasNext()) {
+                long id = iter.next();
+                Changeset cs = ChangesetCache.getInstance().get((int) id);
+                if (cs != null && !cs.isOpen()) {
+                    ds.putChangeset(cs);
+                    iter.remove();
+                }
+            }
 
             // query changesets 100 by 100 (OSM API limit)
             int n = ChangesetQuery.MAX_CHANGESETS_NUMBER;
             for (int i = 0; i < changesetIds.size(); i += n) {
+                List<Changeset> downloadedCS = new ArrayList<>(changesetIds.size());
                 for (Changeset c : changesetReader.queryChangesets(
                         new ChangesetQuery().forChangesetIds(changesetIds.subList(i, Math.min(i + n, changesetIds.size()))),
                         progressMonitor.createSubTaskMonitor(1, false))) {
                     ds.putChangeset(c);
+                    downloadedCS.add(c);
                 }
+                ChangesetCache.getInstance().update(downloadedCS);
             }
         }