Changeset 15555 in josm

Timestamp:

2019-12-03T16:28:41+01:00 (5 years ago)

Author:

GerdP

Message:

fix #18385: Combine way action may remove parts of the ways

• Count all edges that are added to the graph, even if they are rejected because they are duplicates.
• add new method buildSpanningPathNoRemove() which returns null if any duplicate edge was found

and use this method in CombineWayAction

Location:

trunk

Files:

• src/org/openstreetmap/josm/actions/CombineWayAction.java (modified) (1 diff)
• src/org/openstreetmap/josm/data/osm/NodeGraph.java (modified) (5 diffs)
• test/data/regress/18385 (added)
• test/data/regress/18385/data.osm (added)
• test/unit/org/openstreetmap/josm/actions/CombineWayActionTest.java (modified) (3 diffs)

trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java

@@ -124 +124 @@
         // try to build a new way which includes all the combined ways
         NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ways);
-        List<Node> path = graph.buildSpanningPath();
+        List<Node> path = graph.buildSpanningPathNoRemove();
         if (path == null) {
             warnCombiningImpossible();

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

@@ -139 +139 @@
     private final Set<NodePair> edges;
     private int numUndirectedEges;
+    /** counts 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<>();
@@ -195 +197 @@
      */
     public void add(NodePair pair) {
-        if (!edges.contains(pair)) {
-            edges.add(pair);
-        }
+        addedEdges++;
+        edges.add(pair);
     }
 
@@ -290 +291 @@
     public List<Node> buildSpanningPath() {
         prepare();
-        if(numUndirectedEges > 0 && isConnected()) {
+        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
@@ -311 +312 @@
 
     /**
+     * Tries to find a path through the graph which visits each edge (i.e.
+     * the segment of a way) exactly once. If the graph was build from overlapping
+     * ways duplicate edges were removed already. This method will return null if
+     * any duplicated edge was removed.
+     *
+     * @return the path; null, if no path was found or duplicated edges were found
+     * @since xxx
+     */
+    public List<Node> buildSpanningPathNoRemove() {
+        if (edges.size() != addedEdges)
+            return null;
+        return buildSpanningPath();
+    }
+
+    /**
      * Find out if the graph is connected.
      * @return true if it is connected.
@@ -321 +337 @@
         HashSet<Node> visited = new HashSet<>();
         toVisit.add(nodes.iterator().next());
-        while(!toVisit.isEmpty()) {
+        while (!toVisit.isEmpty()) {
             Node n = toVisit.pop();
             if (!visited.contains(n)) {

trunk/test/unit/org/openstreetmap/josm/actions/CombineWayActionTest.java

@@ -3 +3 @@
 
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
 
 import java.io.IOException;
@@ -46 +47 @@
             DataSet ds = OsmReader.parseDataSet(is, null);
             NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ds.getWays());
-            List<Node> path = graph.buildSpanningPath();
+            List<Node> path = graph.buildSpanningPathNoRemove();
             assertEquals(10, path.size());
             Set<Long> firstAndLastObtained = new HashSet<>();
@@ -55 +56 @@
             firstAndLastExpected.add(35213705L);
             assertEquals(firstAndLastExpected, firstAndLastObtained);
+        }
+    }
+
+    /**
+     * Non-regression test for bug #1835 (combine way with overlapping ways)
+     * @throws IOException if any I/O error occurs
+     * @throws IllegalDataException if OSM parsing fails
+     */
+    @Test
+    public void testTicket18385() throws IOException, IllegalDataException {
+        try (InputStream is = TestUtils.getRegressionDataStream(18385, "data.osm")) {
+            DataSet ds = OsmReader.parseDataSet(is, null);
+            NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ds.getWays());
+            List<Node> path = graph.buildSpanningPathNoRemove();
+            assertNull(path);
         }
     }