Repository: graphhopper/graphhopper
Pull request #2150 (2020-10-05 17:57:21)

Add Graph#getEdgeIteratorStateForKey(edgeKey) and edgeState.getEdgeKey()
This PR adds two new methods: 

* `EdgeIteratorState#getEdgeKey()` can be used to get an edge key from an edge state. The edge key is a combination of the edge ID and the direction of the edge, so its a unique identifier of a (directed) edge. It is equal to `2*edgeId` if the edge state matches the direction in which the edge is stored in BaseGraph and equal to `2*edgeId+1` otherwise.

* `Graph#getEdgeIteratorStateForKey(edgeKey) can be used to retrieve an edge state given an edge key.

Compared to #2146 this PR does not try to get rid of `GHUtility#createEdgeKey(int, int, int, boolean)` yet, but this should be at least easier to do after this PR.


Patch:
diff --git a/core/files/changelog.txt b/core/files/changelog.txt
index 5c706ae06..f3aee46f8 100644
--- a/core/files/changelog.txt
+++ b/core/files/changelog.txt
@@ -1,5 +1,6 @@
 3.0
     removed Dockerfile
+    the second argument of the VirtualEdgeIteratorState constructor is now an edge key (was an edge id before)
 
 2.0
     AbstractFlagEncoder#getMaxSpeed returns now Double#NaN instead of -1 if no maxspeed was found
