Repository: graphhopper/graphhopper
Pull request #2065 (2020-06-09 22:27:54)

Make virtual edge IDs consecutive
When we insert a virtual node between two nodes, like nodes 0 and 1 here: 

```
0-x-1
```

four `VirtualEdgeIteratorState`s get created. Two are visible for the edge explorer at the virtual node and one is visible from each of the real nodes (0 and 1). However, these edge states only represent the two directions of the two edges 0-x and x-1 and in fact `edgeState.getEdge()` returns the same number for each pair. Also the virtual edge IDs were not consecutive before this PR. So if 0-1 was the only edge with ID 0 we would get two virtual edge states with ID 1 and two with ID 3. IDs 2 and 4 could still be used to *obtain* the virtual edge states using `graph.getEdgeIteratorState(2,x)` but the returned edge state would still not have edge ID 2 (in this case it would be `edgeState.getEdge()==1` instead).

With this PR the virtual edge IDs will just be 1 and 2 (the same for both directions of the edges just as we do for non-virtual edges as well) and `getEdgeIteratorState(3, x)` will an error.

easbar: > I feared a problem there will be gaps (but shortcuts come before virtual edges) and also that there can be a problem in QueryOverlay like "colliding" edge IDs, but it seems we never need to store the "raw" virtual edge ID in a map.

What do you mean? So far it was like this: 

```
0,1,2,....|8,9,10,11,12,...,|25,27,29,31
base     |shortcuts           |virtual
```

and now its like this:

```
0,1,2,....|8,9,10,11,12,...,|25,26,27,28
base     |shortcuts           |virtual
```
so if anything we 'closed' the gaps that existed between the virtual edge IDs?



karussell: > Sorry I am not sure if I can follow. What do you mean? So far it was like this:

(I just had to think twice. I thought it was like `base | virtual |shortcuts` and then if we somewhere use the internal information that the difference has to be "virtual edges"*2 then there would have been a gap. So please just ignore my comment)

> You mean these internal ids of the directed edges?

