Repository: graphhopper/graphhopper (java)

Issue:
Bugs in node-based CH preparation heuristics
So far there are two todos in `NodeBasedNodeContractor`, that refer to odd/false calculations regarding the CH preparation heuristics (also pointed out here: https://github.com/graphhopper/graphhopper/pull/1225#issue-153508946):

https://github.com/graphhopper/graphhopper/blob/0a967b3dd4f8a78d3cbe3bc0b64e820b950995d4/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java#L81-L86

https://github.com/graphhopper/graphhopper/blob/0a967b3dd4f8a78d3cbe3bc0b64e820b950995d4/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java#L312-L314

These are easy to fix, but fixing them probably requires re-optimizing the CH preparation parameters.

I think there is another one: One of the CH preparation heuristics counts the number of contracted neighbor nodes. Currently this is done like this:

https://github.com/graphhopper/graphhopper/blob/0a967b3dd4f8a78d3cbe3bc0b64e820b950995d4/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java#L116-L123

with:

https://github.com/graphhopper/graphhopper/blob/0a967b3dd4f8a78d3cbe3bc0b64e820b950995d4/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java#L69-L75

and:

https://github.com/graphhopper/graphhopper/blob/5c980b4627578626268873f9424de35188187441/core/src/main/java/com/graphhopper/routing/util/LevelEdgeFilter.java#L40-L52

A 'contracted neighbor' should be a node that is contracted already and connected to the current node via an edge or a shortcut. The `super.accept(edgeState)` in the `remainingNodesFilter` accepts all shortcuts and all edges that go to equal or higher CH level (we can ignore the `maxNodes` condition because there are no virtual edges during CH preparation). We increase the `contractedNeighbors` counter for every shortcut and do not increase it for non-shortcut edges. This seems wrong to me: there can be shortcuts leading to un-contracted nodes and there can be non-shortcuts leading to contracted nodes. 

So it should be something like this:

```java
// just an edge explorer using `DefaultEdgeFilter.allEdges`
EdgeIterator iter = allEdgeExplorer.setBaseNode(node);
while (iter.next()) {
     // we only calculate priorities for not yet contracted nodes
     assert chGraph.getLevel(iter.getBaseNode()) == maxLevel;
     if (chGraph.getLevel(iter.getAdjNode()) < maxLevel) {
          contractedNeighbors++;
     }
}
```

Another (probably minor/not important) thing to consider here is that there can be multiple edges/shortcuts going to the same node in which case we should not increase `contractedNeighbors` multiple times.

Pull request:
Use a fixed number of maximum visited nodes for node-based CH
This PR fixes #1810 and improves the node-based CH performance.

So far we were limiting the number of visited nodes for witness path searches based on the (estimated) 'mean degree' of the graph. However, as pointed out in #1810 there were two critical bugs in this calculation. First, the visited nodes limit was zero when building the initial queue (all witness searches were cancelled immediately) and second the cast to an int meant that the limit was also zero if `meanDegree < 1` and otherwise it would only ever be a multiple of `100`. The third bug pointed out in #1810 is obsolete as we removed the 'contracted neighbor' heuristic in the meantime.

I did new parameter studies for the node-based CH preparation and found that we get better results using a simpler approach. Instead of adjusting the visited node limit based on the mean degree of the graph I just set it to a fixed number. However, I use a different number for the heuristic calculation for the node ordering and for the actual node contraction. This way we can save time during the witness path searches that are only done to determine the node ordering without skipping too many witness path searches when actually contracting a node. I found that using a value of 30 for the heuristics and a value of 200 for the contraction work quite well. This can depend on the map and exact use-case, so it might be worthwhile to tune these values further, especially when there is a preference for a faster preparation, faster queries or less shortcuts/memory usage. 

The other thing I found out is that using (only) neighbor updates, and no periodic and no lazy updates at all works better than what we are currently doing in master. With the set of parameters I use in this PR there are less shortcuts, the preparation is faster and the query times are equal (if not faster). I tested this using maps of different sizes (Bavaria, Germany and planet). To give an example: For master I ran the preparation for planet in 4943s vs. this branch 4556s (-8%), the number of shortcuts decreased from 221mio to 194mio (-14%) and the average query time was around 1.51ms for both. Pretty good, I would say, considering that I only removed code or simplified the algorithm :)

