Repository: graphhopper/graphhopper
Pull request #1179 (2017-10-06 12:31:41)

Implements a simple version of stall-on-demand for CH queries.
This is a simple version of stall-on-demand that leads to a 1.5x speed up of CH queries on the osm map for Germany. Also see discussion in: https://github.com/graphhopper/graphhopper/issues/240.
I put the stall-on-demand version of the bidirectional ch dijkstra into a separate class, because PrepareContractionHierarchies already seems very large (?). I thought it would be better to leave it up to configuration whether stall-on-demand is used or not. I also added some measurement tests for stall on demand in the measurement class. Not sure if this is really needed, but for testing it is helpful at the moment. I might test some of the more aggressive versions of stall on demand if I find the time.

karussell: Wow, cool - will try!
karussell: Wow, really nice & thanks a lot! I can confirm this is a huge improvement from 3.9ms to 2.7ms in my case (measurement of Germany & car)
karussell: BTW: for disabled instructions the differences are even bigger: 2.9ms vs. 1.5ms!
devemux86: Seem impressive results!
boldtrn: Wow this sounds very impressive! If I understand we only stall a node when we are sure that the path via this node is worse than a previously found path. [We do this by checking the current weight + the weight to one of the next edges is higher than the previously calculated best weight](https://github.com/graphhopper/graphhopper/pull/1179/files#diff-5400334343d76e757c16a0bcc75896e4R70).

Could it happen that we due to this incorrectly stall a node and might not find the best path anymore?
```
Assume this is a part of a graph. We are calculating the shortest path from some node X that is to the left to node D.
The weight to Node C is 5
The weight to Node A is 4
The weight for the edge between A and C is 2.
If we now check if A is stallable, we check 4+2 > 5 => Ok, A is stallable
The weight of the edge A-B and B-C might be 1, but the weight of the edge C-D might be 5, but we stalled A, and cannot find the best path anymore.
------  C
     /      \
--  A - B - D 
```   

Probably this situation is impossible because of the hierarchy and due to this it is guaranteed that we always find the best path?
ammagamma: Thanks for testing everyone!
@boldtrn I am not sure if I understand your example completely. Checking if A is stallable happens when settling A during the bidirectional CH Dijkstra. A can be stalled if there is an incoming edge coming from a node such that the tentative distance of the neighboring node plus the edge weight is smaller than the tentative distance of A (5+2 would have to be smaller than 4 in your example).
But you are right, the stalling optimization is specific to the query algorithm in contraction hierarchies (and some other hierarchical approaches). It is guaranteed that the shortest path is always found. For example if a node that lies on a shortest path gets stalled it will be discovered by the backward search. It gets more complicated when one tries to stall not only the current node, but also other ones that are reached from the stalled node (aggressive stalling). In this case one might have to un-stall nodes later, but this does not apply for the simple version that is used here.
boldtrn: > But you are right, the stalling optimization is specific to the query algorithm in contraction hierarchies (and some other hierarchical approaches). It is guaranteed that the shortest path is always found.

Thanks for the answer. I thought that this would work due to the hierarchical properties of CH, but I couldn't proof it myself :). 

> For example if a node that lies on a shortest path gets stalled it will be discovered by the backward search.

Ah that's interesting, so the stalling only happens for one direction. That makes sense.


ammagamma: some integration tests are failing now that sod is used by default, will have a look ;)
ammagamma: Looks like I am too used to IntelliJ's organize imports feature ...

Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/AStarBidirectionCH.java b/core/src/main/java/com/graphhopper/routing/AStarBidirectionCH.java
new file mode 100644
index 000000000..7dd961447
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/AStarBidirectionCH.java
@@ -0,0 +1,60 @@
+/*
+ *  Licensed to GraphHopper GmbH under one or more contributor
+ *  license agreements. See the NOTICE file distributed with this work for 
+ *  additional information regarding copyright ownership.
+ * 
+ *  GraphHopper GmbH licenses this file to you under the Apache License, 
+ *  Version 2.0 (the "License"); you may not use this file except in 
+ *  compliance with the License. You may obtain a copy of the License at
+ * 
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+package com.graphhopper.routing;
+
+import com.graphhopper.routing.ch.Path4CH;
+import com.graphhopper.routing.util.TraversalMode;
+import com.graphhopper.routing.weighting.Weighting;
+import com.graphhopper.storage.Graph;
+
+public class AStarBidirectionCH extends AStarBidirection {
+    public AStarBidirectionCH(Graph graph, Weighting weighting, TraversalMode traversalMode) {
+        super(graph, weighting, traversalMode);
+    }
+
+    @Override
+    protected void initCollections(int size) {
+        super.initCollections(Math.min(size, 2000));
+    }
+
+    @Override
+    protected boolean finished() {
+        // we need to finish BOTH searches for CH!
+        if (finishedFrom && finishedTo)
+            return true;
+
+        // changed finish condition for CH
+        return currFrom.weight >= bestPath.getWeight() && currTo.weight >= bestPath.getWeight();
+    }
+
+    @Override
+    protected Path createAndInitPath() {
+        bestPath = new Path4CH(graph, graph.getBaseGraph(), weighting);
+        return bestPath;
+    }
+
+    @Override
+    public String getName() {
+        return "astarbi|ch";
+    }
+
+    @Override
+    public String toString() {
+        return getName() + "|" + weighting;
+    }
+}
diff --git a/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java b/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
index edece875d..771b9b85f 100644
--- a/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
+++ b/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
@@ -17,7 +17,6 @@
  */
 package com.graphhopper.routing;
 
