Repository: graphhopper/graphhopper
Pull request #1665 (2019-07-16 07:53:19)

Adds AbstractBidirAlgo#calcPath with restricted source/target edges.
For #1647 I have added a new `calcPath` method to `AbstractBidirAlgo` that, additionally to the from/to node ids, also takes two edge ids that are enforced as start/target edges. This allows to strictly enforce the first and last edge of a path.

For now this is only supported on the low-level java API level and how to obtain the edge ids for the edges one wants to restrict is another question (?).


Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java b/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
index d97852661..13ebfb958 100644
--- a/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
+++ b/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
@@ -19,6 +19,7 @@ package com.graphhopper.routing;
 
 import com.carrotsearch.hppc.IntObjectMap;
 import com.graphhopper.coll.GHIntObjectHashMap;
+import com.graphhopper.routing.util.EdgeFilter;
 import com.graphhopper.routing.util.TraversalMode;
 import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.Graph;
@@ -30,15 +31,20 @@ import com.graphhopper.util.GHUtility;
 
 import java.util.PriorityQueue;
 
+import static com.graphhopper.util.EdgeIterator.ANY_EDGE;
+
 /**
  * Common subclass for bidirectional algorithms.
  * <p>
  *
  * @author Peter Karich
+ * @author easbar
  */
 public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
     protected int from;
     protected int to;
+    protected int fromOutEdge;
+    protected int toInEdge;
     protected IntObjectMap<SPTEntry> bestWeightMapFrom;
     protected IntObjectMap<SPTEntry> bestWeightMapTo;
     protected IntObjectMap<SPTEntry> bestWeightMapOther;
@@ -55,6 +61,8 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
 
     public AbstractBidirAlgo(Graph graph, Weighting weighting, TraversalMode tMode) {
         super(graph, weighting, tMode);
+        fromOutEdge = ANY_EDGE;
+        toInEdge = ANY_EDGE;
         int size = Math.min(Math.max(200, graph.getNodes() / 10), 150_000);
         initCollections(size);
     }
@@ -88,6 +96,24 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
 
     @Override
     public Path calcPath(int from, int to) {
+        return calcPath(from, to, ANY_EDGE, ANY_EDGE);
+    }
+
+    /**
+     * like {@link #calcPath(int, int)}, but this method also allows to strictly restrict the edge the
+     * path will begin with and the edge it will end with.
+     *
+     * @param fromOutEdge the edge id of the first edge of the path. using {@link EdgeIterator#ANY_EDGE} means
+     *                    not enforcing the first edge of the path
+     * @param toInEdge    the edge id of the last edge of the path. using {@link EdgeIterator#ANY_EDGE} means
+     *                    not enforcing the last edge of the path
+     */
+    public Path calcPath(int from, int to, int fromOutEdge, int toInEdge) {
+        if ((fromOutEdge != ANY_EDGE || toInEdge != ANY_EDGE) && !traversalMode.isEdgeBased()) {
+            throw new IllegalArgumentException("Restricting the start/target edges is only possible for edge-based graph traversal");
+        }
+        this.fromOutEdge = fromOutEdge;
+        this.toInEdge = toInEdge;
         checkAlreadyRun();
         createAndInitPath();
         init(from, 0, to, 0);
@@ -130,8 +156,9 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
                 bestWeightMapOther = bestWeightMapFrom;
                 updateBestPath(GHUtility.getEdge(graph, currFrom.adjNode, to), currFrom, to, true);
             }