With the new parameters the preparation is faster than before, even when we enable the `GermanyCountryRule` that uses access=destination for all tracks (related to #2375).

The only 'downside' to this PR is that now the gap between node- and edge-based CH performance is even bigger. But hopefully some of these ideas will work for edge-based CH as well.

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 899be7d9c..e37c5d03f 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,5 +1,6 @@
 ### 5.0 [not yet released]
 
+- improved node-based CH performance (faster preparation and less shortcuts(=memory usage)) (#2491)
 - the GraphHopperApplication class was moved from com.graphhopper.http to com.graphhopper.application (#2487)
 - it is now possible to add CH preparations to an existing graph folder, CH graphs no longer need to be added before
   GraphHopperStorage#freeze (#2481)
diff --git a/core/src/main/java/com/graphhopper/routing/ch/CHParameters.java b/core/src/main/java/com/graphhopper/routing/ch/CHParameters.java
index 8c3d6910b..5f7b7e718 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/CHParameters.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/CHParameters.java
@@ -12,6 +12,8 @@ public final class CHParameters {
     // node contraction, node-based
     public static final String EDGE_DIFFERENCE_WEIGHT = Parameters.CH.PREPARE + "node.edge_difference_weight";
     public static final String ORIGINAL_EDGE_COUNT_WEIGHT = Parameters.CH.PREPARE + "node.original_edge_count_weight";
+    public static final String MAX_VISITED_NODES_HEURISTIC = Parameters.CH.PREPARE + "node.max_visited_nodes_heuristic";
+    public static final String MAX_VISITED_NODES_CONTRACTION = Parameters.CH.PREPARE + "node.max_visited_nodes_contraction";
     // node contraction, edge-based
     public static final String EDGE_QUOTIENT_WEIGHT = Parameters.CH.PREPARE + "edge.edge_quotient_weight";
     public static final String ORIGINAL_EDGE_QUOTIENT_WEIGHT = Parameters.CH.PREPARE + "edge.original_edge_quotient_weight";
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 4e9c14587..5e2da23f6 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedNodeContractor.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedNodeContractor.java
@@ -102,11 +102,6 @@ class EdgeBasedNodeContractor implements NodeContractor {
         hierarchyDepths = new int[prepareGraph.getNodes()];
     }
 
-    @Override
-    public void prepareContraction() {
-        // not needed
-    }
-
     @Override
     public float calculatePriority(int node) {
         activeStats = countingStats;
diff --git a/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java b/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java
index bcb1056d0..3cfdb7b9b 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java
@@ -26,8 +26,7 @@ import java.util.ArrayList;
 import java.util.List;
 import java.util.Locale;
 
-import static com.graphhopper.routing.ch.CHParameters.EDGE_DIFFERENCE_WEIGHT;
-import static com.graphhopper.routing.ch.CHParameters.ORIGINAL_EDGE_COUNT_WEIGHT;
+import static com.graphhopper.routing.ch.CHParameters.*;
 import static com.graphhopper.util.Helper.nf;
 
 class NodeBasedNodeContractor implements NodeContractor {
@@ -59,6 +58,8 @@ class NodeBasedNodeContractor implements NodeContractor {
     private void extractParams(PMap pMap) {
         params.edgeDifferenceWeight = pMap.getFloat(EDGE_DIFFERENCE_WEIGHT, params.edgeDifferenceWeight);
         params.originalEdgesCountWeight = pMap.getFloat(ORIGINAL_EDGE_COUNT_WEIGHT, params.originalEdgesCountWeight);
+        params.maxVisitedNodesHeuristic = pMap.getInt(MAX_VISITED_NODES_HEURISTIC, params.maxVisitedNodesHeuristic);
+        params.maxVisitedNodesContraction = pMap.getInt(MAX_VISITED_NODES_CONTRACTION, params.maxVisitedNodesContraction);
     }
 
     @Override
@@ -67,16 +68,7 @@ class NodeBasedNodeContractor implements NodeContractor {
         outEdgeExplorer = prepareGraph.createOutEdgeExplorer();
         existingShortcutExplorer = prepareGraph.createOutEdgeExplorer();
         witnessPathSearcher = new NodeBasedWitnessPathSearcher(prepareGraph);
-    }
-
-    @Override
-    public void prepareContraction() {
-        // todo: initializing meanDegree here instead of in initFromGraph() means that in the first round of calculating
-        // node priorities all shortcut searches are cancelled immediately and all possible shortcuts are counted because
-        // no witness path can be found. this is not really what we want, but changing it requires re-optimizing the
-        // graph contraction parameters, because it affects the node contraction order.
-        // when this is done there should be no need for this method any longer.
-        meanDegree = prepareGraph.getOriginalEdges() / prepareGraph.getNodes();
+        meanDegree = prepareGraph.getOriginalEdges() * 1.0 / prepareGraph.getNodes();
     }
 
     @Override
@@ -105,7 +97,7 @@ class NodeBasedNodeContractor implements NodeContractor {
         // originalEdgesCount = σ(v) := sum_{ (u,w) ∈ shortcuts(v) } of r(u, w)
         shortcutsCount = 0;
         originalEdgesCount = 0;
-        findAndHandleShortcuts(node, this::countShortcuts);
+        findAndHandleShortcuts(node, this::countShortcuts, params.maxVisitedNodesHeuristic);
 
         // from shortcuts we can compute the edgeDifference
         // # low influence: with it the shortcut creation is slightly faster
@@ -124,7 +116,7 @@ class NodeBasedNodeContractor implements NodeContractor {
 
     @Override
     public IntContainer contractNode(int node) {
-        long degree = findAndHandleShortcuts(node, this::addOrUpdateShortcut);
+        long degree = findAndHandleShortcuts(node, this::addOrUpdateShortcut, params.maxVisitedNodesContraction);
         insertShortcuts(node);
         // put weight factor on meanDegree instead of taking the average => meanDegree is more stable
         meanDegree = (meanDegree * 2 + degree) / 3;
@@ -214,8 +206,7 @@ class NodeBasedNodeContractor implements NodeContractor {
      * Returns the 'degree' of the given node (disregarding edges from/to already contracted nodes).
      * Note that here the degree is not the total number of adjacent edges, but only the number of incoming edges
      */
-    private long findAndHandleShortcuts(int node, PrepareShortcutHandler handler) {
-        int maxVisitedNodes = getMaxVisitedNodesEstimate();
+    private long findAndHandleShortcuts(int node, PrepareShortcutHandler handler, int maxVisitedNodes) {
         long degree = 0;
         PrepareGraphEdgeIterator incomingEdges = inEdgeExplorer.setBaseNode(node);
         // collect outgoing nodes (goal-nodes) only once
@@ -307,12 +298,6 @@ class NodeBasedNodeContractor implements NodeContractor {
         return dijkstraSW.getCurrentSeconds();
     }
 
-    private int getMaxVisitedNodesEstimate() {
-        // todo: we return 0 here if meanDegree is < 1, which is not really what we want, but changing this changes
-        // the node contraction order and requires re-optimizing the parameters of the graph contraction
-        return (int) meanDegree * 100;
-    }
-
     @FunctionalInterface
     private interface PrepareShortcutHandler {
         void handleShortcut(int fromNode, int toNode, double existingDirectWeight,
@@ -324,6 +309,12 @@ class NodeBasedNodeContractor implements NodeContractor {
         // default values were optimized for Unterfranken
         private float edgeDifferenceWeight = 10;
         private float originalEdgesCountWeight = 1;
+        // these values seemed to work best for planet (fast prep without compromising too much for the query time)
+        // higher values can further decrease the number of shortcuts and improve the query time, but only by a few
+        // percent and at the cost of a longer preparation. for smaller maps smaller values can work even better, i.e.
+        // try 20/100 or similar.
+        private int maxVisitedNodesHeuristic = 30;
+        private int maxVisitedNodesContraction = 200;
     }
 
     private static class Shortcut {
@@ -358,5 +349,4 @@ class NodeBasedNodeContractor implements NodeContractor {
             return str + to + ", weight:" + weight + " (" + skippedEdge1 + "," + skippedEdge2 + ")";
         }
     }
-
-}
+}
\ No newline at end of file
diff --git a/core/src/main/java/com/graphhopper/routing/ch/NodeContractor.java b/core/src/main/java/com/graphhopper/routing/ch/NodeContractor.java
index 5def209c9..62b8d8db8 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/NodeContractor.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/NodeContractor.java
@@ -47,5 +47,4 @@ public interface NodeContractor {
 
     float getDijkstraSeconds();
 
-    void prepareContraction();
 }
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 b18bb62f3..27949217d 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java
@@ -223,7 +223,6 @@ public class PrepareContractionHierarchies {
         // but has always been like that and changing it would possibly require retuning the contraction parameters
         updatePrioritiesOfRemainingNodes();
         logger.info("Finished building queue, took: {}s, {}", sw.stop().getSeconds(), getMemInfo());
-        nodeContractor.prepareContraction();
         final int initSize = sortedNodes.size();
         int level = 0;
         checkCounter = 0;
@@ -323,7 +322,6 @@ public class PrepareContractionHierarchies {
     }
 
     private void contractNodesUsingFixedNodeOrdering() {
-        nodeContractor.prepareContraction();
         final int nodesToContract = nodeOrderingProvider.getNumNodes();
         final int logSize = Math.max(10, (int) (params.getLogMessagesPercentage() / 100.0 * nodesToContract));
         StopWatch stopWatch = new StopWatch();
@@ -528,7 +526,7 @@ public class PrepareContractionHierarchies {
                 // todo: optimize
                 return new Params(0, 100, 0, 100, 5);
             } else {
-                return new Params(20, 10, 20, 100, 20);
+                return new Params(0, 0, 100, 100, 20);
             }
         }
 


Test patch:
diff --git a/core/src/test/java/com/graphhopper/GraphHopperTest.java b/core/src/test/java/com/graphhopper/GraphHopperTest.java
index f485906c2..0f8cc07bb 100644
--- a/core/src/test/java/com/graphhopper/GraphHopperTest.java
+++ b/core/src/test/java/com/graphhopper/GraphHopperTest.java
@@ -95,8 +95,8 @@ public class GraphHopperTest {
             ASTAR + ",false,444",
             DIJKSTRA_BI + ",false,228",
             ASTAR_BI + ",false,184",
-            ASTAR_BI + ",true,36",
-            DIJKSTRA_BI + ",true,30"
+            ASTAR_BI + ",true,67",
+            DIJKSTRA_BI + ",true,65"
     })
     public void testMonacoDifferentAlgorithms(String algo, boolean withCH, int expectedVisitedNodes) {
         final String vehicle = "car";
@@ -308,7 +308,7 @@ public class GraphHopperTest {
             ResponsePath bestPath = rsp.getBest();
             long sum = rsp.getHints().getLong("visited_nodes.sum", 0);
             assertNotEquals(sum, 0);
-            assertTrue(sum < 125, "Too many nodes visited " + sum);
+            assertTrue(sum < 155, "Too many nodes visited " + sum);
             assertEquals(3535, bestPath.getDistance(), 1);
             assertEquals(115, bestPath.getPoints().size());
         }
@@ -1374,7 +1374,7 @@ public class GraphHopperTest {
         // identify the number of counts to compare with none-CH foot route which had nearly 700 counts
         long sum = rsp.getHints().getLong("visited_nodes.sum", 0);
         assertNotEquals(sum, 0);
-        assertTrue(sum < 120, "Too many nodes visited " + sum);
+        assertTrue(sum < 145, "Too many nodes visited " + sum);
         assertEquals(3437.1, bestPath.getDistance(), .1);
         assertEquals(85, bestPath.getPoints().size());
 
@@ -1494,7 +1494,7 @@ public class GraphHopperTest {
 
         GHResponse rsp = hopper.route(req);
         long chSum = rsp.getHints().getLong("visited_nodes.sum", 0);
-        assertTrue(chSum < 60, "Too many visited nodes for ch mode " + chSum);
+        assertTrue(chSum < 70, "Too many visited nodes for ch mode " + chSum);
         ResponsePath bestPath = rsp.getBest();
         assertEquals(3587, bestPath.getDistance(), 1);
         assertEquals(91, bestPath.getPoints().size());
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 0af65173b..b44f9973f 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/NodeBasedNodeContractorTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ch/NodeBasedNodeContractorTest.java
@@ -59,7 +59,6 @@ public class NodeBasedNodeContractorTest {
         CHPreparationGraph.buildFromGraph(prepareGraph, g, g.createCHGraph(store, chConfig).getWeighting());
         NodeContractor nodeContractor = new NodeBasedNodeContractor(prepareGraph, new CHStorageBuilder(store), new PMap());
         nodeContractor.initFromGraph();
-        nodeContractor.prepareContraction();
         return nodeContractor;
     }