-import com.graphhopper.routing.util.FlagEncoder;
 import com.graphhopper.routing.util.TraversalMode;
 import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.Graph;
diff --git a/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionCH.java b/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionCH.java
new file mode 100644
index 000000000..ffe70dfc4
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionCH.java
@@ -0,0 +1,95 @@
+/*
+ *  Licensed to GraphHopper GmbH under one or more contributor
+ *  license agreements. See the NOTICE file distributed with this work for 
+ *  additional information regarding copyright ownership.
+ * 
+ *  GraphHopper GmbH licenses this file to you under the Apache License, 
+ *  Version 2.0 (the "License"); you may not use this file except in 
+ *  compliance with the License. You may obtain a copy of the License at
+ * 
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+package com.graphhopper.routing;
+
+import com.carrotsearch.hppc.IntObjectMap;
+import com.graphhopper.routing.util.TraversalMode;
+import com.graphhopper.routing.weighting.Weighting;
+import com.graphhopper.storage.Graph;
+import com.graphhopper.storage.SPTEntry;
+import com.graphhopper.util.EdgeExplorer;
+import com.graphhopper.util.EdgeIterator;
+
+/**
+ * Uses a very simple version of stall-on-demand (SOD) for CH queries to prevent exploring nodes that can not be part
+ * of a shortest path. When a node that is about to be settled is stallable it is not expanded, but no further search
+ * for neighboring stallable nodes is performed.
+ *
+ * @author ammagamma
+ */
+public class DijkstraBidirectionCH extends DijkstraBidirectionCHNoSOD {
+    public DijkstraBidirectionCH(Graph graph, Weighting weighting, TraversalMode traversalMode) {
+        super(graph, weighting, traversalMode);
+    }
+
+    @Override
+    public boolean fillEdgesFrom() {
+        if (pqOpenSetFrom.isEmpty()) {
+            return false;
+        }
+        currFrom = pqOpenSetFrom.poll();
+        visitedCountFrom++;
+        if (entryIsStallable(currFrom, bestWeightMapFrom, inEdgeExplorer, false)) {
+            return true;
+        }
+        bestWeightMapOther = bestWeightMapTo;
+        fillEdges(currFrom, pqOpenSetFrom, bestWeightMapFrom, outEdgeExplorer, false);
+        return true;
+    }
+
+    @Override
+    public boolean fillEdgesTo() {
+        if (pqOpenSetTo.isEmpty()) {
+            return false;
+        }
+        currTo = pqOpenSetTo.poll();
+        visitedCountTo++;
+        if (entryIsStallable(currTo, bestWeightMapTo, outEdgeExplorer, true)) {
+            return true;
+        }
+        bestWeightMapOther = bestWeightMapFrom;
+        fillEdges(currTo, pqOpenSetTo, bestWeightMapTo, inEdgeExplorer, true);
+        return true;
+    }
+
+    @Override
+    public String getName() {
+        return "dijkstrabi|ch";
+    }
+
+    @Override
+    public String toString() {
+        return getName() + "|" + weighting;
+    }
+
+    private boolean entryIsStallable(SPTEntry entry, IntObjectMap<SPTEntry> bestWeightMap, EdgeExplorer edgeExplorer,
+                                     boolean reverse) {
+        // We check for all 'incoming' edges if we can prove that the current node (that is about to be settled) is 
+        // reached via a suboptimal path. We do this regardless of the CH level of the adjacent nodes.
+        EdgeIterator iter = edgeExplorer.setBaseNode(entry.adjNode);
+        while (iter.next()) {
+            int traversalId = traversalMode.createTraversalId(iter, reverse);
+            SPTEntry adjNode = bestWeightMap.get(traversalId);
+            if (adjNode != null &&
+                    adjNode.weight + weighting.calcWeight(iter, !reverse, entry.edge) < entry.weight) {
+                return true;
+            }
+        }
+        return false;
+    }
+}
diff --git a/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionCHNoSOD.java b/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionCHNoSOD.java
new file mode 100644
index 000000000..b810763ff
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionCHNoSOD.java
@@ -0,0 +1,60 @@
+/*
+ *  Licensed to GraphHopper GmbH under one or more contributor
+ *  license agreements. See the NOTICE file distributed with this work for 
+ *  additional information regarding copyright ownership.
+ * 
+ *  GraphHopper GmbH licenses this file to you under the Apache License, 
+ *  Version 2.0 (the "License"); you may not use this file except in 
+ *  compliance with the License. You may obtain a copy of the License at
+ * 
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+package com.graphhopper.routing;
+
+import com.graphhopper.routing.ch.Path4CH;
+import com.graphhopper.routing.util.TraversalMode;
+import com.graphhopper.routing.weighting.Weighting;
+import com.graphhopper.storage.Graph;
+
+public class DijkstraBidirectionCHNoSOD extends DijkstraBidirectionRef {
+    public DijkstraBidirectionCHNoSOD(Graph graph, Weighting weighting, TraversalMode traversalMode) {
+        super(graph, weighting, traversalMode);
+    }
+
+    @Override
+    protected void initCollections(int size) {
+        super.initCollections(Math.min(size, 2000));
+    }
+
+    @Override
+    public boolean finished() {
+        // we need to finish BOTH searches for CH!
+        if (finishedFrom && finishedTo)
+            return true;
+
+        // changed also the final finish condition for CH
+        return currFrom.weight >= bestPath.getWeight() && currTo.weight >= bestPath.getWeight();
+    }
+
+    @Override
+    protected Path createAndInitPath() {
+        bestPath = new Path4CH(graph, graph.getBaseGraph(), weighting);
+        return bestPath;
+    }
+
+    @Override
+    public String getName() {
+        return "dijkstrabi|ch|no_sod";
+    }
+
+    @Override
+    public String toString() {
+        return getName() + "|" + weighting;
+    }
+}
diff --git a/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionRef.java b/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionRef.java
index c9ea680d5..3e122fad1 100644
--- a/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionRef.java
+++ b/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionRef.java
@@ -42,8 +42,8 @@ public class DijkstraBidirectionRef extends AbstractBidirAlgo {
     protected SPTEntry currFrom;
     protected SPTEntry currTo;
     protected PathBidirRef bestPath;
-    private PriorityQueue<SPTEntry> pqOpenSetFrom;
-    private PriorityQueue<SPTEntry> pqOpenSetTo;
+    PriorityQueue<SPTEntry> pqOpenSetFrom;
+    PriorityQueue<SPTEntry> pqOpenSetTo;
     private boolean updateBestPath = true;
 
     public DijkstraBidirectionRef(Graph graph, Weighting weighting, TraversalMode tMode) {
diff --git a/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java b/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java
index 34eead530..2701f7c3b 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java
@@ -647,9 +647,12 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation imple
             AStarBidirection tmpAlgo = new AStarBidirectionCH(graph, prepareWeighting, traversalMode);
             tmpAlgo.setApproximation(RoutingAlgorithmFactorySimple.getApproximation(ASTAR_BI, opts, graph.getNodeAccess()));
             algo = tmpAlgo;
-
         } else if (DIJKSTRA_BI.equals(opts.getAlgorithm())) {
-            algo = new DijkstraBidirectionCH(graph, prepareWeighting, traversalMode);
+            if (opts.getHints().getBool("stall_on_demand", true)) {
+                algo = new DijkstraBidirectionCH(graph, prepareWeighting, traversalMode);
+            } else {
+                algo = new DijkstraBidirectionCHNoSOD(graph, prepareWeighting, traversalMode);
+            }
         } else {
             throw new IllegalArgumentException("Algorithm " + opts.getAlgorithm() + " not supported for Contraction Hierarchies. Try with ch.disable=true");
         }
@@ -659,80 +662,6 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation imple
         return algo;
     }
 
-    public static class AStarBidirectionCH extends AStarBidirection {
-        public AStarBidirectionCH(Graph graph, Weighting weighting, TraversalMode traversalMode) {
-            super(graph, weighting, traversalMode);
-        }
-
-        @Override
-        protected void initCollections(int size) {
-            super.initCollections(Math.min(size, 2000));
-        }
-
-        @Override
-        protected boolean finished() {
-            // we need to finish BOTH searches for CH!
-            if (finishedFrom && finishedTo)
-                return true;
-
-            // changed finish condition for CH
-            return currFrom.weight >= bestPath.getWeight() && currTo.weight >= bestPath.getWeight();
-        }
-
-        @Override
-        protected Path createAndInitPath() {
-            bestPath = new Path4CH(graph, graph.getBaseGraph(), weighting);
-            return bestPath;
-        }
-
-        @Override
-        public String getName() {
-            return "astarbi|ch";
-        }
-
-        @Override
-        public String toString() {
-            return getName() + "|" + weighting;
-        }
-    }
-
-    public static class DijkstraBidirectionCH extends DijkstraBidirectionRef {
-        public DijkstraBidirectionCH(Graph graph, Weighting weighting, TraversalMode traversalMode) {
-            super(graph, weighting, traversalMode);
-        }
-
-        @Override
-        protected void initCollections(int size) {
-            super.initCollections(Math.min(size, 2000));
-        }
-
-        @Override
-        public boolean finished() {
-            // we need to finish BOTH searches for CH!
-            if (finishedFrom && finishedTo)
-                return true;
-
-            // changed also the final finish condition for CH
-            return currFrom.weight >= bestPath.getWeight() && currTo.weight >= bestPath.getWeight();
-        }
-
-        @Override
-        protected Path createAndInitPath() {
-            bestPath = new Path4CH(graph, graph.getBaseGraph(), weighting);
-            return bestPath;
-        }
-
-        @Override
-        public String getName() {
-            return "dijkstrabi|ch";
-        }
-
-        @Override
-        public String toString() {
-            return getName() + "|" + weighting;
-        }
-    }
-
     @Override
     public String toString() {
         return "prepare|dijkstrabi|ch";
diff --git a/tools/src/main/java/com/graphhopper/tools/Measurement.java b/tools/src/main/java/com/graphhopper/tools/Measurement.java
index d178122a2..7ec739bce 100644
--- a/tools/src/main/java/com/graphhopper/tools/Measurement.java
+++ b/tools/src/main/java/com/graphhopper/tools/Measurement.java
@@ -48,6 +48,8 @@ import java.util.Map.Entry;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.atomic.AtomicLong;
 
+import static com.graphhopper.util.Parameters.Algorithms.DIJKSTRA_BI;
+
 /**
  * @author Peter Karich
  */