-        } else if (from == to) {
-            // special case of identical start and end
+        } else if (from == to && fromOutEdge == ANY_EDGE && toInEdge == ANY_EDGE) {
+            // special handling if start and end are the same and no directions are restricted
+            // the resulting weight should be zero
             if (currFrom.weight != 0 || currTo.weight != 0) {
                 throw new IllegalStateException("If from=to, the starting weight must be zero for from and to");
             }
@@ -147,9 +174,55 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
     }
 
     protected void postInitFrom() {
+        if (fromOutEdge == ANY_EDGE) {
+            fillEdgesFromUsingFilter(additionalEdgeFilter);
+        } else {
+            // need to use a local reference here, because additionalEdgeFilter is modified when calling fillEdgesFromUsingFilter
+            final EdgeFilter tmpFilter = additionalEdgeFilter;
+            fillEdgesFromUsingFilter(new EdgeFilter() {
+                @Override
+                public boolean accept(EdgeIteratorState edgeState) {
+                    return (tmpFilter == null || tmpFilter.accept(edgeState)) && edgeState.getOrigEdgeFirst() == fromOutEdge;
+                }
+            });
+        }
     }
 
     protected void postInitTo() {
+        if (toInEdge == ANY_EDGE) {
+            fillEdgesToUsingFilter(additionalEdgeFilter);
+        } else {
+            final EdgeFilter tmpFilter = additionalEdgeFilter;
+            fillEdgesToUsingFilter(new EdgeFilter() {
+                @Override
+                public boolean accept(EdgeIteratorState edgeState) {
+                    return (tmpFilter == null || tmpFilter.accept(edgeState)) && edgeState.getOrigEdgeLast() == toInEdge;
+                }
+            });
+        }
+    }
+
+    /**
+     * @param edgeFilter edge filter used to fill edges. the {@link #additionalEdgeFilter} reference will be set to
+     *                   edgeFilter by this method, so make sure edgeFilter does not use it directly.
+     */
+    protected void fillEdgesFromUsingFilter(EdgeFilter edgeFilter) {
+        // we temporarily ignore the additionalEdgeFilter
+        EdgeFilter tmpFilter = additionalEdgeFilter;
+        additionalEdgeFilter = edgeFilter;
+        finishedFrom = !fillEdgesFrom();
+        additionalEdgeFilter = tmpFilter;
+    }
+
+    /**
+     * @see #fillEdgesFromUsingFilter(EdgeFilter)
+     */
+    protected void fillEdgesToUsingFilter(EdgeFilter edgeFilter) {
+        // we temporarily ignore the additionalEdgeFilter
+        EdgeFilter tmpFilter = additionalEdgeFilter;
+        additionalEdgeFilter = edgeFilter;
+        finishedTo = !fillEdgesTo();
+        additionalEdgeFilter = tmpFilter;
     }
 
     protected void runAlgo() {
@@ -347,6 +420,7 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
 
     void setFromDataStructures(AbstractBidirAlgo other) {
         from = other.from;
+        fromOutEdge = other.fromOutEdge;
         pqOpenSetFrom = other.pqOpenSetFrom;
         bestWeightMapFrom = other.bestWeightMapFrom;
         finishedFrom = other.finishedFrom;
@@ -357,6 +431,7 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
 
     void setToDataStructures(AbstractBidirAlgo other) {
         to = other.to;
+        toInEdge = other.toInEdge;
         pqOpenSetTo = other.pqOpenSetTo;
         bestWeightMapTo = other.bestWeightMapTo;
         finishedTo = other.finishedTo;
diff --git a/core/src/main/java/com/graphhopper/routing/AbstractBidirectionEdgeCHNoSOD.java b/core/src/main/java/com/graphhopper/routing/AbstractBidirectionEdgeCHNoSOD.java
index 6e98c7cee..5b1d1df95 100644
--- a/core/src/main/java/com/graphhopper/routing/AbstractBidirectionEdgeCHNoSOD.java
+++ b/core/src/main/java/com/graphhopper/routing/AbstractBidirectionEdgeCHNoSOD.java
@@ -30,6 +30,8 @@ import com.graphhopper.util.EdgeIterator;
 import com.graphhopper.util.EdgeIteratorState;
 import com.graphhopper.util.GHUtility;
 
+import static com.graphhopper.util.EdgeIterator.ANY_EDGE;
+
 /**
  * @author easbar
  */
@@ -53,18 +55,35 @@ public abstract class AbstractBidirectionEdgeCHNoSOD extends AbstractBidirAlgo {
 
     @Override
     protected void postInitFrom() {
-        EdgeFilter filter = additionalEdgeFilter;
-        setEdgeFilter(EdgeFilter.ALL_EDGES);
-        fillEdgesFrom();
-        setEdgeFilter(filter);
+        // With CH the additionalEdgeFilter is the one that filters out edges leading or coming from higher rank nodes,
+        // i.e. LevelEdgeFilter, For the first step though we need all edges, so we need to ignore this filter.
+        // Using an arbitrary filter is not supported for CH anyway.
+        if (fromOutEdge == ANY_EDGE) {
+            fillEdgesFromUsingFilter(EdgeFilter.ALL_EDGES);
+        } else {
+            fillEdgesFromUsingFilter(new EdgeFilter() {
+                @Override
+                public boolean accept(EdgeIteratorState edgeState) {
+                    return edgeState.getOrigEdgeFirst() == fromOutEdge;
+                }
+            });
+        }
+        finishedFrom = bestPath.isFound();
     }
 
     @Override
     protected void postInitTo() {
-        EdgeFilter filter = additionalEdgeFilter;
-        setEdgeFilter(EdgeFilter.ALL_EDGES);
-        fillEdgesTo();
-        setEdgeFilter(filter);
+        if (toInEdge == ANY_EDGE) {
+            fillEdgesToUsingFilter(EdgeFilter.ALL_EDGES);
+        } else {
+            fillEdgesToUsingFilter(new EdgeFilter() {
+                @Override
+                public boolean accept(EdgeIteratorState edgeState) {
+                    return edgeState.getOrigEdgeLast() == toInEdge;
+                }
+            });
+        }
+        finishedTo = bestPath.isFound();
     }
 
     @Override
@@ -88,7 +107,9 @@ public abstract class AbstractBidirectionEdgeCHNoSOD extends AbstractBidirAlgo {
         // node of the shortest path matches the source or target. in this case one of the searches does not contribute
         // anything to the shortest path.
         int oppositeNode = reverse ? from : to;
-        if (edgeState.getAdjNode() == oppositeNode) {
+        int oppositeEdge = reverse ? fromOutEdge : toInEdge;
+        boolean oppositeEdgeRestricted = reverse ? (fromOutEdge != ANY_EDGE) : (toInEdge != ANY_EDGE);
+        if (edgeState.getAdjNode() == oppositeNode && (!oppositeEdgeRestricted || getOrigEdgeId(edgeState, reverse) == oppositeEdge)) {
             if (entry.getWeightOfVisitedPath() < bestPath.getWeight()) {
                 bestPath.setSwitchToFrom(reverse);
                 bestPath.setSPTEntry(entry);
diff --git a/core/src/main/java/com/graphhopper/routing/lm/LandmarkStorage.java b/core/src/main/java/com/graphhopper/routing/lm/LandmarkStorage.java
index 2ca516593..ae9090d9b 100644
--- a/core/src/main/java/com/graphhopper/routing/lm/LandmarkStorage.java
+++ b/core/src/main/java/com/graphhopper/routing/lm/LandmarkStorage.java
@@ -57,7 +57,7 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
     private static final Logger LOGGER = LoggerFactory.getLogger(LandmarkStorage.class);
     // This value is used to identify nodes where no subnetwork is associated
     private static final int UNSET_SUBNETWORK = -1;
-    // This value should only be used if subnetwork is too small to be explicitely stored
+    // This value should only be used if subnetwork is too small to be explicitly stored
     private static final int UNCLEAR_SUBNETWORK = 0;
     // one node has an associated landmark information ('one landmark row'): the forward and backward weight
     private long LM_ROW_LENGTH;
diff --git a/core/src/main/java/com/graphhopper/util/EdgeIterator.java b/core/src/main/java/com/graphhopper/util/EdgeIterator.java
index 0f4d77c43..0359dedba 100644
--- a/core/src/main/java/com/graphhopper/util/EdgeIterator.java
+++ b/core/src/main/java/com/graphhopper/util/EdgeIterator.java
@@ -46,6 +46,11 @@ public interface EdgeIterator extends EdgeIteratorState {
      */
     int NO_EDGE = -1;
 
+    /**
+     * Integer value used in places where normally an edge would be expected, but no specific edge shall be specified.
+     */
+    int ANY_EDGE = -2;
+
     /**
      * To be called to go to the next edge state.
      * <p>


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java b/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java
index 1c1b63a3a..68e908c1c 100644
--- a/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java
+++ b/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java
@@ -93,6 +93,7 @@ public class AStarBidirectionTest extends AbstractRoutingAlgorithmTester {
                 toRef.set(currTo);
             }
         };
+        astar.createAndInitPath();
         astar.init(0, 1, 1, 0.5);
 
         assertEquals(1, ((AStar.AStarEntry) fromRef.get()).weightOfVisitedPath, .1);
diff --git a/core/src/test/java/com/graphhopper/routing/DirectedBidirectionalDijkstraTest.java b/core/src/test/java/com/graphhopper/routing/DirectedBidirectionalDijkstraTest.java
new file mode 100644
index 000000000..0a8e28613
--- /dev/null
+++ b/core/src/test/java/com/graphhopper/routing/DirectedBidirectionalDijkstraTest.java
@@ -0,0 +1,564 @@
+package com.graphhopper.routing;
+
+import com.carrotsearch.hppc.IntArrayList;
+import com.graphhopper.Repeat;
+import com.graphhopper.RepeatRule;
+import com.graphhopper.routing.util.*;
+import com.graphhopper.routing.weighting.*;
+import com.graphhopper.storage.*;
+import com.graphhopper.storage.index.LocationIndex;
+import com.graphhopper.storage.index.LocationIndexTree;
+import com.graphhopper.storage.index.QueryResult;
+import com.graphhopper.util.EdgeIteratorState;
+import com.graphhopper.util.GHUtility;
+import org.junit.Before;
+import org.junit.Ignore;
+import org.junit.Rule;
+import org.junit.Test;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Random;
+
+import static com.graphhopper.util.EdgeIterator.ANY_EDGE;
+import static com.graphhopper.util.EdgeIterator.NO_EDGE;
+import static org.junit.Assert.*;
+import static org.junit.Assert.assertEquals;
+
+/**
+ * This test makes sure that {@link DijkstraBidirectionRef#calcPath(int from, int to, int fromOutEdge, int toInEdge)}, i.e.
+ * calculating a path with restricted/enforced first/last edges works as expected.
+ * <p>
+ * For other bidirectional algorithms we simply compare with {@link DijkstraBidirectionRef} in {@link DirectedRoutingTest}
+ */
+public class DirectedBidirectionalDijkstraTest {
+    private Directory dir;
+    private TurnCostExtension turnCostExtension;
+    private int maxTurnCosts;
+    private GraphHopperStorage graph;
+    private FlagEncoder encoder;
+    private EncodingManager encodingManager;
+    private Weighting weighting;
+    private LocationIndex locationIndex;
+    private QueryGraph queryGraph;
+
+    @Rule
+    public RepeatRule repeatRule = new RepeatRule();
+
+    @Before
+    public void setup() {
+        dir = new RAMDirectory();
+        maxTurnCosts = 10;
+        encoder = new CarFlagEncoder(5, 5, maxTurnCosts);
+        encodingManager = EncodingManager.create(encoder);
+        turnCostExtension = new TurnCostExtension();
+        graph = new GraphHopperStorage(dir, encodingManager, false, turnCostExtension).create(1000);
+        weighting = createWeighting(Double.POSITIVE_INFINITY);
+    }
+
+    private Weighting createWeighting(double defaultUTurnCosts) {
+        return new TurnWeighting(new FastestWeighting(encoder), turnCostExtension, defaultUTurnCosts);
+    }
+
+    @Test
+    public void connectionNotFound() {
+        // nodes 0 and 2 are not connected
+        // 0 -> 1     2 -> 3
+        graph.edge(0, 1, 1, false);
+        graph.edge(2, 3, 1, false);
+
+        Path path = calcPath(0, 3, 0, 1);
+        assertNotFound(path);
+    }
+
+    @Test
+    public void singleEdge() {
+        graph.edge(0, 1, 1, true);
+
+        // source edge does not exist -> no path
+        assertNotFound(calcPath(0, 1, 5, 0));
+        // target edge does not exist -> no path
+        assertNotFound(calcPath(0, 1, 0, 5));
+        // using NO_EDGE -> no path
+        assertNotFound(calcPath(0, 1, NO_EDGE, 0));
+        assertNotFound(calcPath(0, 1, 0, NO_EDGE));
+        // using ANY_EDGE -> no restriction
+        assertPath(calcPath(0, 1, ANY_EDGE, 0), 0.06, 1, 60, nodes(0, 1));
+        assertPath(calcPath(0, 1, 0, ANY_EDGE), 0.06, 1, 60, nodes(0, 1));
+        // edges exist -> they are used as restrictions
+        assertPath(calcPath(0, 1, 0, 0), 0.06, 1, 60, nodes(0, 1));
+    }
+
+    @Test
+    public void simpleGraph() {
+        // 0 -> 1 -> 2
+        graph.edge(0, 1, 1, true);
+        graph.edge(1, 2, 1, true);
+
+        // source edge does not exist -> no path
+        assertNotFound(calcPath(0, 2, 5, 0));
+        // target edge does not exist -> no path
+        assertNotFound(calcPath(0, 2, 0, 5));
+        // using NO_EDGE -> no  path
+        assertNotFound(calcPath(0, 2, NO_EDGE, 0));
+        assertNotFound(calcPath(0, 2, 0, NO_EDGE));
+        // using ANY_EDGE -> no restriction
+        assertPath(calcPath(0, 2, ANY_EDGE, 1), 0.12, 2, 120, nodes(0, 1, 2));
+        assertPath(calcPath(0, 2, 0, ANY_EDGE), 0.12, 2, 120, nodes(0, 1, 2));
+        // edges exist -> they are used as restrictions
+        assertPath(calcPath(0, 2, 0, 1), 0.12, 2, 120, nodes(0, 1, 2));
+    }
+
+    @Test
+    public void sourceEqualsTarget() {
+        // Since we are enforcing source/target edges, starting and arriving at the same node normally does not yield
+        // zero weight. Either the weight is finite (using a real path back to the source node) or the
+        // weight is infinite (when no such path exists). The exception of course would involve zero weight edges.
+        // 0 - 1
+        //  \  |
+        //   - 2
+        graph.edge(0, 1, 1, true);
+        graph.edge(0, 2, 1, true);
+        graph.edge(1, 2, 1, true);
+        assertPath(calcPath(0, 0, 0, 1), 0.18, 3, 180, nodes(0, 1, 2, 0));
+        assertPath(calcPath(0, 0, 1, 0), 0.18, 3, 180, nodes(0, 2, 1, 0));
+        // without restrictions the weight should be zero
+        assertPath(calcPath(0, 0, ANY_EDGE, ANY_EDGE), 0, 0, 0, nodes(0));
+        // in some cases no path is possible
+        assertNotFound(calcPath(0, 0, 1, 1));
+        assertNotFound(calcPath(0, 0, 5, 1));
+    }
+
+    @Test
+    public void restrictedEdges() {
+        // =: costly edge
+        // 0 = 1 - 2 - 3 = 4
+        //  \      |      /
+        //   - 5 - 6 - 7 -
+        int costlySource = graph.edge(0, 1, 5, true).getEdge();
+        graph.edge(1, 2, 1, true);
+        graph.edge(2, 3, 1, true);
+        int costlyTarget = graph.edge(3, 4, 5, true).getEdge();
+        int cheapSource = graph.edge(0, 5, 1, true).getEdge();
+        graph.edge(5, 6, 1, true);
+        graph.edge(6, 7, 1, true);
+        int cheapTarget = graph.edge(7, 4, 1, true).getEdge();
+        graph.edge(2, 6, 1, true);
+
+        assertPath(calcPath(0, 4, cheapSource, cheapTarget), 0.24, 4, 240, nodes(0, 5, 6, 7, 4));
+        assertPath(calcPath(0, 4, cheapSource, costlyTarget), 0.54, 9, 540, nodes(0, 5, 6, 2, 3, 4));
+        assertPath(calcPath(0, 4, costlySource, cheapTarget), 0.54, 9, 540, nodes(0, 1, 2, 6, 7, 4));
+        assertPath(calcPath(0, 4, costlySource, costlyTarget), 0.72, 12, 720, nodes(0, 1, 2, 3, 4));
+    }
+
+    @Test
+    public void notConnectedDueToRestrictions() {
+        //   - 1 -
+        //  /     \
+        // 0       2
+        //  \     /
+        //   - 3 -
+        // we cannot go from 0 to 2 if we enforce north-south or south-north
+        int sourceNorth = graph.edge(0, 1, 1, true).getEdge();
+        int sourceSouth = graph.edge(0, 3, 2, true).getEdge();
+        int targetNorth = graph.edge(1, 2, 3, true).getEdge();
+        int targetSouth = graph.edge(3, 2, 4, true).getEdge();
+
+        assertPath(calcPath(0, 2, sourceNorth, targetNorth), 0.24, 4, 240, nodes(0, 1, 2));
+        assertNotFound(calcPath(0, 2, sourceNorth, targetSouth));
+        assertNotFound(calcPath(0, 2, sourceSouth, targetNorth));
+        assertPath(calcPath(0, 2, sourceSouth, targetSouth), 0.36, 6, 360, nodes(0, 3, 2));
+    }
+
+    @Test
+    public void restrictions_one_ways() {
+        // 0 <- 1 <- 2
+        //  \   |   /
+        //   >--3-->
+        graph.edge(0, 3, 1, false);
+        graph.edge(1, 0, 1, false);
+        graph.edge(3, 2, 1, false);
+        graph.edge(2, 1, 1, false);
+        graph.edge(1, 3, 1, true);
+
+        assertPath(calcPath(0, 2, 0, 2), 0.12, 2, 120, nodes(0, 3, 2));
+        assertNotFound(calcPath(0, 2, 1, 2));
+        assertNotFound(calcPath(0, 2, 0, 3));
+        assertNotFound(calcPath(0, 2, 1, 3));
+    }
+
+    @Test
+    public void forcingDirectionDoesNotMeanWeCannotUseEdgeAtAll() {
+        // 0 - 6 - 7
+        // |
+        // 1
+        // |
+        // 2 - 3
+        // |   |
+        // 5 - 4
+        int north = graph.edge(1, 0, 1, true).getEdge();
+        int south = graph.edge(1, 2, 1, true).getEdge();
+        graph.edge(2, 5, 1, false);
+        graph.edge(5, 4, 1, false);
+        graph.edge(4, 3, 1, false);
+        graph.edge(3, 2, 1, false);
+        graph.edge(1, 0, 1, false);
+        graph.edge(0, 6, 1, false);
+        int targetEdge = graph.edge(6, 7, 1, false).getEdge();
+        assertPath(calcPath(1, 7, north, targetEdge), 0.18, 3, 180, nodes(1, 0, 6, 7));
+        assertPath(calcPath(1, 7, south, targetEdge), 0.54, 9, 540, nodes(1, 2, 5, 4, 3, 2, 1, 0, 6, 7));
+    }
+
+    @Test
+    public void directedCircle() {
+        // 0---6--1 -> 2
+        // |          /
+        // 5 <- 4 <- 3
+        graph.edge(0, 6, 1, true);
+        graph.edge(6, 1, 1, true);
+        graph.edge(1, 2, 1, false);
+        graph.edge(2, 3, 1, false);
+        graph.edge(3, 4, 1, false);
+        graph.edge(4, 5, 1, false);
+        graph.edge(5, 0, 1, false);
+        assertPath(calcPath(6, 0, 1, 6), 0.36, 6, 360, nodes(6, 1, 2, 3, 4, 5, 0));
+    }
+
+    @Test
+    public void directedRouting() {
+        // =: costly edge
+        //   0 - 1   3 = 4
+        //   |    \ /    |
+        //   9     2     10
+        //   |    / \    |
+        //   8 = 7   6 = 5
+        graph.edge(0, 1, 1, true);
+        graph.edge(1, 2, 1, true);
+        graph.edge(2, 3, 1, true);
+        graph.edge(3, 4, 3, true);
+        int rightNorth = graph.edge(4, 10, 1, true).getEdge();
+        int rightSouth = graph.edge(10, 5, 1, true).getEdge();
+        graph.edge(5, 6, 2, true);
+        graph.edge(6, 2, 1, true);
+        graph.edge(2, 7, 1, true);
+        graph.edge(7, 8, 9, true);
+        int leftSouth = graph.edge(8, 9, 1, true).getEdge();
+        int leftNorth = graph.edge(9, 0, 1, true).getEdge();
+
+        // make paths fully deterministic by applying some turn costs at junction node 2
+        addTurnCost(7, 2, 3, 1);
+        addTurnCost(7, 2, 6, 3);
+        addTurnCost(1, 2, 3, 5);
+        addTurnCost(1, 2, 6, 7);
+        addTurnCost(1, 2, 7, 9);
+
+        final double unitEdgeWeight = 0.06;
+        assertPath(calcPath(9, 9, leftNorth, leftSouth),
+                23 * unitEdgeWeight + 5, 23, (long) ((23 * unitEdgeWeight + 5) * 1000),
+                nodes(9, 0, 1, 2, 3, 4, 10, 5, 6, 2, 7, 8, 9));
+        assertPath(calcPath(9, 9, leftSouth, leftNorth),
+                14 * unitEdgeWeight, 14, (long) ((14 * unitEdgeWeight) * 1000),
+                nodes(9, 8, 7, 2, 1, 0, 9));
+        assertPath(calcPath(9, 10, leftSouth, rightSouth),
+                15 * unitEdgeWeight + 3, 15, (long) ((15 * unitEdgeWeight + 3) * 1000),
+                nodes(9, 8, 7, 2, 6, 5, 10));
+        assertPath(calcPath(9, 10, leftSouth, rightNorth),
+                16 * unitEdgeWeight + 1, 16, (long) ((16 * unitEdgeWeight + 1) * 1000),
+                nodes(9, 8, 7, 2, 3, 4, 10));
+    }
+
+    @Test
+    public void enforceLoopEdge() {
+        //  o       o
+        //  0 - 1 - 2
+        graph.edge(0, 0, 1, true);
+        graph.edge(0, 1, 1, true);
+        graph.edge(1, 2, 1, true);
+        graph.edge(2, 2, 1, true);
+
+        assertPath(calcPath(0, 2, ANY_EDGE, ANY_EDGE), 0.12, 2, 120, nodes(0, 1, 2));
+        assertPath(calcPath(0, 2, 1, 2), 0.12, 2, 120, nodes(0, 1, 2));
+        // we can enforce taking the loop at start/target
+        assertPath(calcPath(0, 2, 0, 2), 0.18, 3, 180, nodes(0, 0, 1, 2));
+        assertPath(calcPath(0, 2, 1, 3), 0.18, 3, 180, nodes(0, 1, 2, 2));
+        assertPath(calcPath(0, 2, 0, 3), 0.24, 4, 240, nodes(0, 0, 1, 2, 2));
+    }
+
+    @Test
+    public void sourceAndTargetAreNeighbors() {
+        // 0-1-2-3
+        graph.edge(0, 1, 100, true);
+        graph.edge(1, 2, 100, true);
+        graph.edge(2, 3, 100, true);
+        assertPath(calcPath(1, 2, ANY_EDGE, ANY_EDGE), 6, 100, 6000, nodes(1, 2));
+        assertPath(calcPath(1, 2, 1, ANY_EDGE), 6, 100, 6000, nodes(1, 2));
+        assertPath(calcPath(1, 2, ANY_EDGE, 1), 6, 100, 6000, nodes(1, 2));
+        assertPath(calcPath(1, 2, 1, 1), 6, 100, 6000, nodes(1, 2));
+        // this case is a bit sketchy: we may not find a valid path just because the from/to
+        // node initialization hits the target/source node, but we have to also consider the
+        // edge restriction at the source/target nodes
+        assertNotFound(calcPath(1, 2, 1, 2));
+        assertNotFound(calcPath(1, 2, 0, 1));
+        assertNotFound(calcPath(1, 2, 0, 2));
+
+        // if we allow u-turns it is of course different again
+        assertPath(calcPath(1, 2, 1, 2, createWeighting(100)), 118, 300, 118000, nodes(1, 2, 3, 2));
+        assertPath(calcPath(1, 2, 0, 1, createWeighting(100)), 118, 300, 118000, nodes(1, 0, 1, 2));
+        assertPath(calcPath(1, 2, 0, 2, createWeighting(100)), 230, 500, 230000, nodes(1, 0, 1, 2, 3, 2));
+    }
+
+    @Test
+    public void worksWithTurnCosts() {
+        // 0 - 1 - 2
+        // |   |   |
+        // 3 - 4 - 5
+        graph.edge(0, 1, 1, true);
+        graph.edge(1, 2, 1, true);
+        graph.edge(1, 4, 1, true);
+        graph.edge(0, 3, 1, true);
+        graph.edge(3, 4, 1, true);
+        graph.edge(4, 5, 1, true);
+        graph.edge(5, 2, 1, true);
+
+        addRestriction(0, 3, 4);
+        addTurnCost(4, 5, 2, 6);
+
+        // due to the restrictions we have to take the expensive path with turn costs
+        assertPath(calcPath(0, 2, 0, 6), 6.24, 4, 6240, nodes(0, 1, 4, 5, 2));
+        // enforcing going south from node 0 yields no path, because of the restricted turn 0->3->4
+        assertNotFound(calcPath(0, 2, 3, ANY_EDGE));
+        // without the restriction its possible
+        assertPath(calcPath(0, 2, ANY_EDGE, ANY_EDGE), 0.12, 2, 120, nodes(0, 1, 2));
+    }
+
+    @Test
+    public void finiteUTurnCosts() {
+        // = expensive edge
+        //      3 - 4
+        //      |   |
+        //      2 = 5
+        //      |
+        // 0 -- 1 -- 6
+        // |         |
+        // 7 -- 8 -- 9
+        int right0 = graph.edge(0, 1, 10, true).getEdge();
+        graph.edge(1, 2, 10, true);
+        graph.edge(2, 3, 10, true);
+        graph.edge(3, 4, 10, true);
+        graph.edge(4, 5, 10, true);
+        graph.edge(5, 2, 1000, true);
+        int left6 = graph.edge(1, 6, 10, true).getEdge();
+        int left0 = graph.edge(0, 7, 10, true).getEdge();
+        graph.edge(7, 8, 10, true);
+        graph.edge(8, 9, 10, true);
+        int right6 = graph.edge(9, 6, 10, true).getEdge();
+
+        // enforce p-turn (using the loop in clockwise direction)
+        addRestriction(0, 1, 6);
+        addRestriction(5, 4, 3);
+
+        assertPath(calcPath(0, 6, right0, left6), 64.2, 1070, 64200, nodes(0, 1, 2, 3, 4, 5, 2, 1, 6));
+        // if the u-turn cost is finite it depends on its value if we rather do the p-turn or do an immediate u-turn at node 2
+        assertPath(calcPath(0, 6, right0, left6, createWeighting(65)), 64.2, 1070, 64200, nodes(0, 1, 2, 3, 4, 5, 2, 1, 6));
+        assertPath(calcPath(0, 6, right0, left6, createWeighting(40)), 42.4, 40, 42400, nodes(0, 1, 2, 1, 6));
+
+        assertPath(calcPath(0, 6, left0, right6), 2.4, 40, 2400, nodes(0, 7, 8, 9, 6));
+        assertPath(calcPath(0, 6, left0, left6), 66.6, 1110, 66600, nodes(0, 7, 8, 9, 6, 1, 2, 3, 4, 5, 2, 1, 6));
+        // if the u-turn cost is finite we do a u-turn at node 1 (not at node 7 at the beginning!)
+        assertPath(calcPath(0, 6, left0, left6, createWeighting(40)), 43.6, 60, 43600, nodes(0, 7, 8, 9, 6, 1, 6));
+    }
+
+    @Test
+    @Repeat(times = 10)
+    public void compare_standard_dijkstra() {
+        compare_with_dijkstra(weighting);
+    }
+
+    @Test
+    @Repeat(times = 10)
+    public void compare_standard_dijkstra_finite_uturn_costs() {
+        compare_with_dijkstra(createWeighting(40));
+    }
+
+    private void compare_with_dijkstra(Weighting w) {
+        // if we do not use start/target edge restrictions we should get the same result as with Dijkstra.
+        // basically this test should cover all kinds of interesting cases except the ones where we restrict the
+        // start/target edges.
+        final long seed = System.nanoTime();
+        final int numQueries = 1000;
+        System.out.println("compare_standard_dijkstra seed: " + seed);
+
+        Random rnd = new Random(seed);
+        int numNodes = 100;
+        GHUtility.buildRandomGraph(graph, rnd, numNodes, 2.2, true, true, encoder.getAverageSpeedEnc(), 0.7, 0.8, 0.8);
+        GHUtility.addRandomTurnCosts(graph, seed, encoder, maxTurnCosts, turnCostExtension);
+
+        long numStrictViolations = 0;
+        for (int i = 0; i < numQueries; i++) {
+            int source = rnd.nextInt(numNodes);
+            int target = rnd.nextInt(numNodes);
+            Path dijkstraPath = new Dijkstra(graph, w, TraversalMode.EDGE_BASED).calcPath(source, target);
+            Path path = calcPath(source, target, ANY_EDGE, ANY_EDGE, w);
+            assertEquals("dijkstra found/did not find a path, from: " + source + ", to: " + target, dijkstraPath.isFound(), path.isFound());
+            assertEquals("weight does not match dijkstra, from: " + source + ", to: " + target, dijkstraPath.getWeight(), path.getWeight(), 1.e-6);
+            // we do not do a strict check because there can be ambiguity, for example when there are zero weight loops.
+            // however, when there are too many deviations we fail
+            if (
+                    Math.abs(dijkstraPath.getDistance() - path.getDistance()) > 1.e-6
+                            || Math.abs(dijkstraPath.getTime() - path.getTime()) > 10
+                            || !dijkstraPath.calcNodes().equals(path.calcNodes())) {
+                numStrictViolations++;
+            }
+        }
+        if (numStrictViolations > Math.max(1, 0.05 * numQueries)) {
+            fail("Too many strict violations: " + numStrictViolations + " / " + numQueries);
+        }
+    }
+
+    @Test
+    public void blockArea() {
+        // 0 - 1 - 2 - 3
+        // |           |
+        // 4 --- 5 --- 6
+        EdgeIteratorState edge1 = graph.edge(0, 1, 10, true);
+        graph.edge(1, 2, 10, true);
+        EdgeIteratorState edge2 = graph.edge(2, 3, 10, true);
+        graph.edge(0, 4, 100, true);
+        graph.edge(4, 5, 100, true);
+        graph.edge(5, 6, 100, true);
+        graph.edge(6, 3, 100, true);
+
+        // usually we would take the direct route
+        assertPath(calcPath(0, 3, ANY_EDGE, ANY_EDGE), 1.8, 30, 1800, nodes(0, 1, 2, 3));
+
+        // with forced edges we might have to go around
+        assertPath(calcPath(0, 3, 3, ANY_EDGE), 24, 400, 24000, nodes(0, 4, 5, 6, 3));
+        assertPath(calcPath(0, 3, ANY_EDGE, 6), 24, 400, 24000, nodes(0, 4, 5, 6, 3));
+
+        // with avoided edges we also have to take a longer route
+        assertPath(calcPath(0, 3, ANY_EDGE, ANY_EDGE, createAvoidEdgeWeighting(edge1)), 24, 400, 24000, nodes(0, 4, 5, 6, 3));
+        assertPath(calcPath(0, 3, ANY_EDGE, ANY_EDGE, createAvoidEdgeWeighting(edge2)), 24, 400, 24000, nodes(0, 4, 5, 6, 3));
+
+        // enforcing forbidden start/target edges still does not allow using them
+        assertNotFound(calcPath(0, 3, edge1.getEdge(), edge2.getEdge(), createAvoidEdgeWeighting(edge1)));
+        assertNotFound(calcPath(0, 3, edge1.getEdge(), edge2.getEdge(), createAvoidEdgeWeighting(edge2)));
+
+        // .. even when the nodes are just next to each other
+        assertNotFound(calcPath(0, 1, edge1.getEdge(), ANY_EDGE, createAvoidEdgeWeighting(edge1)));
+        assertNotFound(calcPath(0, 1, ANY_EDGE, edge2.getEdge(), createAvoidEdgeWeighting(edge2)));
+    }
+
+    private AvoidEdgesWeighting createAvoidEdgeWeighting(EdgeIteratorState edgeOut) {
+        AvoidEdgesWeighting avoidEdgesWeighting = new AvoidEdgesWeighting(weighting);
+        avoidEdgesWeighting.setEdgePenaltyFactor(Double.POSITIVE_INFINITY);
+        avoidEdgesWeighting.addEdges(Collections.singletonList(edgeOut));
+        return avoidEdgesWeighting;
+    }
+
+    @Test
+    public void directedRouting_noUTurnAtVirtualEdge() {
+        // what happens if we force to leave the snapped (virtual) node in eastern direction, even though we would
+        // like to go to node 0 just west from us ? we have to make sure there is no u-turn at node 1 (from the
+        // virtual edge onto edge 1-0). the query graph does this for us!
+
+        //    x
+        // 0 -- 1 -> 2
+        // |         |
+        // 5 <- 4 <- 3
+        graph.edge(0, 1, 1, true);
+        graph.edge(1, 2, 1, false);
+        graph.edge(2, 3, 1, false);
+        graph.edge(3, 4, 1, false);
+        graph.edge(4, 5, 1, false);
+        graph.edge(5, 0, 1, false);
+        NodeAccess na = graph.getNodeAccess();
+        na.setNode(0, 1, 0);
+        na.setNode(1, 1, 1);
+        na.setNode(2, 1, 2);
+        na.setNode(3, 0, 2);
+        na.setNode(4, 0, 1);
+        na.setNode(5, 0, 0);
+        initQueryGraph();
+
+        QueryResult qr = findClosest();
+        assertEquals("wanted to get EDGE", QueryResult.Position.EDGE, qr.getSnappedPosition());
+        assertEquals(6, qr.getClosestNode());
+
+        // check what edges there are on the query graph directly, there should not be a direct connection from 1 to 0
+        // anymore, but only the virtual edge from 1 to 6 (this is how the u-turn is prevented).
+        assertEquals(new HashSet<>(Arrays.asList(0, 2)), GHUtility.getNeighbors(graph.createEdgeExplorer().setBaseNode(1)));
+        assertEquals(new HashSet<>(Arrays.asList(6, 2)), GHUtility.getNeighbors(queryGraph.createEdgeExplorer().setBaseNode(1)));
+
+        EdgeIteratorState virtualEdge = GHUtility.getEdge(queryGraph, 6, 1);
+        int outEdge = virtualEdge.getEdge();
+        AbstractBidirAlgo algo = createAlgo(queryGraph, weighting);
+        Path path = algo.calcPath(6, 0, outEdge, ANY_EDGE);
+        assertEquals(nodes(6, 1, 2, 3, 4, 5, 0), path.calcNodes());
+        assertEquals(5 + virtualEdge.getDistance(), path.getDistance(), 1.e-3);
+    }
+
+    private void initQueryGraph() {
+        queryGraph = new QueryGraph(graph);
+        locationIndex = new LocationIndexTree(graph, dir);
+        locationIndex.prepareIndex();
+    }
+
+    private QueryResult findClosest() {
+        QueryResult qr = locationIndex.findClosest(1.1, 0.5, EdgeFilter.ALL_EDGES);
+        queryGraph.lookup(Collections.singletonList(qr));
+        return qr;
+    }
+
+    private Path calcPath(int source, int target, int sourceOutEdge, int targetInEdge) {
+        return calcPath(source, target, sourceOutEdge, targetInEdge, weighting);
+    }
+
+    private Path calcPath(int source, int target, int sourceOutEdge, int targetInEdge, Weighting w) {
+        AbstractBidirAlgo algo = createAlgo(graph, w);
+        return algo.calcPath(source, target, sourceOutEdge, targetInEdge);
+    }
+
+    private AbstractBidirAlgo createAlgo(Graph graph, Weighting weighting) {
+        return new DijkstraBidirectionRef(graph, weighting, TraversalMode.EDGE_BASED);
+    }
+
+    private void addRestriction(int fromNode, int node, int toNode) {
+        turnCostExtension.addTurnInfo(
+                GHUtility.getEdge(graph, fromNode, node).getEdge(),
+                node,
+                GHUtility.getEdge(graph, node, toNode).getEdge(),
+                encoder.getTurnFlags(true, 0)
+        );
+    }
+
+    private void addTurnCost(int fromNode, int node, int toNode, double turnCost) {
+        turnCostExtension.addTurnInfo(
+                GHUtility.getEdge(graph, fromNode, node).getEdge(),
+                node,
+                GHUtility.getEdge(graph, node, toNode).getEdge(),
+                encoder.getTurnFlags(false, turnCost)
+        );
+    }
+
+    private IntArrayList nodes(int... nodes) {
+        return IntArrayList.from(nodes);
+    }
+
+    private void assertPath(Path path, double weight, double distance, long time, IntArrayList nodes) {
+        assertTrue("expected a path, but no path was found", path.isFound());
+        assertEquals("unexpected weight", weight, path.getWeight(), 1.e-6);
+        assertEquals("unexpected distance", distance, path.getDistance(), 1.e-6);
+        assertEquals("unexpected time", time, path.getTime());
+        assertEquals("unexpected nodes", nodes, path.calcNodes());
+    }
+
+    private void assertNotFound(Path path) {
+        assertFalse("expected no path, but a path was found", path.isFound());
+        assertEquals(Double.MAX_VALUE, path.getWeight(), 1.e-6);
+        // if no path is found dist&time are zero, see core #1566
+        assertEquals(0, path.getDistance(), 1.e-6);
+        assertEquals(0, path.getTime());
+        assertEquals(nodes(), path.calcNodes());
+    }
+}
diff --git a/core/src/test/java/com/graphhopper/routing/weighting/DirectedRoutingTest.java b/core/src/test/java/com/graphhopper/routing/weighting/DirectedRoutingTest.java
new file mode 100644
index 000000000..f71d19f0d
--- /dev/null
+++ b/core/src/test/java/com/graphhopper/routing/weighting/DirectedRoutingTest.java
@@ -0,0 +1,325 @@
+package com.graphhopper.routing.weighting;
+
+import com.graphhopper.Repeat;
+import com.graphhopper.RepeatRule;
+import com.graphhopper.routing.*;
+import com.graphhopper.routing.ch.PrepareContractionHierarchies;
+import com.graphhopper.routing.lm.PrepareLandmarks;
+import com.graphhopper.routing.util.*;
+import com.graphhopper.storage.*;
+import com.graphhopper.storage.index.LocationIndex;
+import com.graphhopper.storage.index.LocationIndexTree;
+import com.graphhopper.storage.index.QueryResult;
+import com.graphhopper.util.CHEdgeIteratorState;
+import com.graphhopper.util.EdgeExplorer;
+import com.graphhopper.util.EdgeIterator;
+import com.graphhopper.util.GHUtility;
+import com.graphhopper.util.shapes.BBox;
+import com.graphhopper.util.shapes.GHPoint;
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+import java.util.*;
+
+import static com.graphhopper.util.EdgeIterator.ANY_EDGE;
+import static com.graphhopper.util.EdgeIterator.NO_EDGE;
+import static com.graphhopper.util.Parameters.Algorithms.ASTAR_BI;
+import static com.graphhopper.util.Parameters.Algorithms.DIJKSTRA_BI;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+/**
+ * This test makes sure the different bidirectional routing algorithms correctly implement restrictions of the source/
+ * target edges, by comparing with {@link DijkstraBidirectionRef}
+ *
+ * @author easbar
+ * @see DirectedBidirectionalDijkstraTest
+ */
+@RunWith(Parameterized.class)
+public class DirectedRoutingTest {
+    private final Algo algo;
+    private final double uTurnCosts;
+    private final boolean prepareCH;
+    private final boolean prepareLM;
+    private Directory dir;
+    private GraphHopperStorage graph;
+    private CHGraph chGraph;
+    private CarFlagEncoder encoder;
+    private TurnCostExtension turnCostExtension;
+    private int maxTurnCosts;
+    private Weighting weighting;
+    private EncodingManager encodingManager;
+    private PrepareContractionHierarchies pch;
+    private PrepareLandmarks lm;
+
+    @Rule
+    public RepeatRule repeatRule = new RepeatRule();
+
+    @Parameterized.Parameters(name = "{0}, u-turn-costs: {1}")
+    public static Collection<Object[]> params() {
+        return Arrays.asList(new Object[][]{
+                {Algo.ASTAR, Double.POSITIVE_INFINITY, false, false},
+                {Algo.CH_ASTAR, Double.POSITIVE_INFINITY, true, false},
+                {Algo.CH_DIJKSTRA, Double.POSITIVE_INFINITY, true, false},
+                // todo: yields warnings and fails, see #1665, #1687
+//                {Algo.LM, Double.POSITIVE_INFINITY, false, true}
+                {Algo.ASTAR, 40, false, false},
+                // todo: CH does not handle finite u-turn costs so far, see #1652
+//                {Algo.CH_ASTAR, 40, true, false},
+//                {Algo.CH_DIJKSTRA, 40, true, false},
+                // todo: yields warnings and fails, see #1665, 1687
+//                {Algo.LM, 40, false, true}
+                // todo: add AlternativeRoute ?
+        });
+    }
+
+    private enum Algo {
+        ASTAR,
+        CH_ASTAR,
+        CH_DIJKSTRA,
+        LM
+    }
+
+    public DirectedRoutingTest(Algo algo, double uTurnCosts, boolean prepareCH, boolean prepareLM) {
+        this.algo = algo;
+        this.uTurnCosts = uTurnCosts;
+        this.prepareCH = prepareCH;
+        this.prepareLM = prepareLM;
+    }
+
+    @Before
+    public void init() {
+        dir = new RAMDirectory();
+        maxTurnCosts = 10;
+        // todonow: make this work with speed_both_directions=true!
+        encoder = new CarFlagEncoder(5, 5, maxTurnCosts);
+        encodingManager = EncodingManager.create(encoder);
+        weighting = new FastestWeighting(encoder);
+        turnCostExtension = new TurnCostExtension();
+        graph = createGraph();
+        chGraph = graph.getCHGraph();
+    }
+
+    private void preProcessGraph() {
+        graph.freeze();
+        if (!prepareCH && !prepareLM) {
+            return;
+        }
+        if (prepareCH) {
+            pch = new PrepareContractionHierarchies(chGraph, weighting, TraversalMode.EDGE_BASED);
+            pch.doWork();
+        }
+        if (prepareLM) {
+            lm = new PrepareLandmarks(dir, graph, weighting, 16, 8);
+            lm.setMaximumWeight(1000);
+            lm.doWork();
+        }
+    }
+
+    private AbstractBidirAlgo createAlgo() {
+        return createAlgo(prepareCH ? chGraph : graph);
+    }
+
+    private AbstractBidirAlgo createAlgo(Graph graph) {
+        switch (algo) {
+            case ASTAR:
+                return new AStarBidirection(graph, createTurnWeighting(graph), TraversalMode.EDGE_BASED);
+            case CH_DIJKSTRA:
+                return (AbstractBidirAlgo) pch.createAlgo(graph, AlgorithmOptions.start().weighting(weighting).algorithm(DIJKSTRA_BI).build());
+            case CH_ASTAR:
+                return (AbstractBidirAlgo) pch.createAlgo(graph, AlgorithmOptions.start().weighting(weighting).algorithm(ASTAR_BI).build());
+            case LM:
+                AStarBidirection astarbi = new AStarBidirection(graph, createTurnWeighting(graph), TraversalMode.EDGE_BASED);
+                return (AbstractBidirAlgo) lm.getDecoratedAlgorithm(graph, astarbi, AlgorithmOptions.start().build());
+            default:
+                throw new IllegalArgumentException("unknown algo " + algo);
+        }
+    }
+
+    private TurnWeighting createTurnWeighting(Graph g) {
+        return new TurnWeighting(weighting, (TurnCostExtension) g.getExtension(), uTurnCosts);
+    }
+
+    @Test
+    @Repeat(times = 10)
+    public void randomGraph() {
+        final long seed = System.nanoTime();
+        System.out.println("random Graph seed: " + seed);
+        final int numQueries = 50;
+        Random rnd = new Random(seed);
+        GHUtility.buildRandomGraph(graph, rnd, 100, 2.2, true, true, encoder.getAverageSpeedEnc(), 0.7, 0.8, 0.8);
+        GHUtility.addRandomTurnCosts(graph, seed, encoder, maxTurnCosts, turnCostExtension);
+//        GHUtility.printGraphForUnitTest(graph, encoder);
+        preProcessGraph();
+        List<String> strictViolations = new ArrayList<>();
+        for (int i = 0; i < numQueries; i++) {
+            int source = getRandom(rnd);
+            int target = getRandom(rnd);
+            int sourceOutEdge = getSourceOutEdge(rnd, source, graph);
+            int targetInEdge = getTargetInEdge(rnd, target, graph);
+//            System.out.println("source: " + source + ", target: " + target + ", sourceOutEdge: " + sourceOutEdge + ", targetInEdge: " + targetInEdge);
+            Path refPath = new DijkstraBidirectionRef(graph, createTurnWeighting(graph), TraversalMode.EDGE_BASED)
+                    .calcPath(source, target, sourceOutEdge, targetInEdge);
+            Path path = createAlgo()
+                    .calcPath(source, target, sourceOutEdge, targetInEdge);
+            strictViolations.addAll(comparePaths(refPath, path, source, target));
+        }
+        if (strictViolations.size() > Math.max(1, 0.20 * numQueries)) {
+            for (String strictViolation : strictViolations) {
+                System.out.println("strict violation: " + strictViolation);
+            }
+            fail("Too many strict violations: " + strictViolations.size() + " / " + numQueries);
+        }
+    }
+
+    /**
+     * Similar to {@link #randomGraph()}, but using the {@link QueryGraph} as it is done in real usage.
+     */
+    @Test
+    @Repeat(times = 10)
+    public void randomGraph_withQueryGraph() {
+        final long seed = System.nanoTime();
+        System.out.println("randomGraph_withQueryGraph seed: " + seed);
+        final int numQueries = 50;
+
+        // we may not use an offset when query graph is involved, otherwise traveling via virtual edges will not be
+        // the same as taking the direct edge!
+        double pOffset = 0;
+        Random rnd = new Random(seed);
+        GHUtility.buildRandomGraph(graph, rnd, 50, 2.2, true, true, encoder.getAverageSpeedEnc(), 0.7, 0.8, pOffset);
+        GHUtility.addRandomTurnCosts(graph, seed, encoder, maxTurnCosts, turnCostExtension);
+//        GHUtility.printGraphForUnitTest(graph, encoder);
+        preProcessGraph();
+        LocationIndexTree index = new LocationIndexTree(graph, dir);
+        index.prepareIndex();
+        List<String> strictViolations = new ArrayList<>();
+        for (int i = 0; i < numQueries; i++) {
+            List<GHPoint> points = getRandomPoints(2, index, rnd);
+
+            List<QueryResult> chQueryResults = findQueryResults(index, points);
+            List<QueryResult> queryResults = findQueryResults(index, points);
+
+            QueryGraph chQueryGraph = new QueryGraph(prepareCH ? chGraph : graph);
+            QueryGraph queryGraph = new QueryGraph(graph);
+
+            chQueryGraph.lookup(chQueryResults);
+            queryGraph.lookup(queryResults);
+
+            int source = queryResults.get(0).getClosestNode();
+            int target = queryResults.get(1).getClosestNode();
+            Random tmpRnd1 = new Random(seed);
+            int sourceOutEdge = getSourceOutEdge(tmpRnd1, source, queryGraph);
+            int targetInEdge = getTargetInEdge(tmpRnd1, target, queryGraph);
+            Random tmpRnd2 = new Random(seed);
+            int chSourceOutEdge = getSourceOutEdge(tmpRnd2, source, chQueryGraph);
+            int chTargetInEdge = getTargetInEdge(tmpRnd2, target, chQueryGraph);
+
+            Path refPath = new DijkstraBidirectionRef(queryGraph, createTurnWeighting(queryGraph), TraversalMode.EDGE_BASED)
+                    .calcPath(source, target, sourceOutEdge, targetInEdge);
+            Path path = createAlgo(chQueryGraph)
+                    .calcPath(source, target, chSourceOutEdge, chTargetInEdge);
+            strictViolations.addAll(comparePaths(refPath, path, source, target));
+        }
+        // we do not do a strict check because there can be ambiguity, for example when there are zero weight loops.
+        // however, when there are too many deviations we fail
+        if (strictViolations.size() > Math.max(1, 0.20 * numQueries)) {
+            fail("Too many strict violations: " + strictViolations.size() + " / " + numQueries);
+        }
+    }
+
+    private List<GHPoint> getRandomPoints(int numPoints, LocationIndex index, Random rnd) {
+        List<GHPoint> points = new ArrayList<>(numPoints);
+        BBox bounds = graph.getBounds();
+        final int maxAttempts = 100 * numPoints;
+        int attempts = 0;
+        while (attempts < maxAttempts && points.size() < numPoints) {
+            double lat = rnd.nextDouble() * (bounds.maxLat - bounds.minLat) + bounds.minLat;
+            double lon = rnd.nextDouble() * (bounds.maxLon - bounds.minLon) + bounds.minLon;
+            QueryResult queryResult = index.findClosest(lat, lon, EdgeFilter.ALL_EDGES);
+            if (queryResult.isValid()) {
+                points.add(new GHPoint(lat, lon));
+            }
+            attempts++;
+        }
+        assertEquals("could not find valid random points after " + attempts + " attempts", numPoints, points.size());
+        return points;
+    }
+
+    private List<QueryResult> findQueryResults(LocationIndexTree index, List<GHPoint> ghPoints) {
+        List<QueryResult> result = new ArrayList<>(ghPoints.size());
+        for (GHPoint ghPoint : ghPoints) {
+            result.add(index.findClosest(ghPoint.getLat(), ghPoint.getLon(), DefaultEdgeFilter.ALL_EDGES));
+        }
+        return result;
+    }
+
+    private List<String> comparePaths(Path refPath, Path path, int source, int target) {
+        List<String> strictViolations = new ArrayList<>();
+        double refWeight = refPath.getWeight();
+        double weight = path.getWeight();
+        if (Math.abs(refWeight - weight) > 1.e-2) {
+            System.out.println("expected: " + refPath.calcNodes());
+            System.out.println("given:    " + path.calcNodes());
+            fail("wrong weight: " + source + "->" + target + ", expected: " + refWeight + ", given: " + weight);
+        }
+        if (Math.abs(path.getDistance() - refPath.getDistance()) > 1.e-1) {
+            strictViolations.add("wrong distance " + source + "->" + target + ", expected: " + refPath.getDistance() + ", given: " + path.getDistance());
+        }
+        if (Math.abs(path.getTime() - refPath.getTime()) > 50) {
+            strictViolations.add("wrong time " + source + "->" + target + ", expected: " + refPath.getTime() + ", given: " + path.getTime());
+        }
+        if (!refPath.calcNodes().equals(path.calcNodes())) {
+            strictViolations.add("wrong nodes " + source + "->" + target + "\nexpected: " + refPath.calcNodes() + "\ngiven:    " + path.calcNodes());
+        }
+        return strictViolations;
+    }
+
+    private GraphHopperStorage createGraph() {
+        GraphHopperStorage gh = new GraphHopperStorage(new ArrayList<Weighting>(), Collections.singletonList(weighting), dir, encodingManager,
+                false, turnCostExtension);
+        gh.create(1000);
+        return gh;
+    }
+
+    private int getTargetInEdge(Random rnd, int node, Graph graph) {
+        return getAdjEdge(rnd, node, graph);
+    }
+
+    private int getSourceOutEdge(Random rnd, int node, Graph graph) {
+        return getAdjEdge(rnd, node, graph);
+    }
+
+    private int getAdjEdge(Random rnd, int node, Graph graph) {
+        // sometimes do not restrict anything
+        if (rnd.nextDouble() < 0.05) {
+            return ANY_EDGE;
+        }
+        // sometimes use NO_EDGE
+        if (rnd.nextDouble() < 0.05) {
+            return NO_EDGE;
+        }
+        // use all edge explorer, sometimes we will find an edge we can restrict sometimes we do not
+        EdgeExplorer explorer = graph.createEdgeExplorer();
+        EdgeIterator iter = explorer.setBaseNode(node);
+        List<Integer> edgeIds = new ArrayList<>();
+        while (iter.next()) {
+            if (iter instanceof CHEdgeIteratorState && ((CHEdgeIteratorState) iter).isShortcut()) {
+                // skip shortcuts here so we get the same restricted edges for a normal query graph and a
+                // query graph that wraps a CH graph (provided that the rnd number generator is in the same
+                // state)!
+                continue;
+            }
+            edgeIds.add(iter.getOrigEdgeFirst());
+            edgeIds.add(iter.getOrigEdgeLast());
+        }
+        return edgeIds.isEmpty() ? ANY_EDGE : edgeIds.get(rnd.nextInt(edgeIds.size()));
+    }
+
+    private int getRandom(Random rnd) {
+        return rnd.nextInt(graph.getNodes());
+    }
+
+}