Repository: graphhopper/graphhopper
Pull request #1534 (2019-02-04 09:06:36)

Allows reusing CH node ordering.
As discussed in #1509  this PR allows re-using the node ordering in between CH contractions. Since we were already storing CH levels no additional DataAccess is needed and I only added a method to retrieve the inverse of the ch levels (switch array indices and levels).  A performance test on the map of Germany showed this:

|profile|contraction time|average query time|
|-|-|-|
|car|672s|0.97ms|
|motorcycle|445s|0.80ms|
|motorcycle with ordering from car|149s|0.86ms|
|car with ordering from motorcycle|>>672s|?|

The test shows that for example reusing the car ordering for motorcycle speeds up the preparation by a factor of about 3 and does not alter the query time too much. However, reusing the motorcycle ordering for car did not work at all, i.e. the preparation took (a lot) longer than when recalculating the ordering heuristically.
So I think in some cases re-using the node ordering can be beneficial, but the pre-processing is still too slow for a flexible scenario and it is hard to know beforehand whether it leads to good results. For example I do not understand why reusing the motorcycle ordering for car is so slow.

The shown query time is an average over 50k random queries without path unpacking and location lookup. For the profiles I used `FastestWeighting` with `Car/MotorcycleFlagEncoder`.

In any case using a fixed node ordering is quite useful for testing (previously in `ManualPrepareContractionHierarchies`).
I also added a `CHGraph#isFrozen()` check to `PrepareContractionHierarchies` to be a bit more defensive there.

