Repository: graphhopper/graphhopper
Pull request #1745 (2019-10-07 05:40:38)

Landmark bugs
Minimal fix for the two failing tests in #1687.

The first was already discussed (missing setter for the 'fallback' approximator).

The second one was due to an incorrect treatment of "minned out" "delta" weights. See comment in code.

michaz: I understand you are already investigating creating an extra `factor` for the delta weights, doing performance tests etc., but IMO step one is maintaining correctness (in this case doing the right thing when a delta weight is minned out). Then, step two is seeing how we can make sure this happens less often.
michaz: I think (?) one issue here was the test -- there was a "setGet"-test, but it was rather technical and white-box -- it was basically testing that the bits would be twiddled in the same way the code says they would be twiddled. :-) But the important property -- that the remaining weight must never be over-estimated -- was not tested.

Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedNodeContractor.java b/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedNodeContractor.java
index bd114fffc..7124daf26 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedNodeContractor.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedNodeContractor.java
@@ -489,9 +489,10 @@ class EdgeBasedNodeContractor extends AbstractNodeContractor {
                             while (EdgeIterator.Edge.isValid(root.parent.edge)) {
                                 root = root.getParent();
                             }
-                            // todo: removing this 'optimization' improves contraction time significantly, but introduces 
-                            // more shortcuts (makes slower queries). why is this so ? any 'duplicate' shortcuts should be detected at time of
-                            // insertion !??
+                            // removing this 'optimization' improves contraction time, but introduces more
+                            // shortcuts (makes slower queries). note that 'duplicate' shortcuts get detected at time
+                            // of insertion when running with adding shortcut handler, but not when we are only counting.
+                            // only running this check while counting does not seem to improve contraction time a lot.
                             AddedShortcut addedShortcut = new AddedShortcut(sourceNode, root.getParent().incEdge, targetNode, entry.incEdge);
                             if (addedShortcuts.contains(addedShortcut)) {
                                 continue;
diff --git a/core/src/main/java/com/graphhopper/routing/lm/LMApproximator.java b/core/src/main/java/com/graphhopper/routing/lm/LMApproximator.java
index fe99f60ec..74e084fc4 100644
--- a/core/src/main/java/com/graphhopper/routing/lm/LMApproximator.java
+++ b/core/src/main/java/com/graphhopper/routing/lm/LMApproximator.java
@@ -33,12 +33,12 @@ import java.util.Arrays;
  */
 public class LMApproximator implements WeightApproximator {
     private static class VirtEntry {
-        private int node;
+        private int towerNode;
         private int weight;
 
         @Override
         public String toString() {
-            return node + ", " + weight;
+            return towerNode + ", " + weight;
         }
     }
 
@@ -49,7 +49,7 @@ public class LMApproximator implements WeightApproximator {
     private int[] activeFromIntWeights;
     private int[] activeToIntWeights;
     private double epsilon = 1;
-    private int to = -1;
+    private int toTowerNode = -1;
     // do activate landmark recalculation
     private boolean doALMRecalc = true;
     private final double factor;
@@ -92,13 +92,13 @@ public class LMApproximator implements WeightApproximator {
                 VirtEntry virtEntry = new VirtEntry();
                 if (weight < Integer.MAX_VALUE && (reverseWeight >= Integer.MAX_VALUE || weight < reverseWeight)) {
                     virtEntry.weight = weight;
-                    virtEntry.node = reverse ? edge.getBaseNode() : edge.getAdjNode();
+                    virtEntry.towerNode = reverse ? edge.getBaseNode() : edge.getAdjNode();
                 } else {
                     virtEntry.weight = reverseWeight;
                     if (reverseWeight >= Integer.MAX_VALUE)
                         throw new IllegalStateException("At least one direction of edge (" + edge + ") should be accessible but wasn't!");
 
-                    virtEntry.node = reverse ? edge.getAdjNode() : edge.getBaseNode();
+                    virtEntry.towerNode = reverse ? edge.getAdjNode() : edge.getBaseNode();
                 }
 
                 virtNodeMap.put(idxVirtNode, virtEntry);
@@ -119,23 +119,23 @@ public class LMApproximator implements WeightApproximator {
         if (!doALMRecalc && fallback || lms.isEmpty())
             return fallBackApproximation.approximate(queryNode);
 
-        int node = queryNode;
+        int towerNode = queryNode;
         int virtEdgeWeightInt = 0;
         if (queryNode >= maxBaseNodes) {
             // handle virtual node
             VirtEntry virtEntry = virtNodeMap.get(queryNode);
-            node = virtEntry.node;
+            towerNode = virtEntry.towerNode;
             virtEdgeWeightInt = virtEntry.weight;
         }
 
-        if (node == to)
+        if (towerNode == toTowerNode)
             return 0;
 
         // select better active landmarks, LATER: use 'success' statistics about last active landmark
         // we have to update the priority queues and the maps if done in the middle of the search http://cstheory.stackexchange.com/q/36355/13229
         if (doALMRecalc) {
             doALMRecalc = false;
-            boolean res = lms.initActiveLandmarks(node, to, activeLandmarks, activeFromIntWeights, activeToIntWeights, reverse);
+            boolean res = lms.initActiveLandmarks(towerNode, toTowerNode, activeLandmarks, activeFromIntWeights, activeToIntWeights, reverse);
             if (!res) {
                 // note: fallback==true means forever true!
                 fallback = true;
@@ -143,7 +143,7 @@ public class LMApproximator implements WeightApproximator {
             }
         }
 
-        int maxWeightInt = getMaxWeight(node, virtEdgeWeightInt, activeLandmarks, activeFromIntWeights, activeToIntWeights);
+        int maxWeightInt = getMaxWeight(towerNode, virtEdgeWeightInt, activeLandmarks, activeFromIntWeights, activeToIntWeights);
         if (maxWeightInt < 0) {
             // allow negative weight for now until we have more precise approximation (including query graph)
             return 0;
@@ -194,13 +194,10 @@ public class LMApproximator implements WeightApproximator {
         return maxWeightInt;
     }
 
-    final int getNode(int node) {
-        return node >= maxBaseNodes ? virtNodeMap.get(node).node : node;
-    }
-
     @Override
     public void setTo(int to) {
-        this.to = getNode(to);
+        this.fallBackApproximation.setTo(to);
+        this.toTowerNode = to >= maxBaseNodes ? virtNodeMap.get(to).towerNode : to;
     }
 
     @Override
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 793db907e..43dc13280 100644
--- a/core/src/main/java/com/graphhopper/routing/lm/LandmarkStorage.java
+++ b/core/src/main/java/com/graphhopper/routing/lm/LandmarkStorage.java
@@ -503,6 +503,11 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
             return Integer.MAX_VALUE;
         // throw new IllegalStateException("Do not call getToWeight for wrong landmark[" + landmarkIndex + "]=" + landmarkIDs[landmarkIndex] + " and node " + node);
 
+        // If delta is 'maxed out' (minned out, really), we can only return 0, since we can't give a better
+        // under-approximation of the weight, since it can be arbitrarily smaller than 'from'.
+        if (delta == DELTA_MIN)
+            return 0;
+
         //the right bits of "res" store the backward value
         int from = res & FROM_WEIGHT_INF;
 
diff --git a/core/src/main/java/com/graphhopper/routing/util/CarFlagEncoder.java b/core/src/main/java/com/graphhopper/routing/util/CarFlagEncoder.java
index bb70eda98..0d91d03fd 100644
--- a/core/src/main/java/com/graphhopper/routing/util/CarFlagEncoder.java
+++ b/core/src/main/java/com/graphhopper/routing/util/CarFlagEncoder.java
@@ -317,35 +317,6 @@ public class CarFlagEncoder extends AbstractFlagEncoder {
                 || way.hasTag("motor_vehicle:forward");
     }
 
-    public String getWayInfo(ReaderWay way) {
-        String str = "";
-        String highwayValue = way.getTag("highway");
-        // for now only motorway links
-        if ("motorway_link".equals(highwayValue)) {
-            String destination = way.getTag("destination");
-            if (!Helper.isEmpty(destination)) {
-                int counter = 0;
-                for (String d : destination.split(";")) {
-                    if (d.trim().isEmpty())
-                        continue;
-
-                    if (counter > 0)
-                        str += ", ";
-
-                    str += d.trim();
-                    counter++;
-                }
-            }
-        }
-        if (str.isEmpty())
-            return str;
-        // I18N
-        if (str.contains(","))
-            return "destinations: " + str;
-        else
-            return "destination: " + str;
-    }
-
     /**
      * @param way   needed to retrieve tags
      * @param speed speed guessed e.g. from the road type or other tags


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/lm/LandmarkStorageTest.java b/core/src/test/java/com/graphhopper/routing/lm/LandmarkStorageTest.java
index 4a9fa9c3e..6db6d077f 100644
--- a/core/src/test/java/com/graphhopper/routing/lm/LandmarkStorageTest.java
+++ b/core/src/test/java/com/graphhopper/routing/lm/LandmarkStorageTest.java
@@ -100,18 +100,14 @@ public class LandmarkStorageTest {
         lms.setWeight(0, 0, 16, 999999, true);
         assertEquals((int) Math.pow(2, 18) - 2, lms.getFromWeight(0, 0));
 
-        /* FROM_WEIGHT_BITS = 18 --> remaining bits: 32-18 = 14
-        The delta value is signed and will therefore go from -2^(14-1) to 2^(14-1).
-        Now 2^13-1 is used for infinity, 2^13-2 as maximum and -2^13 as minimum.
-        If the difference between forward and backward weight is too large it will use
-        the maximum (if positive) or the minimum (if negative) instead of 0 or infinity
-        The delta will then be added to the backward weight*/
         lms.setWeight(0, 0, 16, 999999, false);
-        assertEquals((int) (Math.pow(2, 18) - 2 + Math.pow(2, 13) - 2), lms.getToWeight(0, 0));
-        //                 {backward weight}   {delta weight}
+        // The important property is that the weight that is returned
+        // is _not bigger_ than the weight that was set.
+        assertTrue(lms.getToWeight(0, 0) * lms.getFactor() <= 999999);
         lms.setWeight(0, 0, 16, 1, false);
-        assertEquals((int) (Math.pow(2, 18) - 2 + -Math.pow(2, 13)), lms.getToWeight(0, 0));
-        //                 {backward weight}   {delta weight}
+        // This is an underrun of the 'delta' field -- but still, the important property is that the weight that is returned
+        // is _not bigger_ than the weight that was set.
+        assertTrue(lms.getToWeight(0, 0) * lms.getFactor() <= 1);
 
         da.setInt(0, Integer.MAX_VALUE);
         assertTrue(lms.isInfinity(0));
@@ -317,6 +313,5 @@ public class LandmarkStorageTest {
         assertEquals(9, storage.getLandmarks(1)[1]);
 
         assertEquals((int) Math.pow(2, 13) - 2, storage.getToWeight(0, 9) - storage.getFromWeight(0, 9));
-        assertEquals((int) -Math.pow(2, 13), storage.getToWeight(1, 12) - storage.getFromWeight(1, 12));
     }
 }
diff --git a/core/src/test/java/com/graphhopper/routing/weighting/BidirectionalRoutingTest.java b/core/src/test/java/com/graphhopper/routing/weighting/BidirectionalRoutingTest.java
new file mode 100644
index 000000000..56729ca4a
--- /dev/null
+++ b/core/src/test/java/com/graphhopper/routing/weighting/BidirectionalRoutingTest.java
@@ -0,0 +1,225 @@
+package com.graphhopper.routing.weighting;
+
+import com.graphhopper.RepeatRule;
+import com.graphhopper.routing.*;
+import com.graphhopper.routing.ch.PrepareContractionHierarchies;
+import com.graphhopper.routing.lm.PrepareLandmarks;
+import com.graphhopper.routing.profiles.DecimalEncodedValue;
+import com.graphhopper.routing.util.CarFlagEncoder;
+import com.graphhopper.routing.util.EncodingManager;
+import com.graphhopper.routing.util.TraversalMode;
+import com.graphhopper.storage.*;
+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.Parameters.Algorithms.ASTAR_BI;
+import static com.graphhopper.util.Parameters.Algorithms.DIJKSTRA_BI;
+import static org.junit.Assert.fail;
+
+/**
+ * This test compares the different bidirectional routing algorithms with {@link DijkstraBidirectionRef}
+ * // todo: no real need of emphasizing bidirectional here ?
+ *
+ * @author easbar
+ */
+@RunWith(Parameterized.class)
+public class BidirectionalRoutingTest {
+    private final Algo algo;
+    private final boolean prepareCH;
+    private final boolean prepareLM;
+    private Directory dir;
+    private GraphHopperStorage graph;
+    private CHGraph chGraph;
+    private CarFlagEncoder encoder;
+    private Weighting weighting;
+    private EncodingManager encodingManager;
+    private PrepareContractionHierarchies pch;
+    private PrepareLandmarks lm;
+
+    @Rule
+    public RepeatRule repeatRule = new RepeatRule();
+
+    @Parameterized.Parameters(name = "{0}")
+    public static Collection<Object[]> params() {
+        // todonow: run node & edge-based ?
+        return Arrays.asList(new Object[][]{
+                {Algo.ASTAR, false, false},
+                {Algo.CH_ASTAR, true, false},
+                {Algo.CH_DIJKSTRA, true, false},
+                {Algo.LM, false, true}
+        });
+    }
+
+    private enum Algo {
+        ASTAR,
+        CH_ASTAR,
+        CH_DIJKSTRA,
+        LM
+    }
+
+    public BidirectionalRoutingTest(Algo algo, boolean prepareCH, boolean prepareLM) {
+        this.algo = algo;
+        this.prepareCH = prepareCH;
+        this.prepareLM = prepareLM;
+    }
+
+    @Before
+    public void init() {
+        dir = new RAMDirectory();
+        // todonow: make this work with speed_both_directions=true!
+        encoder = new CarFlagEncoder(5, 5, 0);
+        encodingManager = EncodingManager.create(encoder);
+        weighting = new FastestWeighting(encoder);
+        graph = createGraph();
+        chGraph = graph.getCHGraph();
+    }
+
+    private void preProcessGraph() {
+        graph.freeze();
+        if (prepareCH) {
+            pch = new PrepareContractionHierarchies(chGraph);
+            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, weighting, TraversalMode.NODE_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, weighting, TraversalMode.NODE_BASED);
+                return (AbstractBidirAlgo) lm.getDecoratedAlgorithm(graph, astarbi, AlgorithmOptions.start().build());
+            default:
+                throw new IllegalArgumentException("unknown algo " + algo);
+        }
+    }
+
+    @Test
+    public void lm_problem_to_node_of_fallback_approximator() {
+        // this test would fail because when the distance is approximated for the start node 0 the LMApproximator
+        // uses the fall back approximator for which the to node is never set. This in turn means that the to coordinates
+        // are zero and a way too large approximation is returned. Eventually the best path is not updated correctly
+        // because the spt entry of the fwd search already has a way too large weight.
+
+        //   ---<---
+        //   |     |
+        //   | 4   |
+        //   |/  \ 0
+        //   1   | |
+        //     \ | |
+        //       3 |
+        // 2 --<----
+        DecimalEncodedValue speedEnc = encoder.getAverageSpeedEnc();
+        NodeAccess na = graph.getNodeAccess();
+        na.setNode(0, 49.405150, 9.709054);
+        na.setNode(1, 49.403705, 9.700517);
+        na.setNode(2, 49.400112, 9.700209);
+        na.setNode(3, 49.403009, 9.708364);
+        na.setNode(4, 49.409021, 9.703622);
+        // 30s
+        graph.edge(4, 3, 1000, true).set(speedEnc, 120);
+        graph.edge(0, 2, 1000, false).set(speedEnc, 120);
+        // 360s
+        graph.edge(1, 3, 1000, true).set(speedEnc, 10);
+        // 80s
+        graph.edge(0, 1, 1000, false).set(speedEnc, 45);
+        graph.edge(1, 4, 1000, true).set(speedEnc, 45);
+        preProcessGraph();
+
+        int source = 0;
+        int target = 3;
+
+        Path refPath = new DijkstraBidirectionRef(graph, weighting, TraversalMode.NODE_BASED)
+                .calcPath(source, target);
+        Path path = createAlgo()
+                .calcPath(0, 3);
+        comparePaths(refPath, path, source, target);
+    }
+
+    @Test
+    public void lm_issue2() {
+        // This would fail because an underrun of 'delta' would not be treated correctly, and the remaining
+        // weight would be over-approximated
+
+        //                    ---
+        //                  /     \
+        // 0 - 1 - 5 - 6 - 9 - 4 - 0
+        //          \     /
+        //            ->-
+        NodeAccess na = graph.getNodeAccess();
+        DecimalEncodedValue speedEnc = encoder.getAverageSpeedEnc();
+        na.setNode(0, 49.406987, 9.709767);
+        na.setNode(1, 49.403612, 9.702953);
+        na.setNode(2, 49.409755, 9.706517);
+        na.setNode(3, 49.409021, 9.708649);
+        na.setNode(4, 49.400674, 9.700906);
+        na.setNode(5, 49.408735, 9.709486);
+        na.setNode(6, 49.406402, 9.700937);
+        na.setNode(7, 49.406965, 9.702660);
+        na.setNode(8, 49.405227, 9.702863);
+        na.setNode(9, 49.409411, 9.709085);
+        graph.edge(0, 1, 623.197000, true).set(speedEnc, 112);
+        graph.edge(5, 1, 741.414000, true).set(speedEnc, 13);
+        graph.edge(9, 4, 1140.835000, true).set(speedEnc, 35);
+        graph.edge(5, 6, 670.689000, true).set(speedEnc, 18);
+        graph.edge(5, 9, 80.731000, false).set(speedEnc, 88);
+        graph.edge(0, 9, 273.948000, true).set(speedEnc, 82);
+        graph.edge(4, 0, 956.552000, true).set(speedEnc, 60);
+        preProcessGraph();
+        int source = 5;
+        int target = 4;
+        Path refPath = new DijkstraBidirectionRef(graph, weighting, TraversalMode.NODE_BASED)
+                .calcPath(source, target);
+        Path path = createAlgo()
+                .calcPath(source, target);
+        comparePaths(refPath, path, source, target);
+    }
+
+
+    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(Collections.singletonList(weighting), dir, encodingManager,
+                false, new GraphExtension.NoOpExtension());
+        gh.create(1000);
+        return gh;
+    }
+
+}
\ No newline at end of file