@@ -115,14 +117,14 @@ public class Measurement {
             GHBitSet allowedEdges = printGraphDetails(g, vehicleStr);
             printMiscUnitPerfTests(g, isCH, encoder, count * 100, allowedEdges);
             printLocationIndexQuery(g, hopper.getLocationIndex(), count);
-            printTimeOfRouteQuery(hopper, isCH, isLM, count / 20, "routing", vehicleStr, true, -1);
+            printTimeOfRouteQuery(hopper, isCH, isLM, count / 20, "routing", vehicleStr, true, -1, true);
 
             if (hopper.getLMFactoryDecorator().isEnabled()) {
                 System.gc();
                 isLM = true;
                 int activeLMCount = 12;
                 for (; activeLMCount > 3; activeLMCount -= 4) {
-                    printTimeOfRouteQuery(hopper, isCH, isLM, count / 4, "routingLM" + activeLMCount, vehicleStr, true, activeLMCount);
+                    printTimeOfRouteQuery(hopper, isCH, isLM, count / 4, "routingLM" + activeLMCount, vehicleStr, true, activeLMCount, true);
                 }
 
                 // compareRouting(hopper, vehicleStr, count / 5);
@@ -130,13 +132,13 @@ public class Measurement {
 
             if (hopper.getCHFactoryDecorator().isEnabled()) {
                 isCH = true;
-
+//                compareCHWithAndWithoutSOD(hopper, vehicleStr, count/5);
                 if (hopper.getLMFactoryDecorator().isEnabled()) {
                     isLM = true;
                     System.gc();
                     // try just one constellation, often ~4-6 is best
                     int lmCount = 5;
-                    printTimeOfRouteQuery(hopper, isCH, isLM, count, "routingCHLM" + lmCount, vehicleStr, true, lmCount);
+                    printTimeOfRouteQuery(hopper, isCH, isLM, count, "routingCHLM" + lmCount, vehicleStr, true, lmCount, true);
                 }
 
                 isLM = false;
@@ -145,8 +147,9 @@ public class Measurement {
                 CHGraph lg = g.getGraph(CHGraph.class, weighting);
                 fillAllowedEdges(lg.getAllEdges(), allowedEdges);
                 printMiscUnitPerfTests(lg, isCH, encoder, count * 100, allowedEdges);
-                printTimeOfRouteQuery(hopper, isCH, isLM, count, "routingCH", vehicleStr, true, -1);
-                printTimeOfRouteQuery(hopper, isCH, isLM, count, "routingCH_no_instr", vehicleStr, false, -1);
+                printTimeOfRouteQuery(hopper, isCH, isLM, count, "routingCH", vehicleStr, true, -1, true);
+                printTimeOfRouteQuery(hopper, isCH, isLM, count, "routingCH_no_sod", vehicleStr, true, -1, false);
+                printTimeOfRouteQuery(hopper, isCH, isLM, count, "routingCH_no_instr", vehicleStr, false, -1, true);
             }
             logger.info("store into " + propLocation);
         } catch (Exception ex) {
@@ -322,9 +325,59 @@ public class Measurement {
         }
     }
 
+    private void compareCHWithAndWithoutSOD(final GraphHopper hopper, String vehicle, int count) {
+        logger.info("Comparing " + count + " routes for CH with and without stall on demand." +
+                " Differences will be printed to stderr.");
+        final Random rand = new Random(seed);
+        final Graph g = hopper.getGraphHopperStorage();
+        final NodeAccess na = g.getNodeAccess();
+
+        for (int i = 0; i < count; i++) {
+            int from = rand.nextInt(maxNode);
+            int to = rand.nextInt(maxNode);
+
+            double fromLat = na.getLatitude(from);
+            double fromLon = na.getLongitude(from);
+            double toLat = na.getLatitude(to);
+            double toLon = na.getLongitude(to);
+            GHRequest sodReq = new GHRequest(fromLat, fromLon, toLat, toLon).
+                    setWeighting("fastest").
+                    setVehicle(vehicle).
+                    setAlgorithm(DIJKSTRA_BI);
+
+            GHRequest noSodReq = new GHRequest(fromLat, fromLon, toLat, toLon).
+                    setWeighting("fastest").
+                    setVehicle(vehicle).
+                    setAlgorithm(DIJKSTRA_BI);
+            noSodReq.getHints().put("stall_on_demand", false);
+
+            GHResponse sodRsp = hopper.route(sodReq);
+            GHResponse noSodRsp = hopper.route(noSodReq);
+
+            String locStr = " iteration " + i + ". " + fromLat + "," + fromLon + " -> " + toLat + "," + toLon;
+            if (sodRsp.hasErrors()) {
+                if (noSodRsp.hasErrors()) {
+                    logger.info("Error with and without SOD");
+                    continue;
+                } else {
+                    logger.error("Error with SOD but not without SOD" + locStr);
+                    continue;
+                }
+            }
+            String infoStr =
+                    " weight:" + noSodRsp.getBest().getRouteWeight() + ", original: " + sodRsp.getBest().getRouteWeight()
+                            + " distance:" + noSodRsp.getBest().getDistance() + ", original: " + sodRsp.getBest().getDistance()
+                            + " time:" + Helper.round2(noSodRsp.getBest().getTime() / 1000) + ", original: " + Helper.round2(sodRsp.getBest().getTime() / 1000)
+                            + " points:" + noSodRsp.getBest().getPoints().size() + ", original: " + sodRsp.getBest().getPoints().size();
+
+            if (Math.abs(1 - noSodRsp.getBest().getRouteWeight() / sodRsp.getBest().getRouteWeight()) > 0.000001)
+                logger.error("Too big weight difference for SOD. " + locStr + infoStr);
+        }
+    }
+
     private void printTimeOfRouteQuery(final GraphHopper hopper, final boolean ch, final boolean lm,
                                        int count, String prefix, final String vehicle,
-                                       final boolean withInstructions, final int activeLandmarks) {
+                                       final boolean withInstructions, final int activeLandmarks, final boolean sod) {
         final Graph g = hopper.getGraphHopperStorage();
         final AtomicLong maxDistance = new AtomicLong(0);
         final AtomicLong minDistance = new AtomicLong(Long.MAX_VALUE);
@@ -355,6 +408,7 @@ public class Measurement {
                         setVehicle(vehicle);
 
                 req.getHints().put(CH.DISABLE, !ch).
+                        put("stall_on_demand", sod).
                         put(Landmark.DISABLE, !lm).
                         put(Landmark.ACTIVE_COUNT, activeLandmarks).
                         put("instructions", withInstructions);
@@ -412,8 +466,11 @@ public class Measurement {
 
         count -= failedCount.get();
 
-        // if using none-bidirectional algorithm make sure you exclude CH routing
-        final String algoStr = ch ? Algorithms.DIJKSTRA_BI : Algorithms.ASTAR_BI;
+        // if using non-bidirectional algorithm make sure you exclude CH routing
+        String algoStr = ch ? Algorithms.DIJKSTRA_BI : Algorithms.ASTAR_BI;
+        if (ch && !sod) {
+            algoStr += "_no_sod";
+        }
         put(prefix + ".guessed_algorithm", algoStr);
         put(prefix + ".failed_count", failedCount.get());
         put(prefix + ".distance_min", minDistance.get());
diff --git a/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java b/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java
index 44a94e10a..1e549e0b0 100644
--- a/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java
+++ b/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java
@@ -97,7 +97,7 @@ public class MiniGraphUI {
             final RoutingAlgorithmFactory tmpFactory = hopper.getAlgorithmFactory(map);
             algoFactory = new RoutingAlgorithmFactory() {
 
-                class TmpAlgo extends PrepareContractionHierarchies.DijkstraBidirectionCH implements DebugAlgo {
+                class TmpAlgo extends DijkstraBidirectionCH implements DebugAlgo {
                     private final GraphicsWrapper mg;
                     private Graphics2D g2;
 


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/ch/DijkstraBidirectionCHTest.java b/core/src/test/java/com/graphhopper/routing/DijkstraBidirectionCHTest.java
similarity index 61%
rename from core/src/test/java/com/graphhopper/routing/ch/DijkstraBidirectionCHTest.java
rename to core/src/test/java/com/graphhopper/routing/DijkstraBidirectionCHTest.java
index f50a5b37f..112c13e10 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/DijkstraBidirectionCHTest.java
+++ b/core/src/test/java/com/graphhopper/routing/DijkstraBidirectionCHTest.java
@@ -15,9 +15,10 @@
  *  See the License for the specific language governing permissions and
  *  limitations under the License.
  */
-package com.graphhopper.routing.ch;
+package com.graphhopper.routing;
 
-import com.graphhopper.routing.*;
+import com.carrotsearch.hppc.IntArrayList;
+import com.graphhopper.routing.ch.PrepareContractionHierarchies;
 import com.graphhopper.routing.util.*;
 import com.graphhopper.routing.weighting.FastestWeighting;
 import com.graphhopper.routing.weighting.ShortestWeighting;
@@ -166,4 +167,106 @@ public class DijkstraBidirectionCHTest extends AbstractRoutingAlgorithmTester {
         assertEquals(p3.toString(), 12240 * 1000, p3.getTime());
         assertEquals(Helper.createTList(0, 4, 5, 7), p3.calcNodes());
     }
+
+    // 7------8------.---9----0
+    // |      | \    |   |
+    // 6------   |   |   |
+    // |      |  1   |   |
+    // 5------   |   |  /
+    // |  _,--|   2  | /
+    // |/         |  |/
+    // 4----------3--/
+    @Test
+    public void testStallingNodesReducesNumberOfVisitedNodes() {
+        GraphHopperStorage graph = createGHStorage(false);
+        graph.edge(8, 9, 100, false);
+        graph.edge(8, 3, 2, false);
+        graph.edge(8, 5, 1, false);
+        graph.edge(8, 6, 1, false);
+        graph.edge(8, 7, 1, false);
+        graph.edge(1, 2, 2, false);
+        graph.edge(1, 8, 1, false);
+        graph.edge(2, 3, 3, false);
+        for (int i = 3; i < 7; ++i) {
+            graph.edge(i, i + 1, 1, false);
+        }
+        graph.edge(9, 0, 1, false);
+        graph.edge(3, 9, 200, false);
+        CHGraph chGraph = graph.getGraph(CHGraph.class);
+
+        // explicitly set the node levels equal to the node ids
+        // the graph contraction with this ordering yields no shortcuts
+        for (int i = 0; i < 10; ++i) {
+            chGraph.setLevel(i, i);
+        }
+        graph.freeze();
+        RoutingAlgorithm algo = createCHAlgo(graph, chGraph, true, defaultOpts);
+        Path p = algo.calcPath(1, 0);
+        // node 3 will be stalled and nodes 4-7 won't be explored --> we visit 7 nodes
+        // note that node 9 will be visited by both forward and backward searches
+        assertEquals(7, algo.getVisitedNodes());
+        assertEquals(102, p.getDistance(), 1.e-3);
+        assertEquals(p.toString(), Helper.createTList(1, 8, 9, 0), p.calcNodes());
+
+        // without stalling we visit 11 nodes
+        RoutingAlgorithm algoNoSod = createCHAlgo(graph, chGraph, false, defaultOpts);
+        Path pNoSod = algoNoSod.calcPath(1, 0);
+        assertEquals(11, algoNoSod.getVisitedNodes());
+        assertEquals(102, pNoSod.getDistance(), 1.e-3);
+        assertEquals(pNoSod.toString(), Helper.createTList(1, 8, 9, 0), pNoSod.calcNodes());
+    }
+
+    // t(0)--slow->1--s(2)
+    //    \        |
+    //    fast     |
+    //      \--<---|
+    @Test
+    public void testDirectionDependentSpeedFwdSearch() {
+        runTestWithDirectionDependentEdgeSpeed(10, 20, 0, 2, Helper.createTList(0, 1, 2), new MotorcycleFlagEncoder());
+        runTestWithDirectionDependentEdgeSpeed(10, 20, 0, 2, Helper.createTList(0, 1, 2), new Bike2WeightFlagEncoder());
+    }
+
+    // s(0)--fast->1--t(2)
+    //    \        |
+    //    slow     |
+    //      \--<---|
+    @Test
+    public void testDirectionDependentSpeedBwdSearch() {
+        runTestWithDirectionDependentEdgeSpeed(20, 10, 2, 0, Helper.createTList(2, 1, 0), new MotorcycleFlagEncoder());
+        runTestWithDirectionDependentEdgeSpeed(20, 10, 2, 0, Helper.createTList(2, 1, 0), new Bike2WeightFlagEncoder());
+    }
+
+    private void runTestWithDirectionDependentEdgeSpeed(
+            int speed, int revSpeed, int from, int to, IntArrayList expectedPath, FlagEncoder encoder) {
+        EncodingManager encodingManager = new EncodingManager(encoder);
+        FastestWeighting weighting = new FastestWeighting(encoder);
+        AlgorithmOptions algoOpts = AlgorithmOptions.start().weighting(weighting).build();
+        GraphHopperStorage graph = createGHStorage(encodingManager, Arrays.asList(weighting), false);
+        EdgeIteratorState edge = graph.edge(0, 1, 2, true);
+        long flags = edge.getFlags();
+        flags = encoder.setSpeed(flags, speed);
+        flags = encoder.setReverseSpeed(flags, revSpeed);
+        edge.setFlags(flags);
+        graph.edge(1, 2, 1, true);
+
+        CHGraph chGraph = graph.getGraph(CHGraph.class);
+        for (int i = 0; i < 3; ++i) {
+            chGraph.setLevel(i, i);
+        }
+        graph.freeze();
+
+        RoutingAlgorithm algo = createCHAlgo(graph, chGraph, true, algoOpts);
+        Path p = algo.calcPath(from, to);
+        assertEquals(3, p.getDistance(), 1.e-3);
+        assertEquals(p.toString(), expectedPath, p.calcNodes());
+    }
+
+    private RoutingAlgorithm createCHAlgo(GraphHopperStorage graph, CHGraph chGraph, boolean withSOD, AlgorithmOptions algorithmOptions) {
+        PrepareContractionHierarchies ch = new PrepareContractionHierarchies(new GHDirectory("", DAType.RAM_INT),
+                graph, chGraph, algorithmOptions.getWeighting(), TraversalMode.NODE_BASED);
+        if (!withSOD) {
+            algorithmOptions.getHints().put("stall_on_demand", false);
+        }
+        return ch.createAlgo(chGraph, algorithmOptions);
+    }
 }