easbar: Ok I ran a few tests with random weight (not speed) deviations (+/- the given percentage) on the map of Germany. I also added the test to this PR, TrafficChangeWithNodeOrderingReusingTest`.

|max weight deviation (%)| contraction time (s)| querying time (ms)| contraction time, with deviations, reused node ordering (s) | querying time, with deviations, reused node ordering (ms)|
|-|-|-|-|-|
|0|599|0.98|148|1.01|
|5|629|1.02|159|1.00|
|10|610|0.98|151|1.05|
|50|598|0.93|183|1.16|

So it looks like up to 10% weight deviations the query speed is hardly affected at all and even with 50% deviation it stays close to the original query speed. I guess for a more realistic scenario it would be better to use real traffic data instead of random weights (often whole roads will be blocked by traffic not single road segments).

Maybe a better model is to only consider *increases* of the weights (so the deviations do not cancel out each other). I tested this for Bavaria:

|max weight deviation (%)| contraction time (s)| querying time (ms)| contraction time, with deviations, reused node ordering (s) | querying time, with deviations, reused node ordering (ms)|
|-|-|-|-|-|
|0|103|0.53|27|0.52|
|1|103|0.55|25|0.48|
|5|102|0.51|26|0.49|
|10|101|0.50|26|0.49|
|50|101|0.50|28|0.55|

This did not change (rather confirmed) my conclusions above.
karussell: Thanks for the fixes and of course for the analysis, this looks promising! So I'll squash&merge (?)
easbar: >  So I'll squash&merge (?)

Yes, from my side this is ready.

Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/ch/ManualPrepareContractionHierarchies.java b/core/src/main/java/com/graphhopper/routing/ch/ManualPrepareContractionHierarchies.java
deleted file mode 100644
index ca82dc83a..000000000
--- a/core/src/main/java/com/graphhopper/routing/ch/ManualPrepareContractionHierarchies.java
+++ /dev/null
@@ -1,113 +0,0 @@
-/*
- *  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.ch;
-
-import com.graphhopper.routing.util.DefaultEdgeFilter;
-import com.graphhopper.routing.util.EdgeFilter;
-import com.graphhopper.routing.util.TraversalMode;
-import com.graphhopper.routing.weighting.Weighting;
-import com.graphhopper.storage.CHGraph;
-import com.graphhopper.storage.Directory;
-import com.graphhopper.storage.GraphHopperStorage;
-import com.graphhopper.util.CHEdgeExplorer;
-import com.graphhopper.util.CHEdgeIterator;
-import com.graphhopper.util.StopWatch;
-
-import java.util.*;
-
-import static com.graphhopper.util.Helper.nf;
-
-/**
- * Makes it possible to control the node contraction order in contraction hierarchies, which is useful for debugging
- * and performance analysis.
- * todo: remove this class and move the same functionality into PrepareContractionHierarchies. Also this should be
- * extended to the case where we can save/load the contraction order to/from disk. For example when we use another
- * vehicle profile we still might get reasonable results for a previous contraction order. see #1509
- */
-public class ManualPrepareContractionHierarchies extends PrepareContractionHierarchies {
-    private List<Integer> contractionOrder = new ArrayList<>();
-
-    public ManualPrepareContractionHierarchies(CHGraph chGraph, Weighting weighting, TraversalMode traversalMode) {
-        super(chGraph, weighting, traversalMode);
-    }
-
-    ManualPrepareContractionHierarchies setContractionOrder(List<Integer> contractionOrder) {
-        this.contractionOrder = contractionOrder;
-        return this;
-    }
-
-    @Override
-    public String toString() {
-        return super.toString() + "|manual";
-    }
-
-    @Override
-    protected void runGraphContraction() {
-        setMaxLevelOnAllNodes();
-        contractNodes();
-    }
-
-    private void setMaxLevelOnAllNodes() {
-        int nodes = prepareGraph.getNodes();
-        for (int node = 0; node < nodes; node++) {
-            prepareGraph.setLevel(node, nodes);
-        }
-    }
-
-    private void contractNodes() {
-        if (contractionOrder.size() != prepareGraph.getNodes()) {
-            throw new IllegalArgumentException(String.format(Locale.ROOT,
-                    "contraction order size (%d) must be equal to number of nodes in graph (%d)",
-                    contractionOrder.size(), prepareGraph.getNodes()));
-        }
-        final EdgeFilter allFilter = DefaultEdgeFilter.allEdges(prepareWeighting.getFlagEncoder());
-        CHEdgeExplorer explorer = prepareGraph.createEdgeExplorer(allFilter);
-        CHEdgeExplorer discExplorer = prepareGraph.createEdgeExplorer(allFilter);
-        final int nodesToContract = contractionOrder.size();
-        final long logSize = 10;
-        StopWatch stopWatch = new StopWatch();
-        for (int i = 0; i < nodesToContract; ++i) {
-            stopWatch.start();
-            int node = contractionOrder.get(i);
-            // contract node
-            nodeContractor.contractNode(node);
-            long shortcutCount = nodeContractor.getAddedShortcutsCount();
-            prepareGraph.setLevel(node, i);
-
-            // disconnect neighbors
-            CHEdgeIterator iter = explorer.setBaseNode(node);
-            while (iter.next()) {
-                if (prepareGraph.getLevel(iter.getAdjNode()) != maxLevel)
-                    continue;
-                prepareGraph.disconnect(discExplorer, iter);
-            }
-            stopWatch.stop();
-            if (i % logSize == 0) {
-                logger.info(String.format(Locale.ROOT,
-                        "contracted %s / %s nodes, shortcuts: %s, last batch took: %.2f s, time per node: %.2f micros, %s",
-                        nf(i),
-                        nf(nodesToContract),
-                        nf(shortcutCount),
-                        stopWatch.getSeconds(),
-                        stopWatch.getNanos() / logSize * 1.e-3,
-                        nodeContractor.getStatisticsString()));
-            }
-        }
-    }
-
-}
diff --git a/core/src/main/java/com/graphhopper/routing/ch/NodeOrderingProvider.java b/core/src/main/java/com/graphhopper/routing/ch/NodeOrderingProvider.java
new file mode 100644
index 000000000..da5377c18
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/ch/NodeOrderingProvider.java
@@ -0,0 +1,7 @@
+package com.graphhopper.routing.ch;
+
+public interface NodeOrderingProvider {
+    int getNodeIdForLevel(int level);
+
+    int getNumNodes();
+}
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 7c51d6bd9..6af742cc7 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java
@@ -51,11 +51,11 @@ import static com.graphhopper.util.Parameters.Algorithms.DIJKSTRA_BI;
  * @author Peter Karich
  */
 public class PrepareContractionHierarchies extends AbstractAlgoPreparation implements RoutingAlgorithmFactory {
-    final Logger logger = LoggerFactory.getLogger(getClass());
-    final PreparationWeighting prepareWeighting;
+    private final Logger logger = LoggerFactory.getLogger(getClass());
+    private final PreparationWeighting prepareWeighting;
     private final Weighting weighting;
     private final TraversalMode traversalMode;
-    final CHGraph prepareGraph;
+    private final CHGraph prepareGraph;
     private final Random rand = new Random(123);
     private final StopWatch allSW = new StopWatch();
     private final StopWatch periodicUpdateSW = new StopWatch();
@@ -63,15 +63,15 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation imple
     private final StopWatch neighborUpdateSW = new StopWatch();
     private final StopWatch contractionSW = new StopWatch();
     private final Params params;
-    NodeContractor nodeContractor;
+    private NodeContractor nodeContractor;
+    private NodeOrderingProvider nodeOrderingProvider;
     private CHEdgeExplorer vehicleAllExplorer;
     private CHEdgeExplorer vehicleAllTmpExplorer;
-    int maxLevel;
+    private int maxLevel;
     // nodes with highest priority come last
     private GHTreeMapComposed sortedNodes;
     private float[] oldPriorities;
     private PMap pMap = new PMap();
-    private int initSize;
     private int checkCounter;
 
     public PrepareContractionHierarchies(CHGraph chGraph, Weighting weighting, TraversalMode traversalMode) {
@@ -96,32 +96,49 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation imple
         return this;
     }
 
+    /**
+     * Instead of heuristically determining a node ordering for the graph contraction it is also possible
+     * to use a fixed ordering. For example this allows re-using a previously calculated node ordering.
+     * This will speed up CH preparation, but might lead to slower queries.
+     */
+    public PrepareContractionHierarchies useFixedNodeOrdering(NodeOrderingProvider nodeOrderingProvider) {
+        if (nodeOrderingProvider.getNumNodes() != prepareGraph.getNodes()) {
+            throw new IllegalArgumentException(
+                    "contraction order size (" + nodeOrderingProvider.getNumNodes() + ")" +
+                            " must be equal to number of nodes in graph (" + prepareGraph.getNodes() + ").");
+        }
+        this.nodeOrderingProvider = nodeOrderingProvider;
+        return this;
+    }
+
     @Override
     public void doSpecificWork() {
+        if (!prepareGraph.isReadyForContraction()) {
+            throw new IllegalStateException("Given CHGraph has not been frozen yet");
+        }
         allSW.start();
         initFromGraph();
         runGraphContraction();
+        allSW.stop();
+        logFinalGraphStats();
+    }
 
-        logger.info("took:" + (int) allSW.stop().getSeconds() + "s "
-                + ", new shortcuts: " + nf(nodeContractor.getAddedShortcutsCount())
-                + ", initSize:" + nf(initSize)
-                + ", " + prepareWeighting
-                + ", periodic:" + params.getPeriodicUpdatesPercentage()
-                + ", lazy:" + params.getLastNodesLazyUpdatePercentage()
-                + ", neighbor:" + params.getNeighborUpdatePercentage()
-                + ", " + getTimesAsString()
-                + ", lazy-overhead: " + (int) (100 * ((checkCounter / (double) initSize) - 1)) + "%"
-                + ", " + Helper.getMemInfo());
-
+    private void logFinalGraphStats() {
         int edgeCount = prepareGraph.getOriginalEdges();
-        logger.info("graph now - num edges: {}, num nodes: {}, num shortcuts: {}",
-                nf(edgeCount), nf(prepareGraph.getNodes()), nf(prepareGraph.getEdges() - edgeCount));
+        logger.info("took: {}s, graph now - num edges: {}, num nodes: {}, num shortcuts: {}",
+                (int) allSW.getSeconds(), nf(edgeCount), nf(prepareGraph.getNodes()), nf(prepareGraph.getEdges() - edgeCount));
     }
 
-    protected void runGraphContraction() {
-        if (!prepareNodes())
+    private void runGraphContraction() {
+        if (prepareGraph.getNodes() < 1)
             return;
-        contractNodes();
+        setMaxLevelOnAllNodes();
+        if (nodeOrderingProvider != null) {
+            contractNodesUsingFixedNodeOrdering();
+        } else {
+            contractNodesUsingHeuristicNodeOrdering();
+        }
+
     }
 
     @Override
@@ -188,24 +205,32 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation imple
         nodeContractor.initFromGraph();
     }
 
-    private boolean prepareNodes() {
-        int nodes = prepareGraph.getNodes();
+    private void setMaxLevelOnAllNodes() {
+        final int nodes = prepareGraph.getNodes();
         for (int node = 0; node < nodes; node++) {
             prepareGraph.setLevel(node, maxLevel);
         }
+    }
+
+    private void updatePrioritiesOfRemainingNodes() {
         periodicUpdateSW.start();
+        sortedNodes.clear();
+        final int nodes = prepareGraph.getNodes();
         for (int node = 0; node < nodes; node++) {
+            if (prepareGraph.getLevel(node) != maxLevel)
+                continue;
             float priority = oldPriorities[node] = calculatePriority(node);
             sortedNodes.insert(node, priority);
         }
         periodicUpdateSW.stop();
-
-        return !sortedNodes.isEmpty();
     }
 
-    private void contractNodes() {
+    private void contractNodesUsingHeuristicNodeOrdering() {
+        // note that we update the priorities before preparing the node contractor. this does not make much sense,
+        // but has always been like that and changing it would possibly require retuning the contraction parameters
+        updatePrioritiesOfRemainingNodes();
         nodeContractor.prepareContraction();
-        initSize = sortedNodes.getSize();
+        int initSize = sortedNodes.getSize();
         int level = 0;
         checkCounter = 0;
         long logSize = Math.round(Math.max(10, initSize / 100d * params.getLogMessagesPercentage()));
@@ -238,23 +263,14 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation imple
         while (!sortedNodes.isEmpty()) {
             // periodically update priorities of ALL nodes
             if (periodicUpdate && checkCounter > 0 && checkCounter % periodicUpdatesCount == 0) {
-                periodicUpdateSW.start();
-                sortedNodes.clear();
-                for (int node = 0; node < prepareGraph.getNodes(); node++) {
-                    if (prepareGraph.getLevel(node) != maxLevel)
-                        continue;
-
-                    float priority = oldPriorities[node] = calculatePriority(node);
-                    sortedNodes.insert(node, priority);
-                }
-                periodicUpdateSW.stop();
+                updatePrioritiesOfRemainingNodes();
                 updateCounter++;
                 if (sortedNodes.isEmpty())
                     throw new IllegalStateException("Cannot prepare as no unprepared nodes where found. Called preparation twice?");
             }
 
             if (checkCounter % logSize == 0) {
-                logStats(updateCounter);
+                logHeuristicStats(updateCounter);
             }
 
             checkCounter++;
@@ -273,11 +289,8 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation imple
             }
 
             // contract node v!
-            contractionSW.start();
-            nodeContractor.contractNode(polledNode);
-            prepareGraph.setLevel(polledNode, level);
+            contractNode(polledNode, level);
             level++;
-            contractionSW.stop();
 
             if (sortedNodes.getSize() < nodesToAvoidContract)
                 // skipped nodes are already set to maxLevel
@@ -311,13 +324,81 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation imple
             }
         }
 
-        logStats(updateCounter);
+        logHeuristicStats(updateCounter);
+
+        logger.info(
+                "new shortcuts: " + nf(nodeContractor.getAddedShortcutsCount())
+                        + ", initSize:" + nf(initSize)
+                        + ", " + prepareWeighting
+                        + ", periodic:" + params.getPeriodicUpdatesPercentage()
+                        + ", lazy:" + params.getLastNodesLazyUpdatePercentage()
+                        + ", neighbor:" + params.getNeighborUpdatePercentage()
+                        + ", " + getTimesAsString()
+                        + ", lazy-overhead: " + (int) (100 * ((checkCounter / (double) initSize) - 1)) + "%"
+                        + ", " + Helper.getMemInfo());
 
         // Preparation works only once so we can release temporary data.
         // The preparation object itself has to be intact to create the algorithm.
         close();
     }
 
+    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();
+        stopWatch.start();
+        for (int i = 0; i < nodesToContract; ++i) {
+            int node = nodeOrderingProvider.getNodeIdForLevel(i);
+            contractNode(node, i);
+
+            // disconnect neighbors
+            CHEdgeIterator iter = vehicleAllExplorer.setBaseNode(node);
+            while (iter.next()) {
+                if (prepareGraph.getLevel(iter.getAdjNode()) != maxLevel)
+                    continue;
+                prepareGraph.disconnect(vehicleAllTmpExplorer, iter);
+            }
+            if (i % logSize == 0) {
+                stopWatch.stop();
+                logFixedNodeOrderingStats(i, logSize, stopWatch);
+                stopWatch.start();
+            }
+        }
+    }
+
+    private void contractNode(int node, int level) {
+        contractionSW.start();
+        nodeContractor.contractNode(node);
+        prepareGraph.setLevel(node, level);
+        contractionSW.stop();
+    }
+
+    private void logHeuristicStats(int updateCounter) {
+        logger.info(String.format(Locale.ROOT,
+                "nodes: %10s, shortcuts: %10s, updates: %2d, checked-nodes: %10s, %s, %s, %s",
+                nf(sortedNodes.getSize()),
+                nf(nodeContractor.getAddedShortcutsCount()),
+                updateCounter,
+                nf(checkCounter),
+                getTimesAsString(),
+                nodeContractor.getStatisticsString(),
+                Helper.getMemInfo()));
+    }
+
+    private void logFixedNodeOrderingStats(int nodesContracted, int logSize, StopWatch stopWatch) {
+        logger.info(String.format(Locale.ROOT,
+                "nodes: %10s / %10s (%6.2f%%), shortcuts: %10s, speed = %6.2f nodes/ms, %s, %s",
+                nf(nodesContracted),
+                nf(prepareGraph.getNodes()),
+                (100.0 * nodesContracted / prepareGraph.getNodes()),
+                nf(nodeContractor.getAddedShortcutsCount()),
+                nodesContracted == 0 ? 0 : logSize / (double) stopWatch.getMillis(),
+                nodeContractor.getStatisticsString(),
+                Helper.getMemInfo())
+        );
+    }
+
     private void close() {
         nodeContractor.close();
         sortedNodes = null;
@@ -391,18 +472,6 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation imple
         return new TurnWeighting(prepareWeighting, turnCostExtension);
     }
 
-    private void logStats(int updateCounter) {
-        logger.info(String.format(Locale.ROOT,
-                "nodes: %10s, shortcuts: %10s, updates: %2d, checked-nodes: %10s, %s, %s, %s",
-                nf(sortedNodes.getSize()),
-                nf(nodeContractor.getAddedShortcutsCount()),
-                updateCounter,
-                nf(checkCounter),
-                getTimesAsString(),
-                nodeContractor.getStatisticsString(),
-                Helper.getMemInfo()));
-    }
-
     private static class Params {
         /**
          * Specifies how often periodic updates will happen. The higher the value the longer the preparation takes
diff --git a/core/src/main/java/com/graphhopper/storage/CHGraph.java b/core/src/main/java/com/graphhopper/storage/CHGraph.java
index ea26cc18d..a6fe64b60 100644
--- a/core/src/main/java/com/graphhopper/storage/CHGraph.java
+++ b/core/src/main/java/com/graphhopper/storage/CHGraph.java
@@ -17,6 +17,7 @@
  */
 package com.graphhopper.storage;
 
+import com.graphhopper.routing.ch.NodeOrderingProvider;
 import com.graphhopper.routing.util.AllCHEdgesIterator;
 import com.graphhopper.routing.util.EdgeFilter;
 import com.graphhopper.util.CHEdgeExplorer;
@@ -82,4 +83,11 @@ public interface CHGraph extends Graph {
      * @return the number of original edges in this graph (without shortcuts)
      */
     int getOriginalEdges();
+
+    NodeOrderingProvider getNodeOrderingProvider();
+
+    /**
+     * @return true if contraction can be started (add shortcuts and set levels), false otherwise
+     */
+    boolean isReadyForContraction();
 }
diff --git a/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java b/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
index ed320970b..2b4893ad0 100644
--- a/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
+++ b/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
@@ -17,6 +17,7 @@
  */
 package com.graphhopper.storage;
 
+import com.graphhopper.routing.ch.NodeOrderingProvider;
 import com.graphhopper.routing.ch.PrepareEncoder;
 import com.graphhopper.routing.util.AllCHEdgesIterator;
 import com.graphhopper.routing.util.EdgeFilter;
@@ -64,6 +65,7 @@ public class CHGraphImpl implements CHGraph, Storable<CHGraph> {
     // shortcut memory layout is synced with edges indices until E_FLAGS, then:
     private int S_SKIP_EDGE1, S_SKIP_EDGE2, S_ORIG_FIRST, S_ORIG_LAST;
     private int shortcutCount = 0;
+    private boolean isReadyForContraction;
 
     CHGraphImpl(Weighting w, Directory dir, final BaseGraph baseGraph, boolean edgeBased) {
         if (w == null)
@@ -254,7 +256,15 @@ public class CHGraphImpl implements CHGraph, Storable<CHGraph> {
         return baseGraph.getBounds();
     }
 
-    void _freeze() {
+    @Override
+    public boolean isReadyForContraction() {
+        return isReadyForContraction;
+    }
+
+    void _prepareForContraction() {
+        if (isReadyForContraction) {
+            return;
+        }
         long maxCapacity = ((long) getNodes()) * nodeCHEntryBytes;
         nodesCH.ensureCapacity(maxCapacity);
         long baseCapacity = baseGraph.nodes.getCapacity();
@@ -269,6 +279,7 @@ public class CHGraphImpl implements CHGraph, Storable<CHGraph> {
 
             nodesCH.setInt(pointer, baseGraph.nodes.getInt(basePointer));
         }
+        isReadyForContraction = true;
     }
 
     String toDetailsString() {
@@ -282,6 +293,8 @@ public class CHGraphImpl implements CHGraph, Storable<CHGraph> {
         CHEdgeIterator tmpIter = explorer.setBaseNode(edgeState.getAdjNode());
         int tmpPrevEdge = EdgeIterator.NO_EDGE;
         while (tmpIter.next()) {
+            // note that we do not disconnect original edges, because we are re-using the base graph for different profiles,
+            // even though this is not optimal from a speed performance point of view.
             if (tmpIter.isShortcut() && tmpIter.getEdge() == edgeState.getEdge()) {
                 // TODO this is ugly, move this somehow into the underlying iteration logic
                 long edgePointer = tmpPrevEdge == EdgeIterator.NO_EDGE ? -1
@@ -332,6 +345,14 @@ public class CHGraphImpl implements CHGraph, Storable<CHGraph> {
         return weight;
     }
 
+    void loadNodesHeader() {
+        isReadyForContraction = nodesCH.getHeader(0 * 4) == 1;
+    }
+
+    void setNodesHeader() {
+        nodesCH.setHeader(0 * 4, isReadyForContraction ? 1 : 0);
+    }
+
     protected int loadEdgesHeader() {
         shortcutCount = shortcuts.getHeader(0 * 4);
         shortcutEntryBytes = shortcuts.getHeader(1 * 4);
@@ -404,6 +425,7 @@ public class CHGraphImpl implements CHGraph, Storable<CHGraph> {
         if (!nodesCH.loadExisting() || !shortcuts.loadExisting())
             return false;
 
+        loadNodesHeader();
         loadEdgesHeader();
         return true;
     }
@@ -467,6 +489,29 @@ public class CHGraphImpl implements CHGraph, Storable<CHGraph> {
         }
     }
 
+    public NodeOrderingProvider getNodeOrderingProvider() {
+        int numNodes = getNodes();
+        final int[] nodeOrdering = new int[numNodes];
+        // the node ordering is the inverse of the ch levels
+        // if we really want to save some memory it could be still reasonable to not create the node ordering here,
+        // but search nodesCH for a given level on demand.
+        for (int i = 0; i < numNodes; ++i) {
+            int level = getLevel(i);
+            nodeOrdering[level] = i;
+        }
+        return new NodeOrderingProvider() {
+            @Override
+            public int getNodeIdForLevel(int level) {
+                return nodeOrdering[level];
+            }
+
+            @Override
+            public int getNumNodes() {
+                return nodeOrdering.length;
+            }
+        };
+    }
+
     class CHEdgeIteratorImpl extends EdgeIterable implements CHEdgeExplorer, CHEdgeIterator {
         public CHEdgeIteratorImpl(BaseGraph baseGraph, EdgeAccess edgeAccess, EdgeFilter filter) {
             super(baseGraph, edgeAccess, filter);
diff --git a/core/src/main/java/com/graphhopper/storage/GraphHopperStorage.java b/core/src/main/java/com/graphhopper/storage/GraphHopperStorage.java
index 5986edfbe..f9832ae9f 100644
--- a/core/src/main/java/com/graphhopper/storage/GraphHopperStorage.java
+++ b/core/src/main/java/com/graphhopper/storage/GraphHopperStorage.java
@@ -81,7 +81,7 @@ public final class GraphHopperStorage implements GraphStorage, Graph {
             @Override
             public void freeze() {
                 for (CHGraphImpl cg : getAllCHGraphs()) {
-                    cg._freeze();
+                    cg._prepareForContraction();
                 }
             }
         };
@@ -326,6 +326,7 @@ public final class GraphHopperStorage implements GraphStorage, Graph {
     @Override
     public void flush() {
         for (CHGraphImpl cg : getAllCHGraphs()) {
+            cg.setNodesHeader();
             cg.setEdgesHeader();
             cg.flush();
         }


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/ch/CHTurnCostTest.java b/core/src/test/java/com/graphhopper/routing/ch/CHTurnCostTest.java
index ad1a2e1e5..bb83ca881 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/CHTurnCostTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ch/CHTurnCostTest.java
@@ -749,12 +749,22 @@ public class CHTurnCostTest {
         return chAlgo.calcPath(from, to);
     }
 
-    private RoutingAlgorithmFactory prepareCH(List<Integer> contractionOrder) {
+    private RoutingAlgorithmFactory prepareCH(final List<Integer> contractionOrder) {
         LOGGER.debug("Calculating CH with contraction order {}", contractionOrder);
         graph.freeze();
-        ManualPrepareContractionHierarchies ch = new ManualPrepareContractionHierarchies(
-                chGraph, weighting, TraversalMode.EDGE_BASED_2DIR)
-                .setContractionOrder(contractionOrder);
+        NodeOrderingProvider nodeOrderingProvider = new NodeOrderingProvider() {
+            @Override
+            public int getNodeIdForLevel(int level) {
+                return contractionOrder.get(level);
+            }
+
+            @Override
+            public int getNumNodes() {
+                return contractionOrder.size();
+            }
+        };
+        PrepareContractionHierarchies ch = new PrepareContractionHierarchies(chGraph, weighting, TraversalMode.EDGE_BASED_2DIR)
+                .useFixedNodeOrdering(nodeOrderingProvider);
         ch.doWork();
         return ch;
     }
diff --git a/core/src/test/java/com/graphhopper/routing/ch/PrepareContractionHierarchiesTest.java b/core/src/test/java/com/graphhopper/routing/ch/PrepareContractionHierarchiesTest.java
index e060054f3..2521384ee 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/PrepareContractionHierarchiesTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ch/PrepareContractionHierarchiesTest.java
@@ -20,10 +20,7 @@ package com.graphhopper.routing.ch;
 import com.carrotsearch.hppc.IntArrayList;
 import com.carrotsearch.hppc.IntIndexedContainer;
 import com.graphhopper.routing.*;
-import com.graphhopper.routing.util.BikeFlagEncoder;
-import com.graphhopper.routing.util.CarFlagEncoder;
-import com.graphhopper.routing.util.EncodingManager;
-import com.graphhopper.routing.util.TraversalMode;
+import com.graphhopper.routing.util.*;
 import com.graphhopper.routing.weighting.FastestWeighting;
 import com.graphhopper.routing.weighting.ShortestWeighting;
 import com.graphhopper.routing.weighting.Weighting;
@@ -32,10 +29,10 @@ import com.graphhopper.util.*;
 import org.junit.Before;
 import org.junit.Test;
 
-import java.util.Arrays;
-import java.util.List;
+import java.util.*;
 
 import static com.graphhopper.util.Parameters.Algorithms.DIJKSTRA_BI;
+import static junit.framework.TestCase.assertTrue;
 import static org.junit.Assert.*;
 
 /**
@@ -363,6 +360,56 @@ public class PrepareContractionHierarchiesTest {
         assertEquals(IntArrayList.from(10, 0, 1, 2, 3, 4, 5, 6), p.calcNodes());
     }
 
+    @Test
+    public void testDisconnects() {
+        final GraphHopperStorage g = createGHStorage();
+        CHGraph lg = g.getGraph(CHGraph.class);
+        //            4
+        //            v
+        //            0
+        //            v
+        //  8 -> 3 -> 6 -> 1 -> 5
+        //            v
+        //            2
+        //            v
+        //            7
+        g.edge(8, 3, 1, false);
+        g.edge(3, 6, 1, false);
+        g.edge(6, 1, 1, false);
+        g.edge(1, 5, 1, false);
+        g.edge(4, 0, 1, false);
+        g.edge(0, 6, 1, false);
+        g.edge(6, 2, 1, false);
+        g.edge(2, 7, 1, false);
+        g.freeze();
+
+        PrepareContractionHierarchies prepare = createPrepareContractionHierarchies(g, lg)
+                .useFixedNodeOrdering(new NodeOrderingProvider() {
+                    @Override
+                    public int getNodeIdForLevel(int level) {
+                        return level;
+                    }
+
+                    @Override
+                    public int getNumNodes() {
+                        return g.getNodes();
+                    }
+                });
+        prepare.doWork();
+        CHEdgeExplorer explorer = lg.createEdgeExplorer();
+        // shortcuts (and edges) leading to or coming from higher level nodes should be disconnected
+        // so far we are only disconnecting shortcuts however, see comments in CHGraphImpl.
+        assertEquals(buildSet(7, 8, 0, 1, 2, 3), GHUtility.getNeighbors(explorer.setBaseNode(6)));
+        assertEquals(buildSet(6, 0), GHUtility.getNeighbors(explorer.setBaseNode(4)));
+        assertEquals(buildSet(6, 1), GHUtility.getNeighbors(explorer.setBaseNode(5)));
+        assertEquals(buildSet(8, 2), GHUtility.getNeighbors(explorer.setBaseNode(7)));
+        assertEquals(buildSet(3), GHUtility.getNeighbors(explorer.setBaseNode(8)));
+    }
+
+    private Set<Integer> buildSet(Integer... values) {
+        return new HashSet<>(Arrays.asList(values));
+    }
+
     @Test
     public void testCircleBug() {
         GraphHopperStorage g = createGHStorage();
@@ -486,6 +533,57 @@ public class PrepareContractionHierarchiesTest {
         checkPath(ghStorage, bikeWeighting, 9, 5, IntArrayList.from(3, 10, 14, 16, 13, 12));
     }
 
+    @Test
+    public void testReusingNodeOrdering() {
+        CarFlagEncoder carFlagEncoder = new CarFlagEncoder();
+        MotorcycleFlagEncoder motorCycleEncoder = new MotorcycleFlagEncoder();
+        EncodingManager em = new EncodingManager(carFlagEncoder, motorCycleEncoder);
+        Weighting carWeighting = new FastestWeighting(carFlagEncoder);
+        Weighting motorCycleWeighting = new FastestWeighting(motorCycleEncoder);
+        Directory dir = new RAMDirectory();
+        GraphHopperStorage ghStorage = new GraphHopperStorage(Arrays.asList(carWeighting, motorCycleWeighting), dir, em, false, new GraphExtension.NoOpExtension());
+        ghStorage.create(1000);
+
+        int numNodes = 5_000;
+        int numQueries = 100;
+        long seed = System.nanoTime();
+        GHUtility.buildRandomGraph(ghStorage, seed, numNodes, 1.3, false, false, 0.9);
+        ghStorage.freeze();
+
+        // create CH for cars
+        StopWatch sw = new StopWatch().start();
+        CHGraph carCH = ghStorage.getGraph(CHGraphImpl.class, carWeighting);
+        TraversalMode traversalMode = TraversalMode.NODE_BASED;
+        PrepareContractionHierarchies carPch = new PrepareContractionHierarchies(carCH, carWeighting, traversalMode);
+        carPch.doWork();
+        long timeCar = sw.stop().getMillis();
+
+        // create CH for motorcycles, re-use car contraction order
+        // this speeds up contraction significantly, but can lead to slower queries
+        sw = new StopWatch().start();
+        CHGraph motorCycleCH = ghStorage.getGraph(CHGraphImpl.class, motorCycleWeighting);
+        NodeOrderingProvider nodeOrderingProvider = carCH.getNodeOrderingProvider();
+        PrepareContractionHierarchies motorCyclePch = new PrepareContractionHierarchies(motorCycleCH, motorCycleWeighting, traversalMode)
+                .useFixedNodeOrdering(nodeOrderingProvider);
+        motorCyclePch.doWork();
+
+        // run a few sample queries to check correctness
+        Random rnd = new Random(seed);
+        for (int i = 0; i < numQueries; ++i) {
+            Dijkstra dijkstra = new Dijkstra(ghStorage, motorCycleWeighting, traversalMode);
+            RoutingAlgorithm chAlgo = motorCyclePch.createAlgo(motorCycleCH, AlgorithmOptions.start().weighting(motorCycleWeighting).build());
+
+            int from = rnd.nextInt(numNodes);
+            int to = rnd.nextInt(numNodes);
+            double dijkstraWeight = dijkstra.calcPath(from, to).getWeight();
+            double chWeight = chAlgo.calcPath(from, to).getWeight();
+            assertEquals(dijkstraWeight, chWeight, 1.e-1);
+        }
+        long timeMotorCycle = sw.getMillis();
+
+        assertTrue("reusing node ordering should speed up ch contraction", timeMotorCycle < 0.5 * timeCar);
+    }
+
     void checkPath(GraphHopperStorage g, Weighting w, int expShortcuts, double expDistance, IntIndexedContainer expNodes) {
         CHGraph lg = g.getGraph(CHGraph.class, w);
         PrepareContractionHierarchies prepare = createPrepareContractionHierarchies(g, lg, w);
diff --git a/reader-osm/src/test/java/com/graphhopper/routing/TrafficChangeWithNodeOrderingReusingTest.java b/reader-osm/src/test/java/com/graphhopper/routing/TrafficChangeWithNodeOrderingReusingTest.java
new file mode 100644
index 000000000..1cac9c248
--- /dev/null
+++ b/reader-osm/src/test/java/com/graphhopper/routing/TrafficChangeWithNodeOrderingReusingTest.java
@@ -0,0 +1,220 @@
+package com.graphhopper.routing;
+
+import com.graphhopper.reader.osm.OSMReader;
+import com.graphhopper.routing.ch.PrepareContractionHierarchies;
+import com.graphhopper.routing.util.CarFlagEncoder;
+import com.graphhopper.routing.util.EncodingManager;
+import com.graphhopper.routing.util.FlagEncoder;
+import com.graphhopper.routing.util.TraversalMode;
+import com.graphhopper.routing.weighting.AbstractWeighting;
+import com.graphhopper.routing.weighting.FastestWeighting;
+import com.graphhopper.routing.weighting.Weighting;
+import com.graphhopper.storage.*;
+import com.graphhopper.util.CHEdgeIteratorState;
+import com.graphhopper.util.EdgeIteratorState;
+import com.graphhopper.util.MiniPerfTest;
+import org.junit.Ignore;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.Locale;
+import java.util.Random;
+
+import static java.lang.System.nanoTime;
+import static org.junit.Assert.assertEquals;
+import static org.junit.runners.Parameterized.Parameters;
+
+/**
+ * Tests CH contraction and query performance when re-using the node ordering after random changes
+ * have been applied to the edge weights (like when considering traffic).
+ */
+@Ignore("for performance testing only")
+@RunWith(Parameterized.class)
+public class TrafficChangeWithNodeOrderingReusingTest {
+    private static final Logger LOGGER = LoggerFactory.getLogger(TrafficChangeWithNodeOrderingReusingTest.class);
+    // make sure to increase xmx/xms for the JVM created by the surefire plugin in parent pom.xml
+    private static final String OSM_FILE = "../local/maps/berlin-latest.osm.pbf";
+
+    private final Weighting baseWeighting;
+    private final Weighting trafficWeighting;
+    private final GraphHopperStorage ghStorage;
+    private final CHGraphImpl baseCHGraph;
+    private final CHGraphImpl trafficCHGraph;
+    private int maxDeviationPercentage;
+
+    @Parameters(name = "maxDeviationPercentage = {0}")
+    public static Object[] data() {
+        return new Object[]{0, 1, 5, 10, 50};
+    }
+
+    public TrafficChangeWithNodeOrderingReusingTest(int maxDeviationPercentage) {
+        this.maxDeviationPercentage = maxDeviationPercentage;
+        FlagEncoder encoder = new CarFlagEncoder();
+        EncodingManager em = new EncodingManager(encoder);
+        baseWeighting = new FastestWeighting(encoder);
+        trafficWeighting = new RandomDeviationWeighting(baseWeighting, maxDeviationPercentage);
+        Directory dir = new RAMDirectory("traffic-change-test");
+        ghStorage = new GraphHopperStorage(Arrays.asList(baseWeighting, trafficWeighting), dir, em, false, new GraphExtension.NoOpExtension());
+        baseCHGraph = ghStorage.getGraph(CHGraphImpl.class, baseWeighting);
+        trafficCHGraph = ghStorage.getGraph(CHGraphImpl.class, trafficWeighting);
+    }
+
+    @Test
+    public void testPerformanceForRandomTrafficChange() throws IOException {
+        final long seed = 2139960664L;
+        final int numQueries = 50_000;
+
+        LOGGER.info("Running performance test, max deviation percentage: " + this.maxDeviationPercentage);
+        // read osm
+        OSMReader reader = new OSMReader(ghStorage);
+        reader.setFile(new File(OSM_FILE));
+        reader.setCreateStorage(true);
+        reader.readGraph();
+        ghStorage.freeze();
+
+        // create CH
+        PrepareContractionHierarchies basePch = new PrepareContractionHierarchies(baseCHGraph, baseWeighting, TraversalMode.NODE_BASED);
+        basePch.doWork();
+
+        // check correctness & performance
+        checkCorrectness(ghStorage, baseCHGraph, basePch, seed, 100);
+        runPerformanceTest(ghStorage, baseCHGraph, basePch, seed, numQueries);
+
+        // now we re-use the contraction order from the previous contraction and re-run it with the traffic weighting
+        PrepareContractionHierarchies trafficPch = new PrepareContractionHierarchies(trafficCHGraph, trafficWeighting, TraversalMode.NODE_BASED)
+                .useFixedNodeOrdering(baseCHGraph.getNodeOrderingProvider());
+        trafficPch.doWork();
+
+        // check correctness & performance
+        checkCorrectness(ghStorage, trafficCHGraph, trafficPch, seed, 100);
+        runPerformanceTest(ghStorage, trafficCHGraph, trafficPch, seed, numQueries);
+    }
+
+    private static void checkCorrectness(GraphHopperStorage ghStorage, CHGraph chGraph, PrepareContractionHierarchies pch, long seed, long numQueries) {
+        LOGGER.info("checking correctness");
+        Random rnd = new Random(seed);
+        int numFails = 0;
+        for (int i = 0; i < numQueries; ++i) {
+            Dijkstra dijkstra = new Dijkstra(ghStorage, pch.getWeighting(), TraversalMode.NODE_BASED);
+            RoutingAlgorithm chAlgo = pch.createAlgo(chGraph, AlgorithmOptions.start().weighting(pch.getWeighting()).build());
+
+            int from = rnd.nextInt(ghStorage.getNodes());
+            int to = rnd.nextInt(ghStorage.getNodes());
+            double dijkstraWeight = dijkstra.calcPath(from, to).getWeight();
+            double chWeight = chAlgo.calcPath(from, to).getWeight();
+            double error = Math.abs(dijkstraWeight - chWeight);
+            if (error > 1) {
+                System.out.println("failure from " + from + " to " + to + " dijkstra: " + dijkstraWeight + " ch: " + chWeight);
+                numFails++;
+            }
+        }
+        LOGGER.info("number of failed queries: " + numFails);
+        assertEquals(0, numFails);
+    }
+
+    private static void runPerformanceTest(final GraphHopperStorage ghStorage, final CHGraph chGraph, final PrepareContractionHierarchies pch,
+                                           long seed, final int iterations) {
+        final int numNodes = ghStorage.getNodes();
+        final Random random = new Random(seed);
+
+        LOGGER.info("Running performance test, seed = {}", seed);
+        final double[] distAndWeight = {0.0, 0.0};
+        MiniPerfTest performanceTest = new MiniPerfTest() {
+            private long queryTime;
+
+            @Override
+            public int doCalc(boolean warmup, int run) {
+                if (!warmup && run % 1000 == 0) {
+                    LOGGER.debug("Finished {} of {} runs. {}", run, iterations,
+                            run > 0 ? String.format(Locale.ROOT, " Time: %6.2fms", queryTime * 1.e-6 / run) : "");
+                }
+                if (run == iterations - 1) {
+                    String avg = fmt(queryTime * 1.e-6 / run);
+                    LOGGER.debug("Finished all ({}) runs, avg time: {}ms", iterations, avg);
+                }
+                int from = random.nextInt(numNodes);
+                int to = random.nextInt(numNodes);
+                long start = nanoTime();
+                RoutingAlgorithm algo = pch.createAlgo(chGraph, AlgorithmOptions.start().weighting(pch.getWeighting()).build());
+                Path path = algo.calcPath(from, to);
+                if (!warmup && !path.isFound())
+                    return 1;
+
+                if (!warmup) {
+                    queryTime += nanoTime() - start;
+                    double distance = path.getDistance();
+                    double weight = path.getWeight();
+                    distAndWeight[0] += distance;
+                    distAndWeight[1] += weight;
+                }
+                return 0;
+            }
+        };
+        performanceTest.setIterations(iterations).start();
+        if (performanceTest.getDummySum() > 0.5 * iterations) {
+            throw new IllegalStateException("too many errors, probably something is wrong");
+        }
+        LOGGER.info("Total distance: {}, total weight: {}", distAndWeight[0], distAndWeight[1]);
+        LOGGER.info("Average query time: {}ms", performanceTest.getMean());
+    }
+
+    private static String fmt(double number) {
+        return String.format(Locale.ROOT, "%.2f", number);
+    }
+
+    /**
+     * Wraps another weighting and applies random weight deviations to it.
+     * Do not use with AStar/Landmarks!
+     */
+    private static class RandomDeviationWeighting extends AbstractWeighting {
+        private final Weighting baseWeighting;
+        private final double maxDeviationPercentage;
+
+        public RandomDeviationWeighting(Weighting baseWeighting, double maxDeviationPercentage) {
+            super(baseWeighting.getFlagEncoder());
+            this.baseWeighting = baseWeighting;
+            this.maxDeviationPercentage = maxDeviationPercentage;
+        }
+
+        @Override
+        public double getMinWeight(double distance) {
+            // left as is, ok for now, but do not use with astar, at least as long as deviations can be negative!!
+            return this.baseWeighting.getMinWeight(distance);
+        }
+
+        @Override
+        public double calcWeight(EdgeIteratorState edgeState, boolean reverse, int prevOrNextEdgeId) {
+            double baseWeight = this.baseWeighting.calcWeight(edgeState, reverse, prevOrNextEdgeId);
+            if (edgeState instanceof CHEdgeIteratorState) {
+                // important! we may not change weights of shortcuts (the deviations are already included in their weight)
+                if (((CHEdgeIteratorState) edgeState).isShortcut()) {
+                    return baseWeight;
+                }
+            }
+            if (Double.isInfinite(baseWeight)) {
+                // we are not touching this, might happen when speed is 0 ?
+                return baseWeight;
+            }
+            // apply a random (but deterministic) weight deviation - deviation may not depend on reverse flag!
+            long seed = edgeState.getEdge();
+            Random rnd = new Random(seed);
+            double deviation = 2 * (rnd.nextDouble() - 0.5) * baseWeight * maxDeviationPercentage / 100;
+            double result = baseWeight + deviation;
+            if (result < 0) {
+                throw new IllegalStateException("negative weights are not allowed: " + result);
+            }
+            return result;
+        }
+
+        @Override
+        public String getName() {
+            return "random_deviation";
+        }
+    }
+}