diff --git a/core/src/main/java/com/graphhopper/reader/OSMTurnRelation.java b/core/src/main/java/com/graphhopper/reader/OSMTurnRelation.java
index 2d03698d4..1f34ea6ec 100644
--- a/core/src/main/java/com/graphhopper/reader/OSMTurnRelation.java
+++ b/core/src/main/java/com/graphhopper/reader/OSMTurnRelation.java
@@ -102,6 +102,7 @@ public class OSMTurnRelation {
             tags.put("no_right_turn", NOT);
             tags.put("no_straight_on", NOT);
             tags.put("no_u_turn", NOT);
+            tags.put("no_entry", NOT);
             tags.put("only_right_turn", ONLY);
             tags.put("only_left_turn", ONLY);
             tags.put("only_straight_on", ONLY);
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 0a4c73b29..3beded025 100644
--- a/core/src/main/java/com/graphhopper/routing/querygraph/QueryGraph.java
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/QueryGraph.java
@@ -34,6 +34,7 @@ import com.graphhopper.storage.index.Snap;
 import com.graphhopper.util.EdgeExplorer;
 import com.graphhopper.util.EdgeIterator;
 import com.graphhopper.util.EdgeIteratorState;
+import com.graphhopper.util.GHUtility;
 import com.graphhopper.util.shapes.BBox;
 
 import java.util.*;
@@ -139,7 +140,7 @@ public class QueryGraph implements Graph {
     public Set<EdgeIteratorState> getUnfavoredVirtualEdges() {
         // Need to create a new set to convert Set<VirtualEdgeIteratorState> to
         // Set<EdgeIteratorState>.
-        return new LinkedHashSet<EdgeIteratorState>(unfavoredEdges);
+        return new LinkedHashSet<>(unfavoredEdges);
     }
 
     /**
@@ -190,6 +191,14 @@ public class QueryGraph implements Graph {
                 + ". found edges were:" + eis + ", " + eis2);
     }
 
+    @Override
+    public EdgeIteratorState getEdgeIteratorStateForKey(int edgeKey) {
+        int edge = GHUtility.getEdgeFromEdgeKey(edgeKey);
+        if (!isVirtualEdge(edge))
+            return baseGraph.getEdgeIteratorStateForKey(edgeKey);
+        return getVirtualEdge(edgeKey - 2 * baseEdges);
+    }
+
     private VirtualEdgeIteratorState getVirtualEdge(int edgeId) {
         return queryOverlay.getVirtualEdge(edgeId);
     }
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 aa3140ee5..89b4afa8f 100644
--- a/core/src/main/java/com/graphhopper/routing/querygraph/QueryOverlayBuilder.java
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/QueryOverlayBuilder.java
@@ -146,8 +146,8 @@ class QueryOverlayBuilder {
 
                 GHPoint3D prevPoint = fullPL.get(0);
                 int adjNode = closestEdge.getAdjNode();
-                int origEdgeKey = GHUtility.createEdgeKey(baseNode, adjNode, closestEdge.getEdge(), false);
-                int origRevEdgeKey = GHUtility.createEdgeKey(baseNode, adjNode, closestEdge.getEdge(), true);
+                int origEdgeKey = closestEdge.getEdgeKey();
+                int origRevEdgeKey = GHUtility.reverseEdgeKey(origEdgeKey);
                 int prevWayIndex = 1;
                 int prevNodeId = baseNode;
                 int virtNodeId = queryOverlay.getVirtualNodes().getSize() + firstVirtualNodeId;
@@ -225,10 +225,10 @@ class QueryOverlayBuilder {
 
         boolean reverse = closestEdge.get(EdgeIteratorState.REVERSE_STATE);
         // edges between base and snapped point
-        VirtualEdgeIteratorState baseEdge = new VirtualEdgeIteratorState(origEdgeKey,
-                virtEdgeId, prevNodeId, nodeId, baseDistance, closestEdge.getFlags(), closestEdge.getName(), basePoints, reverse);
-        VirtualEdgeIteratorState baseReverseEdge = new VirtualEdgeIteratorState(origRevEdgeKey,
-                virtEdgeId, nodeId, prevNodeId, baseDistance, IntsRef.deepCopyOf(closestEdge.getFlags()), closestEdge.getName(), baseReversePoints, !reverse);
+        VirtualEdgeIteratorState baseEdge = new VirtualEdgeIteratorState(origEdgeKey, GHUtility.createEdgeKey(virtEdgeId, false),
+                prevNodeId, nodeId, baseDistance, closestEdge.getFlags(), closestEdge.getName(), basePoints, reverse);
+        VirtualEdgeIteratorState baseReverseEdge = new VirtualEdgeIteratorState(origRevEdgeKey, GHUtility.createEdgeKey(virtEdgeId, true),
+                nodeId, prevNodeId, baseDistance, IntsRef.deepCopyOf(closestEdge.getFlags()), closestEdge.getName(), baseReversePoints, !reverse);
 
         baseEdge.setReverseEdge(baseReverseEdge);
         baseReverseEdge.setReverseEdge(baseEdge);
diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIterator.java b/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIterator.java
index 4f9ea0ce3..69b7938ae 100644
--- a/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIterator.java
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIterator.java
@@ -71,6 +71,11 @@ class VirtualEdgeIterator implements EdgeIterator {
         return getCurrentEdge().getEdge();
     }
 
+    @Override
+    public int getEdgeKey() {
+        return getCurrentEdge().getEdgeKey();
+    }
+
     @Override
     public int getBaseNode() {
         return getCurrentEdge().getBaseNode();
diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIteratorState.java b/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIteratorState.java
index 1f6306af0..a4d91b7c3 100644
--- a/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIteratorState.java
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIteratorState.java
@@ -35,7 +35,7 @@ import com.graphhopper.util.PointList;
  */
 public class VirtualEdgeIteratorState implements EdgeIteratorState {
     private final PointList pointList;
-    private final int edgeId;
+    private final int edgeKey;
     private final int baseNode;
     private final int adjNode;
     private final int originalEdgeKey;
@@ -47,10 +47,10 @@ public class VirtualEdgeIteratorState implements EdgeIteratorState {
     private EdgeIteratorState reverseEdge;
     private final boolean reverse;
 
-    public VirtualEdgeIteratorState(int originalEdgeKey, int edgeId, int baseNode, int adjNode, double distance,
+    public VirtualEdgeIteratorState(int originalEdgeKey, int edgeKey, int baseNode, int adjNode, double distance,
                                     IntsRef edgeFlags, String name, PointList pointList, boolean reverse) {
         this.originalEdgeKey = originalEdgeKey;
-        this.edgeId = edgeId;
+        this.edgeKey = edgeKey;
         this.baseNode = baseNode;
         this.adjNode = adjNode;
         this.distance = distance;
@@ -61,10 +61,10 @@ public class VirtualEdgeIteratorState implements EdgeIteratorState {
     }
 
     /**
-     * This method returns the original edge via its key. I.e. also the direction is
+     * This method returns the original (not virtual!) edge key. I.e. also the direction is
      * already correctly encoded.
      *
-     * @see GHUtility#createEdgeKey(int, int, int, boolean)
+     * @see EdgeIteratorState#getEdgeKey()
      */
     public int getOriginalEdgeKey() {
         return originalEdgeKey;
@@ -72,7 +72,12 @@ public class VirtualEdgeIteratorState implements EdgeIteratorState {
 
     @Override
     public int getEdge() {
-        return edgeId;
+        return GHUtility.getEdgeFromEdgeKey(edgeKey);
+    }
+
+    @Override
+    public int getEdgeKey() {
+        return edgeKey;
     }
 
     @Override
diff --git a/core/src/main/java/com/graphhopper/storage/BaseGraph.java b/core/src/main/java/com/graphhopper/storage/BaseGraph.java
index 63dbb12e8..1366c4aff 100644
--- a/core/src/main/java/com/graphhopper/storage/BaseGraph.java
+++ b/core/src/main/java/com/graphhopper/storage/BaseGraph.java
@@ -572,6 +572,13 @@ class BaseGraph implements Graph {
         return null;
     }
 
+    @Override
+    public EdgeIteratorState getEdgeIteratorStateForKey(int edgeKey) {
+        EdgeIteratorStateImpl edge = new EdgeIteratorStateImpl(edgeAccess, this);
+        edge.init(edgeKey);
+        return edge;
+    }
+
     final void checkAdjNodeBounds(int adjNode) {
         if (adjNode < 0 && adjNode != Integer.MIN_VALUE || adjNode >= nodeCount)
             throw new IllegalStateException("adjNode " + adjNode + " out of bounds [0," + nf(nodeCount) + ")");
@@ -1001,6 +1008,29 @@ class BaseGraph implements Graph {
             return false;
         }
 
+        /**
+         * Similar to {@link #init(int edgeId, int adjNode)}, but here we retrieve the edge in a certain direction
+         * directly using an edge key.
+         */
+        final void init(int edgeKey) {
+            if (edgeKey < 0)
+                throw new IllegalArgumentException("edge keys must not be negative, given: " + edgeKey);
+            this.edgeId = GHUtility.getEdgeFromEdgeKey(edgeKey);
+            edgePointer = edgeAccess.toPointer(edgeId);
+            baseNode = edgeAccess.getNodeA(edgePointer);
+            adjNode = edgeAccess.getNodeB(edgePointer);
+            freshFlags = false;
+
+            if (edgeKey % 2 == 0 || baseNode == adjNode) {
+                reverse = false;
+            } else {
+                reverse = true;
+                int tmp = baseNode;
+                baseNode = adjNode;
+                adjNode = tmp;
+            }
+        }
+
         @Override
         public final int getBaseNode() {
             return baseNode;
@@ -1159,6 +1189,11 @@ class BaseGraph implements Graph {
             return edgeId;
         }
 
+        @Override
+        public int getEdgeKey() {
+            return GHUtility.createEdgeKey(edgeId, reverse);
+        }
+
         @Override
         public int getOrigEdgeFirst() {
             return getEdge();
diff --git a/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java b/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
index ca8ad6f68..b6d45bbeb 100644
--- a/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
+++ b/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
@@ -640,6 +640,12 @@ public class CHGraphImpl implements CHGraph, Storable<CHGraph> {
             return edgeIterable.getEdge();
         }
 
+        @Override
+        public int getEdgeKey() {
+            checkShortcut(false, "getEdgeKey");
+            return edgeIterable.getEdgeKey();
+        }
+
         @Override
         public EdgeIteratorState setFlags(IntsRef edgeFlags) {
             return edgeIterable.setFlags(edgeFlags);
diff --git a/core/src/main/java/com/graphhopper/storage/Graph.java b/core/src/main/java/com/graphhopper/storage/Graph.java
index 29a5255bb..7f23b2ead 100644
--- a/core/src/main/java/com/graphhopper/storage/Graph.java
+++ b/core/src/main/java/com/graphhopper/storage/Graph.java
@@ -82,6 +82,13 @@ public interface Graph {
      */
     EdgeIteratorState getEdgeIteratorState(int edgeId, int adjNode);
 
+    /**
+     * Returns the edge state for the given edge key
+     *
+     * @see EdgeIteratorState#getEdgeKey()
+     */
+    EdgeIteratorState getEdgeIteratorStateForKey(int edgeKey);
+
     /**
      * @return the 'opposite' node of a given edge, so if there is an edge 3-2 and node =2 this returns 3
      */
diff --git a/core/src/main/java/com/graphhopper/storage/GraphHopperStorage.java b/core/src/main/java/com/graphhopper/storage/GraphHopperStorage.java
index 953ef28a1..036a5c898 100644
--- a/core/src/main/java/com/graphhopper/storage/GraphHopperStorage.java
+++ b/core/src/main/java/com/graphhopper/storage/GraphHopperStorage.java
@@ -395,6 +395,11 @@ public final class GraphHopperStorage implements GraphStorage, Graph {
         return baseGraph.getEdgeIteratorState(edgeId, adjNode);
     }
 
+    @Override
+    public EdgeIteratorState getEdgeIteratorStateForKey(int edgeKey) {
+        return baseGraph.getEdgeIteratorStateForKey(edgeKey);
+    }
+
     @Override
     public AllEdgesIterator getAllEdges() {
         return baseGraph.getAllEdges();
diff --git a/core/src/main/java/com/graphhopper/util/EdgeIteratorState.java b/core/src/main/java/com/graphhopper/util/EdgeIteratorState.java
index 6fe27c81c..e8235e75e 100644
--- a/core/src/main/java/com/graphhopper/util/EdgeIteratorState.java
+++ b/core/src/main/java/com/graphhopper/util/EdgeIteratorState.java
@@ -18,6 +18,7 @@
 package com.graphhopper.util;
 
 import com.graphhopper.routing.ev.*;
+import com.graphhopper.storage.Graph;
 import com.graphhopper.storage.IntsRef;
 
 /**
@@ -73,6 +74,16 @@ public interface EdgeIteratorState {
      */
     int getEdge();
 
+    /**
+     * Returns the edge key of the current edge. The edge id can be derived from the edge key by calling
+     * {@link GHUtility#getEdgeFromEdgeKey(int)}, but the edge key also contains information about the
+     * direction of the edge. The edge key is even when the edge is oriented in storage direction and odd
+     * otherwise. You can use the edge key to retrieve an edge state in the associated direction using
+     * {@link Graph#getEdgeIteratorStateForKey(int)}. Loop edges are always returned in 'forward' direction even when
+     * you use an odd edge key.
+     */
+    int getEdgeKey();
+
     /**
      * @return the edge id of the first original edge of the current edge. This is needed for shortcuts
      * in edge-based contraction hierarchies and otherwise simply returns the id of the current edge.
diff --git a/core/src/main/java/com/graphhopper/util/GHUtility.java b/core/src/main/java/com/graphhopper/util/GHUtility.java
index 773c67a8c..7e7e8748d 100644
--- a/core/src/main/java/com/graphhopper/util/GHUtility.java
+++ b/core/src/main/java/com/graphhopper/util/GHUtility.java
@@ -558,6 +558,15 @@ public class GHUtility {
         return (nodeA > nodeB) ? edgeId + 1 : edgeId;
     }
 
+    /**
+     * Creates an edge key, i.e. an integer number that encodes an edge ID and the direction of an edge
+     */
+    public static int createEdgeKey(int edgeId, boolean reverse) {
+        // edge state in storage direction -> edge key is even
+        // edge state against storage direction -> edge key is odd
+        return (edgeId << 1) + (reverse ? 1 : 0);
+    }
+
     /**
      * Returns if the specified edgeKeys (created by createEdgeKey) are identical regardless of the
      * direction.
@@ -703,6 +712,11 @@ public class GHUtility {
             throw new UnsupportedOperationException("Not supported. Edge is empty.");
         }
 
+        @Override
+        public int getEdgeKey() {
+            throw new UnsupportedOperationException("Not supported. Edge is empty.");
+        }
+
         @Override
         public int getBaseNode() {
             throw new UnsupportedOperationException("Not supported. Edge is empty.");
diff --git a/reader-gtfs/src/main/java/com/graphhopper/gtfs/RealtimeFeed.java b/reader-gtfs/src/main/java/com/graphhopper/gtfs/RealtimeFeed.java
index 4bfc3418d..e67d7aa22 100644
--- a/reader-gtfs/src/main/java/com/graphhopper/gtfs/RealtimeFeed.java
+++ b/reader-gtfs/src/main/java/com/graphhopper/gtfs/RealtimeFeed.java
@@ -38,6 +38,7 @@ import com.graphhopper.storage.NodeAccess;
 import com.graphhopper.storage.TurnCostStorage;
 import com.graphhopper.util.EdgeExplorer;
 import com.graphhopper.util.EdgeIteratorState;
+import com.graphhopper.util.GHUtility;
 import com.graphhopper.util.PointList;
 import com.graphhopper.util.shapes.BBox;
 import org.mapdb.Fun;
@@ -202,9 +203,9 @@ public class RealtimeFeed {
             public EdgeIteratorState edge(int a, int b) {
                 int edge = firstEdge++;
                 final VirtualEdgeIteratorState newEdge = new VirtualEdgeIteratorState(-1,
-                        edge, a, b, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
+                        GHUtility.createEdgeKey(edge, false), a, b, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
                 final VirtualEdgeIteratorState reverseNewEdge = new VirtualEdgeIteratorState(-1,
-                        edge, b, a, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), true);
+                        GHUtility.createEdgeKey(edge, true), b, a, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), true);
                 newEdge.setReverseEdge(reverseNewEdge);
                 reverseNewEdge.setReverseEdge(newEdge);
                 additionalEdges.push(newEdge);
@@ -221,6 +222,11 @@ public class RealtimeFeed {
                 return null;
             }
 
+            @Override
+            public EdgeIteratorState getEdgeIteratorStateForKey(int edgeKey) {
+                return null;
+            }
+
             @Override
             public AllEdgesIterator getAllEdges() {
                 return null;
diff --git a/reader-gtfs/src/main/java/com/graphhopper/gtfs/WrapperGraph.java b/reader-gtfs/src/main/java/com/graphhopper/gtfs/WrapperGraph.java
index 51c758885..f254cf82f 100644
--- a/reader-gtfs/src/main/java/com/graphhopper/gtfs/WrapperGraph.java
+++ b/reader-gtfs/src/main/java/com/graphhopper/gtfs/WrapperGraph.java
@@ -58,7 +58,7 @@ public class WrapperGraph implements Graph {
                 throw new RuntimeException();
             }
             extraEdgesBySource.put(extraEdge.getBaseNode(), extraEdge);
-            extraEdgesByDestination.put(extraEdge.getAdjNode(), new VirtualEdgeIteratorState(extraEdge.getOriginalEdgeKey(), extraEdge.getEdge(), extraEdge.getAdjNode(),
+            extraEdgesByDestination.put(extraEdge.getAdjNode(), new VirtualEdgeIteratorState(extraEdge.getOriginalEdgeKey(), extraEdge.getEdgeKey(), extraEdge.getAdjNode(),
                     extraEdge.getBaseNode(), extraEdge.getDistance(), extraEdge.getFlags(), extraEdge.getName(), extraEdge.fetchWayGeometry(FetchMode.ALL), true));
         }
     }
@@ -112,6 +112,11 @@ public class WrapperGraph implements Graph {
         }
     }
 
+    @Override
+    public EdgeIteratorState getEdgeIteratorStateForKey(int edgeKey) {
+        throw new RuntimeException("not implemented yet");
+    }
+
     @Override
     public AllEdgesIterator getAllEdges() {
         return new AllEdgesIterator() {
@@ -133,6 +138,11 @@ public class WrapperGraph implements Graph {
                 throw new UnsupportedOperationException();
             }
 
+            @Override
+            public int getEdgeKey() {
+                throw new UnsupportedOperationException();
+            }
+
             @Override
             public int getOrigEdgeFirst() {
                 return getEdge();
@@ -331,6 +341,11 @@ public class WrapperGraph implements Graph {
                         return current.getEdge();
                     }
 
+                    @Override
+                    public int getEdgeKey() {
+                        return current.getEdgeKey();
+                    }
+
                     @Override
                     public int getOrigEdgeFirst() {
                         return current.getOrigEdgeFirst();


Test patch:
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 99523ae71..3b8a8dc94 100644
--- a/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java
+++ b/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java
@@ -33,9 +33,9 @@ import com.graphhopper.storage.index.LocationIndexTree;
 import com.graphhopper.storage.index.Snap;
 import com.graphhopper.util.*;
 import com.graphhopper.util.shapes.GHPoint;
-import org.junit.After;
-import org.junit.Before;
-import org.junit.Test;
+import org.junit.jupiter.api.AfterEach;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
 
 import java.util.Arrays;
 import java.util.Collections;
@@ -45,7 +45,7 @@ import java.util.List;
 import static com.graphhopper.storage.index.Snap.Position.*;
 import static com.graphhopper.util.EdgeIteratorState.UNFAVORED_EDGE;
 import static com.graphhopper.util.GHUtility.updateDistancesFor;
-import static org.junit.Assert.*;
+import static org.junit.jupiter.api.Assertions.*;
 
 /**
  * @author Peter Karich
@@ -55,14 +55,14 @@ public class QueryGraphTest {
     private FlagEncoder encoder;
     private GraphHopperStorage g;
 
-    @Before
+    @BeforeEach
     public void setUp() {
         encoder = new CarFlagEncoder();
         encodingManager = EncodingManager.create(encoder);
         g = new GraphBuilder(encodingManager).create();
     }
 
-    @After
+    @AfterEach
     public void tearDown() {
         g.close();
     }
@@ -353,12 +353,12 @@ public class QueryGraphTest {
         assertEquals(2, GHUtility.count(ee.setBaseNode(snap.getClosestNode())));
         EdgeIterator iter = ee.setBaseNode(snap.getClosestNode());
         iter.next();
-        assertTrue(iter.toString(), iter.get(accessEnc));
-        assertFalse(iter.toString(), iter.getReverse(accessEnc));
+        assertTrue(iter.get(accessEnc), iter.toString());
+        assertFalse(iter.getReverse(accessEnc), iter.toString());
 
         iter.next();
-        assertFalse(iter.toString(), iter.get(accessEnc));
-        assertTrue(iter.toString(), iter.getReverse(accessEnc));
+        assertFalse(iter.get(accessEnc), iter.toString());
+        assertTrue(iter.getReverse(accessEnc), iter.toString());
     }
 
     @Test
@@ -488,7 +488,7 @@ public class QueryGraphTest {
         it.next();
         assertEquals(endNode, it.getBaseNode());
         assertEquals(startNode, it.getAdjNode());
-        assertEquals("The edge id is not the same,", expectedEdgeId, it.getEdge());
+        assertEquals(expectedEdgeId, it.getEdge(), "The edge id is not the same,");
         assertFalse(it.next());
     }
 
@@ -717,7 +717,7 @@ public class QueryGraphTest {
         locationIndex.prepareIndex();
         Snap snap = locationIndex.findClosest(0.15, 0.15, DefaultEdgeFilter.allEdges(encoder));
         assertTrue(snap.isValid());
-        assertEquals("this test was supposed to test the Position.EDGE case", EDGE, snap.getSnappedPosition());
+        assertEquals(EDGE, snap.getSnappedPosition(), "this test was supposed to test the Position.EDGE case");
         QueryGraph queryGraph = lookup(snap);
         EdgeIterator iter = queryGraph.createEdgeExplorer().setBaseNode(snap.getClosestNode());
 
@@ -758,7 +758,7 @@ public class QueryGraphTest {
         locationIndex.prepareIndex();
         Snap snap = locationIndex.findClosest(0.2, 0.21, DefaultEdgeFilter.allEdges(encoder));
         assertTrue(snap.isValid());
-        assertEquals("this test was supposed to test the Position.PILLAR case", PILLAR, snap.getSnappedPosition());
+        assertEquals(PILLAR, snap.getSnappedPosition(), "this test was supposed to test the Position.PILLAR case");
         QueryGraph queryGraph = lookup(snap);
         EdgeIterator iter = queryGraph.createEdgeExplorer().setBaseNode(snap.getClosestNode());
 
@@ -854,6 +854,91 @@ public class QueryGraphTest {
         assertEquals(2, edge_x1.getEdge());
         assertEquals(2, edge_1x.getEdge());
 
+        // edge keys
+        assertEquals(2, edge_0x.getEdgeKey());
+        assertEquals(3, edge_x0.getEdgeKey());
+        assertEquals(4, edge_x1.getEdgeKey());
+        assertEquals(5, edge_1x.getEdgeKey());
+        assertNodes(queryGraph.getEdgeIteratorStateForKey(2), 0, 2);
+        assertNodes(queryGraph.getEdgeIteratorStateForKey(3), 2, 0);
+        assertNodes(queryGraph.getEdgeIteratorStateForKey(4), 2, 1);
+        assertNodes(queryGraph.getEdgeIteratorStateForKey(5), 1, 2);
+
+        // 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
+        }
+    }
+
+    @Test
+    public void testVirtualEdgeIds_reverse() {
+        // 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 = DistanceCalcEarth.DIST_EARTH.calcDist(na.getLat(0), na.getLon(0), na.getLat(1), na.getLon(1));
+        // this time we store the edge the other way
+        EdgeIteratorState edge = g.edge(1, 0, dist, true);
+        edge.set(speedEnc, 100);
+        edge.setReverse(speedEnc, 50);
+
+        // query graph
+        Snap snap = createLocationResult(50.00, 10.15, edge, 0, EDGE);
+        QueryGraph queryGraph = QueryGraph.create(g, snap);
+        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());
+
+        // edge keys
+        assertEquals(2, edge_0x.getEdgeKey());
+        assertEquals(3, edge_x0.getEdgeKey());
+        assertEquals(4, edge_x1.getEdgeKey());
+        assertEquals(5, edge_1x.getEdgeKey());
+        assertNodes(queryGraph.getEdgeIteratorStateForKey(2), 0, 2);
+        assertNodes(queryGraph.getEdgeIteratorStateForKey(3), 2, 0);
+        assertNodes(queryGraph.getEdgeIteratorStateForKey(4), 2, 1);
+        assertNodes(queryGraph.getEdgeIteratorStateForKey(5), 1, 2);
+
         // 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);
diff --git a/core/src/test/java/com/graphhopper/routing/weighting/FastestWeightingTest.java b/core/src/test/java/com/graphhopper/routing/weighting/FastestWeightingTest.java
index beff91874..11254b29e 100644
--- a/core/src/test/java/com/graphhopper/routing/weighting/FastestWeightingTest.java
+++ b/core/src/test/java/com/graphhopper/routing/weighting/FastestWeightingTest.java
@@ -24,7 +24,10 @@ import com.graphhopper.routing.util.Bike2WeightFlagEncoder;
 import com.graphhopper.routing.util.CarFlagEncoder;
 import com.graphhopper.routing.util.EncodingManager;
 import com.graphhopper.routing.util.FlagEncoder;
-import com.graphhopper.storage.*;
+import com.graphhopper.storage.Graph;
+import com.graphhopper.storage.GraphBuilder;
+import com.graphhopper.storage.GraphHopperStorage;
+import com.graphhopper.storage.IntsRef;
 import com.graphhopper.util.*;
 import com.graphhopper.util.Parameters.Routing;
 import org.junit.Test;
@@ -51,7 +54,7 @@ public class FastestWeightingTest {
     public void testWeightWrongHeading() {
         Weighting instance = new FastestWeighting(encoder, new PMap().putObject(Parameters.Routing.HEADING_PENALTY, 100));
 
-        VirtualEdgeIteratorState virtEdge = new VirtualEdgeIteratorState(0, 1, 1, 2, 10,
+        VirtualEdgeIteratorState virtEdge = new VirtualEdgeIteratorState(0, GHUtility.createEdgeKey(1, false), 1, 2, 10,
                 GHUtility.setProperties(encodingManager.createEdgeFlags(), encoder, 10, true, false), "test", Helper.createPointList(51, 0, 51, 1), false);
         double time = instance.calcEdgeWeight(virtEdge, false);
 
diff --git a/core/src/test/java/com/graphhopper/storage/GraphHopperStorageTest.java b/core/src/test/java/com/graphhopper/storage/GraphHopperStorageTest.java
index 72e2cc5ba..8588f55ea 100644
--- a/core/src/test/java/com/graphhopper/storage/GraphHopperStorageTest.java
+++ b/core/src/test/java/com/graphhopper/storage/GraphHopperStorageTest.java
@@ -323,4 +323,40 @@ public class GraphHopperStorageTest extends AbstractGraphStorageTester {
         Helper.removeDir(new File(defaultGraphLoc));
     }
 
+    @Test
+    public void testEdgeKey() {
+        GraphHopperStorage g = new GraphBuilder(encodingManager).create();
+        g.edge(0, 1, 10, true);
+        // storage direction
+        assertEdge(g.getEdgeIteratorState(0, Integer.MIN_VALUE), 0, 1, false, 0, 0);
+        // reverse direction
+        assertEdge(g.getEdgeIteratorState(0, 0), 1, 0, true, 0, 1);
+        // now use the edge key to retrieve the edge
+        assertEdge(g.getEdgeIteratorStateForKey(0), 0, 1, false, 0, 0);
+        // opposite direction
+        assertEdge(g.getEdgeIteratorStateForKey(1), 1, 0, true, 0, 1);
+    }
+
+    @Test
+    public void testEdgeKey_loop() {
+        GraphHopperStorage g = new GraphBuilder(encodingManager).create();
+        g.edge(0, 0, 10, true);
+        // storage direction
+        assertEdge(g.getEdgeIteratorState(0, Integer.MIN_VALUE), 0, 0, false, 0, 0);
+        // reverse direction cannot be retrieved, we get forward direction anyway
+        assertEdge(g.getEdgeIteratorState(0, 0), 0, 0, false, 0, 0);
+        // now use the edge key to retrieve the edge
+        assertEdge(g.getEdgeIteratorStateForKey(0), 0, 0, false, 0, 0);
+        // opposite direction could be retrieved like this but to be consistent with getEdgeIteratorState(edge,adj)
+        // we return the forward direction anyway! todo: is this really what we should do? probably related to #1631
+        assertEdge(g.getEdgeIteratorStateForKey(1), 0, 0, false, 0, 0);
+    }
+
+    private void assertEdge(EdgeIteratorState edge, int base, int adj, boolean reverse, int edgeId, int key) {
+        assertEquals(base, edge.getBaseNode());
+        assertEquals(adj, edge.getAdjNode());
+        assertEquals(reverse, edge.get(REVERSE_STATE));
+        assertEquals(edgeId, edge.getEdge());
+        assertEquals(key, edge.getEdgeKey());
+    }
 }
diff --git a/reader-gtfs/src/test/java/com/graphhopper/gtfs/GraphExplorerTest.java b/reader-gtfs/src/test/java/com/graphhopper/gtfs/GraphExplorerTest.java
index 63950fc82..0db9459b4 100644
--- a/reader-gtfs/src/test/java/com/graphhopper/gtfs/GraphExplorerTest.java
+++ b/reader-gtfs/src/test/java/com/graphhopper/gtfs/GraphExplorerTest.java
@@ -23,11 +23,13 @@ import com.graphhopper.routing.querygraph.VirtualEdgeIteratorState;
 import com.graphhopper.routing.util.EncodingManager;
 import com.graphhopper.routing.util.FootFlagEncoder;
 import com.graphhopper.routing.weighting.FastestWeighting;
+import com.graphhopper.storage.GraphBuilder;
 import com.graphhopper.storage.GraphHopperStorage;
 import com.graphhopper.storage.RAMDirectory;
 import com.graphhopper.storage.index.Snap;
 import com.graphhopper.util.DistanceCalcEuclidean;
 import com.graphhopper.util.EdgeIteratorState;
+import com.graphhopper.util.GHUtility;
 import com.graphhopper.util.PointList;
 import org.junit.Test;
 
@@ -56,8 +58,7 @@ public class GraphExplorerTest {
 
     @Test
     public void testNonEmptyGraph() {
-        GraphHopperStorage graph = new GraphHopperStorage(new RAMDirectory("wurst"), encodingManager, false);
-        graph.create(0);
+        GraphHopperStorage graph = new GraphBuilder(encodingManager).create();
         EdgeIteratorState d = graph.edge(4, 5);
         d.set(pt.getAccessEnc(), true);
         d.set(foot.getAccessEnc(), true);
@@ -75,18 +76,17 @@ public class GraphExplorerTest {
 
     @Test
     public void testExtraEdgesWithEmptyGraph() {
-        GraphHopperStorage graph = new GraphHopperStorage(new RAMDirectory("wurst"), encodingManager, false);
-
+        GraphHopperStorage graph = new GraphBuilder(encodingManager).create();
         GtfsStorage gtfsStorage = mock(GtfsStorage.class);
         RealtimeFeed realtimeFeed = mock(RealtimeFeed.class);
         List<VirtualEdgeIteratorState> extraEdges = new ArrayList<>();
-        VirtualEdgeIteratorState e = new VirtualEdgeIteratorState(0, 0, 0, 1, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
+        VirtualEdgeIteratorState e = new VirtualEdgeIteratorState(0, GHUtility.createEdgeKey(0, false), 0, 1, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
         e.set(foot.getAccessEnc(), true);
         extraEdges.add(e);
-        VirtualEdgeIteratorState f = new VirtualEdgeIteratorState(1, 1, 1, 2, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
+        VirtualEdgeIteratorState f = new VirtualEdgeIteratorState(1, GHUtility.createEdgeKey(1, false), 1, 2, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
         f.set(foot.getAccessEnc(), true);
         extraEdges.add(f);
-        VirtualEdgeIteratorState g = new VirtualEdgeIteratorState(2, 2, 1, 3, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
+        VirtualEdgeIteratorState g = new VirtualEdgeIteratorState(2, GHUtility.createEdgeKey(2, false), 1, 3, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
         g.set(foot.getAccessEnc(), true);
         extraEdges.add(g);
 
@@ -112,16 +112,16 @@ public class GraphExplorerTest {
         GtfsStorage gtfsStorage = mock(GtfsStorage.class);
         RealtimeFeed realtimeFeed = mock(RealtimeFeed.class);
         List<VirtualEdgeIteratorState> extraEdges = new ArrayList<>();
-        VirtualEdgeIteratorState e = new VirtualEdgeIteratorState(-1, edgeId++, 0, 1, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
+        VirtualEdgeIteratorState e = new VirtualEdgeIteratorState(-1, GHUtility.createEdgeKey(edgeId++, false), 0, 1, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
         e.set(foot.getAccessEnc(), true);
         extraEdges.add(e);
-        VirtualEdgeIteratorState f = new VirtualEdgeIteratorState(-1, edgeId++, 1, 2, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
+        VirtualEdgeIteratorState f = new VirtualEdgeIteratorState(-1, GHUtility.createEdgeKey(edgeId++, false), 1, 2, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
         f.set(foot.getAccessEnc(), true);
         extraEdges.add(f);
-        VirtualEdgeIteratorState g = new VirtualEdgeIteratorState(-1, edgeId++, 1, 3, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
+        VirtualEdgeIteratorState g = new VirtualEdgeIteratorState(-1, GHUtility.createEdgeKey(edgeId++, false), 1, 3, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
         g.set(foot.getAccessEnc(), true);
         extraEdges.add(g);
-        VirtualEdgeIteratorState h = new VirtualEdgeIteratorState(-1, edgeId++, 4, 7, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
+        VirtualEdgeIteratorState h = new VirtualEdgeIteratorState(-1, GHUtility.createEdgeKey(edgeId++, false), 4, 7, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
         h.set(foot.getAccessEnc(), true);
         extraEdges.add(h);
 
@@ -163,16 +163,16 @@ public class GraphExplorerTest {
         GtfsStorage gtfsStorage = mock(GtfsStorage.class);
         RealtimeFeed realtimeFeed = mock(RealtimeFeed.class);
         List<VirtualEdgeIteratorState> extraEdges = new ArrayList<>();
-        VirtualEdgeIteratorState e = new VirtualEdgeIteratorState(-1, edgeId++, 0, 1, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
+        VirtualEdgeIteratorState e = new VirtualEdgeIteratorState(-1, GHUtility.createEdgeKey(edgeId++, false), 0, 1, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
         e.set(foot.getAccessEnc(), true);
         extraEdges.add(e);
-        VirtualEdgeIteratorState f = new VirtualEdgeIteratorState(-1, edgeId++, 1, 2, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
+        VirtualEdgeIteratorState f = new VirtualEdgeIteratorState(-1, GHUtility.createEdgeKey(edgeId++, false), 1, 2, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
         f.set(foot.getAccessEnc(), true);
         extraEdges.add(f);
-        VirtualEdgeIteratorState g = new VirtualEdgeIteratorState(-1, edgeId++, 1, 3, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
+        VirtualEdgeIteratorState g = new VirtualEdgeIteratorState(-1, GHUtility.createEdgeKey(edgeId++, false), 1, 3, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
         g.set(foot.getAccessEnc(), true);
         extraEdges.add(g);
-        VirtualEdgeIteratorState h = new VirtualEdgeIteratorState(-1, edgeId++, 4, 7, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
+        VirtualEdgeIteratorState h = new VirtualEdgeIteratorState(-1, GHUtility.createEdgeKey(edgeId++, false), 4, 7, 0.0, encodingManager.createEdgeFlags(), "", new PointList(), false);
         h.set(foot.getAccessEnc(), true);
         extraEdges.add(h);
 
diff --git a/reader-osm/src/test/java/com/graphhopper/reader/osm/OSMReaderTest.java b/reader-osm/src/test/java/com/graphhopper/reader/osm/OSMReaderTest.java
index e32086064..c2df569d8 100644
--- a/reader-osm/src/test/java/com/graphhopper/reader/osm/OSMReaderTest.java
+++ b/reader-osm/src/test/java/com/graphhopper/reader/osm/OSMReaderTest.java
@@ -522,9 +522,11 @@ public class OSMReaderTest {
 
         // (2-3)->(3-4) only_straight_on = (2-3)->(3-8) restricted
         // (4-3)->(3-8) no_right_turn = (4-3)->(3-8) restricted
+        // (2-3)->(3-8) no_entry = (2-3)->(3-8) restricted
         DecimalEncodedValue carTCEnc = hopper.getEncodingManager().getDecimalEncodedValue(TurnCost.key("car"));
         assertTrue(tcStorage.get(carTCEnc, edge2_3, n3, edge3_8) > 0);
         assertTrue(tcStorage.get(carTCEnc, edge4_3, n3, edge3_8) > 0);
+        assertTrue(tcStorage.get(carTCEnc, edge2_3, n3, edge3_8) > 0);
         assertTrue(tcStorage.get(carTCEnc, edge2_3, n3, edge3_4) == 0);
         assertTrue(tcStorage.get(carTCEnc, edge2_3, n3, edge3_2) == 0);
         assertTrue(tcStorage.get(carTCEnc, edge2_3, n3, edge3_4) == 0);
diff --git a/reader-osm/src/test/resources/com/graphhopper/reader/osm/test-restrictions.xml b/reader-osm/src/test/resources/com/graphhopper/reader/osm/test-restrictions.xml
index 5fe7433ec..cbed25bb9 100644
--- a/reader-osm/src/test/resources/com/graphhopper/reader/osm/test-restrictions.xml
+++ b/reader-osm/src/test/resources/com/graphhopper/reader/osm/test-restrictions.xml
@@ -12,6 +12,7 @@
       (4,3)->(3,8): no_right_turn
       (4,5)->(5,6): right_turn_only
       (6,1)->(1,6): no_u_turn
+      (2,3)->(3,8): no_entry
     -->
     
    <!-- 
@@ -199,5 +200,13 @@
         <tag k="restriction" v="no_right_turn"/>
         <tag k="type" v="restriction"/>
     </relation>
+
+    <relation id="1006">
+        <member type="way" ref="23" role="from"/>
+        <member type="way" ref="38" role="to"/>
+        <member type="node" ref="3" role="via"/>
+        <tag k="restriction" v="no_entry"/>
+        <tag k="type" v="restriction"/>
+    </relation>
     
 </osm>