Repository: graphhopper/graphhopper
Pull request #1455 (2018-09-07 14:37:41)

Replaces truncation with rounding when setting edge distance or CH shortcut weight.
Truncating the shortcut weight before storing it introduces small deviations from Dijkstra, which sometimes makes it harder to check the correctness of CH. Therefore I have replaced the long truncation with a `Math.round()` call.
Performance-wise isolated `Math.round()` will certainly be slower, but the profiler shows that the time spent on weight setting during the CH preparation is negligible. `setWeight` is only used for CH preparation.

ammagamma: tests failed with API limit reached ...
karussell: @ammagamma Would a higher precision also help? As it is very likely that we change this behaviour (we could use the same EncodedValue approach we have for non-CH but then it would be likely without rounding) can you introduce a test that is different with the rounding?
ammagamma: > can you introduce a test that is different with the rounding

Good point. I added a test showcasing the problem where CH yields a different route than Dijkstra. Its quite intricate and I had to carefully pick distance values to reproduce the problem. I am not even sure if the test will fail on any machine. Not sure how deterministic the code / truncation is, need to refresh my knowledge here. I think the problem is that something like 2.010 might be represented as 2.009999 and after the truncation it will be 2.009. If this happens a few times a shortcut or set of nested shortcuts appears to be shorter than the real road and CH can take another way than Dijkstra.

Also this test does not pass with my previous fix, so I reverted it for now.

@Azbesciak Thanks for posting your problem, I might have a look and see if this is related to the issue I am referring to here.
karussell: Is this still an issue with the latest version of CH+turn costs?
easbar: > Is this still an issue with the latest version of CH+turn costs?

Good question :) I am getting much fewer differences between CH and Dijkstra in `CHMeasurement` in the turncost_ch branch with this fix. Also when I increase `WEIGHT_FACTOR` to 10_000 I achieve the same. But then again I am not sure if I understood the issue completely and most of the differences are very small anyway (below one second of driving time, but some rare cases where the difference is a few seconds). I do not think this fix is strictly necessary, but it would be a bit cleaner this way.
easbar: I updated this to master, but I am still unsure. I think rounding is definitely 'more correct' than truncating and e.g. when comparing CH with Dijkstra we get less deviations (but they are always quite small). For better consistency we might even apply the rounding in `EdgeAccess#setDist` (which I have done here). But I am not sure if this is worth it. Asking the other way around: What are the cons of using Math.round instead of truncation ?
karussell: > What are the cons of using Math.round instead of truncation 

Good question. Maybe performance. But we do this now already in FactorizedDecimalEncodedValue and MappedDecimalEncodedValue too:

private int toInt(double val) { return (int) Math.round(val / factor); }

And so this should be probably not be a big issue. Especially since rounding would then just more consistent.
easbar: >  But we do this now already in FactorizedDecimalEncodedValue and MappedDecimalEncodedValue too.

Ok in this case I think we should apply the changes of this PR.
karussell: Will remove the "-1" for clarity

Patch:
diff --git a/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java b/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
index f7b82a836..0a08fa9eb 100644
--- a/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
+++ b/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
@@ -854,7 +854,7 @@ public class CHGraphImpl implements CHGraph, Storable<CHGraph> {
             if (weight > MAX_WEIGHT)
                 weightInt = MAX_WEIGHT_31;
             else
-                weightInt = ((int) (weight * WEIGHT_FACTOR)) << 2;
+                weightInt = ((int) Math.round(weight * WEIGHT_FACTOR)) << 2;
             return weightInt;
         }
 