Yes
easbar: Ah ok I see :) Thanks for reviewing this!

Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/EdgeChangeBuilder.java b/core/src/main/java/com/graphhopper/routing/querygraph/EdgeChangeBuilder.java
index 0da45ebe0..d534afd38 100644
--- a/core/src/main/java/com/graphhopper/routing/querygraph/EdgeChangeBuilder.java
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/EdgeChangeBuilder.java
@@ -66,7 +66,7 @@ class EdgeChangeBuilder {
         //    these adjacent real nodes so we can use them in the next step
         for (int i = 0; i < getNumVirtualNodes(); i++) {
             // base node
-            EdgeIteratorState baseRevEdge = getVirtualEdge(i * 4 + VE_BASE_REV);
+            EdgeIteratorState baseRevEdge = getVirtualEdge(i * 4 + SNAP_BASE);
             int towerNode = baseRevEdge.getAdjNode();
             if (!isVirtualNode(towerNode)) {
                 towerNodesToChange.add(towerNode);
@@ -74,7 +74,7 @@ class EdgeChangeBuilder {
             }
 
             // adj node
-            EdgeIteratorState adjEdge = getVirtualEdge(i * 4 + VE_ADJ);
+            EdgeIteratorState adjEdge = getVirtualEdge(i * 4 + SNAP_ADJ);
             towerNode = adjEdge.getAdjNode();
             if (!isVirtualNode(towerNode)) {
                 towerNodesToChange.add(towerNode);
@@ -101,8 +101,8 @@ class EdgeChangeBuilder {
             edgeChangesAtRealNodes.put(node, edgeChanges);
         }
         EdgeIteratorState edge = base
-                ? getVirtualEdge(virtNode * 4 + VE_BASE)
-                : getVirtualEdge(virtNode * 4 + VE_ADJ_REV);
+                ? getVirtualEdge(virtNode * 4 + BASE_SNAP)
+                : getVirtualEdge(virtNode * 4 + ADJ_SNAP);
         edgeChanges.getAdditionalEdges().add(edge);
     }
 
diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/QueryGraph.java b/core/src/main/java/com/graphhopper/routing/querygraph/QueryGraph.java
index b12b3c3f6..7678fa85d 100644
--- a/core/src/main/java/com/graphhopper/routing/querygraph/QueryGraph.java
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/QueryGraph.java
@@ -52,7 +52,7 @@ import java.util.*;
  * @author Peter Karich
  */
 public class QueryGraph implements Graph {
-    static final int VE_BASE = 0, VE_BASE_REV = 1, VE_ADJ = 2, VE_ADJ_REV = 3;
+    static final int BASE_SNAP = 0, SNAP_BASE = 1, SNAP_ADJ = 2, ADJ_SNAP = 3;
     private final Graph mainGraph;
     private final int mainNodes;
     private final int mainEdges;
@@ -219,7 +219,7 @@ public class QueryGraph implements Graph {
     }
 
     private int getInternalVirtualEdgeId(int origEdgeId) {
-        return origEdgeId - mainEdges;
+        return 2 * (origEdgeId - mainEdges);
     }
 
     @Override
@@ -266,13 +266,12 @@ public class QueryGraph implements Graph {
 
     private List<List<EdgeIteratorState>> buildVirtualEdgesAtVirtualNodes() {
         final List<List<EdgeIteratorState>> virtualEdgesAtVirtualNodes = new ArrayList<>();
-        final int[] vEdges = {VE_BASE_REV, VE_ADJ};
         for (int i = 0; i < queryOverlay.getVirtualNodes().size(); i++) {
-            List<EdgeIteratorState> filteredEdges = new ArrayList<>(2);
-            for (int vEdge : vEdges) {
-                filteredEdges.add(queryOverlay.getVirtualEdge(i * 4 + vEdge));
-            }
-            virtualEdgesAtVirtualNodes.add(filteredEdges);
+            List<EdgeIteratorState> virtualEdges = Arrays.<EdgeIteratorState>asList(
+                    queryOverlay.getVirtualEdge(i * 4 + SNAP_BASE),
+                    queryOverlay.getVirtualEdge(i * 4 + SNAP_ADJ)
+            );
+            virtualEdgesAtVirtualNodes.add(virtualEdges);
         }
         return virtualEdgesAtVirtualNodes;
     }
diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/QueryOverlayBuilder.java b/core/src/main/java/com/graphhopper/routing/querygraph/QueryOverlayBuilder.java
index 81a22c8e1..1c68bf117 100644
--- a/core/src/main/java/com/graphhopper/routing/querygraph/QueryOverlayBuilder.java
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/QueryOverlayBuilder.java
@@ -221,7 +221,7 @@ class QueryOverlayBuilder {
 
         PointList baseReversePoints = basePoints.clone(true);
         double baseDistance = basePoints.calcDistance(Helper.DIST_PLANE);
-        int virtEdgeId = firstVirtualEdgeId + queryOverlay.getNumVirtualEdges();
+        int virtEdgeId = firstVirtualEdgeId + queryOverlay.getNumVirtualEdges() / 2;
 
         boolean reverse = closestEdge.get(EdgeIteratorState.REVERSE_STATE);
         // edges between base and snapped point
diff --git a/core/src/main/java/com/graphhopper/routing/weighting/QueryGraphWeighting.java b/core/src/main/java/com/graphhopper/routing/weighting/QueryGraphWeighting.java
index af78e30ab..97159aa4c 100644
--- a/core/src/main/java/com/graphhopper/routing/weighting/QueryGraphWeighting.java
+++ b/core/src/main/java/com/graphhopper/routing/weighting/QueryGraphWeighting.java
@@ -115,7 +115,7 @@ public class QueryGraphWeighting implements Weighting {
     }
 
     private int getOriginalEdge(int edge) {
-        return closestEdges.get((edge - firstVirtualEdgeId) / 4);
+        return closestEdges.get((edge - firstVirtualEdgeId) / 2);
     }
 
     private boolean isVirtualNode(int node) {


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/HeadingResolverTest.java b/core/src/test/java/com/graphhopper/routing/HeadingResolverTest.java
index 424b8dd61..8a8b87870 100644
--- a/core/src/test/java/com/graphhopper/routing/HeadingResolverTest.java
+++ b/core/src/test/java/com/graphhopper/routing/HeadingResolverTest.java
@@ -118,8 +118,8 @@ class HeadingResolverTest {
         assertEquals(IntArrayList.from(1), resolver.getEdgesWithDifferentHeading(2, 90));
 
         // if the heading points West we get the Eastern edge 2->1
-        assertEquals("2->1", queryGraph.getEdgeIteratorState(3, Integer.MIN_VALUE).toString());
-        assertEquals(IntArrayList.from(3), resolver.getEdgesWithDifferentHeading(2, 270));
+        assertEquals("2->1", queryGraph.getEdgeIteratorState(2, Integer.MIN_VALUE).toString());
+        assertEquals(IntArrayList.from(2), resolver.getEdgesWithDifferentHeading(2, 270));
     }
 
     private QueryResult createQR(EdgeIteratorState closestEdge, double lat, double lon, int wayIndex) {
diff --git a/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java b/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java
index d32c2f7e5..b04368b48 100644
--- a/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java
+++ b/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java
@@ -531,18 +531,6 @@ public class QueryGraphTest {
         graphWithTurnCosts.close();
     }
 
-    private void initHorseshoeGraph(Graph g) {
-        // setup graph
-        //   ____
-        //  |    |
-        //  |    |
-        //  0    1
-        NodeAccess na = g.getNodeAccess();
-        na.setNode(0, 0, 0);
-        na.setNode(1, 0, 2);
-        g.edge(0, 1, 10, true).setWayGeometry(Helper.createPointList(2, 0, 2, 2));
-    }
-
     private QueryResult fakeEdgeQueryResult(EdgeIteratorState edge, double lat, double lon, int wayIndex) {
         QueryResult qr = new QueryResult(lat, lon);
         qr.setClosestEdge(edge);
@@ -552,13 +540,22 @@ public class QueryGraphTest {
         return qr;
     }
 
-    private boolean isAvoidEdge(QueryGraph queryGraph, int virtualEdgeTypeId) {
-        return queryGraph.getVirtualEdges().get(virtualEdgeTypeId).get(EdgeIteratorState.UNFAVORED_EDGE);
+    private boolean isAvoidEdge(EdgeIteratorState edge) {
+        return edge.get(EdgeIteratorState.UNFAVORED_EDGE);
     }
 
     @Test
     public void testEnforceHeading() {
-        initHorseshoeGraph(g);
+        // setup graph
+        //   ____
+        //  |    |
+        //  x    |
+        //  |    |
+        //  0    1
+        NodeAccess na = ((Graph) g).getNodeAccess();
+        na.setNode(0, 0, 0);
+        na.setNode(1, 0, 2);
+        ((Graph) g).edge(0, 1, 10, true).setWayGeometry(Helper.createPointList(2, 0, 2, 2));
         EdgeIteratorState edge = GHUtility.getEdge(g, 0, 1);
 
         // query result on first vertical part of way (upward, base is in south)
@@ -572,14 +569,14 @@ public class QueryGraphTest {
 
         // test penalized south
         boolean expect = true;
-        assertEquals(expect, isAvoidEdge(queryGraph, QueryGraph.VE_BASE_REV));
-        assertEquals(expect, isAvoidEdge(queryGraph, QueryGraph.VE_BASE));
+        assertEquals(expect, isAvoidEdge(queryGraph.getEdgeIteratorState(1, 2)));
+        assertEquals(expect, isAvoidEdge(queryGraph.getEdgeIteratorState(1, 0)));
 
         queryGraph.clearUnfavoredStatus();
         // test cleared edges south
         expect = false;
-        assertEquals(expect, isAvoidEdge(queryGraph, QueryGraph.VE_BASE_REV));
-        assertEquals(expect, isAvoidEdge(queryGraph, QueryGraph.VE_BASE));
+        assertEquals(expect, isAvoidEdge(queryGraph.getEdgeIteratorState(1, 2)));
+        assertEquals(expect, isAvoidEdge(queryGraph.getEdgeIteratorState(1, 0)));
 
         // enforce going south (same as coming in from north)
         unfavoredEdges = headingResolver.getEdgesWithDifferentHeading(qr.getClosestNode(), 180);
@@ -587,10 +584,15 @@ public class QueryGraphTest {
 
         // test penalized north
         expect = true;
-        assertEquals(expect, isAvoidEdge(queryGraph, QueryGraph.VE_ADJ));
-        assertEquals(expect, isAvoidEdge(queryGraph, QueryGraph.VE_ADJ_REV));
+        assertEquals(expect, isAvoidEdge(queryGraph.getEdgeIteratorState(2, 1)));
+        assertEquals(expect, isAvoidEdge(queryGraph.getEdgeIteratorState(2, 2)));
 
         // query result on second vertical part of way (downward, base is in north)
+        //   ____
+        //  |    |
+        //  |    x
+        //  |    |
+        //  0    1
         qr = fakeEdgeQueryResult(edge, 1.5, 2, 2);
         queryGraph = lookup(Arrays.asList(qr));
 
@@ -599,8 +601,8 @@ public class QueryGraphTest {
         queryGraph.unfavorVirtualEdges(unfavoredEdges);
         // test penalized south
         expect = true;
-        assertEquals(expect, isAvoidEdge(queryGraph, QueryGraph.VE_ADJ));
-        assertEquals(expect, isAvoidEdge(queryGraph, QueryGraph.VE_ADJ_REV));
+        assertEquals(expect, isAvoidEdge(queryGraph.getEdgeIteratorState(2, 1)));
+        assertEquals(expect, isAvoidEdge(queryGraph.getEdgeIteratorState(2, 2)));
 
         queryGraph.clearUnfavoredStatus();
         // enforce south
@@ -609,8 +611,8 @@ public class QueryGraphTest {
 
         // test penalized north
         expect = true;
-        assertEquals(expect, isAvoidEdge(queryGraph, QueryGraph.VE_BASE));
-        assertEquals(expect, isAvoidEdge(queryGraph, QueryGraph.VE_BASE_REV));
+        assertEquals(expect, isAvoidEdge(queryGraph.getEdgeIteratorState(1, 0)));
+        assertEquals(expect, isAvoidEdge(queryGraph.getEdgeIteratorState(1, 2)));
     }
 
     @Test
@@ -642,7 +644,15 @@ public class QueryGraphTest {
 
     @Test
     public void testUnfavorVirtualEdgePair() {
-        initHorseshoeGraph(g);
+        // setup graph
+        //   ____
+        //  |    |
+        //  |    |
+        //  0    1
+        NodeAccess na = ((Graph) g).getNodeAccess();
+        na.setNode(0, 0, 0);
+        na.setNode(1, 0, 2);
+        ((Graph) g).edge(0, 1, 10, true).setWayGeometry(Helper.createPointList(2, 0, 2, 2));
         EdgeIteratorState edge = GHUtility.getEdge(g, 0, 1);
 
         // query result on first vertical part of way (upward)
@@ -655,15 +665,15 @@ public class QueryGraphTest {
         VirtualEdgeIteratorState incomingEdge = (VirtualEdgeIteratorState) queryGraph.getEdgeIteratorState(1, 2);
         VirtualEdgeIteratorState incomingEdgeReverse = (VirtualEdgeIteratorState) queryGraph.getEdgeIteratorState(1, incomingEdge.getBaseNode());
         boolean expect = true;  // expect incoming and reverse incoming edge to be avoided
-        assertEquals(expect, incomingEdge.get(EdgeIteratorState.UNFAVORED_EDGE));
-        assertEquals(expect, incomingEdgeReverse.get(EdgeIteratorState.UNFAVORED_EDGE));
+        assertEquals(expect, isAvoidEdge(incomingEdge));
+        assertEquals(expect, isAvoidEdge(incomingEdgeReverse));
         assertEquals(new LinkedHashSet<>(Arrays.asList(incomingEdge, incomingEdgeReverse)),
                 queryGraph.getUnfavoredVirtualEdges());
 
         queryGraph.clearUnfavoredStatus();
         expect = false; // expect incoming and reverse incoming edge not to be avoided
-        assertEquals(expect, incomingEdge.get(EdgeIteratorState.UNFAVORED_EDGE));
-        assertEquals(expect, incomingEdgeReverse.get(EdgeIteratorState.UNFAVORED_EDGE));
+        assertEquals(expect, isAvoidEdge(incomingEdge));
+        assertEquals(expect, isAvoidEdge(incomingEdgeReverse));
         assertEquals(new LinkedHashSet<>(), queryGraph.getUnfavoredVirtualEdges());
     }
 
@@ -804,6 +814,75 @@ public class QueryGraphTest {
         assertEquals(directDist, virtualEdgeDistanceSum, 1.e-3);
     }
 
+    @Test
+    public void testVirtualEdgeIds() {
+        // virtual nodes:     2
+        //                0 - x - 1
+        // virtual edges:   1   2
+        FlagEncoder encoder = new CarFlagEncoder().setSpeedTwoDirections(true);
+        EncodingManager encodingManager = EncodingManager.create(encoder);
+        DecimalEncodedValue speedEnc = encoder.getAverageSpeedEnc();
+        Graph g = new GraphBuilder(encodingManager).create();
+        NodeAccess na = g.getNodeAccess();
+        na.setNode(0, 50.00, 10.10);
+        na.setNode(1, 50.00, 10.20);
+        double dist = Helper.DIST_EARTH.calcDist(na.getLat(0), na.getLon(0), na.getLat(1), na.getLon(1));
+        EdgeIteratorState edge = g.edge(0, 1, dist, true);
+        edge.set(speedEnc, 50);
+        edge.setReverse(speedEnc, 100);
+
+        // query graph
+        QueryResult qr = createLocationResult(50.00, 10.15, edge, 0, EDGE);
+        QueryGraph queryGraph = QueryGraph.create(g, qr);
+        assertEquals(3, queryGraph.getNodes());
+        assertEquals(5, queryGraph.getEdges());
+        assertEquals(4, queryGraph.getVirtualEdges().size());
+
+        EdgeIteratorState edge_0x = queryGraph.getEdgeIteratorState(1, 2);
+        EdgeIteratorState edge_x0 = queryGraph.getEdgeIteratorState(1, 0);
+        EdgeIteratorState edge_x1 = queryGraph.getEdgeIteratorState(2, 1);
+        EdgeIteratorState edge_1x = queryGraph.getEdgeIteratorState(2, 2);
+
+        assertNodes(edge_0x, 0, 2);
+        assertNodes(edge_x0, 2, 0);
+        assertNodes(edge_x1, 2, 1);
+        assertNodes(edge_1x, 1, 2);
+
+        // virtual edge IDs are 1 and 2
+        assertEquals(1, edge_0x.getEdge());
+        assertEquals(1, edge_x0.getEdge());
+        assertEquals(2, edge_x1.getEdge());
+        assertEquals(2, edge_1x.getEdge());
+
+        // internally each edge is represented by two edge states for the two directions
+        assertSame(queryGraph.getVirtualEdges().get(0), edge_0x);
+        assertSame(queryGraph.getVirtualEdges().get(1), edge_x0);
+        assertSame(queryGraph.getVirtualEdges().get(2), edge_x1);
+        assertSame(queryGraph.getVirtualEdges().get(3), edge_1x);
+
+        for (EdgeIteratorState e : Arrays.asList(edge_0x, edge_x1)) {
+            assertEquals(50, e.get(speedEnc), 1.e-6);
+            assertEquals(100, e.getReverse(speedEnc), 1.e-6);
+        }
+
+        for (EdgeIteratorState e : Arrays.asList(edge_x0, edge_1x)) {
+            assertEquals(100, e.get(speedEnc), 1.e-6);
+            assertEquals(50, e.getReverse(speedEnc), 1.e-6);
+        }
+
+        try {
+            queryGraph.getEdgeIteratorState(3, 2);
+            fail("there should be an error");
+        } catch (IndexOutOfBoundsException e) {
+            // ok
+        }
+    }
+
+    private void assertNodes(EdgeIteratorState edge, int base, int adj) {
+        assertEquals(base, edge.getBaseNode());
+        assertEquals(adj, edge.getAdjNode());
+    }
+
     private QueryGraph lookup(QueryResult res) {
         return lookup(Collections.singletonList(res));
     }
diff --git a/web/src/test/java/com/graphhopper/http/resources/SPTResourceTest.java b/web/src/test/java/com/graphhopper/http/resources/SPTResourceTest.java
index fa7d3ba98..6eaeb119e 100644
--- a/web/src/test/java/com/graphhopper/http/resources/SPTResourceTest.java
+++ b/web/src/test/java/com/graphhopper/http/resources/SPTResourceTest.java
@@ -98,7 +98,7 @@ public class SPTResourceTest {
         assertTrue(lines.length > 500);
         assertEquals("prev_node_id,edge_id,node_id,time,distance", lines[0]);
         assertEquals("-1,-1,1884,0,0", lines[1]);
-        assertEquals("1884,2274,1324,3817,74", lines[2]);
+        assertEquals("1884,2273,1324,3817,74", lines[2]);
         assertEquals("1884,2272,263,13496,262", lines[3]);
     }