diff --git a/core/src/main/java/com/graphhopper/storage/EdgeAccess.java b/core/src/main/java/com/graphhopper/storage/EdgeAccess.java
index 8ea3a7cbb..54f4e429c 100644
--- a/core/src/main/java/com/graphhopper/storage/EdgeAccess.java
+++ b/core/src/main/java/com/graphhopper/storage/EdgeAccess.java
@@ -28,7 +28,7 @@ abstract class EdgeAccess {
     private static final int NO_NODE = -1;
     // distance of around +-1000 000 meter are ok
     private static final double INT_DIST_FACTOR = 1000d;
-    static double MAX_DIST = (Integer.MAX_VALUE - 1) / INT_DIST_FACTOR;
+    static double MAX_DIST = Integer.MAX_VALUE / INT_DIST_FACTOR;
     final DataAccess edges;
     int E_NODEA, E_NODEB, E_LINKA, E_LINKB, E_DIST, E_FLAGS;
 
@@ -73,12 +73,13 @@ abstract class EdgeAccess {
      * Translates double distance to integer in order to save it in a DataAccess object
      */
     private int distToInt(double distance) {
-        int integ = (int) (distance * INT_DIST_FACTOR);
-        if (integ < 0)
+        if (distance < 0)
             throw new IllegalArgumentException("Distance cannot be negative: " + distance);
-        if (integ >= Integer.MAX_VALUE)
-            return Integer.MAX_VALUE;
-        // throw new IllegalArgumentException("Distance too large leading to overflowed integer (#435): " + distance + " ");
+        if (distance > MAX_DIST) {
+            distance = MAX_DIST;
+        }
+        int integ = (int) Math.round(distance * INT_DIST_FACTOR);
+        assert integ >= 0 : "distance out of range";
         return integ;
     }
 


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedNodeContractorTest.java b/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedNodeContractorTest.java
index d05d7d60a..111ec5473 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedNodeContractorTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedNodeContractorTest.java
@@ -1165,7 +1165,6 @@ public class EdgeBasedNodeContractorTest {
     }
 
     @Test
-    @Ignore("this test fails because of shortcut weight truncation in CHGraphImpl")
     public void testNodeContraction_minorWeightDeviation() {
         // 0 -> 1 -> 2 -> 3 -> 4
         graph.edge(0, 1, 51.401, false);
diff --git a/core/src/test/java/com/graphhopper/routing/ch/NodeBasedNodeContractorTest.java b/core/src/test/java/com/graphhopper/routing/ch/NodeBasedNodeContractorTest.java
index 1a15ca9fe..2d37a290a 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/NodeBasedNodeContractorTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ch/NodeBasedNodeContractorTest.java
@@ -18,11 +18,14 @@
 package com.graphhopper.routing.ch;
 
 import com.graphhopper.routing.Dijkstra;
+import com.graphhopper.routing.DijkstraBidirectionCH;
 import com.graphhopper.routing.DijkstraOneToMany;
+import com.graphhopper.routing.Path;
 import com.graphhopper.routing.profiles.BooleanEncodedValue;
 import com.graphhopper.routing.profiles.EncodedValue;
 import com.graphhopper.routing.profiles.SimpleBooleanEncodedValue;
 import com.graphhopper.routing.util.*;
+import com.graphhopper.routing.weighting.FastestWeighting;
 import com.graphhopper.routing.weighting.ShortestWeighting;
 import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.CHGraph;
@@ -57,7 +60,11 @@ public class NodeBasedNodeContractorTest {
     private final TraversalMode traversalMode = TraversalMode.NODE_BASED;
 
     private NodeContractor createNodeContractor() {
-        NodeContractor nodeContractor = new NodeBasedNodeContractor(lg, weighting, new PMap());
+        return createNodeContractor(lg, weighting);
+    }
+
+    private NodeContractor createNodeContractor(CHGraph chGraph, Weighting weighting) {
+        NodeContractor nodeContractor = new NodeBasedNodeContractor(chGraph, weighting, new PMap());
         nodeContractor.initFromGraph();
         nodeContractor.prepareContraction();
         return nodeContractor;
@@ -288,6 +295,108 @@ public class NodeBasedNodeContractorTest {
         checkNoShortcuts();
     }
 
+    @Test
+    public void testNodeContraction_shortcutDistanceRounding() {
+        assertTrue("this test was constructed assuming we are using the ShortestWeighting", weighting instanceof ShortestWeighting);
+        // 0 ------------> 4
+        //  \             /
+        //   1 --> 2 --> 3
+        double[] distances = {4.019, 1.006, 1.004, 1.006, 1.004};
+        graph.edge(0, 4, distances[0], false);
+        EdgeIteratorState edge1 = graph.edge(0, 1, distances[1], false);
+        EdgeIteratorState edge2 = graph.edge(1, 2, distances[2], false);
+        EdgeIteratorState edge3 = graph.edge(2, 3, distances[3], false);
+        EdgeIteratorState edge4 = graph.edge(3, 4, distances[4], false);
+        graph.freeze();
+        setMaxLevelOnAllNodes();
+
+        // make sure that distances do not get changed in storage (they might get truncated)
+        AllCHEdgesIterator iter = lg.getAllEdges();
+        double[] storedDistances = new double[iter.length()];
+        int count = 0;
+        while (iter.next()) {
+            storedDistances[count++] = iter.getDistance();
+        }
+        assertArrayEquals(distances, storedDistances, 1.e-6);
+
+        // perform CH contraction
+        contractInOrder(1, 3, 2, 0, 4);
+
+        // first we compare dijkstra with CH to make sure they produce the same results
+        int from = 0;
+        int to = 4;
+        Dijkstra dikstra = new Dijkstra(graph, weighting, TraversalMode.NODE_BASED);
+        Path dijkstraPath = dikstra.calcPath(from, to);
+
+        DijkstraBidirectionCH ch = new DijkstraBidirectionCH(lg, new PreparationWeighting(weighting));
+        Path chPath = ch.calcPath(from, to);
+        assertEquals(dijkstraPath.calcNodes(), chPath.calcNodes());
+        assertEquals(dijkstraPath.getDistance(), chPath.getDistance(), 1.e-6);
+        assertEquals(dijkstraPath.getWeight(), chPath.getWeight(), 1.e-6);
+
+        // on a more detailed level we check that the right shortcuts were added
+        // contracting nodes 1&3 will always introduce shortcuts, but contracting node 2 should not because going from
+        // 0 to 4 directly via edge 4 is cheaper. however, if shortcut distances get truncated it appears as if going
+        // via node 2 is better. here we check that this does not happen.
+        checkShortcuts(
+                expectedShortcut(0, 2, edge1, edge2, true, false),
+                expectedShortcut(2, 4, edge3, edge4, true, false)
+        );
+    }
+
+    /**
+     * similar to the previous test, but using the fastest weighting
+     */
+    @Test
+    public void testNodeContraction_shortcutWeightRounding() {
+        CarFlagEncoder encoder = new CarFlagEncoder();
+        EncodingManager encodingManager = EncodingManager.create(encoder);
+        Weighting weighting = new FastestWeighting(encoder);
+        GraphHopperStorage graph = new GraphBuilder(encodingManager).setCHGraph(weighting).create();
+        CHGraph lg = graph.getGraph(CHGraph.class);
+        // 0 ------------> 4
+        //  \             /
+        //   1 --> 2 --> 3
+        double fac = 60 / 3.6;
+        double[] distances = {fac * 4.019, fac * 1.006, fac * 1.004, fac * 1.006, fac * 1.004};
+        graph.edge(0, 4, distances[0], false);
+        graph.edge(0, 1, distances[1], false);
+        graph.edge(1, 2, distances[2], false);
+        graph.edge(2, 3, distances[3], false);
+        graph.edge(3, 4, distances[4], false);
+        graph.freeze();
+        setMaxLevelOnAllNodes(lg);
+
+        // perform CH contraction
+        contractInOrder(lg, weighting, 1, 3, 2, 0, 4);
+
+        // first we compare dijkstra with CH to make sure they produce the same results
+        int from = 0;
+        int to = 4;
+        Dijkstra dikstra = new Dijkstra(graph, weighting, TraversalMode.NODE_BASED);
+        Path dijkstraPath = dikstra.calcPath(from, to);
+
+        DijkstraBidirectionCH ch = new DijkstraBidirectionCH(lg, new PreparationWeighting(weighting));
+        Path chPath = ch.calcPath(from, to);
+        assertEquals(dijkstraPath.calcNodes(), chPath.calcNodes());
+        assertEquals(dijkstraPath.getDistance(), chPath.getDistance(), 1.e-6);
+        assertEquals(dijkstraPath.getWeight(), chPath.getWeight(), 1.e-6);
+    }
+
+    private void contractInOrder(int... nodeIds) {
+        contractInOrder(lg, weighting, nodeIds);
+    }
+
+    private void contractInOrder(CHGraph chGraph, Weighting weighting, int... nodeIds) {
+        NodeContractor nodeContractor = createNodeContractor(chGraph, weighting);
+        int level = 0;
+        for (int n : nodeIds) {
+            nodeContractor.contractNode(n);
+            chGraph.setLevel(n, level);
+            level++;
+        }
+    }
+
     /**
      * Queries the ch graph and checks if the graph's shortcuts match the given expected shortcuts.
      */
@@ -323,15 +432,17 @@ public class NodeBasedNodeContractorTest {
     }
 
     private Set<Shortcut> setOf(Shortcut... shortcuts) {
-        Set<Shortcut> result = new HashSet<>();
-        result.addAll(Arrays.asList(shortcuts));
-        return result;
+        return new HashSet<>(Arrays.asList(shortcuts));
     }
 
     private void setMaxLevelOnAllNodes() {
-        int nodes = lg.getNodes();
+        setMaxLevelOnAllNodes(lg);
+    }
+
+    private void setMaxLevelOnAllNodes(CHGraph chGraph) {
+        int nodes = chGraph.getNodes();
         for (int node = 0; node < nodes; node++) {
-            lg.setLevel(node, nodes);
+            chGraph.setLevel(node, nodes);
         }
     }
 
diff --git a/core/src/test/java/com/graphhopper/storage/AbstractGraphStorageTester.java b/core/src/test/java/com/graphhopper/storage/AbstractGraphStorageTester.java
index ee6460fed..fdb57d4c5 100644
--- a/core/src/test/java/com/graphhopper/storage/AbstractGraphStorageTester.java
+++ b/core/src/test/java/com/graphhopper/storage/AbstractGraphStorageTester.java
@@ -122,12 +122,9 @@ public abstract class AbstractGraphStorageTester {
         EdgeIteratorState edge1 = graph.edge(0, 1, maxDist, true);
         assertEquals(maxDist, edge1.getDistance(), 1);
 
-        // max out should NOT lead to infinity as this leads fast to NaN!
-        try {
-            graph.edge(0, 2, maxDist + 1, true);
-        } catch (Exception ex) {
-            assertTrue(ex.getMessage(), ex.getMessage().startsWith("Distance too large"));
-        }
+        // max out should NOT lead to infinity as this leads fast to NaN! -> we set dist to the maximum if its larger than desired
+        EdgeIteratorState edge2 = graph.edge(0, 2, maxDist + 1, true);
+        assertEquals(maxDist, edge2.getDistance(), 1);
     }
 
     @Test
diff --git a/core/src/test/java/com/graphhopper/storage/GraphHopperStorageCHTest.java b/core/src/test/java/com/graphhopper/storage/GraphHopperStorageCHTest.java
index d9a31cc83..20933a742 100644
--- a/core/src/test/java/com/graphhopper/storage/GraphHopperStorageCHTest.java
+++ b/core/src/test/java/com/graphhopper/storage/GraphHopperStorageCHTest.java
@@ -243,6 +243,24 @@ public class GraphHopperStorageCHTest extends GraphHopperStorageTest {
         assertEquals(1.011011, sc1.getWeight(), 1e-3);
     }
 
+    @Test
+    public void weightAndDistanceExact() {
+        graph = createGHStorage();
+        CHGraph chGraph = getGraph(graph);
+        graph.edge(0, 1, 1, false);
+        graph.edge(1, 2, 1, false);
+        graph.freeze();
+
+        // we just make up some weights and distances, they do not really have to be related to our previous edges.
+        // 1.004+1.006 = 2.09999999999. we make sure this does not become 2.09 instead of 2.10 (due to truncation)
+        double x1 = 1.004;
+        double x2 = 1.006;
+        chGraph.shortcut(0, 2, PrepareEncoder.getScFwdDir(), x1 + x2, x1 + x2, 0, 1);
+        CHEdgeIteratorState sc = chGraph.getEdgeIteratorState(2, 2);
+        assertEquals(2.01, sc.getDistance(), 1.e-6);
+        assertEquals(2.01, sc.getWeight(), 1.e-6);
+    }
+
     @Test
     public void testQueryGraph() {
         graph = createGHStorage();
diff --git a/reader-gtfs/src/test/java/com/graphhopper/GraphHopperMultimodalIT.java b/reader-gtfs/src/test/java/com/graphhopper/GraphHopperMultimodalIT.java
index 0fca220de..3ef9c3bc7 100644
--- a/reader-gtfs/src/test/java/com/graphhopper/GraphHopperMultimodalIT.java
+++ b/reader-gtfs/src/test/java/com/graphhopper/GraphHopperMultimodalIT.java
@@ -82,11 +82,11 @@ public class GraphHopperMultimodalIT {
 
         PathWrapper firstTransitSolution = response.getAll().stream().filter(p -> p.getLegs().size() > 1).findFirst().get(); // There can be a walk-only trip.
         assertThat(firstTransitSolution.getLegs().get(0).getDepartureTime().toInstant().atZone(zoneId).toLocalTime())
-                .isEqualTo(LocalTime.parse("06:41:04.834"));
+                .isEqualTo(LocalTime.parse("06:41:04.833"));
         assertThat(firstTransitSolution.getLegs().get(0).getArrivalTime().toInstant())
                 .isEqualTo(firstTransitSolution.getLegs().get(1).getDepartureTime().toInstant());
         assertThat(firstTransitSolution.getLegs().get(2).getArrivalTime().toInstant().atZone(zoneId).toLocalTime())
-                .isEqualTo(LocalTime.parse("06:52:02.728"));
+                .isEqualTo(LocalTime.parse("06:52:02.729"));
     }
 
     @Test
@@ -103,11 +103,11 @@ public class GraphHopperMultimodalIT {
 
         PathWrapper firstTransitSolution = response.getAll().stream().filter(p -> p.getLegs().size() > 1).findFirst().get(); // There can be a walk-only trip.
         assertThat(firstTransitSolution.getLegs().get(0).getDepartureTime().toInstant().atZone(zoneId).toLocalTime())
-                .isEqualTo(LocalTime.parse("06:41:04.834"));
+                .isEqualTo(LocalTime.parse("06:41:04.833"));
         assertThat(firstTransitSolution.getLegs().get(0).getArrivalTime().toInstant())
                 .isEqualTo(firstTransitSolution.getLegs().get(1).getDepartureTime().toInstant());
         assertThat(firstTransitSolution.getLegs().get(2).getArrivalTime().toInstant().atZone(zoneId).toLocalTime())
-                .isEqualTo(LocalTime.parse("06:52:02.728"));
+                .isEqualTo(LocalTime.parse("06:52:02.729"));
 
         PathWrapper walkSolution = response.getAll().stream().filter(p -> p.getLegs().size() == 1).findFirst().get();
         assertThat(walkSolution.getLegs().get(0).getDepartureTime().toInstant().atZone(zoneId).toLocalTime())
@@ -115,7 +115,7 @@ public class GraphHopperMultimodalIT {
         // In principle, this would dominate the transit solution, since it's faster, but
         // by default, walking gets a slight penalty.
         assertThat(walkSolution.getLegs().get(0).getArrivalTime().toInstant().atZone(zoneId).toLocalTime())
-                .isEqualTo(LocalTime.parse("06:51:10.367"));
+                .isEqualTo(LocalTime.parse("06:51:10.370"));
         assertThat(walkSolution.getLegs().size()).isEqualTo(1);
         assertThat(walkSolution.getNumChanges()).isEqualTo(-1);