Repository: graphhopper/graphhopper
Pull request #2132 (2020-09-15 10:41:57)

Use temporary helper graph to speed up CH preparation
This PR aims at reducing the CH preparation time by changing the contraction algorithm. The idea is pretty simple: We use a helper graph which at the beginning of the contraction is more or less a copy of the base graph. The witness searches are performed on this helper graph and the `CHGraph` is only used to store the resulting shortcuts. When we contract a node `x` with neighbors `p` and `q`: `p-x-q` we do not insert the p-q shortcut(s) into the CHGraph directly, but instead we add it to the helper graph. When the witness searches are finished we add the x-p and x-q edges to the `CHGraph` (if they are shortcuts). The p-q shortcut(s) are added only later when we contract node p/q. Importantly, we can also remove all edges adjacent to the node we are contracting from the helper graph after we have performed the witness search. This is the main reason why the preparation becomes faster using this method. So far measurements show that the preparation (node- and edge-based) on this branch is about two to three times faster than master (edge-based performance seems to benefit more from the changes in this branch, also because the turn costs are cached with the helper graph). 

The obvious downside of this approach is that we need additional memory for the helper graph. ~~As the helper graph becomes smaller and smaller during the preparation (while the CH graph becomes bigger and bigger) we need extra memory mostly at the beginning of the contraction~~. The size of the helper graph is initially proportional to the size of the base graph. First I thought there are 'as many' shortcuts as there are base graph edges and thus the memory size of the helper graph will be about equal to the memory we need to store the shortcuts. Unfortunately this is not exactly true for two reasons. First, since we are using 'bidirectional' shortcuts for node-based CH there are *less* shortcuts than base graph edges. Second, to support efficient removal of helper graph edges during the contraction we need to use a less memory efficient representation of the helper graph (this is also partly because of Java's wasteful way of storing heap data). Thus this PR increases the overall memory requirement for CH preparation (node- and edge-based).

I did some experiments on the Germany OSM for four (node-based) profiles (car,mtb,foot,bike) and was able to run the import with `Xmx7000m` (using `Xmx6500m` yielded an out of memory error) on master and needed `Xmx8500m` on this branch (using `Xmx8000m` yielded an out of memory error). The key thing to understand here is that the more profiles we prepare in parallel the more helper graph memory we need at the beginning of the import. So an obvious workaround would be using less threads. Another somewhat hacky possibility would be delaying the different preparations a bit such that the peak memory usages of the different threads do not happen at the same time. 

~~For edge-based CH we need a lot more memory than for node-based CH because there are more shortcuts, the shortcuts are all uni-directional and each shortcut needs more memory. Therefore the helper graph does not increase the overall memory usage (the helper graph memory is less than the memory we need to reserve for the shortcuts anyway). Actually I was able to speed up the preparation for edge-based even more when using a less memory efficient helper graph than the one I am using now.~~

Besides the speed up of the preparation using the approach of this PR has the following advantages:

1) The shortcuts are automatically sorted by the CH levels of their base nodes. This way we might be able to get rid of the `linkA/B` pointers for shortcuts (reduce the memory we need to store shortcuts) and the the shortcut storage is more cache-friendly. In fact the CH queries are faster on this branch.

2) After the shortcuts are written to the CHGraph they will not change again. So in principle it would be possible to start flushing some of the shortcut storage to disk already during the preparation (to reduce RAM usage).

3) Since we pre-calculate the base-edge weights and store them in the helper graph the preparation time is especially faster for 'expensive' weightings. I.e. if we use a custom weighting that does some costly edge-weight computations they are now done only once while the weightings get evaluated many many times during the witness searches on master. Obviously there would be other ways to 'cache' these weights, but with this PR this is already done and I checked that simply caching the weights does not nearly yield the speed up we see here.

Related #1565 


Patch:
diff --git a/core/files/changelog.txt b/core/files/changelog.txt
index 2fe8dd454..93434b24a 100644
--- a/core/files/changelog.txt
+++ b/core/files/changelog.txt
@@ -1,4 +1,5 @@
 2.0
+    much faster CH preparation (node- and edge-based), but increased memory usage during preparation, #2132
     added navigation repo #2071
     use Java 8 also for core, client-hc and reader-osm modules. all modules use Java 8 now
     removed android demo, #1940
diff --git a/core/src/main/java/com/graphhopper/GraphHopper.java b/core/src/main/java/com/graphhopper/GraphHopper.java
index a61c6742f..132c0b0de 100644
--- a/core/src/main/java/com/graphhopper/GraphHopper.java
+++ b/core/src/main/java/com/graphhopper/GraphHopper.java
@@ -23,7 +23,10 @@ import com.graphhopper.config.Profile;
 import com.graphhopper.reader.DataReader;
 import com.graphhopper.reader.dem.*;
 import com.graphhopper.reader.osm.conditional.DateRangeParser;
-import com.graphhopper.routing.*;
+import com.graphhopper.routing.DefaultWeightingFactory;
+import com.graphhopper.routing.Router;
+import com.graphhopper.routing.RouterConfig;
+import com.graphhopper.routing.WeightingFactory;
 import com.graphhopper.routing.ch.CHPreparationHandler;
 import com.graphhopper.routing.ev.DefaultEncodedValueFactory;
 import com.graphhopper.routing.ev.EncodedValueFactory;
diff --git a/core/src/main/java/com/graphhopper/routing/ch/AbstractNodeContractor.java b/core/src/main/java/com/graphhopper/routing/ch/AbstractNodeContractor.java
deleted file mode 100644
index 1ce0f9811..000000000
--- a/core/src/main/java/com/graphhopper/routing/ch/AbstractNodeContractor.java
+++ /dev/null
@@ -1,81 +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.storage.DAType;
-import com.graphhopper.storage.DataAccess;
-import com.graphhopper.storage.GHDirectory;
-
-abstract class AbstractNodeContractor implements NodeContractor {
-    final PrepareCHGraph prepareGraph;
-    PrepareCHEdgeExplorer inEdgeExplorer;
-    PrepareCHEdgeExplorer outEdgeExplorer;
-    private final DataAccess originalEdges;
-    int maxLevel;
-    private int maxEdgesCount;
-
-    public AbstractNodeContractor(PrepareCHGraph prepareGraph) {
-        this.prepareGraph = prepareGraph;
-        originalEdges = new GHDirectory("", DAType.RAM_INT).find("");
-        originalEdges.create(1000);
-    }
-
-    @Override
-    public void initFromGraph() {
-        inEdgeExplorer = prepareGraph.createInEdgeExplorer();
-        outEdgeExplorer = prepareGraph.createOutEdgeExplorer();
-        maxLevel = prepareGraph.getNodes();
-        maxEdgesCount = prepareGraph.getOriginalEdges();
-    }
-
-    @Override
-    public void close() {
-        originalEdges.close();
-    }
-
-    boolean isContracted(int node) {
-        return prepareGraph.getLevel(node) != maxLevel;
-    }
-
-    void setOrigEdgeCount(int edgeId, int value) {
-        edgeId -= maxEdgesCount;
-        if (edgeId < 0) {
-            // ignore setting as every normal edge has original edge count of 1
-            if (value != 1)
-                throw new IllegalStateException("Trying to set original edge count for normal edge to a value = " + value
-                        + ", edge:" + (edgeId + maxEdgesCount) + ", max:" + maxEdgesCount + ", graph.max:" +
-                        prepareGraph.getEdges());
-            return;
-        }
-
-        long tmp = (long) edgeId * 4;
-        originalEdges.ensureCapacity(tmp + 4);
-        originalEdges.setInt(tmp, value);
-    }
-
-    int getOrigEdgeCount(int edgeId) {
-        edgeId -= maxEdgesCount;
-        if (edgeId < 0)
-            return 1;
-
-        long tmp = (long) edgeId * 4;
-        originalEdges.ensureCapacity(tmp + 4);
-        return originalEdges.getInt(tmp);
-    }
-}
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 205a87d32..8c3d6910b 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/CHParameters.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/CHParameters.java
@@ -12,7 +12,6 @@ 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 CONTRACTED_NEIGHBORS_WEIGHT = Parameters.CH.PREPARE + "node.contracted_neighbors_weight";
     // 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/CHPreparationGraph.java b/core/src/main/java/com/graphhopper/routing/ch/CHPreparationGraph.java
new file mode 100644
index 000000000..8791bf371
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/ch/CHPreparationGraph.java
@@ -0,0 +1,867 @@
+/*
+ *  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.carrotsearch.hppc.*;
+import com.carrotsearch.hppc.sorting.IndirectComparator;
+import com.carrotsearch.hppc.sorting.IndirectSort;
+import com.graphhopper.routing.ev.BooleanEncodedValue;
+import com.graphhopper.routing.ev.DecimalEncodedValue;
+import com.graphhopper.routing.ev.TurnCost;
+import com.graphhopper.routing.util.AllEdgesIterator;
+import com.graphhopper.routing.util.FlagEncoder;
+import com.graphhopper.routing.weighting.Weighting;
+import com.graphhopper.storage.Graph;
+import com.graphhopper.storage.TurnCostStorage;
+import com.graphhopper.util.BitUtil;
+import com.graphhopper.util.EdgeIterator;
+import com.graphhopper.util.GHUtility;
+
+/**
+ * Graph data structure used for CH preparation. It allows caching weights, and edges that are not needed anymore
+ * (those adjacent to contracted nodes) can be removed (see {@link #disconnect}.
+ */
+public class CHPreparationGraph {
+    private final int nodes;
+    private final int edges;
+    private final boolean edgeBased;
+    private final TurnCostFunction turnCostFunction;
+    // each edge/shortcut between nodes a/b is represented as a single object and we maintain a list of references
+    // to these objects at every node. this needs to be memory-efficient especially for node-based (because there
+    // are less shortcuts overall so the size of the prepare graph is crucial, while for edge-based most memory is
+    // consumed towards the end of the preparation anyway). for edge-based it would actually be better/faster to keep
+    // separate lists of incoming/outgoing edges and even use uni-directional edge-objects.
+    private SplitArray2D<PrepareEdge> prepareEdges;
+    private IntSet neighborSet;
+    private OrigGraph origGraph;
+    private OrigGraph.Builder origGraphBuilder;
+    private int nextShortcutId;
+    private boolean ready;
+
+    public static CHPreparationGraph nodeBased(int nodes, int edges) {
+        return new CHPreparationGraph(nodes, edges, false, (in, via, out) -> 0);
+    }
+
+    public static CHPreparationGraph edgeBased(int nodes, int edges, TurnCostFunction turnCostFunction) {
+        return new CHPreparationGraph(nodes, edges, true, turnCostFunction);
+    }
+
+    /**
+     * @param nodes (fixed) number of nodes of the graph
+     * @param edges the maximum number of (non-shortcut) edges in this graph. edges-1 is the maximum edge id that may
+     *              be used.
+     */
+    private CHPreparationGraph(int nodes, int edges, boolean edgeBased, TurnCostFunction turnCostFunction) {
+        this.turnCostFunction = turnCostFunction;
+        this.nodes = nodes;
+        this.edges = edges;
+        this.edgeBased = edgeBased;
+        prepareEdges = new SplitArray2D<>(nodes, 2);
+        origGraphBuilder = edgeBased ? new OrigGraph.Builder() : null;
+        neighborSet = new IntHashSet();
+        nextShortcutId = edges;
+    }
+
+    public static void buildFromGraph(CHPreparationGraph prepareGraph, Graph graph, Weighting weighting) {
+        if (graph.getNodes() != prepareGraph.getNodes())
+            throw new IllegalArgumentException("Cannot initialize from given graph. The number of nodes does not match: " +
+                    graph.getNodes() + " vs. " + prepareGraph.getNodes());
+        if (graph.getEdges() != prepareGraph.getOriginalEdges())
+            throw new IllegalArgumentException("Cannot initialize from given graph. The number of edges does not match: " +
+                    graph.getEdges() + " vs. " + prepareGraph.getOriginalEdges());
+        BooleanEncodedValue accessEnc = weighting.getFlagEncoder().getAccessEnc();
+        AllEdgesIterator iter = graph.getAllEdges();
+        while (iter.next()) {
+            double weightFwd = iter.get(accessEnc) ? weighting.calcEdgeWeight(iter, false) : Double.POSITIVE_INFINITY;
+            double weightBwd = iter.getReverse(accessEnc) ? weighting.calcEdgeWeight(iter, true) : Double.POSITIVE_INFINITY;
+            prepareGraph.addEdge(iter.getBaseNode(), iter.getAdjNode(), iter.getEdge(), weightFwd, weightBwd);
+        }
+        prepareGraph.prepareForContraction();
+    }
+
+    /**
+     * Builds a turn cost function for a given graph('s turn cost storage) and a weighting.
+     * The trivial implementation would be simply returning {@link Weighting#calcTurnWeight}. However, it turned out
+     * that reading all turn costs for the current encoder and then storing them in separate arrays upfront speeds up
+     * edge-based CH preparation by about 25%. See #2084
+     */
+    public static TurnCostFunction buildTurnCostFunctionFromTurnCostStorage(Graph graph, Weighting weighting) {
+        FlagEncoder encoder = weighting.getFlagEncoder();
+        String key = TurnCost.key(encoder.toString());
+        if (!encoder.hasEncodedValue(key))
+            return (inEdge, viaNode, outEdge) -> 0;
+
+        DecimalEncodedValue turnCostEnc = encoder.getDecimalEncodedValue(key);
+        TurnCostStorage turnCostStorage = graph.getTurnCostStorage();
+        // we maintain a list of inEdge/outEdge/turn-cost triples (we use two arrays for this) that is sorted by nodes
+        LongArrayList turnCostEdgePairs = new LongArrayList();
+        DoubleArrayList turnCosts = new DoubleArrayList();
+        // for each node we store the index of the first turn cost entry/triple in the list
+        final int[] turnCostNodes = new int[graph.getNodes() + 1];
+        TurnCostStorage.TurnRelationIterator tcIter = turnCostStorage.getAllTurnRelations();
+        int lastNode = -1;
+        while (tcIter.next()) {
+            int viaNode = tcIter.getViaNode();
+            if (viaNode < lastNode)
+                throw new IllegalStateException();
+            long edgePair = BitUtil.LITTLE.combineIntsToLong(tcIter.getFromEdge(), tcIter.getToEdge());
+            // note that as long as we only use OSM turn restrictions all the turn costs are infinite anyway
+            double turnCost = tcIter.getCost(turnCostEnc);
+            int index = turnCostEdgePairs.size();
+            turnCostEdgePairs.add(edgePair);
+            turnCosts.add(turnCost);
+            if (viaNode != lastNode) {
+                for (int i = lastNode + 1; i <= viaNode; i++) {
+                    turnCostNodes[i] = index;
+                }
+            }
+            lastNode = viaNode;
+        }
+        for (int i = lastNode + 1; i <= turnCostNodes.length - 1; i++) {
+            turnCostNodes[i] = turnCostEdgePairs.size();
+        }
+        turnCostNodes[turnCostNodes.length - 1] = turnCostEdgePairs.size();
+
+        // currently the u-turn costs are the same for all junctions, so for now we just get them for one of them
+        double uTurnCosts = weighting.calcTurnWeight(1, 0, 1);
+        return (inEdge, viaNode, outEdge) -> {
+            if (!EdgeIterator.Edge.isValid(inEdge) || !EdgeIterator.Edge.isValid(outEdge))
+                return 0;
+            else if (inEdge == outEdge)
+                return uTurnCosts;
+            // traverse all turn cost entries we have for this viaNode and return the turn costs if we find a match
+            for (int i = turnCostNodes[viaNode]; i < turnCostNodes[viaNode + 1]; i++) {
+                long l = turnCostEdgePairs.get(i);
+                if (inEdge == BitUtil.LITTLE.getIntLow(l) && outEdge == BitUtil.LITTLE.getIntHigh(l))
+                    return turnCosts.get(i);
+            }
+            return 0;
+        };
+    }
+
+    public int getNodes() {
+        return nodes;
+    }
+
+    public int getOriginalEdges() {
+        return edges;
+    }
+
+    public int getDegree(int node) {
+        return prepareEdges.size(node);
+    }
+
+    public void addEdge(int from, int to, int edge, double weightFwd, double weightBwd) {
+        checkNotReady();
+        boolean fwd = Double.isFinite(weightFwd);
+        boolean bwd = Double.isFinite(weightBwd);
+        if (!fwd && !bwd)
+            return;
+        PrepareBaseEdge prepareEdge = new PrepareBaseEdge(edge, from, to, (float) weightFwd, (float) weightBwd);
+        if (fwd) {
+            addOutEdge(from, prepareEdge);
+            addInEdge(to, prepareEdge);
+        }
+        if (bwd && from != to) {
+            addOutEdge(to, prepareEdge);
+            addInEdge(from, prepareEdge);
+        }
+        if (edgeBased)
+            origGraphBuilder.addEdge(from, to, edge, fwd, bwd);
+    }
+
+    public int addShortcut(int from, int to, int origEdgeKeyFirst, int origEdgeKeyLast, int skipped1,
+                           int skipped2, double weight, int origEdgeCount) {
+        checkReady();
+        PrepareEdge prepareEdge = edgeBased
+                ? new EdgeBasedPrepareShortcut(nextShortcutId, from, to, origEdgeKeyFirst, origEdgeKeyLast, weight, skipped1, skipped2, origEdgeCount)
+                : new PrepareShortcut(nextShortcutId, from, to, weight, skipped1, skipped2, origEdgeCount);
+        addOutEdge(from, prepareEdge);
+        if (from != to)
+            addInEdge(to, prepareEdge);
+        return nextShortcutId++;
+    }
+
+    public void prepareForContraction() {
+        checkNotReady();
+        prepareEdges.trimToSize();
+        origGraph = edgeBased ? origGraphBuilder.build() : null;
+        origGraphBuilder = null;
+        ready = true;
+    }
+
+    public PrepareGraphEdgeExplorer createOutEdgeExplorer() {
+        checkReady();
+        return new PrepareGraphEdgeExplorerImpl(prepareEdges, false);
+    }
+
+    public PrepareGraphEdgeExplorer createInEdgeExplorer() {
+        checkReady();
+        return new PrepareGraphEdgeExplorerImpl(prepareEdges, true);
+    }
+
+    public PrepareGraphOrigEdgeExplorer createOutOrigEdgeExplorer() {
+        checkReady();
+        if (!edgeBased)
+            throw new IllegalStateException("orig out explorer is not available for node-based graph");
+        return origGraph.createOutOrigEdgeExplorer();
+    }
+
+    public PrepareGraphOrigEdgeExplorer createInOrigEdgeExplorer() {
+        checkReady();
+        if (!edgeBased)
+            throw new IllegalStateException("orig in explorer is not available for node-based graph");
+        return origGraph.createInOrigEdgeExplorer();
+    }
+
+    public double getTurnWeight(int inEdge, int viaNode, int outEdge) {
+        return turnCostFunction.getTurnWeight(inEdge, viaNode, outEdge);
+    }
+
+    public IntContainer disconnect(int node) {
+        checkReady();
+        // we use this neighbor set to guarantee a deterministic order of the returned
+        // node ids
+        neighborSet.clear();
+        IntArrayList neighbors = new IntArrayList(getDegree(node));
+        for (int i = 0; i < prepareEdges.size(node); i++) {
+            PrepareEdge prepareEdge = prepareEdges.get(node, i);
+            int adjNode = prepareEdge.getNodeB();
+            if (adjNode == node)
+                adjNode = prepareEdge.getNodeA();
+            if (adjNode == node)
+                // this is a loop
+                continue;
+            prepareEdges.remove(adjNode, prepareEdge);
+            if (neighborSet.add(adjNode))
+                neighbors.add(adjNode);
+        }
+        prepareEdges.clear(node);
+        return neighbors;
+    }
+
+    public void close() {
+        checkReady();
+        prepareEdges = null;
+        neighborSet = null;
+        if (edgeBased)
+            origGraph = null;
+    }
+
+    private void addOutEdge(int node, PrepareEdge prepareEdge) {
+        prepareEdges.addPartTwo(node, prepareEdge);
+    }
+
+    private void addInEdge(int node, PrepareEdge prepareEdge) {
+        prepareEdges.addPartOne(node, prepareEdge);
+    }
+
+    private void checkReady() {
+        if (!ready)
+            throw new IllegalStateException("You need to call prepareForContraction() before calling this method");
+    }
+
+    private void checkNotReady() {
+        if (ready)
+            throw new IllegalStateException("You cannot call this method after calling prepareForContraction()");
+    }
+
+    @FunctionalInterface
+    public interface TurnCostFunction {
+        double getTurnWeight(int inEdge, int viaNode, int outEdge);
+    }
+
+    private static class PrepareGraphEdgeExplorerImpl implements PrepareGraphEdgeExplorer, PrepareGraphEdgeIterator {
+        private final SplitArray2D<PrepareEdge> prepareEdges;
+        private final boolean reverse;
+        private int node = -1;
+        private int end;
+        private PrepareEdge currEdge;
+        private int index;
+
+        PrepareGraphEdgeExplorerImpl(SplitArray2D<PrepareEdge> prepareEdges, boolean reverse) {
+            this.prepareEdges = prepareEdges;
+            this.reverse = reverse;
+        }
+
+        @Override
+        public PrepareGraphEdgeIterator setBaseNode(int node) {
+            this.node = node;
+            // we store the in edges in the first and the out edges in the second part of the prepareEdges
+            this.index = reverse ? -1 : (prepareEdges.mid(node) - 1);
+            this.end = reverse ? prepareEdges.mid(node) : prepareEdges.size(node);
+            return this;
+        }
+
+        @Override
+        public boolean next() {
+            index++;
+            if (index == end) {
+                currEdge = null;
+                return false;
+            }
+            currEdge = prepareEdges.get(node, index);
+            return true;
+        }
+
+        @Override
+        public int getBaseNode() {
+            return node;
+        }
+
+        @Override
+        public int getAdjNode() {
+            return nodeAisBase() ? currEdge.getNodeB() : currEdge.getNodeA();
+        }
+
+        @Override
+        public int getPrepareEdge() {
+            return currEdge.getPrepareEdge();
+        }
+
+        @Override
+        public boolean isShortcut() {
+            return currEdge.isShortcut();
+        }
+
+        @Override
+        public int getOrigEdgeKeyFirst() {
+            return nodeAisBase() ? currEdge.getOrigEdgeKeyFirstAB() : currEdge.getOrigEdgeKeyFirstBA();
+        }
+
+        @Override
+        public int getOrigEdgeKeyLast() {
+            return nodeAisBase() ? currEdge.getOrigEdgeKeyLastAB() : currEdge.getOrigEdgeKeyLastBA();
+        }
+
+        @Override
+        public int getSkipped1() {
+            return currEdge.getSkipped1();
+        }
+
+        @Override
+        public int getSkipped2() {
+            return currEdge.getSkipped2();
+        }
+
+        @Override
+        public double getWeight() {
+            if (nodeAisBase()) {
+                return reverse ? currEdge.getWeightBA() : currEdge.getWeightAB();
+            } else {
+                return reverse ? currEdge.getWeightAB() : currEdge.getWeightBA();
+            }
+        }
+
+        @Override
+        public int getOrigEdgeCount() {
+            return currEdge.getOrigEdgeCount();
+        }
+
+        @Override
+        public void setSkippedEdges(int skipped1, int skipped2) {
+            currEdge.setSkipped1(skipped1);
+            currEdge.setSkipped2(skipped2);
+        }
+
+        @Override
+        public void setWeight(double weight) {
+            assert Double.isFinite(weight);
+            currEdge.setWeight(weight);
+        }
+
+        @Override
+        public void setOrigEdgeCount(int origEdgeCount) {
+            currEdge.setOrigEdgeCount(origEdgeCount);
+        }
+
+        @Override
+        public String toString() {
+            return currEdge == null ? "not_started" : getBaseNode() + "-" + getAdjNode();
+        }
+
+        private boolean nodeAisBase() {
+            // in some cases we need to determine which direction of the (bidirectional) edge we want
+            return currEdge.getNodeA() == node;
+        }
+    }
+
+    interface PrepareEdge {
+        boolean isShortcut();
+
+        int getPrepareEdge();
+
+        int getNodeA();
+
+        int getNodeB();
+
+        double getWeightAB();
+
+        double getWeightBA();
+
+        int getOrigEdgeKeyFirstAB();
+
+        int getOrigEdgeKeyFirstBA();
+
+        int getOrigEdgeKeyLastAB();
+
+        int getOrigEdgeKeyLastBA();
+
+        int getSkipped1();
+
+        int getSkipped2();
+
+        int getOrigEdgeCount();
+
+        void setSkipped1(int skipped1);
+
+        void setSkipped2(int skipped2);
+
+        void setWeight(double weight);
+
+        void setOrigEdgeCount(int origEdgeCount);
+    }
+
+    public static class PrepareBaseEdge implements PrepareEdge {
+        private final int prepareEdge;
+        private final int nodeA;
+        private final int nodeB;
+        private final float weightAB;
+        private final float weightBA;
+
+        public PrepareBaseEdge(int prepareEdge, int nodeA, int nodeB, float weightAB, float weightBA) {
+            this.prepareEdge = prepareEdge;
+            this.nodeA = nodeA;
+            this.nodeB = nodeB;
+            this.weightAB = weightAB;
+            this.weightBA = weightBA;
+        }
+
+        @Override
+        public boolean isShortcut() {
+            return false;
+        }
+
+        @Override
+        public int getPrepareEdge() {
+            return prepareEdge;
+        }
+
+        @Override
+        public int getNodeA() {
+            return nodeA;
+        }
+
+        @Override
+        public int getNodeB() {
+            return nodeB;
+        }
+
+        @Override
+        public double getWeightAB() {
+            return weightAB;
+        }
+
+        @Override
+        public double getWeightBA() {
+            return weightBA;
+        }
+
+        @Override
+        public int getOrigEdgeKeyFirstAB() {
+            int key = prepareEdge << 1;
+            return nodeA > nodeB ? key + 1 : key;
+        }
+
+        @Override
+        public int getOrigEdgeKeyFirstBA() {
+            int key = prepareEdge << 1;
+            return nodeB > nodeA ? key + 1 : key;
+        }
+
+        @Override
+        public int getOrigEdgeKeyLastAB() {
+            return getOrigEdgeKeyFirstAB();
+        }
+
+        @Override
+        public int getOrigEdgeKeyLastBA() {
+            return getOrigEdgeKeyFirstBA();
+        }
+
+        @Override
+        public int getSkipped1() {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public int getSkipped2() {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public int getOrigEdgeCount() {
+            return 1;
+        }
+
+        @Override
+        public void setSkipped1(int skipped1) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public void setSkipped2(int skipped2) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public void setWeight(double weight) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public void setOrigEdgeCount(int origEdgeCount) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public String toString() {
+            return nodeA + "-" + nodeB + " (" + prepareEdge + ") " + weightAB + " " + weightBA;
+        }
+    }
+
+    private static class PrepareShortcut implements PrepareEdge {
+        private final int prepareEdge;
+        private final int from;
+        private final int to;
+        private double weight;
+        private int skipped1;
+        private int skipped2;
+        private int origEdgeCount;
+
+        private PrepareShortcut(int prepareEdge, int from, int to, double weight, int skipped1, int skipped2, int origEdgeCount) {
+            this.prepareEdge = prepareEdge;
+            this.from = from;
+            this.to = to;
+            assert Double.isFinite(weight);
+            this.weight = weight;
+            this.skipped1 = skipped1;
+            this.skipped2 = skipped2;
+            this.origEdgeCount = origEdgeCount;
+        }
+
+        @Override
+        public boolean isShortcut() {
+            return true;
+        }
+
+        @Override
+        public int getPrepareEdge() {
+            return prepareEdge;
+        }
+
+        @Override
+        public int getNodeA() {
+            return from;
+        }
+
+        @Override
+        public int getNodeB() {
+            return to;
+        }
+
+        @Override
+        public double getWeightAB() {
+            return weight;
+        }
+
+        @Override
+        public double getWeightBA() {
+            return weight;
+        }
+
+        @Override
+        public int getOrigEdgeKeyFirstAB() {
+            throw new IllegalStateException("Not supported for node-based shortcuts");
+        }
+
+        @Override
+        public int getOrigEdgeKeyFirstBA() {
+            throw new IllegalStateException("Not supported for node-based shortcuts");
+        }
+
+        @Override
+        public int getOrigEdgeKeyLastAB() {
+            throw new IllegalStateException("Not supported for node-based shortcuts");
+        }
+
+        @Override
+        public int getOrigEdgeKeyLastBA() {
+            throw new IllegalStateException("Not supported for node-based shortcuts");
+        }
+
+        @Override
+        public int getSkipped1() {
+            return skipped1;
+        }
+
+        @Override
+        public int getSkipped2() {
+            return skipped2;
+        }
+
+        @Override
+        public int getOrigEdgeCount() {
+            return origEdgeCount;
+        }
+
+        @Override
+        public void setSkipped1(int skipped1) {
+            this.skipped1 = skipped1;
+        }
+
+        @Override
+        public void setSkipped2(int skipped2) {
+            this.skipped2 = skipped2;
+        }
+
+        @Override
+        public void setWeight(double weight) {
+            this.weight = weight;
+        }
+
+        @Override
+        public void setOrigEdgeCount(int origEdgeCount) {
+            this.origEdgeCount = origEdgeCount;
+        }
+
+        @Override
+        public String toString() {
+            return from + "-" + to + " " + weight;
+        }
+    }
+
+    private static class EdgeBasedPrepareShortcut extends PrepareShortcut {
+        // we use this subclass to save some memory for node-based where these are not needed
+        private final int origEdgeKeyFirst;
+        private final int origEdgeKeyLast;
+
+        public EdgeBasedPrepareShortcut(int prepareEdge, int from, int to, int origEdgeKeyFirst, int origEdgeKeyLast,
+                                        double weight, int skipped1, int skipped2, int origEdgeCount) {
+            super(prepareEdge, from, to, weight, skipped1, skipped2, origEdgeCount);
+            this.origEdgeKeyFirst = origEdgeKeyFirst;
+            this.origEdgeKeyLast = origEdgeKeyLast;
+        }
+
+        @Override
+        public int getOrigEdgeKeyFirstAB() {
+            return origEdgeKeyFirst;
+        }
+
+        @Override
+        public int getOrigEdgeKeyFirstBA() {
+            return origEdgeKeyFirst;
+        }
+
+        @Override
+        public int getOrigEdgeKeyLastAB() {
+            return origEdgeKeyLast;
+        }
+
+        @Override
+        public int getOrigEdgeKeyLastBA() {
+            return origEdgeKeyLast;
+        }
+
+        @Override
+        public String toString() {
+            return getNodeA() + "-" + getNodeB() + " (" + origEdgeKeyFirst + ", " + origEdgeKeyLast + ") " + getWeightAB();
+        }
+    }
+
+    /**
+     * This helper graph can be used to quickly obtain the edge-keys of the edges of a node. It is only used for
+     * edge-based CH. In principle we could use base graph for this, but it turned out it is faster to use this
+     * graph (because it does not need to read all the edge flags to determine the access flags).
+     */
+    private static class OrigGraph {
+        // we store a list of 'edges' in the format: adjNode|edgeId|accessFlags, we use two ints for each edge
+        private final IntArrayList adjNodes;
+        private final IntArrayList edgesAndFlags;
+        // for each node we store the index at which the edges for this node begin in the above edge list
+        private final IntArrayList firstEdgesByNode;
+
+        private OrigGraph(IntArrayList firstEdgesByNode, IntArrayList adjNodes, IntArrayList edgesAndFlags) {
+            this.firstEdgesByNode = firstEdgesByNode;
+            this.adjNodes = adjNodes;
+            this.edgesAndFlags = edgesAndFlags;
+        }
+
+        PrepareGraphOrigEdgeExplorer createOutOrigEdgeExplorer() {
+            return new OrigEdgeIteratorImpl(this, false);
+        }
+
+        PrepareGraphOrigEdgeExplorer createInOrigEdgeExplorer() {
+            return new OrigEdgeIteratorImpl(this, true);
+        }
+
+        static class Builder {
+            private final IntArrayList fromNodes = new IntArrayList();
+            private final IntArrayList toNodes = new IntArrayList();
+            private final IntArrayList edgesAndFlags = new IntArrayList();
+            private int maxFrom = -1;
+            private int maxTo = -1;
+
+            void addEdge(int from, int to, int edge, boolean fwd, boolean bwd) {
+                fromNodes.add(from);
+                toNodes.add(to);
+                edgesAndFlags.add(getEdgeWithFlags(edge, fwd, bwd));
+                maxFrom = Math.max(maxFrom, from);
+                maxTo = Math.max(maxTo, to);
+
+                fromNodes.add(to);
+                toNodes.add(from);
+                edgesAndFlags.add(getEdgeWithFlags(edge, bwd, fwd));
+                maxFrom = Math.max(maxFrom, to);
+                maxTo = Math.max(maxTo, from);
+            }
+
+            OrigGraph build() {
+                int[] sortOrder = IndirectSort.mergesort(0, fromNodes.elementsCount, new IndirectComparator.AscendingIntComparator(fromNodes.buffer));
+                sortAndTrim(fromNodes, sortOrder);
+                sortAndTrim(toNodes, sortOrder);
+                sortAndTrim(edgesAndFlags, sortOrder);
+                return new OrigGraph(buildFirstEdgesByNode(), toNodes, edgesAndFlags);
+            }
+
+            private int getEdgeWithFlags(int edge, boolean fwd, boolean bwd) {
+                // we use only 30 bits for the edge Id and store two access flags along with the same int
+                if (edge >= Integer.MAX_VALUE >> 2)
+                    throw new IllegalArgumentException("Maximum edge ID exceeded: " + Integer.MAX_VALUE);
+                edge <<= 1;
+                if (fwd)
+                    edge++;
+                edge <<= 1;
+                if (bwd)
+                    edge++;
+                return edge;
+            }
+
+            private IntArrayList buildFirstEdgesByNode() {
+                // it is assumed the edges have been sorted already
+                final int numFroms = maxFrom + 1;
+                IntArrayList firstEdgesByNode = new IntArrayList(numFroms + 1);
+                firstEdgesByNode.elementsCount = numFroms + 1;
+                int numEdges = fromNodes.size();
+                if (numFroms == 0) {
+                    firstEdgesByNode.set(0, numEdges);
+                    return firstEdgesByNode;
+                }
+                int edgeIndex = 0;
+                for (int from = 0; from < numFroms; from++) {
+                    while (edgeIndex < numEdges && fromNodes.get(edgeIndex) < from) {
+                        edgeIndex++;
+                    }
+                    firstEdgesByNode.set(from, edgeIndex);
+                }
+                firstEdgesByNode.set(numFroms, numEdges);
+                return firstEdgesByNode;
+            }
+
+        }
+    }
+
+    private static class OrigEdgeIteratorImpl implements PrepareGraphOrigEdgeExplorer, PrepareGraphOrigEdgeIterator {
+        private final OrigGraph graph;
+        private final boolean reverse;
+        private int node;
+        private int endEdge;
+        private int index;
+
+        public OrigEdgeIteratorImpl(OrigGraph graph, boolean reverse) {
+            this.graph = graph;
+            this.reverse = reverse;
+        }
+
+        @Override
+        public PrepareGraphOrigEdgeIterator setBaseNode(int node) {
+            this.node = node;
+            index = graph.firstEdgesByNode.get(node) - 1;
+            endEdge = graph.firstEdgesByNode.get(node + 1);
+            return this;
+        }
+
+        @Override
+        public boolean next() {
+            while (true) {
+                index++;
+                if (index >= endEdge)
+                    return false;
+                if (hasAccess())
+                    return true;
+            }
+        }
+
+        @Override
+        public int getBaseNode() {
+            return node;
+        }
+
+        @Override
+        public int getAdjNode() {
+            return graph.adjNodes.get(index);
+        }
+
+        @Override
+        public int getOrigEdgeKeyFirst() {
+            int e = graph.edgesAndFlags.get(index);
+            return GHUtility.createEdgeKey(node, getAdjNode(), e >> 2, false);
+        }
+
+        @Override
+        public int getOrigEdgeKeyLast() {
+            return getOrigEdgeKeyFirst();
+        }
+
+        private boolean hasAccess() {
+            int e = graph.edgesAndFlags.get(index);
+            if (reverse) {
+                return (e & 0b01) == 0b01;
+            } else {
+                return (e & 0b10) == 0b10;
+            }
+        }
+    }
+
+    private static void sortAndTrim(IntArrayList arr, int[] sortOrder) {
+        arr.buffer = applySortOrder(sortOrder, arr.buffer);
+        arr.elementsCount = arr.buffer.length;
+    }
+
+    private static int[] applySortOrder(int[] sortOrder, int[] arr) {
+        if (sortOrder.length > arr.length) {
+            throw new IllegalArgumentException("sort order must not be shorter than array");
+        }
+        int[] result = new int[sortOrder.length];
+        for (int i = 0; i < result.length; i++) {
+            result[i] = arr[sortOrder[i]];
+        }
+        return result;
+    }
+}
diff --git a/core/src/main/java/com/graphhopper/routing/ch/CHPreparationHandler.java b/core/src/main/java/com/graphhopper/routing/ch/CHPreparationHandler.java
index da57b3ea6..d7e8b0be3 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/CHPreparationHandler.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/CHPreparationHandler.java
@@ -185,17 +185,14 @@ public class CHPreparationHandler {
             LOGGER.info((++counter) + "/" + preparations.size() + " calling " +
                     "CH prepare.doWork for profile '" + prepare.getCHConfig().getName() + "' " + prepare.getCHConfig().getTraversalMode() + " ... (" + getMemInfo() + ")");
             final String name = prepare.getCHConfig().getName();
-            completionService.submit(new Runnable() {
-                @Override
-                public void run() {
-                    // toString is not taken into account so we need to cheat, see http://stackoverflow.com/q/6113746/194609 for other options
-                    Thread.currentThread().setName(name);
-                    prepare.doWork();
-                    if (closeEarly)
-                        prepare.close();
-
-                    properties.put(CH.PREPARE + "date." + name, createFormatter().format(new Date()));
-                }
+            completionService.submit(() -> {
+                // toString is not taken into account so we need to cheat, see http://stackoverflow.com/q/6113746/194609 for other options
+                Thread.currentThread().setName(name);
+                prepare.doWork();
+                if (closeEarly)
+                    prepare.close();
+
+                properties.put(CH.PREPARE + "date." + name, createFormatter().format(new Date()));
             }, name);
         }
 
@@ -209,6 +206,7 @@ public class CHPreparationHandler {
             threadPool.shutdownNow();
             throw new RuntimeException(e);
         }
+        LOGGER.info("Finished CH preparation, {}", getMemInfo());
     }
 
     public void createPreparations(GraphHopperStorage ghStorage) {
@@ -217,6 +215,7 @@ public class CHPreparationHandler {
         if (!hasCHConfigs())
             throw new IllegalStateException("No CH profiles found");
 
+        LOGGER.info("Creating CH preparations, {}", getMemInfo());
         for (CHConfig chConfig : chConfigs) {
             addPreparation(createCHPreparation(ghStorage, chConfig));
         }
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 627e2bbd0..9cafd0afb 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedNodeContractor.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedNodeContractor.java
@@ -17,17 +17,14 @@
  */
 package com.graphhopper.routing.ch;
 
-import com.carrotsearch.hppc.IntHashSet;
-import com.carrotsearch.hppc.IntSet;
-import com.graphhopper.util.EdgeIterator;
-import com.graphhopper.util.PMap;
-import com.graphhopper.util.StopWatch;
+import com.carrotsearch.hppc.*;
+import com.carrotsearch.hppc.cursors.IntCursor;
+import com.graphhopper.util.BitUtil;
+import com.graphhopper.util.*;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
-import java.util.HashSet;
 import java.util.Locale;
-import java.util.Set;
 
 import static com.graphhopper.routing.ch.CHParameters.*;
 import static com.graphhopper.util.Helper.nf;
@@ -44,22 +41,28 @@ import static com.graphhopper.util.Helper.nf;
  *
  * @author easbar
  */
-class EdgeBasedNodeContractor extends AbstractNodeContractor {
+class EdgeBasedNodeContractor implements NodeContractor {
     private static final Logger LOGGER = LoggerFactory.getLogger(EdgeBasedNodeContractor.class);
+    private final CHPreparationGraph prepareGraph;
+    private PrepareGraphEdgeExplorer inEdgeExplorer;
+    private PrepareGraphEdgeExplorer outEdgeExplorer;
+    private PrepareGraphEdgeExplorer existingShortcutExplorer;
+    private PrepareGraphOrigEdgeExplorer sourceNodeOrigInEdgeExplorer;
+    private PrepareGraphOrigEdgeExplorer targetNodeOrigOutEdgeExplorer;
+    private ShortcutHandler shortcutHandler;
     private final Params params = new Params();
     private final PMap pMap;
     private final StopWatch dijkstraSW = new StopWatch();
+    // temporary data used during node contraction
     private final IntSet sourceNodes = new IntHashSet(10);
-    private final IntSet toNodes = new IntHashSet(10);
+    private final IntSet targetNodes = new IntHashSet(10);
+    private final LongSet addedShortcuts = new LongHashSet();
     private final Stats addingStats = new Stats();
     private final Stats countingStats = new Stats();
     private Stats activeStats;
+
     private int[] hierarchyDepths;
     private EdgeBasedWitnessPathSearcher witnessPathSearcher;
-    private PrepareCHEdgeExplorer existingShortcutExplorer;
-    private PrepareCHEdgeExplorer allEdgeExplorer;
-    private PrepareCHEdgeExplorer sourceNodeOrigInEdgeExplorer;
-    private PrepareCHEdgeExplorer targetNodeOrigOutEdgeExplorer;
 
     // counts the total number of added shortcuts
     private int addedShortcutsCount;
@@ -74,8 +77,9 @@ class EdgeBasedNodeContractor extends AbstractNodeContractor {
     // counters used for performance analysis
     private int numPolledEdges;
 
-    public EdgeBasedNodeContractor(PrepareCHGraph prepareGraph, PMap pMap) {
-        super(prepareGraph);
+    public EdgeBasedNodeContractor(CHPreparationGraph prepareGraph, ShortcutHandler shortcutHandler, PMap pMap) {
+        this.prepareGraph = prepareGraph;
+        this.shortcutHandler = shortcutHandler;
         this.pMap = pMap;
         extractParams(pMap);
     }
@@ -88,20 +92,18 @@ class EdgeBasedNodeContractor extends AbstractNodeContractor {
 
     @Override
     public void initFromGraph() {
-        super.initFromGraph();
-        witnessPathSearcher = new EdgeBasedWitnessPathSearcher(prepareGraph, pMap);
         inEdgeExplorer = prepareGraph.createInEdgeExplorer();
         outEdgeExplorer = prepareGraph.createOutEdgeExplorer();
-        allEdgeExplorer = prepareGraph.createAllEdgeExplorer();
         existingShortcutExplorer = prepareGraph.createOutEdgeExplorer();
-        sourceNodeOrigInEdgeExplorer = prepareGraph.createOriginalInEdgeExplorer();
-        targetNodeOrigOutEdgeExplorer = prepareGraph.createOriginalOutEdgeExplorer();
+        sourceNodeOrigInEdgeExplorer = prepareGraph.createInOrigEdgeExplorer();
+        targetNodeOrigOutEdgeExplorer = prepareGraph.createOutOrigEdgeExplorer();
+        witnessPathSearcher = new EdgeBasedWitnessPathSearcher(prepareGraph, pMap);
         hierarchyDepths = new int[prepareGraph.getNodes()];
     }
 
     @Override
     public void prepareContraction() {
-        // not needed 
+        // not needed
     }
 
     @Override
@@ -114,7 +116,7 @@ class EdgeBasedNodeContractor extends AbstractNodeContractor {
             // no shortcuts will be introduced
             return Float.NEGATIVE_INFINITY;
         stats().stopWatch.start();
-        findAndHandleShortcuts(node, this::countShortcuts);
+        findAndHandlePrepareShortcuts(node, this::countShortcuts);
         stats().stopWatch.stop();
         // the higher the priority the later (!) this node will be contracted
         float edgeQuotient = numShortcuts / (float) numPrevEdges;
@@ -133,12 +135,20 @@ class EdgeBasedNodeContractor extends AbstractNodeContractor {
     }
 
     @Override
-    public void contractNode(int node) {
+    public IntContainer contractNode(int node) {
         activeStats = addingStats;
         stats().stopWatch.start();
-        findAndHandleShortcuts(node, this::addShortcut);
-        updateHierarchyDepthsOfNeighbors(node);
+        findAndHandlePrepareShortcuts(node, this::addShortcutsToPrepareGraph);
+        insertShortcuts(node);
+        IntContainer neighbors = prepareGraph.disconnect(node);
+        updateHierarchyDepthsOfNeighbors(node, neighbors);
         stats().stopWatch.stop();
+        return neighbors;
+    }
+
+    @Override
+    public void finishContraction() {
+        shortcutHandler.finishContraction();
     }
 
     @Override
@@ -168,17 +178,21 @@ class EdgeBasedNodeContractor extends AbstractNodeContractor {
         return numPolledEdges;
     }
 
-    private void findAndHandleShortcuts(int node, ShortcutHandler shortcutHandler) {
+    /**
+     * This method performs witness searches between all nodes adjacent to the given node and calls the
+     * given handler for all required shortcuts.
+     */
+    private void findAndHandlePrepareShortcuts(int node, PrepareShortcutHandler shortcutHandler) {
         numPolledEdges = 0;
         stats().nodes++;
-        Set<AddedShortcut> addedShortcuts = new HashSet<>();
+        addedShortcuts.clear();
 
         // first we need to identify the possible source nodes from which we can reach the center node
         sourceNodes.clear();
-        PrepareCHEdgeIterator incomingEdges = inEdgeExplorer.setBaseNode(node);
+        PrepareGraphEdgeIterator incomingEdges = inEdgeExplorer.setBaseNode(node);
         while (incomingEdges.next()) {
             int sourceNode = incomingEdges.getAdjNode();
-            if (isContracted(sourceNode) || sourceNode == node) {
+            if (sourceNode == node) {
                 continue;
             }
             boolean isNewSourceNode = sourceNodes.add(sourceNode);
@@ -186,56 +200,52 @@ class EdgeBasedNodeContractor extends AbstractNodeContractor {
                 continue;
             }
             // for each source node we need to look at every incoming original edge and find the initial entries
-            PrepareCHEdgeIterator origInIter = sourceNodeOrigInEdgeExplorer.setBaseNode(sourceNode);
+            PrepareGraphOrigEdgeIterator origInIter = sourceNodeOrigInEdgeExplorer.setBaseNode(sourceNode);
             while (origInIter.next()) {
-                int numInitialEntries = witnessPathSearcher.initSearch(node, sourceNode, origInIter.getOrigEdgeLast());
+                int numInitialEntries = witnessPathSearcher.initSearch(node, sourceNode, GHUtility.getEdgeFromEdgeKey(origInIter.getOrigEdgeKeyLast()));
                 if (numInitialEntries < 1) {
                     continue;
                 }
 
                 // now we need to identify all target nodes that can be reached from the center node
-                toNodes.clear();
-                PrepareCHEdgeIterator outgoingEdges = outEdgeExplorer.setBaseNode(node);
+                targetNodes.clear();
+                PrepareGraphEdgeIterator outgoingEdges = outEdgeExplorer.setBaseNode(node);
                 while (outgoingEdges.next()) {
                     int targetNode = outgoingEdges.getAdjNode();
-                    if (isContracted(targetNode) || targetNode == node) {
+                    if (targetNode == node) {
                         continue;
                     }
-                    boolean isNewTargetNode = toNodes.add(targetNode);
+                    boolean isNewTargetNode = targetNodes.add(targetNode);
                     if (!isNewTargetNode) {
                         continue;
                     }
                     // for each target edge outgoing from a target node we need to check if reaching it requires
                     // a 'bridge-path'
-                    PrepareCHEdgeIterator targetEdgeIter = targetNodeOrigOutEdgeExplorer.setBaseNode(targetNode);
+                    PrepareGraphOrigEdgeIterator targetEdgeIter = targetNodeOrigOutEdgeExplorer.setBaseNode(targetNode);
                     while (targetEdgeIter.next()) {
-                        int targetEdge = targetEdgeIter.getOrigEdgeFirst();
                         dijkstraSW.start();
-                        CHEntry entry = witnessPathSearcher.runSearch(targetNode, targetEdge);
+                        PrepareCHEntry entry = witnessPathSearcher.runSearch(targetNode, GHUtility.getEdgeFromEdgeKey(targetEdgeIter.getOrigEdgeKeyFirst()));
                         dijkstraSW.stop();
                         if (entry == null || Double.isInfinite(entry.weight)) {
                             continue;
                         }
-                        CHEntry root = entry.getParent();
-                        while (EdgeIterator.Edge.isValid(root.parent.edge)) {
+                        PrepareCHEntry root = entry.getParent();
+                        while (EdgeIterator.Edge.isValid(root.parent.prepareEdge)) {
                             root = root.getParent();
                         }
                         // 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)) {
+                        // shortcuts (makes slower queries). note that we are not detecting 'duplicate' shortcuts at a later
+                        // stage again, especially when we are just running with the counting handler.
+                        long addedShortcutKey = BitUtil.LITTLE.combineIntsToLong(root.getParent().incEdgeKey, entry.incEdgeKey);
+                        if (!addedShortcuts.add(addedShortcutKey))
                             continue;
-                        }
                         // root parent weight was misused to store initial turn cost here
                         double initialTurnCost = root.getParent().weight;
                         entry.weight -= initialTurnCost;
                         LOGGER.trace("Adding shortcuts for target entry {}", entry);
                         // todo: re-implement loop-avoidance heuristic as it existed in GH 1.0? it did not work the
                         // way it was implemented so it was removed.
-                        shortcutHandler.handleShortcut(root, entry);
-                        addedShortcuts.add(addedShortcut);
+                        shortcutHandler.handleShortcut(root, entry, incomingEdges.getOrigEdgeCount() + outgoingEdges.getOrigEdgeCount());
                     }
                 }
                 numPolledEdges += witnessPathSearcher.getNumPolledEdges();
@@ -243,106 +253,124 @@ class EdgeBasedNodeContractor extends AbstractNodeContractor {
         }
     }
 
+    /**
+     * Calls the shortcut handler for all edges and shortcuts adjacent to the given node. After this method is called
+     * these edges and shortcuts will be removed from the prepare graph, so this method offers the last chance to deal
+     * with them.
+     */
+    private void insertShortcuts(int node) {
+        shortcutHandler.startContractingNode();
+        {
+            PrepareGraphEdgeIterator iter = outEdgeExplorer.setBaseNode(node);
+            while (iter.next()) {
+                if (!iter.isShortcut())
+                    continue;
+                shortcutHandler.addShortcut(iter.getPrepareEdge(), node, iter.getAdjNode(),
+                        GHUtility.getEdgeFromEdgeKey(iter.getOrigEdgeKeyFirst()), GHUtility.getEdgeFromEdgeKey(iter.getOrigEdgeKeyLast()),
+                        iter.getSkipped1(), iter.getSkipped2(), iter.getWeight(), false);
+            }
+        }
+        {
+            PrepareGraphEdgeIterator iter = inEdgeExplorer.setBaseNode(node);
+            while (iter.next()) {
+                if (!iter.isShortcut())
+                    continue;
+                // we added loops using the outEdgeExplorer already above
+                if (iter.getAdjNode() == node)
+                    continue;
+                shortcutHandler.addShortcut(iter.getPrepareEdge(), node, iter.getAdjNode(),
+                        GHUtility.getEdgeFromEdgeKey(iter.getOrigEdgeKeyFirst()), GHUtility.getEdgeFromEdgeKey(iter.getOrigEdgeKeyLast()),
+                        iter.getSkipped1(), iter.getSkipped2(), iter.getWeight(), true);
+            }
+        }
+        addedShortcutsCount += shortcutHandler.finishContractingNode();
+    }
+
     private void countPreviousEdges(int node) {
         // todo: this edge counting can probably be simplified, but we might need to re-optimize heuristic parameters then
-        PrepareCHEdgeIterator outIter = outEdgeExplorer.setBaseNode(node);
+        PrepareGraphEdgeIterator outIter = outEdgeExplorer.setBaseNode(node);
         while (outIter.next()) {
-            if (isContracted(outIter.getAdjNode()))
-                continue;
+            numAllEdges++;
             numPrevEdges++;
-            if (!outIter.isShortcut()) {
-                numPrevOrigEdges++;
-            }
+            numPrevOrigEdges += outIter.getOrigEdgeCount();
         }
 
-        PrepareCHEdgeIterator inIter = inEdgeExplorer.setBaseNode(node);
+        PrepareGraphEdgeIterator inIter = inEdgeExplorer.setBaseNode(node);
         while (inIter.next()) {
-            if (isContracted(inIter.getAdjNode()))
-                continue;
+            numAllEdges++;
             // do not consider loop edges a second time
             if (inIter.getBaseNode() == inIter.getAdjNode())
                 continue;
             numPrevEdges++;
-            if (!inIter.isShortcut()) {
-                numPrevOrigEdges++;
-            }
-        }
-
-        PrepareCHEdgeIterator allIter = allEdgeExplorer.setBaseNode(node);
-        while (allIter.next()) {
-            numAllEdges++;
-            if (isContracted(allIter.getAdjNode()))
-                continue;
-            if (allIter.isShortcut()) {
-                numPrevOrigEdges += getOrigEdgeCount(allIter.getEdge());
-            }
+            numPrevOrigEdges += inIter.getOrigEdgeCount();
         }
     }
 
-    private void updateHierarchyDepthsOfNeighbors(int node) {
-        PrepareCHEdgeIterator iter = allEdgeExplorer.setBaseNode(node);
-        while (iter.next()) {
-            if (isContracted(iter.getAdjNode()) || iter.getAdjNode() == node)
+    private void updateHierarchyDepthsOfNeighbors(int node, IntContainer neighbors) {
+        int level = hierarchyDepths[node];
+        for (IntCursor n : neighbors) {
+            if (n.value == node)
                 continue;
-            hierarchyDepths[iter.getAdjNode()] = Math.max(hierarchyDepths[iter.getAdjNode()], hierarchyDepths[node] + 1);
+            hierarchyDepths[n.value] = Math.max(hierarchyDepths[n.value], level + 1);
         }
     }
 
-    private CHEntry addShortcut(CHEntry edgeFrom, CHEntry edgeTo) {
-        if (edgeTo.parent.edge != edgeFrom.edge) {
-            CHEntry prev = addShortcut(edgeFrom, edgeTo.getParent());
-            return doAddShortcut(prev, edgeTo);
+    private PrepareCHEntry addShortcutsToPrepareGraph(PrepareCHEntry edgeFrom, PrepareCHEntry edgeTo, int origEdgeCount) {
+        if (edgeTo.parent.prepareEdge != edgeFrom.prepareEdge) {
+            // counting origEdgeCount correctly is tricky with loop shortcuts and the recursion we use here. so we
+            // simply ignore this, it probably does not matter that much
+            PrepareCHEntry prev = addShortcutsToPrepareGraph(edgeFrom, edgeTo.getParent(), origEdgeCount);
+            return doAddShortcut(prev, edgeTo, origEdgeCount);
         } else {
-            return doAddShortcut(edgeFrom, edgeTo);
+            return doAddShortcut(edgeFrom, edgeTo, origEdgeCount);
         }
     }
 
-    private CHEntry doAddShortcut(CHEntry edgeFrom, CHEntry edgeTo) {
+    private PrepareCHEntry doAddShortcut(PrepareCHEntry edgeFrom, PrepareCHEntry edgeTo, int origEdgeCount) {
         int from = edgeFrom.parent.adjNode;
         int adjNode = edgeTo.adjNode;
 
-        final PrepareCHEdgeIterator iter = existingShortcutExplorer.setBaseNode(from);
+        final PrepareGraphEdgeIterator iter = existingShortcutExplorer.setBaseNode(from);
         while (iter.next()) {
-            if (!isSameShortcut(iter, adjNode, edgeFrom.getParent().incEdge, edgeTo.incEdge)) {
-                // this is some other (shortcut) edge, we do not care
+            if (!isSameShortcut(iter, adjNode, edgeFrom.getParent().incEdgeKey, edgeTo.incEdgeKey)) {
+                // this is some other (shortcut) edge -> we do not care
                 continue;
             }
-            final double existingWeight = iter.getWeight(false);
+            final double existingWeight = iter.getWeight();
             if (existingWeight <= edgeTo.weight) {
                 // our shortcut already exists with lower weight --> do nothing
-                CHEntry entry = new CHEntry(iter.getEdge(), iter.getOrigEdgeLast(), adjNode, existingWeight);
+                PrepareCHEntry entry = new PrepareCHEntry(iter.getPrepareEdge(), iter.getOrigEdgeKeyLast(), adjNode, existingWeight);
                 entry.parent = edgeFrom.parent;
                 return entry;
             } else {
                 // update weight
-                iter.setSkippedEdges(edgeFrom.edge, edgeTo.edge);
+                iter.setSkippedEdges(edgeFrom.prepareEdge, edgeTo.prepareEdge);
                 iter.setWeight(edgeTo.weight);
-                CHEntry entry = new CHEntry(iter.getEdge(), iter.getOrigEdgeLast(), adjNode, edgeTo.weight);
+                iter.setOrigEdgeCount(origEdgeCount);
+                PrepareCHEntry entry = new PrepareCHEntry(iter.getPrepareEdge(), iter.getOrigEdgeKeyLast(), adjNode, edgeTo.weight);
                 entry.parent = edgeFrom.parent;
                 return entry;
             }
         }
 
         // our shortcut is new --> add it
-        // this is a bit of a hack, we misuse incEdge of edgeFrom's parent to store the first orig edge
-        int origFirst = edgeFrom.getParent().incEdge;
-        LOGGER.trace("Adding shortcut from {} to {}, weight: {}, firstOrigEdge: {}, lastOrigEdge: {}",
-                from, adjNode, edgeTo.weight, edgeFrom.getParent().incEdge, edgeTo.incEdge);
-        int accessFlags = PrepareEncoder.getScFwdDir();
-        int shortcutId = prepareGraph.shortcutEdgeBased(from, adjNode, accessFlags, edgeTo.weight, edgeFrom.edge, edgeTo.edge, origFirst, edgeTo.incEdge);
-        final int origEdgeCount = getOrigEdgeCount(edgeFrom.edge) + getOrigEdgeCount(edgeTo.edge);
-        setOrigEdgeCount(shortcutId, origEdgeCount);
-        addedShortcutsCount++;
-        CHEntry entry = new CHEntry(shortcutId, shortcutId, edgeTo.adjNode, edgeTo.weight);
+        // this is a bit of a hack, we misuse incEdgeKey of edgeFrom's parent to store the first orig edge
+        int origFirstKey = edgeFrom.getParent().incEdgeKey;
+        LOGGER.trace("Adding shortcut from {} to {}, weight: {}, firstOrigEdgeKey: {}, lastOrigEdgeKey: {}",
+                from, adjNode, edgeTo.weight, origFirstKey, edgeTo.incEdgeKey);
+        int prepareEdge = prepareGraph.addShortcut(from, adjNode, origFirstKey, edgeTo.incEdgeKey, edgeFrom.prepareEdge, edgeTo.prepareEdge, edgeTo.weight, origEdgeCount);
+        // does not matter here
+        int incEdgeKey = -1;
+        PrepareCHEntry entry = new PrepareCHEntry(prepareEdge, incEdgeKey, edgeTo.adjNode, edgeTo.weight);
         entry.parent = edgeFrom.parent;
         return entry;
     }
 
-    private boolean isSameShortcut(PrepareCHEdgeIterator iter, int adjNode, int firstOrigEdge, int lastOrigEdge) {
+    private boolean isSameShortcut(PrepareGraphEdgeIterator iter, int adjNode, int firstOrigEdgeKey, int lastOrigEdgeKey) {
         return iter.isShortcut()
                 && (iter.getAdjNode() == adjNode)
-                && (iter.getOrigEdgeFirst() == firstOrigEdge)
-                && (iter.getOrigEdgeLast() == lastOrigEdge);
+                && (iter.getOrigEdgeKeyFirst() == firstOrigEdgeKey)
+                && (iter.getOrigEdgeKeyLast() == lastOrigEdgeKey);
     }
 
     private void resetEdgeCounters() {
@@ -353,25 +381,41 @@ class EdgeBasedNodeContractor extends AbstractNodeContractor {
         numAllEdges = 0;
     }
 
+    @Override
+    public void close() {
+        prepareGraph.close();
+        inEdgeExplorer = null;
+        outEdgeExplorer = null;
+        existingShortcutExplorer = null;
+        sourceNodeOrigInEdgeExplorer = null;
+        targetNodeOrigOutEdgeExplorer = null;
+        shortcutHandler = null;
+        witnessPathSearcher.close();
+        sourceNodes.release();
+        targetNodes.release();
+        addedShortcuts.release();
+        hierarchyDepths = null;
+    }
+
     private Stats stats() {
         return activeStats;
     }
 
     @FunctionalInterface
-    private interface ShortcutHandler {
-        void handleShortcut(CHEntry edgeFrom, CHEntry edgeTo);
+    private interface PrepareShortcutHandler {
+        void handleShortcut(PrepareCHEntry edgeFrom, PrepareCHEntry edgeTo, int origEdgeCount);
     }
 
-    private void countShortcuts(CHEntry edgeFrom, CHEntry edgeTo) {
+    private void countShortcuts(PrepareCHEntry edgeFrom, PrepareCHEntry edgeTo, int origEdgeCount) {
         int fromNode = edgeFrom.parent.adjNode;
         int toNode = edgeTo.adjNode;
-        int firstOrigEdge = edgeFrom.getParent().incEdge;
-        int lastOrigEdge = edgeTo.incEdge;
+        int firstOrigEdgeKey = edgeFrom.getParent().incEdgeKey;
+        int lastOrigEdgeKey = edgeTo.incEdgeKey;
 
         // check if this shortcut already exists
-        final PrepareCHEdgeIterator iter = existingShortcutExplorer.setBaseNode(fromNode);
+        final PrepareGraphEdgeIterator iter = existingShortcutExplorer.setBaseNode(fromNode);
         while (iter.next()) {
-            if (isSameShortcut(iter, toNode, firstOrigEdge, lastOrigEdge)) {
+            if (isSameShortcut(iter, toNode, firstOrigEdgeKey, lastOrigEdgeKey)) {
                 // this shortcut exists already, maybe its weight will be updated but we should not count it as
                 // a new edge
                 return;
@@ -380,7 +424,7 @@ class EdgeBasedNodeContractor extends AbstractNodeContractor {
 
         // this shortcut is new --> increase counts
         numShortcuts++;
-        numOrigEdges += getOrigEdgeCount(edgeFrom.edge) + getOrigEdgeCount(edgeTo.edge);
+        numOrigEdges += origEdgeCount;
     }
 
     public static class Params {
@@ -401,34 +445,30 @@ class EdgeBasedNodeContractor extends AbstractNodeContractor {
         }
     }
 
-    private static class AddedShortcut {
-        int startNode;
-        int startEdge;
-        int endNode;
-        int targetEdge;
-
-        public AddedShortcut(int startNode, int startEdge, int endNode, int targetEdge) {
-            this.startNode = startNode;
-            this.startEdge = startEdge;
-            this.endNode = endNode;
-            this.targetEdge = targetEdge;
-        }
-
-        @Override
-        public boolean equals(Object o) {
-            if (this == o) return true;
-            if (o == null || getClass() != o.getClass()) return false;
-            AddedShortcut that = (AddedShortcut) o;
-            return startNode == that.startNode &&
-                    startEdge == that.startEdge &&
-                    endNode == that.endNode &&
-                    targetEdge == that.targetEdge;
-        }
-
-        @Override
-        public int hashCode() {
-            return 31 * startNode + endNode;
-        }
+    /**
+     * This handler is called on every shortcut that this contractor finds necessary to add for the contracted node.
+     */
+    public interface ShortcutHandler {
+        /**
+         * Use this hook for any kind of initialization to be done before a node is contracted
+         */
+        void startContractingNode();
+
+        /**
+         * This method is called for every shortcut found by the contractor
+         */
+        void addShortcut(int prepareEdge, int from, int to, int origEdgeFirst, int origEdgeLast, int skipped1, int skipped2, double weight, boolean reverse);
+
+        /**
+         * Use this hook for any kind of post-processing after the node is contracted
+         *
+         * @return the actual number of shortcuts that were added to the graph
+         */
+        int finishContractingNode();
+
+        /**
+         * This method is called at the very end of the graph contraction (after the last node was contracted)
+         */
+        void finishContraction();
     }
-
 }
diff --git a/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedShortcutInserter.java b/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedShortcutInserter.java
new file mode 100644
index 000000000..b7023fcdf
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedShortcutInserter.java
@@ -0,0 +1,87 @@
+/*
+ *  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.carrotsearch.hppc.IntArrayList;
+import com.graphhopper.routing.util.AllCHEdgesIterator;
+import com.graphhopper.storage.CHGraph;
+
+/**
+ * Shortcut handler that inserts the given shortcuts into a CHGraph
+ */
+public class EdgeBasedShortcutInserter implements EdgeBasedNodeContractor.ShortcutHandler {
+    private final CHGraph chGraph;
+    private final int origEdges;
+    private final IntArrayList shortcutsByPrepareEdges;
+    private int shortcutCount;
+
+    public EdgeBasedShortcutInserter(CHGraph chGraph) {
+        this.chGraph = chGraph;
+        this.origEdges = chGraph.getOriginalEdges();
+        this.shortcutsByPrepareEdges = new IntArrayList();
+    }
+
+    @Override
+    public void startContractingNode() {
+        shortcutCount = 0;
+    }
+
+    @Override
+    public void addShortcut(int prepareEdge, int from, int to, int origEdgeFirst, int origEdgeLast, int skipped1, int skipped2, double weight, boolean reverse) {
+        int flags = reverse ? PrepareEncoder.getScBwdDir() : PrepareEncoder.getScFwdDir();
+        int scId = chGraph.shortcutEdgeBased(from, to, flags, weight, skipped1, skipped2, origEdgeFirst, origEdgeLast);
+        shortcutCount++;
+        setShortcutForPrepareEdge(prepareEdge, scId);
+    }
+
+    @Override
+    public int finishContractingNode() {
+        return shortcutCount;
+    }
+
+    @Override
+    public void finishContraction() {
+        // during contraction the skip1/2 edges of shortcuts refer to the prepare edge-ids *not* the CHGraph (shortcut)
+        // ids (because they are not known before the insertion) -> we need to re-map these ids here
+        AllCHEdgesIterator iter = chGraph.getAllEdges();
+        while (iter.next()) {
+            // todo: performance, ideally this loop would start with the first *shortcut* not edge
+            if (!iter.isShortcut())
+                continue;
+            int skip1 = getShortcutForArc(iter.getSkippedEdge1());
+            int skip2 = getShortcutForArc(iter.getSkippedEdge2());
+            iter.setSkippedEdges(skip1, skip2);
+        }
+    }
+
+    private void setShortcutForPrepareEdge(int prepareEdge, int shortcut) {
+        int index = prepareEdge - origEdges;
+        if (index >= shortcutsByPrepareEdges.size())
+            shortcutsByPrepareEdges.resize(index + 1);
+        shortcutsByPrepareEdges.set(index, shortcut);
+    }
+
+    private int getShortcutForArc(int prepareEdge) {
+        if (prepareEdge < origEdges)
+            return prepareEdge;
+        int index = prepareEdge - origEdges;
+        return shortcutsByPrepareEdges.get(index);
+    }
+
+}
diff --git a/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedWitnessPathSearcher.java b/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedWitnessPathSearcher.java
index 49c2f2a84..1b68ab4ae 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedWitnessPathSearcher.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedWitnessPathSearcher.java
@@ -64,11 +64,9 @@ public class EdgeBasedWitnessPathSearcher {
     private static final int NO_NODE = -1;
     private static final double MAX_ZERO_WEIGHT_LOOP = 1.e-3;
 
-    // graph variables
-    private final PrepareCHGraph chGraph;
-    private final PrepareCHEdgeExplorer outEdgeExplorer;
-    private final PrepareCHEdgeExplorer origInEdgeExplorer;
-    private final int maxLevel;
+    private final CHPreparationGraph prepareGraph;
+    private PrepareGraphEdgeExplorer outEdgeExplorer;
+    private PrepareGraphOrigEdgeExplorer origInEdgeExplorer;
 
     // general parameters affecting the number of found witnesses and the search time
     private final Params params = new Params();
@@ -78,7 +76,7 @@ public class EdgeBasedWitnessPathSearcher {
     private int sourceNode;
     private int centerNode;
     private double bestPathWeight;
-    private int bestPathIncEdge;
+    private int bestPathIncKey;
     private boolean bestPathIsBridgePath;
     private int numPathsToCenter;
     private int numSettledEdges;
@@ -87,12 +85,10 @@ public class EdgeBasedWitnessPathSearcher {
     // data structures used to build the shortest path tree
     // we allocate memory for all possible edge keys and keep track which ones have been discovered so far
     private double[] weights;
-    private int[] edges;
-    private int[] incEdges;
+    private int[] prepareEdges;
     private int[] parents;
-    private int[] adjNodes;
-    private boolean[] isPathToCenters;
-    private IntObjectMap<CHEntry> initialEntryParents;
+    private int[] adjNodesAndIsPathToCenters;
+    private IntObjectMap<PrepareCHEntry> initialEntryParents;
     private IntArrayList changedEdges;
     private IntFloatBinaryHeap dijkstraHeap;
 
@@ -105,17 +101,15 @@ public class EdgeBasedWitnessPathSearcher {
     private final Stats currentBatchStats = new Stats();
     private final Stats totalStats = new Stats();
 
-    public EdgeBasedWitnessPathSearcher(PrepareCHGraph chGraph, PMap pMap) {
-        this.chGraph = chGraph;
+    public EdgeBasedWitnessPathSearcher(CHPreparationGraph prepareGraph, PMap pMap) {
+        this.prepareGraph = prepareGraph;
         extractParams(pMap);
 
-        outEdgeExplorer = chGraph.createOutEdgeExplorer();
-        origInEdgeExplorer = chGraph.createOriginalInEdgeExplorer();
-        maxLevel = chGraph.getNodes();
+        outEdgeExplorer = prepareGraph.createOutEdgeExplorer();
+        origInEdgeExplorer = prepareGraph.createInOrigEdgeExplorer();
 
         maxSettledEdges = params.minimumMaxSettledEdges;
-        int numOriginalEdges = chGraph.getOriginalEdges();
-        initStorage(2 * numOriginalEdges);
+        initStorage(2 * prepareGraph.getOriginalEdges());
         initCollections();
     }
 
@@ -164,22 +158,21 @@ public class EdgeBasedWitnessPathSearcher {
      * 'bridge-path' (see above) has been found to be the optimal path or null if the optimal path is either a witness
      * path or no finite weight path starting with the search edge and leading to the target edge could be found at all.
      */
-    public CHEntry runSearch(int targetNode, int targetEdge) {
+    public PrepareCHEntry runSearch(int targetNode, int targetEdge) {
         // if source and target are equal we already have a candidate for the best path: a simple turn from the source
         // to the target edge
         bestPathWeight = sourceNode == targetNode
                 ? calcTurnWeight(sourceEdge, sourceNode, targetEdge)
                 : Double.POSITIVE_INFINITY;
-        bestPathIncEdge = NO_EDGE;
+        bestPathIncKey = NO_EDGE;
         bestPathIsBridgePath = false;
 
         // check if we can already reach the target from the shortest path tree we discovered so far
-        PrepareCHEdgeIterator inIter = origInEdgeExplorer.setBaseNode(targetNode);
+        PrepareGraphOrigEdgeIterator inIter = origInEdgeExplorer.setBaseNode(targetNode);
         while (inIter.next()) {
-            final int incEdge = inIter.getOrigEdgeLast();
-            final int edgeKey = getEdgeKey(incEdge, targetNode);
-            if (EdgeIterator.Edge.isValid(edges[edgeKey])) {
-                boolean isZeroWeightLoop = parents[edgeKey] >= 0 && targetNode == adjNodes[parents[edgeKey]] &&
+            final int edgeKey = GHUtility.reverseEdgeKey(inIter.getOrigEdgeKeyLast());
+            if (EdgeIterator.Edge.isValid(prepareEdges[edgeKey])) {
+                boolean isZeroWeightLoop = parents[edgeKey] >= 0 && targetNode == getAdjNode(parents[edgeKey]) &&
                         weights[edgeKey] - weights[parents[edgeKey]] <= MAX_ZERO_WEIGHT_LOOP;
                 if (!isZeroWeightLoop) {
                     // we may not update the best path if we are dealing with a zero weight loop here, because when a
@@ -209,39 +202,39 @@ public class EdgeBasedWitnessPathSearcher {
             currentBatchStats.numPolledEdges++;
             totalStats.numPolledEdges++;
 
-            if (isPathToCenters[currKey]) {
+            if (isPathToCenter(currKey)) {
                 numPathsToCenter--;
             }
 
             // after a certain amount of edges has been settled we only expand entries that might yield a bridge-path
-            if (numSettledEdges > maxSettledEdges && !isPathToCenters[currKey]) {
+            if (numSettledEdges > maxSettledEdges && !isPathToCenter(currKey)) {
                 continue;
             }
 
-            final int fromNode = adjNodes[currKey];
-            PrepareCHEdgeIterator iter = outEdgeExplorer.setBaseNode(fromNode);
+            final int fromNode = getAdjNode(currKey);
+            PrepareGraphEdgeIterator iter = outEdgeExplorer.setBaseNode(fromNode);
             while (iter.next()) {
-                if (isContracted(iter.getAdjNode())) {
-                    continue;
-                }
-                double edgeWeight = iter.getWeight(false) + calcTurnWeight(incEdges[currKey], iter.getBaseNode(), iter.getOrigEdgeFirst());
+                double edgeWeight = iter.getWeight() + calcTurnWeight(GHUtility.getEdgeFromEdgeKey(currKey),
+                        iter.getBaseNode(), GHUtility.getEdgeFromEdgeKey(iter.getOrigEdgeKeyFirst()));
                 double weight = edgeWeight + weights[currKey];
                 if (isInfinite(weight)) {
                     continue;
                 }
-                boolean isPathToCenter = this.isPathToCenters[currKey] && iter.getAdjNode() == centerNode;
+                boolean isPathToCenter = isPathToCenter(currKey) && iter.getAdjNode() == centerNode;
                 boolean isZeroWeightLoop = fromNode == targetNode && edgeWeight <= MAX_ZERO_WEIGHT_LOOP;
 
                 // dijkstra expansion: add or update current entries
-                int key = getEdgeKey(iter.getOrigEdgeLast(), iter.getAdjNode());
-                if (!EdgeIterator.Edge.isValid(edges[key])) {
+                int key = iter.getOrigEdgeKeyLast();
+                if (!EdgeIterator.Edge.isValid(prepareEdges[key])) {
                     setEntry(key, iter, weight, currKey, isPathToCenter);
                     changedEdges.add(key);
                     dijkstraHeap.insert(weight, key);
                     if (!isZeroWeightLoop) {
                         updateBestPath(targetNode, targetEdge, key);
                     }
-                } else if (weight < weights[key]) {
+                } else if (weight < weights[key]
+                        // special case of a witness path with equal weight -> rather take this than the bridge path
+                        || (weight == weights[key] && iter.getAdjNode() == targetNode && !isPathToCenter(currKey))) {
                     updateEntry(key, iter, weight, currKey, isPathToCenter);
                     dijkstraHeap.update(weight, key);
                     if (!isZeroWeightLoop) {
@@ -260,13 +253,13 @@ public class EdgeBasedWitnessPathSearcher {
         }
 
         if (bestPathIsBridgePath) {
-            int edgeKey = getEdgeKey(bestPathIncEdge, targetNode);
-            CHEntry result = getEntryForKey(edgeKey);
+            int edgeKey = bestPathIncKey;
+            PrepareCHEntry result = getEntryForKey(edgeKey);
             // prepend all ancestors
-            CHEntry entry = result;
+            PrepareCHEntry entry = result;
             while (parents[edgeKey] >= 0) {
                 edgeKey = parents[edgeKey];
-                CHEntry parent = getEntryForKey(edgeKey);
+                PrepareCHEntry parent = getEntryForKey(edgeKey);
                 entry.parent = parent;
                 entry = parent;
             }
@@ -277,6 +270,25 @@ public class EdgeBasedWitnessPathSearcher {
         }
     }
 
+    private void setAdjNodeAndPathToCenter(int key, int adjNode, boolean isPathToCenter) {
+        adjNodesAndIsPathToCenters[key] = (adjNode << 1) + (isPathToCenter ? 1 : 0);
+    }
+
+    private int getAdjNode(int key) {
+        return (adjNodesAndIsPathToCenters[key] >> 1);
+    }
+
+    private void setPathToCenter(int key, boolean isPathToCenter) {
+        if (isPathToCenter)
+            adjNodesAndIsPathToCenters[key] |= 0b1;
+        else
+            adjNodesAndIsPathToCenters[key] &= ~0b1;
+    }
+
+    private boolean isPathToCenter(int key) {
+        return (adjNodesAndIsPathToCenters[key] & 0b01) == 0b01;
+    }
+
     public String getStatisticsString() {
         return "last batch: " + currentBatchStats.toString() + " total: " + totalStats.toString();
     }
@@ -294,24 +306,32 @@ public class EdgeBasedWitnessPathSearcher {
         currentBatchStats.reset();
     }
 
+    public void close() {
+        prepareGraph.close();
+        outEdgeExplorer = null;
+        origInEdgeExplorer = null;
+        weights = null;
+        prepareEdges = null;
+        parents = null;
+        adjNodesAndIsPathToCenters = null;
+        initialEntryParents = null;
+        changedEdges.release();
+        dijkstraHeap = null;
+    }
+
     private void initStorage(int numEntries) {
         weights = new double[numEntries];
         Arrays.fill(weights, Double.POSITIVE_INFINITY);
 
-        edges = new int[numEntries];
-        Arrays.fill(edges, NO_EDGE);
-
-        incEdges = new int[numEntries];
-        Arrays.fill(incEdges, NO_EDGE);
+        prepareEdges = new int[numEntries];
+        Arrays.fill(prepareEdges, NO_EDGE);
 
         parents = new int[numEntries];
         Arrays.fill(parents, NO_NODE);
 
-        adjNodes = new int[numEntries];
-        Arrays.fill(adjNodes, NO_NODE);
-
-        isPathToCenters = new boolean[numEntries];
-        Arrays.fill(isPathToCenters, false);
+        adjNodesAndIsPathToCenters = new int[numEntries];
+        // need bit shift, see getAdjNode(int)
+        Arrays.fill(adjNodesAndIsPathToCenters, NO_NODE << 1);
     }
 
     private void initCollections() {
@@ -321,45 +341,39 @@ public class EdgeBasedWitnessPathSearcher {
     }
 
     private void setInitialEntries(int sourceNode, int sourceEdge, int centerNode) {
-        PrepareCHEdgeIterator outIter = outEdgeExplorer.setBaseNode(sourceNode);
+        PrepareGraphEdgeIterator outIter = outEdgeExplorer.setBaseNode(sourceNode);
         while (outIter.next()) {
-            if (isContracted(outIter.getAdjNode())) {
-                continue;
-            }
-            double turnWeight = calcTurnWeight(sourceEdge, sourceNode, outIter.getOrigEdgeFirst());
+            double turnWeight = calcTurnWeight(sourceEdge, sourceNode, GHUtility.getEdgeFromEdgeKey(outIter.getOrigEdgeKeyFirst()));
             if (isInfinite(turnWeight)) {
                 continue;
             }
-            double edgeWeight = outIter.getWeight(false);
+            double edgeWeight = outIter.getWeight();
             double weight = turnWeight + edgeWeight;
             boolean isPathToCenter = outIter.getAdjNode() == centerNode;
-            int incEdge = outIter.getOrigEdgeLast();
+            int key = outIter.getOrigEdgeKeyLast();
             int adjNode = outIter.getAdjNode();
-            int key = getEdgeKey(incEdge, adjNode);
             int parentKey = -key - 1;
-            // note that we 'misuse' the parent also to store initial turncost and the first original edge of this 
+            // note that we 'misuse' the parent also to store initial turncost and the first original edge key of this
             // initial entry
-            CHEntry parent = new CHEntry(
+            PrepareCHEntry parent = new PrepareCHEntry(
                     NO_EDGE,
-                    outIter.getOrigEdgeFirst(),
+                    outIter.getOrigEdgeKeyFirst(),
                     sourceNode, turnWeight);
-            if (!EdgeIterator.Edge.isValid(edges[key])) {
+            if (!EdgeIterator.Edge.isValid(prepareEdges[key])) {
                 // add new initial entry
-                edges[key] = outIter.getEdge();
-                incEdges[key] = incEdge;
-                adjNodes[key] = adjNode;
+                prepareEdges[key] = outIter.getPrepareEdge();
                 weights[key] = weight;
                 parents[key] = parentKey;
-                isPathToCenters[key] = isPathToCenter;
+                setAdjNodeAndPathToCenter(key, adjNode, isPathToCenter);
                 initialEntryParents.put(parentKey, parent);
                 changedEdges.add(key);
             } else if (weight < weights[key]) {
                 // update existing entry, there may be entries with the same adjNode and last original edge,
                 // but we only need the one with the lowest weight
-                edges[key] = outIter.getEdge();
+                prepareEdges[key] = outIter.getPrepareEdge();
                 weights[key] = weight;
                 parents[key] = parentKey;
-                isPathToCenters[key] = isPathToCenter;
+                setPathToCenter(key, isPathToCenter);
                 initialEntryParents.put(parentKey, parent);
             }
         }
@@ -367,7 +381,7 @@ public class EdgeBasedWitnessPathSearcher {
         // now that we know which entries are actually needed we add them to the heap
         for (int i = 0; i < changedEdges.size(); ++i) {
             int key = changedEdges.get(i);
-            if (isPathToCenters[key]) {
+            if (isPathToCenter(key)) {
                 numPathsToCenter++;
             }
             dijkstraHeap.insert(weights[key], key);
@@ -406,75 +420,62 @@ public class EdgeBasedWitnessPathSearcher {
     }
 
     private void updateBestPath(int targetNode, int targetEdge, int edgeKey) {
-        // whenever we hit the target node we update the best path
-        if (adjNodes[edgeKey] == targetNode) {
-            double totalWeight = weights[edgeKey] + calcTurnWeight(incEdges[edgeKey], targetNode, targetEdge);
+        // whenever we hit the target node we update the best path *if* it allows turning onto the target edge
+        // less costly than the currently best path
+        if (getAdjNode(edgeKey) == targetNode) {
+            double totalWeight = weights[edgeKey] + calcTurnWeight(GHUtility.getEdgeFromEdgeKey(edgeKey), targetNode, targetEdge);
             // there is a path to the target so we know that there must be some parent. therefore a negative parent key
             // means that the parent is a root parent (a parent of an initial entry) and we did not go via the center
             // node.
-            boolean isBridgePath = parents[edgeKey] >= 0 && isPathToCenters[parents[edgeKey]];
+            boolean isBridgePath = parents[edgeKey] >= 0 && isPathToCenter(parents[edgeKey]);
             // in case of equal weights we always prefer a witness path over a bridge-path
             double tolerance = isBridgePath ? 0 : 1.e-6;
             if (totalWeight - tolerance < bestPathWeight) {
                 bestPathWeight = totalWeight;
-                bestPathIncEdge = incEdges[edgeKey];
+                bestPathIncKey = edgeKey;
                 bestPathIsBridgePath = isBridgePath;
             }
         }
     }
 
-    private void setEntry(int key, PrepareCHEdgeIterator edge, double weight, int parent, boolean isPathToCenter) {
-        edges[key] = edge.getEdge();
-        incEdges[key] = edge.getOrigEdgeLast();
-        adjNodes[key] = edge.getAdjNode();
+    private void setEntry(int key, PrepareGraphEdgeIterator edge, double weight, int parent, boolean isPathToCenter) {
+        prepareEdges[key] = edge.getPrepareEdge();
         weights[key] = weight;
         parents[key] = parent;
-        if (isPathToCenter) {
-            isPathToCenters[key] = true;
+        setAdjNodeAndPathToCenter(key, edge.getAdjNode(), isPathToCenter);
+        if (isPathToCenter)
             numPathsToCenter++;
-        }
     }
 
-    private void updateEntry(int key, PrepareCHEdgeIterator edge, double weight, int currKey, boolean isPathToCenter) {
-        edges[key] = edge.getEdge();
+    private void updateEntry(int key, PrepareGraphEdgeIterator edge, double weight, int parent, boolean isPathToCenter) {
+        prepareEdges[key] = edge.getPrepareEdge();
         weights[key] = weight;
-        parents[key] = currKey;
+        parents[key] = parent;
         if (isPathToCenter) {
-            if (!isPathToCenters[key]) {
+            if (!isPathToCenter(key)) {
                 numPathsToCenter++;
             }
         } else {
-            if (isPathToCenters[key]) {
+            if (isPathToCenter(key)) {
                 numPathsToCenter--;
             }
         }
-        isPathToCenters[key] = isPathToCenter;
+        setPathToCenter(key, isPathToCenter);
     }
 
     private void resetEntry(int key) {
         weights[key] = Double.POSITIVE_INFINITY;
-        edges[key] = NO_EDGE;
-        incEdges[key] = NO_EDGE;
+        prepareEdges[key] = NO_EDGE;
         parents[key] = NO_NODE;
-        adjNodes[key] = NO_NODE;
-        isPathToCenters[key] = false;
-    }
-
-    private CHEntry getEntryForKey(int edgeKey) {
-        return new CHEntry(edges[edgeKey], incEdges[edgeKey], adjNodes[edgeKey], weights[edgeKey]);
+        setAdjNodeAndPathToCenter(key, NO_NODE, false);
     }
 
-    private int getEdgeKey(int edge, int adjNode) {
-        int baseNode = chGraph.getOtherNode(edge, adjNode);
-        return GHUtility.createEdgeKey(baseNode, adjNode, edge, false);
+    private PrepareCHEntry getEntryForKey(int edgeKey) {
+        return new PrepareCHEntry(prepareEdges[edgeKey], edgeKey, getAdjNode(edgeKey), weights[edgeKey]);
     }
 
     private double calcTurnWeight(int inEdge, int viaNode, int outEdge) {
-        return chGraph.getTurnWeight(inEdge, viaNode, outEdge);
-    }
-
-    private boolean isContracted(int node) {
-        return chGraph.getLevel(node) != maxLevel;
+        return prepareGraph.getTurnWeight(inEdge, viaNode, outEdge);
     }
 
     static class Params {
@@ -515,6 +516,5 @@ public class EdgeBasedWitnessPathSearcher {
             numSettledEdges = 0;
             maxNumSettledEdges = 0;
         }
-
     }
 }
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 c858b76c7..6de0daaf0 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java
@@ -17,23 +17,24 @@
  */
 package com.graphhopper.routing.ch;
 
-import com.graphhopper.storage.NodeAccess;
+import com.carrotsearch.hppc.IntContainer;
 import com.graphhopper.util.PMap;
 import com.graphhopper.util.StopWatch;
 
-import java.util.Collection;
-import java.util.HashMap;
 import java.util.Locale;
-import java.util.Map;
 
-import static com.graphhopper.routing.ch.CHParameters.*;
+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.util.Helper.nf;
 
-class NodeBasedNodeContractor extends AbstractNodeContractor {
-    private final Map<Shortcut, Shortcut> shortcuts = new HashMap<>();
+class NodeBasedNodeContractor implements NodeContractor {
+    private final CHPreparationGraph prepareGraph;
     private final Params params = new Params();
-    private PrepareCHEdgeExplorer allEdgeExplorer;
-    private NodeBasedWitnessPathSearcher prepareAlgo;
+    private ShortcutHandler shortcutHandler;
+    private PrepareGraphEdgeExplorer inEdgeExplorer;
+    private PrepareGraphEdgeExplorer outEdgeExplorer;
+    private PrepareGraphEdgeExplorer existingShortcutExplorer;
+    private NodeBasedWitnessPathSearcher witnessPathSearcher;
     private int addedShortcutsCount;
     private long dijkstraCount;
     private final StopWatch dijkstraSW = new StopWatch();
@@ -44,22 +45,23 @@ class NodeBasedNodeContractor extends AbstractNodeContractor {
     private int originalEdgesCount;
     private int shortcutsCount;
 
-    NodeBasedNodeContractor(PrepareCHGraph prepareGraph, PMap pMap) {
-        super(prepareGraph);
+    NodeBasedNodeContractor(CHPreparationGraph prepareGraph, ShortcutHandler shortcutHandler, PMap pMap) {
+        this.prepareGraph = prepareGraph;
         extractParams(pMap);
+        this.shortcutHandler = shortcutHandler;
     }
 
     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.contractedNeighborsWeight = pMap.getFloat(CONTRACTED_NEIGHBORS_WEIGHT, params.contractedNeighborsWeight);
     }
 
     @Override
     public void initFromGraph() {
-        super.initFromGraph();
-        allEdgeExplorer = prepareGraph.createAllEdgeExplorer();
-        prepareAlgo = new NodeBasedWitnessPathSearcher(prepareGraph, maxLevel);
+        inEdgeExplorer = prepareGraph.createInEdgeExplorer();
+        outEdgeExplorer = prepareGraph.createOutEdgeExplorer();
+        existingShortcutExplorer = prepareGraph.createOutEdgeExplorer();
+        witnessPathSearcher = new NodeBasedWitnessPathSearcher(prepareGraph);
     }
 
     @Override
@@ -69,25 +71,26 @@ class NodeBasedNodeContractor extends AbstractNodeContractor {
         // 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.getEdges() / prepareGraph.getNodes();
+        meanDegree = prepareGraph.getOriginalEdges() / prepareGraph.getNodes();
     }
 
     @Override
     public void close() {
-        super.close();
-        prepareAlgo.close();
+        prepareGraph.close();
+        shortcutHandler = null;
+        inEdgeExplorer = null;
+        outEdgeExplorer = null;
+        existingShortcutExplorer = null;
+        witnessPathSearcher.close();
     }
 
     /**
-     * Warning: the calculated priority must NOT depend on priority(v) and therefore handleShortcuts should also not
+     * Warning: the calculated priority must NOT depend on priority(v) and therefore findAndHandleShortcuts should also not
      * depend on the priority(v). Otherwise updating the priority before contracting in contractNodes() could lead to
      * a slowish or even endless loop.
      */
     @Override
     public float calculatePriority(int node) {
-        if (prepareGraph.getLevel(node) != maxLevel)
-            throw new IllegalArgumentException("Priority should only be calculated for not yet contracted nodes");
-
         // # huge influence: the bigger the less shortcuts gets created and the faster is the preparation
         //
         // every adjNode has an 'original edge' number associated. initially it is r=1
@@ -96,28 +99,7 @@ class NodeBasedNodeContractor extends AbstractNodeContractor {
         // originalEdgesCount = σ(v) := sum_{ (u,w) ∈ shortcuts(v) } of r(u, w)
         shortcutsCount = 0;
         originalEdgesCount = 0;
-        handleShortcuts(node, this::countShortcut);
-
-        // # lowest influence on preparation speed or shortcut creation count
-        // (but according to paper should speed up queries)
-        //
-        // number of already contracted neighbors of v
-        int contractedNeighbors = 0;
-        int degree = 0;
-        PrepareCHEdgeIterator iter = allEdgeExplorer.setBaseNode(node);
-        while (iter.next()) {
-            // only increase the degree for edges going to equal level nodes (the current node is at maxLevel)
-            // todo: for historic reasons increase degree also for all shortcuts, even though its wrong, see #1810
-            if (iter.isShortcut() || prepareGraph.getLevel(iter.getAdjNode()) == maxLevel) {
-                degree++;
-            }
-            // todo: just because there is a shortcut it does not mean the neighbor is contracted AND
-            //       just because an edge is not a shortcut does not mean the neighbor is not contracted
-            //       see #1810
-            if (iter.isShortcut()) {
-                contractedNeighbors++;
-            }
-        }
+        findAndHandleShortcuts(node, this::countShortcuts);
 
         // from shortcuts we can compute the edgeDifference
         // # low influence: with it the shortcut creation is slightly faster
@@ -125,154 +107,149 @@ class NodeBasedNodeContractor extends AbstractNodeContractor {
         // |shortcuts(v)| − |{(u, v) | v uncontracted}| − |{(v, w) | v uncontracted}|
         // meanDegree is used instead of outDegree+inDegree as if one adjNode is in both directions
         // only one bucket memory is used. Additionally one shortcut could also stand for two directions.
-        int edgeDifference = shortcutsCount - degree;
+        int edgeDifference = shortcutsCount - prepareGraph.getDegree(node);
 
         // according to the paper do a simple linear combination of the properties to get the priority.
         return params.edgeDifferenceWeight * edgeDifference +
-                params.originalEdgesCountWeight * originalEdgesCount +
-                params.contractedNeighborsWeight * contractedNeighbors;
+                params.originalEdgesCountWeight * originalEdgesCount;
+        // todo: maybe use contracted-neighbors heuristic (contract nodes with lots of contracted neighbors later) as in GH 1.0 again?
+        //       maybe use hierarchy-depths heuristic as in edge-based?
     }
 
     @Override
-    public void contractNode(int node) {
-        shortcuts.clear();
-        long degree = handleShortcuts(node, this::addOrUpdateShortcut);
-        addedShortcutsCount += writeShortcuts(shortcuts.keySet());
+    public IntContainer contractNode(int node) {
+        long degree = findAndHandleShortcuts(node, this::addOrUpdateShortcut);
+        insertShortcuts(node);
         // put weight factor on meanDegree instead of taking the average => meanDegree is more stable
         meanDegree = (meanDegree * 2 + degree) / 3;
+        return prepareGraph.disconnect(node);
+    }
+
+    /**
+     * Calls the shortcut handler for all edges and shortcuts adjacent to the given node. After this method is called
+     * these edges and shortcuts will be removed from the prepare graph, so this method offers the last chance to deal
+     * with them.
+     */
+    private void insertShortcuts(int node) {
+        shortcutHandler.startContractingNode();
+        {
+            PrepareGraphEdgeIterator iter = outEdgeExplorer.setBaseNode(node);
+            while (iter.next()) {
+                if (!iter.isShortcut())
+                    continue;
+                shortcutHandler.addOutShortcut(iter.getPrepareEdge(), node, iter.getAdjNode(), iter.getSkipped1(), iter.getSkipped2(), iter.getWeight());
+            }
+        }
+        {
+            PrepareGraphEdgeIterator iter = inEdgeExplorer.setBaseNode(node);
+            while (iter.next()) {
+                if (!iter.isShortcut())
+                    continue;
+                shortcutHandler.addInShortcut(iter.getPrepareEdge(), node, iter.getAdjNode(), iter.getSkipped2(), iter.getSkipped1(), iter.getWeight());
+            }
+        }
+        addedShortcutsCount += shortcutHandler.finishContractingNode();
+    }
+
+    @Override
+    public void finishContraction() {
+        shortcutHandler.finishContraction();
     }
 
     @Override
     public String getStatisticsString() {
         return String.format(Locale.ROOT, "meanDegree: %.2f, dijkstras: %10s, mem: %10s",
-                meanDegree, nf(dijkstraCount), prepareAlgo.getMemoryUsageAsString());
+                meanDegree, nf(dijkstraCount), witnessPathSearcher.getMemoryUsageAsString());
     }
 
     /**
      * Searches for shortcuts and calls the given handler on each shortcut that is found. The graph is not directly
      * changed by this method.
-     * Returns the 'degree' of the handler's 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
+     * 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 handleShortcuts(int node, ShortcutHandler handler) {
+    private long findAndHandleShortcuts(int node, PrepareShortcutHandler handler) {
         int maxVisitedNodes = getMaxVisitedNodesEstimate();
         long degree = 0;
-        PrepareCHEdgeIterator incomingEdges = inEdgeExplorer.setBaseNode(node);
+        PrepareGraphEdgeIterator incomingEdges = inEdgeExplorer.setBaseNode(node);
         // collect outgoing nodes (goal-nodes) only once
         while (incomingEdges.next()) {
             int fromNode = incomingEdges.getAdjNode();
-            // accept only not-contracted nodes, do not consider loops at the node that is being contracted
-            if (fromNode == node || isContracted(fromNode))
+            // do not consider loops at the node that is being contracted
+            if (fromNode == node)
                 continue;
 
-            final double incomingEdgeWeight = incomingEdges.getWeight(true);
+            final double incomingEdgeWeight = incomingEdges.getWeight();
             // this check is important to prevent calling calcMillis on inaccessible edges and also allows early exit
             if (Double.isInfinite(incomingEdgeWeight)) {
                 continue;
             }
-            int incomingEdge = incomingEdges.getEdge();
-            int inOrigEdgeCount = getOrigEdgeCount(incomingEdge);
             // collect outgoing nodes (goal-nodes) only once
-            PrepareCHEdgeIterator outgoingEdges = outEdgeExplorer.setBaseNode(node);
+            PrepareGraphEdgeIterator outgoingEdges = outEdgeExplorer.setBaseNode(node);
             // force fresh maps etc as this cannot be determined by from node alone (e.g. same from node but different avoidNode)
-            prepareAlgo.clear();
+            witnessPathSearcher.clear();
             degree++;
             while (outgoingEdges.next()) {
                 int toNode = outgoingEdges.getAdjNode();
-                // add only not-contracted nodes, do not consider loops at the node that is being contracted
-                if (toNode == node || isContracted(toNode) || fromNode == toNode)
+                // do not consider loops at the node that is being contracted
+                if (toNode == node || fromNode == toNode)
                     continue;
 
                 // Limit weight as ferries or forbidden edges can increase local search too much.
                 // If we decrease the correct weight we only explore less and introduce more shortcuts.
                 // I.e. no change to accuracy is made.
-                double existingDirectWeight = incomingEdgeWeight + outgoingEdges.getWeight(false);
-                if (Double.isNaN(existingDirectWeight))
-                    throw new IllegalStateException("Weighting should never return NaN values"
-                            + ", in:" + getCoords(incomingEdges, prepareGraph.getNodeAccess()) + ", out:" + getCoords(outgoingEdges, prepareGraph.getNodeAccess()));
-
+                double existingDirectWeight = incomingEdgeWeight + outgoingEdges.getWeight();
                 if (Double.isInfinite(existingDirectWeight))
                     continue;
 
-                prepareAlgo.setWeightLimit(existingDirectWeight);
-                prepareAlgo.setMaxVisitedNodes(maxVisitedNodes);
-                prepareAlgo.ignoreNode(node);
+                witnessPathSearcher.setWeightLimit(existingDirectWeight);
+                witnessPathSearcher.setMaxVisitedNodes(maxVisitedNodes);
+                witnessPathSearcher.ignoreNode(node);
 
                 dijkstraSW.start();
                 dijkstraCount++;
-                int endNode = prepareAlgo.findEndNode(fromNode, toNode);
+                int endNode = witnessPathSearcher.findEndNode(fromNode, toNode);
                 dijkstraSW.stop();
 
                 // compare end node as the limit could force dijkstra to finish earlier
-                if (endNode == toNode && prepareAlgo.getWeight(endNode) <= existingDirectWeight)
+                if (endNode == toNode && witnessPathSearcher.getWeight(endNode) <= existingDirectWeight)
                     // FOUND witness path, so do not add shortcut
                     continue;
 
                 handler.handleShortcut(fromNode, toNode, existingDirectWeight,
-                        outgoingEdges.getEdge(), getOrigEdgeCount(outgoingEdges.getEdge()),
-                        incomingEdge, inOrigEdgeCount);
+                        outgoingEdges.getPrepareEdge(), outgoingEdges.getOrigEdgeCount(),
+                        incomingEdges.getPrepareEdge(), incomingEdges.getOrigEdgeCount());
             }
         }
         return degree;
     }
 
-    /**
-     * Actually writes the given shortcuts to the graph.
-     *
-     * @return the actual number of shortcuts that were added to the graph
-     */
-    private int writeShortcuts(Collection<Shortcut> shortcuts) {
-        int tmpNewShortcuts = 0;
-        NEXT_SC:
-        for (Shortcut sc : shortcuts) {
-            boolean updatedInGraph = false;
-            // check if we need to update some existing shortcut in the graph
-            PrepareCHEdgeIterator iter = outEdgeExplorer.setBaseNode(sc.from);
-            while (iter.next()) {
-                if (iter.isShortcut() && iter.getAdjNode() == sc.to) {
-                    int status = iter.getMergeStatus(sc.flags);
-                    if (status == 0)
-                        continue;
-
-                    if (sc.weight >= iter.getWeight(false)) {
-                        // special case if a bidirectional shortcut has worse weight and still has to be added as otherwise the opposite direction would be missing
-                        // see testShortcutMergeBug
-                        if (status == 2)
-                            break;
-
-                        continue NEXT_SC;
-                    }
-
-                    if (iter.getEdge() == sc.skippedEdge1 || iter.getEdge() == sc.skippedEdge2) {
-                        throw new IllegalStateException("Shortcut cannot update itself! " + iter.getEdge()
-                                + ", skipEdge1:" + sc.skippedEdge1 + ", skipEdge2:" + sc.skippedEdge2
-                                + ", edge " + iter + ":" + getCoords(iter, prepareGraph.getNodeAccess())
-                                + ", sc:" + sc);
-                    }
-
-                    iter.setFlagsAndWeight(sc.flags, sc.weight);
-                    iter.setSkippedEdges(sc.skippedEdge1, sc.skippedEdge2);
-                    setOrigEdgeCount(iter.getEdge(), sc.originalEdges);
-                    updatedInGraph = true;
-                    break;
-                }
-            }
-
-            if (!updatedInGraph) {
-                int scId = prepareGraph.shortcut(sc.from, sc.to, sc.flags, sc.weight, sc.skippedEdge1, sc.skippedEdge2);
-                setOrigEdgeCount(scId, sc.originalEdges);
+    private void countShortcuts(int fromNode, int toNode, double existingDirectWeight,
+                                int outgoingEdge, int outOrigEdgeCount,
+                                int incomingEdge, int inOrigEdgeCount) {
+        shortcutsCount++;
+        originalEdgesCount += inOrigEdgeCount + outOrigEdgeCount;
+    }
 
-                tmpNewShortcuts++;
+    private void addOrUpdateShortcut(int fromNode, int toNode, double weight,
+                                     int outgoingEdge, int outOrigEdgeCount,
+                                     int incomingEdge, int inOrigEdgeCount) {
+        boolean exists = false;
+        PrepareGraphEdgeIterator iter = existingShortcutExplorer.setBaseNode(fromNode);
+        while (iter.next()) {
+            // do not update base edges!
+            if (iter.getAdjNode() != toNode || !iter.isShortcut()) {
+                continue;
+            }
+            exists = true;
+            if (weight < iter.getWeight()) {
+                iter.setWeight(weight);
+                iter.setSkippedEdges(incomingEdge, outgoingEdge);
+                iter.setOrigEdgeCount(inOrigEdgeCount + outOrigEdgeCount);
             }
         }
-        return tmpNewShortcuts;
-    }
-
-    private String getCoords(PrepareCHEdgeIterator edge, NodeAccess na) {
-        int base = edge.getBaseNode();
-        int adj = edge.getAdjNode();
-        return base + "->" + adj + " (" + edge.getEdge() + "); "
-                + na.getLat(base) + "," + na.getLon(base) + " -> " + na.getLat(adj) + "," + na.getLon(adj);
+        if (!exists)
+            prepareGraph.addShortcut(fromNode, toNode, -1, -1, incomingEdge, outgoingEdge, weight, inOrigEdgeCount + outOrigEdgeCount);
     }
 
     @Override
@@ -296,105 +273,49 @@ class NodeBasedNodeContractor extends AbstractNodeContractor {
         return (int) meanDegree * 100;
     }
 
-    private static class Shortcut {
-        int from;
-        int to;
-        int skippedEdge1;
-        int skippedEdge2;
-        double weight;
-        int originalEdges;
-        int flags = PrepareEncoder.getScFwdDir();
-
-        public Shortcut(int from, int to, double weight) {
-            this.from = from;
-            this.to = to;
-            this.weight = weight;
-        }
-
-        @Override
-        public int hashCode() {
-            int hash = 5;
-            hash = 23 * hash + from;
-            hash = 23 * hash + to;
-            return 23 * hash
-                    + (int) (Double.doubleToLongBits(this.weight) ^ (Double.doubleToLongBits(this.weight) >>> 32));
-        }
-
-        @Override
-        public boolean equals(Object obj) {
-            if (obj == null || getClass() != obj.getClass())
-                return false;
-
-            final Shortcut other = (Shortcut) obj;
-            return this.from == other.from && this.to == other.to &&
-                    Double.doubleToLongBits(this.weight) == Double.doubleToLongBits(other.weight);
-
-        }
-
-        @Override
-        public String toString() {
-            String str;
-            if (flags == PrepareEncoder.getScDirMask())
-                str = from + "<->";
-            else
-                str = from + "->";
-
-            return str + to + ", weight:" + weight + " (" + skippedEdge1 + "," + skippedEdge2 + ")";
-        }
-    }
-
     @FunctionalInterface
-    private interface ShortcutHandler {
+    private interface PrepareShortcutHandler {
         void handleShortcut(int fromNode, int toNode, double existingDirectWeight,
                             int outgoingEdge, int outOrigEdgeCount,
                             int incomingEdge, int inOrigEdgeCount);
     }
 
-    private void countShortcut(int fromNode, int toNode, double existingDirectWeight,
-                               int outgoingEdge, int outOrigEdgeCount,
-                               int incomingEdge, int inOrigEdgeCount) {
-        shortcutsCount++;
-        originalEdgesCount += inOrigEdgeCount + outOrigEdgeCount;
-    }
-
-    /**
-     * Adds a new shortcut to the temporary set of shortcuts or updates/merges it with an
-     * existing one.
-     */
-    private void addOrUpdateShortcut(int fromNode, int toNode, double existingDirectWeight,
-                                     int outgoingEdge, int outOrigEdgeCount,
-                                     int incomingEdge, int inOrigEdgeCount) {
-        // FOUND shortcut
-        // but be sure that it is the only shortcut in the collection
-        // and also in the graph for u->w. If existing AND identical weight => update setProperties.
-        // Hint: shortcuts are always one-way due to distinct level of every node but we don't
-        // know yet the levels so we need to determine the correct direction or if both directions
-        Shortcut sc = new Shortcut(fromNode, toNode, existingDirectWeight);
-        if (shortcuts.containsKey(sc))
-            return;
-
-        Shortcut tmpSc = new Shortcut(toNode, fromNode, existingDirectWeight);
-        Shortcut tmpRetSc = shortcuts.get(tmpSc);
-        // overwrite flags only if skipped edges are identical
-        if (tmpRetSc != null && tmpRetSc.skippedEdge2 == incomingEdge && tmpRetSc.skippedEdge1 == outgoingEdge) {
-            tmpRetSc.flags = PrepareEncoder.getScDirMask();
-            return;
-        }
-
-        Shortcut old = shortcuts.put(sc, sc);
-        if (old != null)
-            throw new IllegalStateException("Shortcut did not exist (" + sc + ") but was overwriting another one? " + old);
-
-        sc.skippedEdge1 = incomingEdge;
-        sc.skippedEdge2 = outgoingEdge;
-        sc.originalEdges = inOrigEdgeCount + outOrigEdgeCount;
-    }
-
     public static class Params {
         // default values were optimized for Unterfranken
         private float edgeDifferenceWeight = 10;
         private float originalEdgesCountWeight = 1;
-        private float contractedNeighborsWeight = 1;
     }
 
+    /**
+     * This handler is called on every shortcut that this contractor finds necessary to add for the contracted node.
+     */
+    public interface ShortcutHandler {
+        /**
+         * Use this hook for any kind of initialization to be done before a node is contracted
+         */
+        void startContractingNode();
+
+        /**
+         * This method is called for every shortcut outgoing from the contracted node and found by the contractor
+         */
+        void addOutShortcut(int prepareEdge, int node, int adjNode, int skipped1, int skipped2, double weight);
+
+        /**
+         * This method is called for every shortcut incoming to the contracted node and found by the contractor.
+         * Incoming shortcuts are added only *after* all outgoing ones were add.
+         */
+        void addInShortcut(int prepareEdge, int node, int adjNode, int skipped1, int skipped2, double weight);
+
+        /**
+         * Use this hook for any kind of post-processing after the node is contracted
+         *
+         * @return the actual number of shortcuts that were added to the graph for this node
+         */
+        int finishContractingNode();
+
+        /**
+         * This method is called at the very end of the graph contraction (after the last node was contracted)
+         */
+        void finishContraction();
+    }
 }
diff --git a/core/src/main/java/com/graphhopper/routing/ch/NodeBasedShortcutHandler.java b/core/src/main/java/com/graphhopper/routing/ch/NodeBasedShortcutHandler.java
new file mode 100644
index 000000000..fde50085d
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/ch/NodeBasedShortcutHandler.java
@@ -0,0 +1,151 @@
+/*
+ *  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.carrotsearch.hppc.IntArrayList;
+import com.graphhopper.routing.util.AllCHEdgesIterator;
+import com.graphhopper.storage.CHGraph;
+
+import java.util.ArrayList;
+import java.util.List;
+
+class NodeBasedShortcutHandler implements NodeBasedNodeContractor.ShortcutHandler {
+    private final CHGraph chGraph;
+    private final int origEdges;
+    // todo: maybe use a set to prevent duplicates instead?
+    private final List<Shortcut> shortcuts;
+    private final IntArrayList shortcutsByPrepareEdges;
+
+    NodeBasedShortcutHandler(CHGraph chGraph) {
+        this.chGraph = chGraph;
+        this.shortcuts = new ArrayList<>();
+        this.origEdges = chGraph.getOriginalEdges();
+        shortcutsByPrepareEdges = new IntArrayList();
+    }
+
+    @Override
+    public void startContractingNode() {
+        shortcuts.clear();
+    }
+
+    @Override
+    public void addOutShortcut(int prepareEdge, int node, int adjNode, int skipped1, int skipped2, double weight) {
+        shortcuts.add(new Shortcut(prepareEdge, -1, node, adjNode, skipped1, skipped2, PrepareEncoder.getScFwdDir(), weight));
+    }
+
+    @Override
+    public void addInShortcut(int prepareEdge, int node, int adjNode, int skipped1, int skipped2, double weight) {
+        // we check if this shortcut already exists (with the same weight) for the other direction and if so we can use
+        // it for both ways instead of adding another one
+        boolean bidir = false;
+        for (Shortcut sc : shortcuts) {
+            if (sc.to == adjNode && Double.doubleToLongBits(sc.weight) == Double.doubleToLongBits(weight)) {
+                if (getShortcutForPrepareEdge(sc.skippedEdge1) == getShortcutForPrepareEdge(skipped1) && getShortcutForPrepareEdge(sc.skippedEdge2) == getShortcutForPrepareEdge(skipped2)) {
+                    if (sc.flags == PrepareEncoder.getScFwdDir()) {
+                        sc.flags = PrepareEncoder.getScDirMask();
+                        sc.prepareEdgeBwd = prepareEdge;
+                        bidir = true;
+                        break;
+                    }
+                }
+            }
+        }
+        if (!bidir) {
+            shortcuts.add(new Shortcut(-1, prepareEdge, node, adjNode, skipped1, skipped2, PrepareEncoder.getScBwdDir(), weight));
+        }
+    }
+
+    @Override
+    public int finishContractingNode() {
+        int shortcutCount = 0;
+        for (Shortcut sc : shortcuts) {
+            int scId = chGraph.shortcut(sc.from, sc.to, sc.flags, sc.weight, sc.skippedEdge1, sc.skippedEdge2);
+            if (sc.flags == PrepareEncoder.getScFwdDir()) {
+                setShortcutForPrepareEdge(sc.prepareEdgeFwd, scId);
+            } else if (sc.flags == PrepareEncoder.getScBwdDir()) {
+                setShortcutForPrepareEdge(sc.prepareEdgeBwd, scId);
+            } else {
+                setShortcutForPrepareEdge(sc.prepareEdgeFwd, scId);
+                setShortcutForPrepareEdge(sc.prepareEdgeBwd, scId);
+            }
+            shortcutCount++;
+        }
+        return shortcutCount;
+    }
+
+    @Override
+    public void finishContraction() {
+        AllCHEdgesIterator iter = chGraph.getAllEdges();
+        while (iter.next()) {
+            // todo: performance, ideally this loop would start with the first *shortcut* not edge
+            if (!iter.isShortcut())
+                continue;
+            int skip1 = getShortcutForPrepareEdge(iter.getSkippedEdge1());
+            int skip2 = getShortcutForPrepareEdge(iter.getSkippedEdge2());
+            iter.setSkippedEdges(skip1, skip2);
+        }
+    }
+
+    private void setShortcutForPrepareEdge(int prepareEdge, int shortcut) {
+        int index = prepareEdge - origEdges;
+        if (index >= shortcutsByPrepareEdges.size())
+            shortcutsByPrepareEdges.resize(index + 1);
+        shortcutsByPrepareEdges.set(index, shortcut);
+    }
+
+    private int getShortcutForPrepareEdge(int prepareEdge) {
+        if (prepareEdge < origEdges)
+            return prepareEdge;
+        int index = prepareEdge - origEdges;
+        return shortcutsByPrepareEdges.get(index);
+    }
+
+    private static class Shortcut {
+        int prepareEdgeFwd;
+        int prepareEdgeBwd;
+        int from;
+        int to;
+        int skippedEdge1;
+        int skippedEdge2;
+        double weight;
+        int flags;
+
+        public Shortcut(int prepareEdgeFwd, int prepareEdgeBwd, int from, int to, int skippedEdge1, int skippedEdge2, int flags, double weight) {
+            this.prepareEdgeFwd = prepareEdgeFwd;
+            this.prepareEdgeBwd = prepareEdgeBwd;
+            this.from = from;
+            this.to = to;
+            this.skippedEdge1 = skippedEdge1;
+            this.skippedEdge2 = skippedEdge2;
+            this.flags = flags;
+            this.weight = weight;
+        }
+
+        @Override
+        public String toString() {
+            String str;
+            if (flags == PrepareEncoder.getScDirMask())
+                str = from + "<->";
+            else
+                str = from + "->";
+
+            return str + to + ", weight:" + weight + " (" + skippedEdge1 + "," + skippedEdge2 + ")";
+        }
+    }
+}
diff --git a/core/src/main/java/com/graphhopper/routing/ch/NodeBasedWitnessPathSearcher.java b/core/src/main/java/com/graphhopper/routing/ch/NodeBasedWitnessPathSearcher.java
index 9db7ed359..f652af640 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/NodeBasedWitnessPathSearcher.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/NodeBasedWitnessPathSearcher.java
@@ -20,7 +20,6 @@ package com.graphhopper.routing.ch;
 import com.carrotsearch.hppc.IntArrayList;
 import com.graphhopper.apache.commons.collections.IntFloatBinaryHeap;
 import com.graphhopper.routing.DijkstraOneToMany;
-import com.graphhopper.util.EdgeIterator;
 import com.graphhopper.util.Helper;
 
 import java.util.Arrays;
@@ -30,19 +29,15 @@ import java.util.Arrays;
  * i.e. its a Dijkstra search that allows re-using the shortest path tree for different searches with the same origin
  * node and uses large int/double arrays instead of hash maps to store the shortest path tree (higher memory consumption,
  * but faster query times -> better for CH preparation). Main reason we use this instead of {@link DijkstraOneToMany}
- * is that we can use this implementation with a {@link PrepareCHGraph}.
+ * is that we can use this implementation with a {@link CHPreparationGraph} and we are only interested in checking for
+ * witness paths (e.g. we do not need to find the actual path).
  */
 public class NodeBasedWitnessPathSearcher {
-    private static final int EMPTY_PARENT = -1;
     private static final int NOT_FOUND = -1;
-    private final PrepareCHGraph graph;
-    private final PrepareCHEdgeExplorer outEdgeExplorer;
+    private PrepareGraphEdgeExplorer outEdgeExplorer;
     private final IntArrayList changedNodes;
-    private final int maxLevel;
     private int maxVisitedNodes = Integer.MAX_VALUE;
     protected double[] weights;
-    private int[] parents;
-    private int[] edgeIds;
     private IntFloatBinaryHeap heap;
     private int ignoreNode = -1;
     private int visitedNodes;
@@ -50,21 +45,9 @@ public class NodeBasedWitnessPathSearcher {
     private int currNode, to;
     private double weightLimit = Double.MAX_VALUE;
 
-    public NodeBasedWitnessPathSearcher(PrepareCHGraph graph) {
-        this(graph, graph.getNodes());
-    }
-
-    public NodeBasedWitnessPathSearcher(PrepareCHGraph graph, int maxLevel) {
-        this.graph = graph;
-        this.maxLevel = maxLevel;
+    public NodeBasedWitnessPathSearcher(CHPreparationGraph graph) {
         outEdgeExplorer = graph.createOutEdgeExplorer();
 
-        parents = new int[graph.getNodes()];
-        Arrays.fill(parents, EMPTY_PARENT);
-
-        edgeIds = new int[graph.getNodes()];
-        Arrays.fill(edgeIds, EdgeIterator.NO_EDGE);
-
         weights = new double[graph.getNodes()];
         Arrays.fill(weights, Double.MAX_VALUE);
 
@@ -95,8 +78,6 @@ public class NodeBasedWitnessPathSearcher {
             for (int i = 0; i < vn; i++) {
                 int n = changedNodes.get(i);
                 weights[n] = Double.MAX_VALUE;
-                parents[n] = EMPTY_PARENT;
-                edgeIds[n] = EdgeIterator.NO_EDGE;
             }
 
             heap.clear();
@@ -109,8 +90,7 @@ public class NodeBasedWitnessPathSearcher {
             changedNodes.add(currNode);
         } else {
             // Cached! Re-use existing data structures
-            int parentNode = parents[to];
-            if (parentNode != EMPTY_PARENT && weights[to] <= weights[currNode])
+            if (weights[to] != Double.MAX_VALUE && weights[to] <= weights[currNode])
                 return to;
 
             if (heap.isEmpty() || isMaxVisitedNodesExceeded())
@@ -131,30 +111,25 @@ public class NodeBasedWitnessPathSearcher {
 
         while (true) {
             visitedNodes++;
-            PrepareCHEdgeIterator iter = outEdgeExplorer.setBaseNode(currNode);
+            PrepareGraphEdgeIterator iter = outEdgeExplorer.setBaseNode(currNode);
             while (iter.next()) {
                 int adjNode = iter.getAdjNode();
-                int prevEdgeId = edgeIds[adjNode];
-                if (!accept(iter, prevEdgeId))
+                if (!accept(iter))
                     continue;
 
-                double tmpWeight = iter.getWeight(false) + weights[currNode];
+                double tmpWeight = iter.getWeight() + weights[currNode];
                 if (Double.isInfinite(tmpWeight))
                     continue;
 
                 double w = weights[adjNode];
                 if (w == Double.MAX_VALUE) {
-                    parents[adjNode] = currNode;
                     weights[adjNode] = tmpWeight;
                     heap.insert(tmpWeight, adjNode);
                     changedNodes.add(adjNode);
-                    edgeIds[adjNode] = iter.getEdge();
                 } else if (w > tmpWeight) {
-                    parents[adjNode] = currNode;
                     weights[adjNode] = tmpWeight;
                     heap.update(tmpWeight, adjNode);
                     changedNodes.add(adjNode);
-                    edgeIds[adjNode] = iter.getEdge();
                 }
             }
 
@@ -183,9 +158,9 @@ public class NodeBasedWitnessPathSearcher {
     }
 
     public void close() {
+        outEdgeExplorer = null;
+        changedNodes.release();
         weights = null;
-        parents = null;
-        edgeIds = null;
         heap = null;
     }
 
@@ -212,14 +187,7 @@ public class NodeBasedWitnessPathSearcher {
         ignoreNode = node;
     }
 
-    private boolean accept(PrepareCHEdgeIterator iter, int prevOrNextEdgeId) {
-        if (iter.getEdge() == prevOrNextEdgeId)
-            return false;
-
-        if (graph.getLevel(iter.getAdjNode()) != maxLevel) {
-            return false;
-        }
-
+    private boolean accept(PrepareGraphEdgeIterator iter) {
         return ignoreNode < 0 || iter.getAdjNode() != ignoreNode;
     }
 
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 5f329b0c8..5def209c9 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/NodeContractor.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/NodeContractor.java
@@ -18,6 +18,8 @@
 
 package com.graphhopper.routing.ch;
 
+import com.carrotsearch.hppc.IntContainer;
+
 public interface NodeContractor {
     void initFromGraph();
 
@@ -30,8 +32,12 @@ public interface NodeContractor {
 
     /**
      * Adds the required shortcuts for the given node.
+     *
+     * @return the set of nodes adjacent to this node (before contraction)
      */
-    void contractNode(int node);
+    IntContainer contractNode(int node);
+
+    void finishContraction();
 
     long getAddedShortcutsCount();
 
diff --git a/core/src/main/java/com/graphhopper/routing/ch/PrepareCHEdgeIteratorImpl.java b/core/src/main/java/com/graphhopper/routing/ch/PrepareCHEdgeIteratorImpl.java
deleted file mode 100644
index 6f2026164..000000000
--- a/core/src/main/java/com/graphhopper/routing/ch/PrepareCHEdgeIteratorImpl.java
+++ /dev/null
@@ -1,190 +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.ev.BooleanEncodedValue;
-import com.graphhopper.routing.weighting.Weighting;
-import com.graphhopper.util.CHEdgeIterator;
-import com.graphhopper.util.EdgeExplorer;
-import com.graphhopper.util.EdgeIterator;
-
-public class PrepareCHEdgeIteratorImpl implements PrepareCHEdgeExplorer, PrepareCHEdgeIterator {
-    private final EdgeExplorer edgeExplorer;
-    private final Weighting weighting;
-    private final ShortcutFilter shortcutFilter;
-    private final BooleanEncodedValue accessEnc;
-    private EdgeIterator chIterator;
-
-    public static PrepareCHEdgeExplorer inEdges(EdgeExplorer edgeExplorer, Weighting weighting) {
-        return new PrepareCHEdgeIteratorImpl(edgeExplorer, weighting, ShortcutFilter.inEdges());
-    }
-
-    public static PrepareCHEdgeExplorer outEdges(EdgeExplorer edgeExplorer, Weighting weighting) {
-        return new PrepareCHEdgeIteratorImpl(edgeExplorer, weighting, ShortcutFilter.outEdges());
-    }
-
-    public static PrepareCHEdgeExplorer allEdges(EdgeExplorer edgeExplorer, Weighting weighting) {
-        return new PrepareCHEdgeIteratorImpl(edgeExplorer, weighting, ShortcutFilter.allEdges());
-    }
-
-    public PrepareCHEdgeIteratorImpl(EdgeExplorer edgeExplorer, Weighting weighting, ShortcutFilter shortcutFilter) {
-        this.edgeExplorer = edgeExplorer;
-        this.weighting = weighting;
-        this.shortcutFilter = shortcutFilter;
-        accessEnc = weighting.getFlagEncoder().getAccessEnc();
-    }
-
-    @Override
-    public PrepareCHEdgeIteratorImpl setBaseNode(int node) {
-        chIterator = edgeExplorer.setBaseNode(node);
-        return this;
-    }
-
-    @Override
-    public boolean next() {
-        assertBaseNodeSet();
-        while (true) {
-            boolean hasNext = chIterator.next();
-            if (!hasNext) {
-                return false;
-            } else if (hasAccess()) {
-                return true;
-            }
-        }
-    }
-
-    private boolean hasAccess() {
-        if (isShortcut()) {
-            return shortcutFilter.accept((CHEdgeIterator) chIterator);
-        } else {
-            // c.f. comment in DefaultEdgeFilter
-            if (chIterator.getBaseNode() == chIterator.getAdjNode()) {
-                return finiteWeight(false) || finiteWeight(true);
-            }
-            return shortcutFilter.fwd && finiteWeight(false) || shortcutFilter.bwd && finiteWeight(true);
-        }
-    }
-
-    private boolean finiteWeight(boolean reverse) {
-        return !Double.isInfinite(getOrigEdgeWeight(reverse, false));
-    }
-
-    /**
-     * @param needWeight if true this method will return as soon as its clear that the weight is finite (no need to
-     *                   do the full computation)
-     */
-    private double getOrigEdgeWeight(boolean reverse, boolean needWeight) {
-        // todo: for #1835 move the access check into the weighting
-        final boolean access = reverse
-                ? chIterator.getReverse(accessEnc)
-                : chIterator.get(accessEnc);
-        if (!access) {
-            return Double.POSITIVE_INFINITY;
-        }
-        if (!needWeight) {
-            return 0;
-        }
-        return weighting.calcEdgeWeight(chIterator, reverse);
-    }
-
-    @Override
-    public int getEdge() {
-        assertBaseNodeSet();
-        return chIterator.getEdge();
-    }
-
-    @Override
-    public int getBaseNode() {
-        assertBaseNodeSet();
-        return chIterator.getBaseNode();
-    }
-
-    @Override
-    public int getAdjNode() {
-        assertBaseNodeSet();
-        return chIterator.getAdjNode();
-    }
-
-    @Override
-    public int getOrigEdgeFirst() {
-        assertBaseNodeSet();
-        return chIterator.getOrigEdgeFirst();
-    }
-
-    @Override
-    public int getOrigEdgeLast() {
-        assertBaseNodeSet();
-        return chIterator.getOrigEdgeLast();
-    }
-
-    @Override
-    public boolean isShortcut() {
-        assertBaseNodeSet();
-        final EdgeIterator iter = chIterator;
-        return iter instanceof CHEdgeIterator && ((CHEdgeIterator) iter).isShortcut();
-    }
-
-    @Override
-    public double getWeight(boolean reverse) {
-        if (isShortcut()) {
-            return ((CHEdgeIterator) chIterator).getWeight();
-        } else {
-            assertBaseNodeSet();
-            return getOrigEdgeWeight(reverse, true);
-        }
-    }
-
-    @Override
-    public void setWeight(double weight) {
-        assertBaseNodeSet();
-        ((CHEdgeIterator) chIterator).setWeight(weight);
-    }
-
-    @Override
-    public String toString() {
-        if (chIterator == null) {
-            return "not initialized";
-        } else {
-            return getBaseNode() + "->" + getAdjNode() + " (" + getEdge() + ")";
-        }
-    }
-
-    @Override
-    public int getMergeStatus(int flags) {
-        assertBaseNodeSet();
-        return ((CHEdgeIterator) chIterator).getMergeStatus(flags);
-    }
-
-    @Override
-    public void setFlagsAndWeight(int flags, double weight) {
-        assertBaseNodeSet();
-        ((CHEdgeIterator) chIterator).setFlagsAndWeight(flags, weight);
-    }
-
-    @Override
-    public void setSkippedEdges(int skippedEdge1, int skippedEdge2) {
-        assertBaseNodeSet();
-        ((CHEdgeIterator) chIterator).setSkippedEdges(skippedEdge1, skippedEdge2);
-    }
-
-    private void assertBaseNodeSet() {
-        assert chIterator != null : "You need to call setBaseNode() before using the iterator";
-    }
-
-}
diff --git a/core/src/main/java/com/graphhopper/routing/ch/PrepareCHEntry.java b/core/src/main/java/com/graphhopper/routing/ch/PrepareCHEntry.java
new file mode 100644
index 000000000..7d8187320
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/ch/PrepareCHEntry.java
@@ -0,0 +1,51 @@
+/*
+ *  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;
+
+public class PrepareCHEntry {
+    /**
+     * The edge key of the incoming original edge at this shortest path tree entry. For original edges this is the same
+     * as the edge key, but for shortcuts this is the edge key of the last original edge of the shortcut.
+     */
+    public int incEdgeKey;
+    /**
+     * The ID of the edge associated with this entry in the prepare graph (this is not the same number that will later
+     * be the ID of the edge/shortcut in the CHGraph.
+     */
+    public int prepareEdge;
+    public int adjNode;
+    public double weight;
+    public PrepareCHEntry parent;
+
+    public PrepareCHEntry(int prepareEdge, int incEdgeKey, int adjNode, double weight) {
+        this.prepareEdge = prepareEdge;
+        this.adjNode = adjNode;
+        this.weight = weight;
+        this.incEdgeKey = incEdgeKey;
+    }
+
+    public PrepareCHEntry getParent() {
+        return parent;
+    }
+
+    @Override
+    public String toString() {
+        return (adjNode + " (" + prepareEdge + ") weight: " + weight) + ", incEdgeKey: " + incEdgeKey;
+    }
+
+}
diff --git a/core/src/main/java/com/graphhopper/routing/ch/PrepareCHGraph.java b/core/src/main/java/com/graphhopper/routing/ch/PrepareCHGraph.java
deleted file mode 100644
index aea630495..000000000
--- a/core/src/main/java/com/graphhopper/routing/ch/PrepareCHGraph.java
+++ /dev/null
@@ -1,144 +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.AllCHEdgesIterator;
-import com.graphhopper.routing.weighting.Weighting;
-import com.graphhopper.storage.CHGraph;
-import com.graphhopper.storage.NodeAccess;
-import com.graphhopper.util.EdgeIterator;
-
-/**
- * Helper adapter api over {@link CHGraph} used for CH preparation.
- */
-public class PrepareCHGraph {
-    private final CHGraph chGraph;
-    private final Weighting weighting;
-
-    public static PrepareCHGraph nodeBased(CHGraph chGraph, Weighting weighting) {
-        if (chGraph.getCHConfig().isEdgeBased()) {
-            throw new IllegalArgumentException("Expected node-based CHGraph, but was edge-based");
-        }
-        return new PrepareCHGraph(chGraph, weighting);
-    }
-
-    public static PrepareCHGraph edgeBased(CHGraph chGraph, Weighting weighting) {
-        if (!chGraph.getCHConfig().isEdgeBased()) {
-            throw new IllegalArgumentException("Expected edge-based CHGraph, but was node-based");
-        }
-        return new PrepareCHGraph(chGraph, weighting);
-    }
-
-    private PrepareCHGraph(CHGraph chGraph, Weighting weighting) {
-        this.chGraph = chGraph;
-        this.weighting = weighting;
-    }
-
-    public PrepareCHEdgeExplorer createInEdgeExplorer() {
-        return PrepareCHEdgeIteratorImpl.inEdges(chGraph.createEdgeExplorer(), weighting);
-    }
-
-    public PrepareCHEdgeExplorer createOutEdgeExplorer() {
-        return PrepareCHEdgeIteratorImpl.outEdges(chGraph.createEdgeExplorer(), weighting);
-    }
-
-    public PrepareCHEdgeExplorer createAllEdgeExplorer() {
-        return PrepareCHEdgeIteratorImpl.allEdges(chGraph.createEdgeExplorer(), weighting);
-    }
-
-    public PrepareCHEdgeExplorer createOriginalInEdgeExplorer() {
-        return PrepareCHEdgeIteratorImpl.inEdges(chGraph.createOriginalEdgeExplorer(), weighting);
-    }
-
-    public PrepareCHEdgeExplorer createOriginalOutEdgeExplorer() {
-        return PrepareCHEdgeIteratorImpl.outEdges(chGraph.createOriginalEdgeExplorer(), weighting);
-    }
-
-    public int getNodes() {
-        return chGraph.getNodes();
-    }
-
-    public int getEdges() {
-        return chGraph.getEdges();
-    }
-
-    public int getOriginalEdges() {
-        return chGraph.getOriginalEdges();
-    }
-
-    public int getLevel(int node) {
-        return chGraph.getLevel(node);
-    }
-
-    public void setLevel(int node, int level) {
-        chGraph.setLevel(node, level);
-    }
-
-    public int shortcut(int a, int b, int accessFlags, double weight, int skippedEdge1, int skippedEdge2) {
-        return chGraph.shortcut(a, b, accessFlags, weight, skippedEdge1, skippedEdge2);
-    }
-
-    public int shortcutEdgeBased(int a, int b, int accessFlags, double weight, int skippedEdge1, int skippedEdge2, int origFirst, int origLast) {
-        return chGraph.shortcutEdgeBased(a, b, accessFlags, weight, skippedEdge1, skippedEdge2, origFirst, origLast);
-    }
-
-    public int getOtherNode(int edge, int adjNode) {
-        return chGraph.getOtherNode(edge, adjNode);
-    }
-
-    public NodeAccess getNodeAccess() {
-        return chGraph.getBaseGraph().getNodeAccess();
-    }
-
-    double getTurnWeight(int inEdge, int viaNode, int outEdge) {
-        return weighting.calcTurnWeight(inEdge, viaNode, outEdge);
-    }
-
-    public AllCHEdgesIterator getAllEdges() {
-        return chGraph.getAllEdges();
-    }
-
-    boolean isReadyForContraction() {
-        return chGraph.isReadyForContraction();
-    }
-
-    /**
-     * Disconnects the edges (higher to lower node) via the specified edgeState pointing from lower to
-     * higher node.
-     * <p>
-     *
-     * @param edgeState the edge from lower to higher
-     */
-    public void disconnect(PrepareCHEdgeExplorer explorer, PrepareCHEdgeIterator edgeState) {
-        // search edge with opposite direction but we need to know the previousEdge so we cannot simply do:
-        // EdgeIteratorState tmpIter = getEdgeIteratorState(edgeState.getEdge(), edgeState.getBaseNode());
-        PrepareCHEdgeIterator tmpIter = explorer.setBaseNode(edgeState.getAdjNode());
-        int prevEdge = 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()) {
-                chGraph.disconnectEdge(edgeState.getEdge(), edgeState.getAdjNode(), prevEdge);
-                break;
-            }
-
-            prevEdge = tmpIter.getEdge();
-        }
-    }
-}
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 60a991b9e..b1d78ffe8 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java
@@ -17,8 +17,8 @@
  */
 package com.graphhopper.routing.ch;
 
-import com.carrotsearch.hppc.IntHashSet;
-import com.carrotsearch.hppc.IntSet;
+import com.carrotsearch.hppc.IntContainer;
+import com.carrotsearch.hppc.cursors.IntCursor;
 import com.graphhopper.coll.MinHeapWithUpdate;
 import com.graphhopper.routing.util.AbstractAlgoPreparation;
 import com.graphhopper.routing.util.TraversalMode;
@@ -34,6 +34,7 @@ import java.util.Locale;
 import java.util.Random;
 
 import static com.graphhopper.routing.ch.CHParameters.*;
+import static com.graphhopper.util.Helper.getMemInfo;
 import static com.graphhopper.util.Helper.nf;
 
 /**
@@ -53,19 +54,17 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation {
     private final Logger logger = LoggerFactory.getLogger(getClass());
     private final CHConfig chConfig;
     private final CHGraph chGraph;
-    private final PrepareCHGraph prepareGraph;
     private final Random rand = new Random(123);
-    private final IntSet updatedNeighbors;
     private final StopWatch allSW = new StopWatch();
     private final StopWatch periodicUpdateSW = new StopWatch();
     private final StopWatch lazyUpdateSW = new StopWatch();
     private final StopWatch neighborUpdateSW = new StopWatch();
     private final StopWatch contractionSW = new StopWatch();
     private final Params params;
-    private final NodeContractor nodeContractor;
+    private final Graph graph;
+    private NodeContractor nodeContractor;
+    private final int nodes;
     private NodeOrderingProvider nodeOrderingProvider;
-    private PrepareCHEdgeExplorer allEdgeExplorer;
-    private PrepareCHEdgeExplorer disconnectExplorer;
     private int maxLevel;
     // nodes with highest priority come last
     private MinHeapWithUpdate sortedNodes;
@@ -77,22 +76,18 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation {
     }
 
     private PrepareContractionHierarchies(GraphHopperStorage ghStorage, CHConfig chConfig) {
+        graph = ghStorage;
         chGraph = ghStorage.getCHGraph(chConfig.getName());
         if (chGraph == null)
             throw new IllegalArgumentException("There is no CH graph '" + chConfig.getName() + "', existing: " + ghStorage.getCHGraphNames());
         this.chConfig = chConfig;
         params = Params.forTraversalMode(chConfig.getTraversalMode());
-        updatedNeighbors = new IntHashSet(50);
+        nodes = chGraph.getNodes();
         if (chConfig.getTraversalMode().isEdgeBased()) {
             TurnCostStorage turnCostStorage = chGraph.getBaseGraph().getTurnCostStorage();
             if (turnCostStorage == null) {
                 throw new IllegalArgumentException("For edge-based CH you need a turn cost storage");
             }
-            prepareGraph = PrepareCHGraph.edgeBased(chGraph, chConfig.getWeighting());
-            nodeContractor = new EdgeBasedNodeContractor(prepareGraph, pMap);
-        } else {
-            prepareGraph = PrepareCHGraph.nodeBased(chGraph, chConfig.getWeighting());
-            nodeContractor = new NodeBasedNodeContractor(prepareGraph, pMap);
         }
     }
 
@@ -112,10 +107,10 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation {
      * This will speed up CH preparation, but might lead to slower queries.
      */
     public PrepareContractionHierarchies useFixedNodeOrdering(NodeOrderingProvider nodeOrderingProvider) {
-        if (nodeOrderingProvider.getNumNodes() != prepareGraph.getNodes()) {
+        if (nodeOrderingProvider.getNumNodes() != nodes) {
             throw new IllegalArgumentException(
                     "contraction order size (" + nodeOrderingProvider.getNumNodes() + ")" +
-                            " must be equal to number of nodes in graph (" + prepareGraph.getNodes() + ").");
+                            " must be equal to number of nodes in graph (" + nodes + ").");
         }
         this.nodeOrderingProvider = nodeOrderingProvider;
         return this;
@@ -123,10 +118,10 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation {
 
     @Override
     public void doSpecificWork() {
-        if (!prepareGraph.isReadyForContraction()) {
+        if (!chGraph.isReadyForContraction()) {
             throw new IllegalStateException("Given CHGraph has not been frozen yet");
         }
-        if (prepareGraph.getEdges() > prepareGraph.getOriginalEdges()) {
+        if (chGraph.getEdges() > chGraph.getOriginalEdges()) {
             throw new IllegalStateException("Given CHGraph has been contracted already");
         }
         allSW.start();
@@ -137,13 +132,13 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation {
     }
 
     private void logFinalGraphStats() {
-        int edgeCount = prepareGraph.getOriginalEdges();
+        int edgeCount = chGraph.getOriginalEdges();
         logger.info("took: {}s, graph now - num edges: {}, num nodes: {}, num shortcuts: {}",
-                (int) allSW.getSeconds(), nf(edgeCount), nf(prepareGraph.getNodes()), nf(prepareGraph.getEdges() - edgeCount));
+                (int) allSW.getSeconds(), nf(edgeCount), nf(nodes), nf(chGraph.getEdges() - edgeCount));
     }
 
     private void runGraphContraction() {
-        if (prepareGraph.getNodes() < 1)
+        if (nodes < 1)
             return;
         setMaxLevelOnAllNodes();
         if (nodeOrderingProvider != null) {
@@ -158,29 +153,50 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation {
     }
 
     private void initFromGraph() {
-        maxLevel = prepareGraph.getNodes();
-        allEdgeExplorer = prepareGraph.createAllEdgeExplorer();
-        disconnectExplorer = prepareGraph.createAllEdgeExplorer();
+        // todo: this whole chain of initFromGraph() methods is just needed because PrepareContractionHierarchies does
+        // not simply prepare contraction hierarchies, but instead it also serves as some kind of 'container' to give
+        // access to the preparations in the GraphHopper class. If this was not so we could make this a lot cleaner here,
+        // declare variables final and would not need all these close() methods...
+        CHPreparationGraph prepareGraph;
+        if (chConfig.getTraversalMode().isEdgeBased()) {
+            TurnCostStorage turnCostStorage = chGraph.getBaseGraph().getTurnCostStorage();
+            if (turnCostStorage == null) {
+                throw new IllegalArgumentException("For edge-based CH you need a turn cost storage");
+            }
+            logger.info("Creating CH prepare graph, {}", getMemInfo());
+            CHPreparationGraph.TurnCostFunction turnCostFunction = CHPreparationGraph.buildTurnCostFunctionFromTurnCostStorage(graph, chConfig.getWeighting());
+            prepareGraph = CHPreparationGraph.edgeBased(graph.getNodes(), graph.getEdges(), turnCostFunction);
+            EdgeBasedNodeContractor.ShortcutHandler shortcutInserter = new EdgeBasedShortcutInserter(chGraph);
+            nodeContractor = new EdgeBasedNodeContractor(prepareGraph, shortcutInserter, pMap);
+        } else {
+            logger.info("Creating CH prepare graph, {}", getMemInfo());
+            prepareGraph = CHPreparationGraph.nodeBased(graph.getNodes(), graph.getEdges());
+            NodeBasedNodeContractor.ShortcutHandler shortcutInserter = new NodeBasedShortcutHandler(chGraph);
+            nodeContractor = new NodeBasedNodeContractor(prepareGraph, shortcutInserter, pMap);
+        }
+        maxLevel = nodes;
         // we need a memory-efficient priority queue with an efficient update method
         // TreeMap is not memory-efficient and PriorityQueue does not support an efficient update method
         // (and is not memory efficient either)
         sortedNodes = new MinHeapWithUpdate(prepareGraph.getNodes());
+        logger.info("Building CH prepare graph, {}", getMemInfo());
+        StopWatch sw = new StopWatch().start();
+        CHPreparationGraph.buildFromGraph(prepareGraph, graph, getWeighting());
+        logger.info("Finished building CH prepare graph, took: {}s, {}", sw.stop().getSeconds(), getMemInfo());
         nodeContractor.initFromGraph();
     }
 
     private void setMaxLevelOnAllNodes() {
-        final int nodes = prepareGraph.getNodes();
         for (int node = 0; node < nodes; node++) {
-            prepareGraph.setLevel(node, maxLevel);
+            chGraph.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)
+            if (isContracted(node))
                 continue;
             float priority = calculatePriority(node);
             sortedNodes.push(node, priority);
@@ -190,11 +206,11 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation {
 
     private void contractNodesUsingHeuristicNodeOrdering() {
         StopWatch sw = new StopWatch().start();
-        logger.info("Building initial queue of nodes to be contracted: {} nodes", prepareGraph.getNodes());
+        logger.info("Building initial queue of nodes to be contracted: {} nodes, {}", nodes, getMemInfo());
         // 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();
-        logger.info("Finished building queue, took: {}s", sw.stop().getSeconds());
+        logger.info("Finished building queue, took: {}s, {}", sw.stop().getSeconds(), getMemInfo());
         nodeContractor.prepareContraction();
         final int initSize = sortedNodes.size();
         int level = 0;
@@ -255,7 +271,7 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation {
             }
 
             // contract node v!
-            contractNode(polledNode, level);
+            IntContainer neighbors = contractNode(polledNode, level);
             level++;
 
             if (sortedNodes.size() < nodesToAvoidContract)
@@ -263,25 +279,19 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation {
                 break;
 
             // there might be multiple edges going to the same neighbor nodes -> only calculate priority once per node
-            updatedNeighbors.clear();
-            PrepareCHEdgeIterator iter = allEdgeExplorer.setBaseNode(polledNode);
-            while (iter.next()) {
-                int nn = iter.getAdjNode();
-                if (prepareGraph.getLevel(nn) != maxLevel)
-                    continue;
-
-                if (neighborUpdate && !updatedNeighbors.contains(nn) && rand.nextInt(100) < params.getNeighborUpdatePercentage()) {
+            for (IntCursor neighbor : neighbors) {
+                int nn = neighbor.value;
+                if (neighborUpdate && rand.nextInt(100) < params.getNeighborUpdatePercentage()) {
                     neighborUpdateSW.start();
                     float priority = calculatePriority(nn);
                     sortedNodes.update(nn, priority);
-                    updatedNeighbors.add(nn);
                     neighborUpdateSW.stop();
                 }
-
-                prepareGraph.disconnect(disconnectExplorer, iter);
             }
         }
 
+        nodeContractor.finishContraction();
+
         logHeuristicStats(updateCounter);
 
         logger.info(
@@ -310,20 +320,13 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation {
             stopIfInterrupted();
             int node = nodeOrderingProvider.getNodeIdForLevel(i);
             contractNode(node, i);
-
-            // disconnect neighbors
-            PrepareCHEdgeIterator iter = allEdgeExplorer.setBaseNode(node);
-            while (iter.next()) {
-                if (prepareGraph.getLevel(iter.getAdjNode()) != maxLevel)
-                    continue;
-                prepareGraph.disconnect(disconnectExplorer, iter);
-            }
             if (i % logSize == 0) {
                 stopWatch.stop();
                 logFixedNodeOrderingStats(i, logSize, stopWatch);
                 stopWatch.start();
             }
         }
+        nodeContractor.finishContraction();
     }
 
     private void stopIfInterrupted() {
@@ -332,11 +335,18 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation {
         }
     }
 
-    private void contractNode(int node, int level) {
+    private IntContainer contractNode(int node, int level) {
+        if (isContracted(node))
+            throw new IllegalArgumentException("Node " + node + " was contracted already");
         contractionSW.start();
-        nodeContractor.contractNode(node);
-        prepareGraph.setLevel(node, level);
+        IntContainer neighbors = nodeContractor.contractNode(node);
+        chGraph.setLevel(node, level);
         contractionSW.stop();
+        return neighbors;
+    }
+
+    private boolean isContracted(int node) {
+        return chGraph.getLevel(node) != maxLevel;
     }
 
     private void logHeuristicStats(int updateCounter) {
@@ -356,8 +366,8 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation {
         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(nodes),
+                (100.0 * nodesContracted / nodes),
                 nf(nodeContractor.getAddedShortcutsCount()),
                 nodesContracted == 0 ? 0 : logSize / (double) stopWatch.getMillis(),
                 nodeContractor.getStatisticsString(),
@@ -412,6 +422,8 @@ public class PrepareContractionHierarchies extends AbstractAlgoPreparation {
     }
 
     private float calculatePriority(int node) {
+        if (isContracted(node))
+            throw new IllegalArgumentException("Priority should only be calculated for not yet contracted nodes");
         return nodeContractor.calculatePriority(node);
     }
 
diff --git a/core/src/main/java/com/graphhopper/routing/ch/PrepareEncoder.java b/core/src/main/java/com/graphhopper/routing/ch/PrepareEncoder.java
index 9726d8ae2..6f2dd42ad 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/PrepareEncoder.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/PrepareEncoder.java
@@ -32,46 +32,21 @@ public class PrepareEncoder {
     /**
      * A bitmask for two directions
      */
-    public static final int getScDirMask() {
+    public static int getScDirMask() {
         return scDirMask;
     }
 
     /**
      * The bit for forward direction
      */
-    public static final int getScFwdDir() {
+    public static int getScFwdDir() {
         return scFwdDir;
     }
 
     /**
      * The bit for backward direction
      */
-    public static final int getScBwdDir() {
+    public static int getScBwdDir() {
         return scBwdDir;
     }
-
-    /**
-     * Returns 1 if existingScFlags of an existing shortcut can be overwritten with a new shortcut by
-     * newScFlags without limiting or changing the directions of the existing shortcut.
-     * The method returns 2 for the same condition but only if the new shortcut has to be added
-     * even if weight is higher than existing shortcut weight.
-     * <pre>
-     *                 | newScFlags:
-     * existingScFlags | -> | <- | <->
-     * ->              |  1 | 0  | 2
-     * <-              |  0 | 1  | 2
-     * <->             |  0 | 0  | 1
-     * </pre>
-     *
-     * @return 1 if newScFlags is identical to existingScFlags for the two direction bits and 0 otherwise.
-     * There are two special cases when it returns 2.
-     */
-    public static final int getScMergeStatus(int existingScFlags, int newScFlags) {
-        if ((existingScFlags & scDirMask) == (newScFlags & scDirMask))
-            return 1;
-        else if ((newScFlags & scDirMask) == scDirMask)
-            return 2;
-
-        return 0;
-    }
 }
diff --git a/core/src/main/java/com/graphhopper/routing/ch/PrepareCHEdgeExplorer.java b/core/src/main/java/com/graphhopper/routing/ch/PrepareGraphEdgeExplorer.java
similarity index 89%
rename from core/src/main/java/com/graphhopper/routing/ch/PrepareCHEdgeExplorer.java
rename to core/src/main/java/com/graphhopper/routing/ch/PrepareGraphEdgeExplorer.java
index 14266bc95..370333236 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/PrepareCHEdgeExplorer.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/PrepareGraphEdgeExplorer.java
@@ -18,6 +18,6 @@
 
 package com.graphhopper.routing.ch;
 
-public interface PrepareCHEdgeExplorer {
-    PrepareCHEdgeIterator setBaseNode(int node);
+public interface PrepareGraphEdgeExplorer {
+    PrepareGraphEdgeIterator setBaseNode(int node);
 }
diff --git a/core/src/main/java/com/graphhopper/routing/ch/PrepareCHEdgeIterator.java b/core/src/main/java/com/graphhopper/routing/ch/PrepareGraphEdgeIterator.java
similarity index 74%
rename from core/src/main/java/com/graphhopper/routing/ch/PrepareCHEdgeIterator.java
rename to core/src/main/java/com/graphhopper/routing/ch/PrepareGraphEdgeIterator.java
index fadb156c4..ebbb51a3b 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/PrepareCHEdgeIterator.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/PrepareGraphEdgeIterator.java
@@ -18,28 +18,32 @@
 
 package com.graphhopper.routing.ch;
 
-public interface PrepareCHEdgeIterator {
+public interface PrepareGraphEdgeIterator {
     boolean next();
 
-    int getEdge();
-
     int getBaseNode();
 
     int getAdjNode();
 
-    int getOrigEdgeFirst();
-
-    int getOrigEdgeLast();
+    int getPrepareEdge();
 
     boolean isShortcut();
 
-    double getWeight(boolean reverse);
+    int getOrigEdgeKeyFirst();
 
-    void setWeight(double weight);
+    int getOrigEdgeKeyLast();
+
+    int getSkipped1();
 
-    int getMergeStatus(int flags);
+    int getSkipped2();
 
-    void setFlagsAndWeight(int flags, double weight);
+    double getWeight();
+
+    int getOrigEdgeCount();
+
+    void setSkippedEdges(int skipped1, int skipped2);
+
+    void setWeight(double weight);
 
-    void setSkippedEdges(int skippedEdge1, int skippedEdge2);
+    void setOrigEdgeCount(int origEdgeCount);
 }
diff --git a/core/src/main/java/com/graphhopper/routing/ch/PrepareGraphOrigEdgeExplorer.java b/core/src/main/java/com/graphhopper/routing/ch/PrepareGraphOrigEdgeExplorer.java
new file mode 100644
index 000000000..e23d05368
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/ch/PrepareGraphOrigEdgeExplorer.java
@@ -0,0 +1,23 @@
+/*
+ *  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;
+
+public interface PrepareGraphOrigEdgeExplorer {
+    PrepareGraphOrigEdgeIterator setBaseNode(int node);
+}
diff --git a/core/src/main/java/com/graphhopper/routing/ch/PrepareGraphOrigEdgeIterator.java b/core/src/main/java/com/graphhopper/routing/ch/PrepareGraphOrigEdgeIterator.java
new file mode 100644
index 000000000..177b7063c
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/ch/PrepareGraphOrigEdgeIterator.java
@@ -0,0 +1,31 @@
+/*
+ *  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;
+
+public interface PrepareGraphOrigEdgeIterator {
+    boolean next();
+
+    int getBaseNode();
+
+    int getAdjNode();
+
+    int getOrigEdgeKeyFirst();
+
+    int getOrigEdgeKeyLast();
+}
diff --git a/core/src/main/java/com/graphhopper/routing/ch/SplitArray2D.java b/core/src/main/java/com/graphhopper/routing/ch/SplitArray2D.java
new file mode 100644
index 000000000..cc290920d
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/ch/SplitArray2D.java
@@ -0,0 +1,140 @@
+/*
+ *  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 java.util.Arrays;
+
+/**
+ * This is a more memory-efficient version of two equal length `ArrayList<T>[]`s, i.e. this is a fixed size array where
+ * each element is a variable sized sub-array and each sub-array is divided into two parts.
+ * This is more memory efficient than two arrays of `ArrayList`s, because it saves the object-overhead of using an
+ * ArrayList object for each sub-array.
+ * <p>
+ * The elements in each sub-array are divided into two parts with ranges [0,mid[ and [mid,size[. We can add elements
+ * to either of the two parts.
+ */
+class SplitArray2D<T> {
+    private static final int GROW_FACTOR = 2;
+    private final int initialSubArrayCapacity;
+    private final Object[][] data;
+    // todo: mids/sizes can probably be combined into a single int to save some memory, but need to check maximum values
+    // checking for Bayern and Germany it seemed like the maximum values were around 50/100 and independent of the
+    // map size
+    private final int[] mids;
+    private final int[] sizes;
+
+    SplitArray2D(int size, int initialSubArrayCapacity) {
+        data = new Object[size][];
+        sizes = new int[size];
+        mids = new int[size];
+        this.initialSubArrayCapacity = initialSubArrayCapacity;
+    }
+
+    int mid(int n) {
+        return mids[n];
+    }
+
+    int size(int n) {
+        return sizes[n];
+    }
+
+    T get(int n, int index) {
+        return (T) data[n][index];
+    }
+
+    /**
+     * Adds the given element to the first part of the n-th sub-array. This changes the order of the existing elements.
+     */
+    void addPartOne(int n, T element) {
+        if (data[n] == null) {
+            data[n] = new Object[initialSubArrayCapacity];
+            data[n][0] = element;
+            mids[n] = 1;
+            sizes[n] = 1;
+        } else {
+            assert data[n].length != 0;
+            if (sizes[n] == data[n].length)
+                grow(n);
+            data[n][sizes[n]] = data[n][mids[n]];
+            data[n][mids[n]] = element;
+            mids[n]++;
+            sizes[n]++;
+        }
+    }
+
+    /**
+     * Adds the given element to the second part of the n-th sub-array. This changes the order of the existing elements.
+     */
+    void addPartTwo(int n, T element) {
+        if (data[n] == null) {
+            data[n] = new Object[initialSubArrayCapacity];
+            data[n][0] = element;
+            sizes[n] = 1;
+        } else {
+            assert data[n].length != 0;
+            if (sizes[n] == data[n].length)
+                grow(n);
+            data[n][sizes[n]] = element;
+            sizes[n]++;
+        }
+    }
+
+    /**
+     * Removes all occurrences of the given element from the given sub-array. Using this method changes the order of the
+     * existing elements in the sub-array unless we remove only the very last element(s)!
+     */
+    void remove(int n, T element) {
+        for (int i = 0; i < mids[n]; ++i) {
+            while (mids[n] > 0 && i < mids[n] && data[n][i] == element) {
+                data[n][i] = data[n][mids[n] - 1];
+                data[n][mids[n] - 1] = data[n][sizes[n] - 1];
+                data[n][sizes[n] - 1] = null;
+                mids[n]--;
+                sizes[n]--;
+            }
+        }
+        for (int i = mids[n]; i < sizes[n]; ++i) {
+            while (sizes[n] > mids[n] && i < sizes[n] && data[n][i] == element) {
+                data[n][i] = data[n][sizes[n] - 1];
+                data[n][sizes[n] - 1] = null;
+                sizes[n]--;
+            }
+        }
+    }
+
+    void clear(int n) {
+        data[n] = null;
+        sizes[n] = 0;
+        mids[n] = 0;
+    }
+
+    private void grow(int n) {
+        // todo: think about grow factor: trimming and then doubling the size might be not what we want, rather
+        // increase by 50% or something?
+        data[n] = Arrays.copyOf(data[n], data[n].length * GROW_FACTOR);
+    }
+
+    void trimToSize() {
+        for (int n = 0; n < data.length; n++) {
+            if (data[n] != null)
+                data[n] = Arrays.copyOf(data[n], sizes[n]);
+        }
+    }
+
+}
diff --git a/core/src/main/java/com/graphhopper/routing/lm/LMPreparationHandler.java b/core/src/main/java/com/graphhopper/routing/lm/LMPreparationHandler.java
index b8e16c532..c24c68c42 100644
--- a/core/src/main/java/com/graphhopper/routing/lm/LMPreparationHandler.java
+++ b/core/src/main/java/com/graphhopper/routing/lm/LMPreparationHandler.java
@@ -193,21 +193,19 @@ public class LMPreparationHandler {
             counter++;
             final int tmpCounter = counter;
             final String name = plm.getLMConfig().getName();
-            completionService.submit(new Runnable() {
-                @Override
-                public void run() {
-                    if (plm.loadExisting())
-                        return;
-
-                    LOGGER.info(tmpCounter + "/" + getPreparations().size() + " calling LM prepare.doWork for " + plm.getLMConfig().getWeighting() + " ... (" + getMemInfo() + ")");
-                    prepared.set(true);
-                    Thread.currentThread().setName(name);
-                    plm.doWork();
-                    if (closeEarly) {
-                        plm.close();
-                    }
-                    properties.put(Landmark.PREPARE + "date." + name, createFormatter().format(new Date()));
+            completionService.submit(() -> {
+                if (plm.loadExisting())
+                    return;
+
+                LOGGER.info(tmpCounter + "/" + getPreparations().size() + " calling LM prepare.doWork for " + plm.getLMConfig().getWeighting() + " ... (" + getMemInfo() + ")");
+                prepared.set(true);
+                Thread.currentThread().setName(name);
+                plm.doWork();
+                if (closeEarly) {
+                    plm.close();
                 }
+                LOGGER.info("LM {} finished {}", name, getMemInfo());
+                properties.put(Landmark.PREPARE + "date." + name, createFormatter().format(new Date()));
             }, name);
         }
 
@@ -221,6 +219,7 @@ public class LMPreparationHandler {
             threadPool.shutdownNow();
             throw new RuntimeException(e);
         }
+        LOGGER.info("Finished LM preparation, {}", getMemInfo());
         return prepared.get();
     }
 
@@ -233,6 +232,7 @@ public class LMPreparationHandler {
         if (lmConfigs.isEmpty())
             throw new IllegalStateException("No landmark weightings found");
 
+        LOGGER.info("Creating LM preparations, {}", getMemInfo());
         List<LandmarkSuggestion> lmSuggestions = new ArrayList<>(lmSuggestionsLocations.size());
         if (!lmSuggestionsLocations.isEmpty()) {
             try {
diff --git a/core/src/main/java/com/graphhopper/storage/BaseGraph.java b/core/src/main/java/com/graphhopper/storage/BaseGraph.java
index f59bb7ca1..63dbb12e8 100644
--- a/core/src/main/java/com/graphhopper/storage/BaseGraph.java
+++ b/core/src/main/java/com/graphhopper/storage/BaseGraph.java
@@ -533,7 +533,7 @@ class BaseGraph implements Graph {
             throw new IllegalStateException("Cannot create edge if graph is already frozen");
 
         ensureNodeIndex(Math.max(nodeA, nodeB));
-        int edgeId = edgeAccess.internalEdgeAdd(nextEdgeId(), nodeA, nodeB);
+        int edgeId = edgeAccess.internalEdgeAdd(nextEdgeId(), nodeA, nodeB, true);
         EdgeIteratorStateImpl edge = new EdgeIteratorStateImpl(edgeAccess, this);
         boolean valid = edge.init(edgeId, nodeB);
         assert valid;
diff --git a/core/src/main/java/com/graphhopper/storage/CHGraph.java b/core/src/main/java/com/graphhopper/storage/CHGraph.java
index 765e1acd9..77ecc46c7 100644
--- a/core/src/main/java/com/graphhopper/storage/CHGraph.java
+++ b/core/src/main/java/com/graphhopper/storage/CHGraph.java
@@ -79,8 +79,6 @@ public interface CHGraph {
 
     AllCHEdgesIterator getAllEdges();
 
-    void disconnectEdge(int edge, int adjNode, int prevEdge);
-
     /**
      * @return the number of original edges in this graph (without shortcuts)
      */
diff --git a/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java b/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
index e14eb6ca1..ca8ad6f68 100644
--- a/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
+++ b/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
@@ -115,7 +115,9 @@ public class CHGraphImpl implements CHGraph, Storable<CHGraph> {
         checkNodeId(a);
         checkNodeId(b);
 
-        int scId = chEdgeAccess.internalEdgeAdd(nextShortcutId(), a, b);
+        // we do not register the edge at node b which should be the higher level node (so no need to 'see' the lower
+        // level node a)
+        int scId = chEdgeAccess.internalEdgeAdd(nextShortcutId(), a, b, false);
         // do not create CHEdgeIteratorImpl object
         long edgePointer = chEdgeAccess.toPointer(scId);
         chEdgeAccess.setAccessAndWeight(edgePointer, accessFlags & scDirMask, weight);
@@ -236,14 +238,6 @@ public class CHGraphImpl implements CHGraph, Storable<CHGraph> {
         return toString() + ", shortcuts:" + nf(shortcutCount) + ", nodesCH:(" + nodesCH.getCapacity() / Helper.MB + "MB)";
     }
 
-    @Override
-    public void disconnectEdge(int edge, int adjNode, int prevEdge) {
-        // TODO this is ugly, move this somehow into the underlying iteration logic
-        long edgePointer = !EdgeIterator.Edge.isValid(prevEdge) ? -1
-                : isShortcut(prevEdge) ? chEdgeAccess.toPointer(prevEdge) : baseGraph.edgeAccess.toPointer(prevEdge);
-        chEdgeAccess.internalEdgeDisconnect(edge, edgePointer, adjNode);
-    }
-
     @Override
     public AllCHEdgesIterator getAllEdges() {
         return new AllCHEdgesIteratorImpl(baseGraph);
@@ -865,11 +859,6 @@ public class CHGraphImpl implements CHGraph, Storable<CHGraph> {
             return edgeIterable.setReverse(property, value);
         }
 
-        @Override
-        public int getMergeStatus(int flags) {
-            return PrepareEncoder.getScMergeStatus(getShortcutFlags(), flags);
-        }
-
         @Override
         public EdgeIteratorState detach(boolean reverseArg) {
             return edgeIterable.detach(reverseArg);
diff --git a/core/src/main/java/com/graphhopper/storage/EdgeAccess.java b/core/src/main/java/com/graphhopper/storage/EdgeAccess.java
index a31560b19..9ab958def 100644
--- a/core/src/main/java/com/graphhopper/storage/EdgeAccess.java
+++ b/core/src/main/java/com/graphhopper/storage/EdgeAccess.java
@@ -64,8 +64,11 @@ abstract class EdgeAccess {
 
     /**
      * Writes a new edge to the array of edges and adds it to the linked list of edges at nodeA and nodeB
+     *
+     * @param connectB if false the edge is not registered at / will not be visible from nodeB, this is useful for
+     *                 CH.
      */
-    final int internalEdgeAdd(int newEdgeId, int nodeA, int nodeB) {
+    final int internalEdgeAdd(int newEdgeId, int nodeA, int nodeB, boolean connectB) {
         writeEdge(newEdgeId, nodeA, nodeB, EdgeIterator.NO_EDGE, EdgeIterator.NO_EDGE);
         long edgePointer = toPointer(newEdgeId);
 
@@ -74,7 +77,7 @@ abstract class EdgeAccess {
             edges.setInt(E_LINKA + edgePointer, edge);
         setEdgeRef(nodeA, newEdgeId);
 
-        if (nodeA != nodeB) {
+        if (connectB && nodeA != nodeB) {
             edge = getEdgeRef(nodeB);
             if (edge > EdgeIterator.NO_EDGE)
                 edges.setInt(E_LINKB + edgePointer, edge);
diff --git a/core/src/main/java/com/graphhopper/util/CHEdgeIteratorState.java b/core/src/main/java/com/graphhopper/util/CHEdgeIteratorState.java
index b6ee07160..685ded62c 100644
--- a/core/src/main/java/com/graphhopper/util/CHEdgeIteratorState.java
+++ b/core/src/main/java/com/graphhopper/util/CHEdgeIteratorState.java
@@ -17,8 +17,6 @@
  */
 package com.graphhopper.util;
 
-import com.graphhopper.routing.ch.PrepareEncoder;
-
 /**
  * The state returned from the EdgeIterator of a CHGraph
  * <p>
@@ -51,13 +49,6 @@ public interface CHEdgeIteratorState extends EdgeIteratorState {
      */
     boolean getBwdAccess();
 
-    /**
-     * This method is only used on preparation.
-     *
-     * @see PrepareEncoder#getScMergeStatus(int, int)
-     */
-    int getMergeStatus(int flags);
-
     /**
      * Returns the weight of this shortcut.
      */


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/AlternativeRouteEdgeCHTest.java b/core/src/test/java/com/graphhopper/routing/AlternativeRouteEdgeCHTest.java
index 10bcd535a..6281fd605 100644
--- a/core/src/test/java/com/graphhopper/routing/AlternativeRouteEdgeCHTest.java
+++ b/core/src/test/java/com/graphhopper/routing/AlternativeRouteEdgeCHTest.java
@@ -141,10 +141,9 @@ public class AlternativeRouteEdgeCHTest {
         hints.putObject("alternative_route.max_paths", 4);
         AlternativeRouteEdgeCH altDijkstra = new AlternativeRouteEdgeCH(g.getRoutingCHGraph(), hints);
         List<AlternativeRouteEdgeCH.AlternativeInfo> pathInfos = altDijkstra.calcAlternatives(10, 5);
-        assertEquals(3, pathInfos.size());
+        assertEquals(2, pathInfos.size());
         assertEquals(IntArrayList.from(10, 4, 3, 6, 5), pathInfos.get(0).path.calcNodes());
         assertEquals(IntArrayList.from(10, 4, 8, 7, 6, 5), pathInfos.get(1).path.calcNodes());
-        assertEquals(IntArrayList.from(10, 4, 8, 7, 6, 3, 2, 9, 1, 5), pathInfos.get(2).path.calcNodes());
         // The shortest path works (no restrictions on the way back
     }
 
diff --git a/core/src/test/java/com/graphhopper/routing/QueryRoutingCHGraphTest.java b/core/src/test/java/com/graphhopper/routing/QueryRoutingCHGraphTest.java
index 373c93351..da8bd906f 100644
--- a/core/src/test/java/com/graphhopper/routing/QueryRoutingCHGraphTest.java
+++ b/core/src/test/java/com/graphhopper/routing/QueryRoutingCHGraphTest.java
@@ -113,7 +113,8 @@ class QueryRoutingCHGraphTest {
 
         assertNodesConnected(queryCHGraph, 0, 1, true);
         assertNodesConnected(queryCHGraph, 1, 2, true);
-        assertNodesConnected(queryCHGraph, 0, 2, false);
+        // the shortcut 0-2 is not visible from node 2
+//        assertNodesConnected(queryCHGraph, 0, 2, false);
 
         RoutingCHEdgeIterator outIter = queryCHGraph.createOutEdgeExplorer().setBaseNode(0);
         assertNextShortcut(outIter, 0, 2, 0, 1);
@@ -121,7 +122,6 @@ class QueryRoutingCHGraphTest {
         assertEnd(outIter);
 
         RoutingCHEdgeIterator inIter = queryCHGraph.createInEdgeExplorer().setBaseNode(2);
-        assertNextShortcut(inIter, 2, 0, 0, 1);
         assertNextEdge(inIter, 2, 1, 1);
         assertEnd(inIter);
     }
@@ -219,7 +219,8 @@ class QueryRoutingCHGraphTest {
         assertNodesConnected(queryCHGraph, 0, 3, true);
         assertNodesConnected(queryCHGraph, 3, 1, true);
         assertNodesConnected(queryCHGraph, 1, 2, true);
-        assertNodesConnected(queryCHGraph, 0, 2, false);
+        // node 0 is not visible from node 0 via shortcut 0-2
+//        assertNodesConnected(queryCHGraph, 0, 2, false);
 
         // at real nodes
         RoutingCHEdgeIterator outIter = queryCHGraph.createOutEdgeExplorer().setBaseNode(0);
@@ -229,7 +230,6 @@ class QueryRoutingCHGraphTest {
         assertEnd(outIter);
 
         RoutingCHEdgeIterator inIter = queryCHGraph.createInEdgeExplorer().setBaseNode(2);
-        assertNextShortcut(inIter, 2, 0, 0, 1);
         assertNextEdge(inIter, 2, 1, 1);
         assertEnd(inIter);
 
diff --git a/core/src/test/java/com/graphhopper/routing/ch/CHPreparationGraphTest.java b/core/src/test/java/com/graphhopper/routing/ch/CHPreparationGraphTest.java
new file mode 100644
index 000000000..9a4fe0b08
--- /dev/null
+++ b/core/src/test/java/com/graphhopper/routing/ch/CHPreparationGraphTest.java
@@ -0,0 +1,56 @@
+/*
+ *  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 org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+/**
+ * So far there aren't many tests but the graph should be very easy to test as it has basically no dependencies and
+ * if a problem arises it should be easy to write a test here.
+ */
+class CHPreparationGraphTest {
+
+    @Test
+    void basic() {
+        // 0->4<-2
+        // |
+        // 3<-1
+        CHPreparationGraph pg = CHPreparationGraph.nodeBased(5, 10);
+        double inf = Double.POSITIVE_INFINITY;
+        pg.addEdge(0, 4, 3, 10, inf);
+        pg.addEdge(4, 2, 0, inf, 5);
+        pg.addEdge(0, 3, 1, 6, 6);
+        pg.addEdge(1, 3, 2, 9, inf);
+        pg.prepareForContraction();
+
+        assertEquals(3, pg.getDegree(0));
+        assertEquals(2, pg.getDegree(4));
+
+        pg.addShortcut(3, 4, 1, 3, 1, 3, 16, 2);
+        pg.disconnect(0);
+        PrepareGraphEdgeIterator iter = pg.createOutEdgeExplorer().setBaseNode(3);
+        String res = "";
+        while (iter.next()) {
+            res += iter.toString() + ",";
+        }
+        assertEquals("3-4,", res);
+    }
+}
\ No newline at end of file
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 55b6f6973..c604acaaf 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/CHTurnCostTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ch/CHTurnCostTest.java
@@ -771,7 +771,10 @@ public class CHTurnCostTest {
         automaticPrepareCH();
         compareCHQueryWithDijkstra(0, 3);
         compareCHQueryWithDijkstra(1, 4);
-        automaticCompareCHWithDijkstra(100);
+        final Random rnd = new Random(System.nanoTime());
+        for (int i = 0; i < 100; ++i) {
+            compareCHQueryWithDijkstra(rnd.nextInt(graph.getNodes()), rnd.nextInt(graph.getNodes()));
+        }
     }
 
     @Test
@@ -988,9 +991,9 @@ public class CHTurnCostTest {
         Dijkstra dijkstra = new Dijkstra(queryGraph, w, TraversalMode.EDGE_BASED);
         Path dijkstraPath = dijkstra.calcPath(4, 6);
         assertEquals(IntArrayList.from(4, 3, 2, 1, 7, 0, 7, 1, 5, 6), dijkstraPath.calcNodes());
-        assertEquals(dijkstraPath.getWeight(), path.getWeight(), 1.e-3);
-        assertEquals(dijkstraPath.getDistance(), path.getDistance(), 1.e-3);
-        assertEquals(dijkstraPath.getTime(), path.getTime(), 1.e-3);
+        assertEquals(dijkstraPath.getWeight(), path.getWeight(), 1.e-2);
+        assertEquals(dijkstraPath.getDistance(), path.getDistance(), 1.e-2);
+        assertEquals(dijkstraPath.getTime(), path.getTime());
     }
 
     /**
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 4a780fd48..4beaef8d5 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedNodeContractorTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedNodeContractorTest.java
@@ -24,7 +24,9 @@ import com.graphhopper.routing.ev.TurnCost;
 import com.graphhopper.routing.util.AllCHEdgesIterator;
 import com.graphhopper.routing.util.CarFlagEncoder;
 import com.graphhopper.routing.util.EncodingManager;
+import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.CHConfig;
+import com.graphhopper.storage.CHGraph;
 import com.graphhopper.storage.GraphBuilder;
 import com.graphhopper.storage.GraphHopperStorage;
 import com.graphhopper.util.EdgeIteratorState;
@@ -33,6 +35,8 @@ import com.graphhopper.util.PMap;
 import org.junit.jupiter.api.BeforeEach;
 import org.junit.jupiter.api.RepeatedTest;
 import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
 
 import java.util.*;
 
@@ -46,9 +50,10 @@ import static org.junit.jupiter.api.Assertions.*;
  */
 public class EdgeBasedNodeContractorTest {
     private final int maxCost = 10;
-    private PrepareCHGraph chGraph;
+    private CHGraph chGraph;
     private CarFlagEncoder encoder;
     private GraphHopperStorage graph;
+    private Weighting weighting;
 
     private List<CHConfig> chConfigs;
 
@@ -68,7 +73,8 @@ public class EdgeBasedNodeContractorTest {
                 )
                 .create();
         chConfigs = graph.getCHConfigs();
-        chGraph = PrepareCHGraph.edgeBased(graph.getCHGraph(chConfigs.get(0).getName()), chConfigs.get(0).getWeighting());
+        chGraph = graph.getCHGraph(chConfigs.get(0).getName());
+        weighting = chGraph.getCHConfig().getWeighting();
     }
 
     @Test
@@ -92,9 +98,9 @@ public class EdgeBasedNodeContractorTest {
 
         contractNodes(5, 6, 3, 2, 9, 1, 8, 4, 7, 0);
         checkShortcuts(
-                createShortcut(8, 2, edge8to3, edge3to2, 5),
-                createShortcut(8, 7, edge8to3.getEdge(), edge2to7.getEdge(), 6, edge2to7.getEdge(), 6),
-                createShortcut(7, 7, edge7to8.getEdge(), edge2to7.getEdge(), edge7to8.getEdge(), 7, 8)
+                createShortcut(2, 8, edge8to3, edge3to2, 5, false, true),
+                createShortcut(8, 7, edge8to3.getEdge(), edge2to7.getEdge(), 6, edge2to7.getEdge(), 6, true, false),
+                createShortcut(7, 7, edge7to8.getEdge(), edge2to7.getEdge(), edge7to8.getEdge(), 7, 8, true, false)
         );
     }
 
@@ -119,12 +125,12 @@ public class EdgeBasedNodeContractorTest {
         contractAllNodesInOrder();
         checkShortcuts(
                 // from contracting node 0: need a shortcut because of turn restriction
-                createShortcut(6, 3, e6to0, e0to3, 9),
+                createShortcut(3, 6, e6to0, e0to3, 9, false, true),
                 // from contracting node 3: two shortcuts:
                 // 1) in case we come from 1->6 (cant turn left)
                 // 2) in case we come from 2->6 (going via node 0 would be more expensive)
-                createShortcut(6, 5, e6to0.getEdge(), e3to5.getEdge(), 7, e3to5.getEdge(), 11),
-                createShortcut(6, 5, e6to3, e3to5, 3)
+                createShortcut(5, 6, e6to0.getEdge(), e3to5.getEdge(), 7, e3to5.getEdge(), 11, false, true),
+                createShortcut(5, 6, e6to3, e3to5, 3, false, true)
         );
     }
 
@@ -144,12 +150,12 @@ public class EdgeBasedNodeContractorTest {
         contractAllNodesInOrder();
         checkShortcuts(
                 // from contraction of node 0
-                createShortcut(4, 2, e0to4, e0to2, 8),
+                createShortcut(2, 4, e0to4, e0to2, 8, false, true),
                 // from contraction of node 2
                 // It might look like it is always better to go directly from 4 to 2, but when we come from edge (2->4)
                 // we may not do a u-turn at 4.
-                createShortcut(4, 3, e0to4.getEdge(), e2to3.getEdge(), 5, e2to3.getEdge(), 10),
-                createShortcut(4, 3, e2to4, e2to3, 4)
+                createShortcut(3, 4, e0to4.getEdge(), e2to3.getEdge(), 5, e2to3.getEdge(), 10, false, true),
+                createShortcut(3, 4, e2to4, e2to3, 4, false, true)
         );
     }
 
@@ -178,12 +184,12 @@ public class EdgeBasedNodeContractorTest {
         contractAllNodesInOrder();
         checkShortcuts(
                 // from contraction of node 3
-                createShortcut(4, 6, e3to4, e3to6, 6),
-                createShortcut(6, 4, e3to6, e3to4, 4),
+                createShortcut(4, 6, e3to4, e3to6, 6, true, false),
+                createShortcut(4, 6, e3to6, e3to4, 4, false, true),
                 // from contraction of node 4
                 // two 'parallel' shortcuts to preserve shortest paths to 5 when coming from 4->6 and 3->6 !!
-                createShortcut(6, 5, e3to6.getEdge(), e4to5.getEdge(), 8, e4to5.getEdge(), 5),
-                createShortcut(6, 5, e4to6, e4to5, 3)
+                createShortcut(5, 6, e3to6.getEdge(), e4to5.getEdge(), 8, e4to5.getEdge(), 5, false, true),
+                createShortcut(5, 6, e4to6, e4to5, 3, false, true)
         );
     }
 
@@ -195,7 +201,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(2, 3, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(0);
+        contractNodes(0, 3, 1, 2);
         // it looks like we need a shortcut from 1 to 2, but shortcuts are only introduced to maintain shortest paths
         // between original edges, so there should be no shortcuts here, because there is no original edge incoming
         // to node 1.
@@ -210,7 +216,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(0, 2, 5, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(0);
+        contractNodes(0, 3, 1, 2);
         // it looks like we need a shortcut from 1 to 2, but shortcuts are only introduced to maintain shortest paths
         // between original edges, so there should be no shortcuts here, because there is no original edge outgoing
         // from node 2.
@@ -228,7 +234,7 @@ public class EdgeBasedNodeContractorTest {
         setRestriction(2, 4, 1);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 3, 4, 1);
         // It looks like we need a shortcut from 3 to 4, but due to the turn restrictions there should be none.
         checkShortcuts();
     }
@@ -250,6 +256,9 @@ public class EdgeBasedNodeContractorTest {
         // contracting node 2 should yield a shortcut to preserve the shortest path from (1->2) to (3->4). note that
         // it does not matter that nodes 0 and 1 have lower level and are contracted already!
         contractNode(nodeContractor, 2, 2);
+        contractNode(nodeContractor, 3, 3);
+        contractNode(nodeContractor, 4, 4);
+        nodeContractor.finishContraction();
         checkShortcuts(createShortcut(3, 4, e3to2, e2to4, 8));
     }
 
@@ -276,7 +285,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(4, 3, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 4, 1, 3);
         checkShortcuts();
     }
 
@@ -289,7 +298,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(3, 4, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 4, 1, 3);
         checkShortcuts();
     }
 
@@ -307,7 +316,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(3, 4, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 4, 1, 3);
         // there should be only one shortcut
         checkShortcuts(
                 createShortcut(1, 3, 1, 3, 1, 3, 2)
@@ -325,7 +334,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(3, 4, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 4, 1, 3);
         checkShortcuts(
                 createShortcut(1, 3, 2, 3, 2, 3, 2)
         );
@@ -347,7 +356,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(3, 4, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 4, 1, 3);
         checkNumShortcuts(1);
     }
 
@@ -362,7 +371,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(3, 4, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 4, 1, 3);
         checkNumShortcuts(1);
     }
 
@@ -376,7 +385,7 @@ public class EdgeBasedNodeContractorTest {
         setTurnCost(3, 2, 4, 4);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 1, 3, 4);
         checkShortcuts(createShortcut(3, 4, e3to2, e2to4, 12));
     }
 
@@ -390,7 +399,7 @@ public class EdgeBasedNodeContractorTest {
         setRestriction(3, 2, 4);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 1, 3, 4);
         checkShortcuts();
     }
 
@@ -405,13 +414,13 @@ public class EdgeBasedNodeContractorTest {
         setTurnCost(e2to4, e3to2, 2, 4);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 1, 3, 4);
         checkShortcuts(
                 // note that for now we add a shortcut for each direction. using fwd/bwd flags would be more efficient,
                 // but requires a more sophisticated way to determine the 'first' and 'last' original edges at various
                 // places
-                createShortcut(3, 4, e3to2, e2to4, 12),
-                createShortcut(4, 3, e2to4, e3to2, 12)
+                createShortcut(3, 4, e3to2, e2to4, 12, true, false),
+                createShortcut(3, 4, e2to4, e3to2, 12, false, true)
         );
     }
 
@@ -426,10 +435,10 @@ public class EdgeBasedNodeContractorTest {
         setTurnCost(e2to4, e2to3, 2, 7);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 1, 3, 4);
         checkShortcuts(
-                createShortcut(3, 4, e2to3, e2to4, 12),
-                createShortcut(4, 3, e2to4, e2to3, 15)
+                createShortcut(3, 4, e2to3, e2to4, 12, true, false),
+                createShortcut(3, 4, e2to4, e2to3, 15, false, true)
         );
     }
 
@@ -442,7 +451,7 @@ public class EdgeBasedNodeContractorTest {
         graph.freeze();
         setMaxLevelOnAllNodes();
 
-        contractNodes(1, 2);
+        contractNodes(1, 2, 3, 4);
         // no shortcuts needed
         checkShortcuts();
     }
@@ -473,13 +482,13 @@ public class EdgeBasedNodeContractorTest {
         graph.freeze();
         setMaxLevelOnAllNodes();
 
-        createNodeContractor().contractNode(2);
+        contractNodes(2, 0, 1, 3, 4);
         if (loopHelps) {
             // it is better to take the loop at node 2, so we need to introduce two shortcuts where the second contains
             // the first (this is important for path unpacking)
             checkShortcuts(
-                    createShortcut(3, 2, e3to2, e2to2, 7),
-                    createShortcut(3, 4, e3to2.getEdge(), e2to4.getEdge(), 5, e2to4.getEdge(), 13));
+                    createShortcut(2, 3, e3to2, e2to2, 7, false, true),
+                    createShortcut(3, 4, e3to2.getEdge(), e2to4.getEdge(), 5, e2to4.getEdge(), 13, true, false));
         } else {
             // taking the loop would be worse, so the path is just 3-2-4 and we only need a single shortcut
             checkShortcuts(
@@ -501,11 +510,11 @@ public class EdgeBasedNodeContractorTest {
         graph.freeze();
         setMaxLevelOnAllNodes();
         setRestriction(7, 3, 5);
-        contractNodes(3, 4);
+        contractNodes(3, 4, 2, 6, 7, 5, 1);
         checkShortcuts(
                 // from contracting node 3
-                createShortcut(7, 4, e7to3, e3to4, 3),
-                createShortcut(4, 5, e3to4, e3to5, 3)
+                createShortcut(4, 7, e7to3, e3to4, 3, false, true),
+                createShortcut(4, 5, e3to4, e3to5, 3, true, false)
                 // important! no shortcut from 7 to 5 when contracting node 4, because it includes a u-turn
         );
     }
@@ -515,7 +524,7 @@ public class EdgeBasedNodeContractorTest {
         // turning on any of the loops is restricted so we take the direct turn -> one extra shortcuts
         GraphWithTwoLoops g = new GraphWithTwoLoops(maxCost, maxCost, 1, 2, 3, 4);
         g.contractAndCheckShortcuts(
-                createShortcut(7, 8, g.e7to6, g.e6to8, 11));
+                createShortcut(7, 8, g.e7to6, g.e6to8, 11, true, false));
     }
 
     @Test
@@ -523,8 +532,8 @@ public class EdgeBasedNodeContractorTest {
         // direct turn is restricted, so we take the left loop -> two extra shortcuts
         GraphWithTwoLoops g = new GraphWithTwoLoops(2, maxCost, 1, 2, 3, maxCost);
         g.contractAndCheckShortcuts(
-                createShortcut(7, 6, g.e7to6.getEdge(), g.e1to6.getEdge(), g.e7to6.getEdge(), g.getScEdge(1), 12),
-                createShortcut(7, 8, g.e7to6.getEdge(), g.e6to8.getEdge(), g.getScEdge(4), g.e6to8.getEdge(), 20)
+                createShortcut(6, 7, g.e7to6.getEdge(), g.e1to6.getEdge(), g.e7to6.getEdge(), g.getScEdge(3), 12, false, true),
+                createShortcut(7, 8, g.e7to6.getEdge(), g.e6to8.getEdge(), g.getScEdge(4), g.e6to8.getEdge(), 20, true, false)
         );
     }
 
@@ -533,8 +542,8 @@ public class EdgeBasedNodeContractorTest {
         // direct turn is restricted, going on left loop is expensive, so we take the right loop -> two extra shortcuts
         GraphWithTwoLoops g = new GraphWithTwoLoops(8, 1, 1, 2, 3, maxCost);
         g.contractAndCheckShortcuts(
-                createShortcut(7, 6, g.e7to6.getEdge(), g.e3to6.getEdge(), g.e7to6.getEdge(), g.getScEdge(3), 12),
-                createShortcut(7, 8, g.e7to6.getEdge(), g.e6to8.getEdge(), g.getScEdge(4), g.e6to8.getEdge(), 21)
+                createShortcut(6, 7, g.e7to6.getEdge(), g.e3to6.getEdge(), g.e7to6.getEdge(), g.getScEdge(2), 12, false, true),
+                createShortcut(7, 8, g.e7to6.getEdge(), g.e6to8.getEdge(), g.getScEdge(4), g.e6to8.getEdge(), 21, true, false)
         );
     }
 
@@ -543,9 +552,9 @@ public class EdgeBasedNodeContractorTest {
         // multiple turns are restricted, it is best to take the left and the right loop -> three extra shortcuts
         GraphWithTwoLoops g = new GraphWithTwoLoops(3, maxCost, 1, maxCost, 3, maxCost);
         g.contractAndCheckShortcuts(
-                createShortcut(7, 6, g.e7to6.getEdge(), g.e1to6.getEdge(), g.e7to6.getEdge(), g.getScEdge(1), 13),
-                createShortcut(7, 6, g.e7to6.getEdge(), g.e3to6.getEdge(), g.getScEdge(4), g.getScEdge(3), 24),
-                createShortcut(7, 8, g.e7to6.getEdge(), g.e6to8.getEdge(), g.getScEdge(5), g.e6to8.getEdge(), 33)
+                createShortcut(6, 7, g.e7to6.getEdge(), g.e1to6.getEdge(), g.e7to6.getEdge(), g.getScEdge(3), 13, false, true),
+                createShortcut(6, 7, g.e7to6.getEdge(), g.e3to6.getEdge(), g.getScEdge(4), g.getScEdge(2), 24, false, true),
+                createShortcut(7, 8, g.e7to6.getEdge(), g.e6to8.getEdge(), g.getScEdge(5), g.e6to8.getEdge(), 33, true, false)
         );
     }
 
@@ -554,9 +563,9 @@ public class EdgeBasedNodeContractorTest {
         // multiple turns are restricted, it is best to take the right and the left loop -> three extra shortcuts
         GraphWithTwoLoops g = new GraphWithTwoLoops(maxCost, 5, 4, 2, maxCost, maxCost);
         g.contractAndCheckShortcuts(
-                createShortcut(7, 6, g.e7to6.getEdge(), g.e3to6.getEdge(), g.e7to6.getEdge(), g.getScEdge(3), 16),
-                createShortcut(7, 6, g.e7to6.getEdge(), g.e1to6.getEdge(), g.getScEdge(4), g.getScEdge(1), 25),
-                createShortcut(7, 8, g.e7to6.getEdge(), g.e6to8.getEdge(), g.getScEdge(5), g.e6to8.getEdge(), 33)
+                createShortcut(6, 7, g.e7to6.getEdge(), g.e3to6.getEdge(), g.e7to6.getEdge(), g.getScEdge(2), 16, false, true),
+                createShortcut(6, 7, g.e7to6.getEdge(), g.e1to6.getEdge(), g.getScEdge(4), g.getScEdge(3), 25, false, true),
+                createShortcut(7, 8, g.e7to6.getEdge(), g.e6to8.getEdge(), g.getScEdge(5), g.e6to8.getEdge(), 33, true, false)
         );
     }
 
@@ -599,13 +608,13 @@ public class EdgeBasedNodeContractorTest {
         }
 
         private void contractAndCheckShortcuts(Shortcut... shortcuts) {
-            contractNodes(0, 1, 2, 3, 4, 5, 6);
+            contractNodes(0, 1, 2, 3, 4, 5, 6, 9, 10, 7, 8);
             HashSet<Shortcut> expectedShortcuts = new HashSet<>();
             expectedShortcuts.addAll(Arrays.asList(
-                    createShortcut(6, 1, e6to0, e0to1, 7),
-                    createShortcut(6, 6, e6to0.getEdge(), e1to6.getEdge(), getScEdge(0), e1to6.getEdge(), 9),
-                    createShortcut(6, 3, e6to2, e2to3, 3),
-                    createShortcut(6, 6, e6to2.getEdge(), e3to6.getEdge(), getScEdge(2), e3to6.getEdge(), 10)
+                    createShortcut(1, 6, e6to0, e0to1, 7, false, true),
+                    createShortcut(6, 6, e6to0.getEdge(), e1to6.getEdge(), getScEdge(0), e1to6.getEdge(), 9, true, false),
+                    createShortcut(3, 6, e6to2, e2to3, 3, false, true),
+                    createShortcut(6, 6, e6to2.getEdge(), e3to6.getEdge(), getScEdge(1), e3to6.getEdge(), 10, true, false)
             ));
             expectedShortcuts.addAll(Arrays.asList(shortcuts));
             checkShortcuts(expectedShortcuts);
@@ -621,7 +630,7 @@ public class EdgeBasedNodeContractorTest {
         // starting the detour by turning left at node 1 seems expensive but is still worth it because going straight
         // at node 2 when coming from node 1 is worse -> one shortcut required
         GraphWithDetour g = new GraphWithDetour(2, 9, 5, 1);
-        contractNodes(0);
+        contractNodes(0, 4, 3, 1, 2);
         checkShortcuts(
                 createShortcut(1, 2, g.e1to0, g.e0to2, 7)
         );
@@ -631,7 +640,7 @@ public class EdgeBasedNodeContractorTest {
     public void testContractNode_detour_detourIsWorse() {
         // starting the detour is cheap but going left at node 2 is expensive -> no shortcut
         GraphWithDetour g = new GraphWithDetour(4, 1, 1, 7);
-        contractNodes(0);
+        contractNodes(0, 4, 3, 1, 2);
         checkShortcuts();
     }
 
@@ -659,21 +668,21 @@ public class EdgeBasedNodeContractorTest {
     @Test
     public void testContractNode_detour_multipleInOut_needsShortcut() {
         GraphWithDetourMultipleInOutEdges g = new GraphWithDetourMultipleInOutEdges(0, 0, 0, 1, 3);
-        contractNodes(0);
+        contractNodes(0, 2, 5, 6, 7, 1, 3, 4);
         checkShortcuts(createShortcut(1, 4, g.e1to0, g.e0to4, 7));
     }
 
     @Test
     public void testContractNode_detour_multipleInOut_noShortcuts() {
         GraphWithDetourMultipleInOutEdges g = new GraphWithDetourMultipleInOutEdges(0, 0, 0, 0, 0);
-        contractNodes(0);
+        contractNodes(0, 2, 5, 6, 7, 1, 3, 4);
         checkShortcuts();
     }
 
     @Test
     public void testContractNode_detour_multipleInOut_restrictedIn() {
         GraphWithDetourMultipleInOutEdges g = new GraphWithDetourMultipleInOutEdges(0, maxCost, 0, maxCost, 0);
-        contractNodes(0);
+        contractNodes(0, 2, 5, 6, 7, 1, 3, 4);
         checkShortcuts();
     }
 
@@ -706,11 +715,11 @@ public class EdgeBasedNodeContractorTest {
     public void testContractNode_loopAvoidance_loopNecessary() {
         // turning from 3 via 2 to 4 is costly, it is better to take the 2-1-0-2 loop so a loop shortcut is required
         GraphWithLoop g = new GraphWithLoop(7);
-        contractNodes(0, 1);
+        contractNodes(0, 1, 3, 4, 5, 2);
         final int numEdges = 6;
         checkShortcuts(
-                createShortcut(2, 1, g.e2to0, g.e0to1, 3),
-                createShortcut(2, 2, g.e2to0.getEdge(), g.e1to2.getEdge(), numEdges, g.e1to2.getEdge(), 4)
+                createShortcut(1, 2, g.e2to0, g.e0to1, 3, false, true),
+                createShortcut(2, 2, g.e2to0.getEdge(), g.e1to2.getEdge(), numEdges, g.e1to2.getEdge(), 4, true, false)
         );
     }
 
@@ -718,9 +727,9 @@ public class EdgeBasedNodeContractorTest {
     public void testContractNode_loopAvoidance_loopAvoidable() {
         // turning from 3 via 2 to 4 is cheap, it is better to go straight 3-2-4, no loop shortcut necessary
         GraphWithLoop g = new GraphWithLoop(3);
-        contractNodes(0, 1);
+        contractNodes(0, 1, 3, 4, 5, 2);
         checkShortcuts(
-                createShortcut(2, 1, g.e2to0, g.e0to1, 3)
+                createShortcut(1, 2, g.e2to0, g.e0to1, 3, false, true)
         );
     }
 
@@ -763,7 +772,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(7, 10, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 10, 4, 1, 5, 7, 9, 3);
         checkShortcuts();
     }
 
@@ -771,9 +780,9 @@ public class EdgeBasedNodeContractorTest {
     public void testContractNode_noUnnecessaryShortcut_witnessPathOfEqualWeight() {
         // this test runs repeatedly because it might pass/fail by chance (because path lengths are equal)
 
-        // 0 -> 1 -> 5
-        //      v    v 
-        //      2 -> 3 -> 4 -> 5
+        // 0 -> 1 -> 5 <_
+        //      v    v   \
+        //      2 -> 3 -> 4
         graph.edge(0, 1, 1, false);
         graph.edge(1, 2, 1, false);
         graph.edge(1, 5, 1, false);
@@ -783,9 +792,12 @@ public class EdgeBasedNodeContractorTest {
         EdgeIteratorState e5to3 = graph.edge(5, 3, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(3, 2);
+        contractNodes(3, 2, 0, 1, 5, 4);
         // when contracting node 2 there is a witness (1-5-3-4) and no shortcut from 1 to 4 should be introduced.
         // what might be tricky here is that both the original path and the witness path have equal weight!
+        // so we have to make sure that the equal weight witness is not rejected to update the currently best
+        // path, or (depending on the implementation-specific edge traversal order) the original path does *not*
+        // update/overwrite the already found witness path.
         checkShortcuts(
                 createShortcut(2, 4, e2to3, e3to4, 2),
                 createShortcut(5, 4, e5to3, e3to4, 2)
@@ -809,7 +821,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(5, 6, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(3);
+        contractNodes(3, 0, 6, 1, 2, 5, 4);
 
         // We do not need a shortcut here! we can only access node 1 from node 0 and at node 5 we can either go to 
         // node 2,4 or 6. To get to node 6 we can either take the northern witness via 2 or the southern one via 4.
@@ -840,7 +852,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(5, 6, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(3);
+        contractNodes(3, 0, 6, 1, 2, 5, 4);
 
         // We do not need a shortcut here! node 1 can be reached from nodes 0, 2 and 4 and from the target node 5 we can
         // only reach node 6. so coming into node 1 from node 0 we can either go north or south via nodes 2/4 to reach
@@ -852,44 +864,42 @@ public class EdgeBasedNodeContractorTest {
         checkShortcuts();
     }
 
-    @Test
-    public void testContractNode_bidirectional_edge_at_fromNode() {
-        int nodeToContract = 2;
-        // we might come from (5->1) so we still need a way back to (3->4) -> we need a shortcut
-        Shortcut expectedShortcuts = createShortcut(1, 3, 1, 2, 1, 2, 2);
-        runTestWithBidirectionalEdgeAtFromNode(nodeToContract, false, expectedShortcuts);
-    }
-
-    @Test
-    public void testContractNode_bidirectional_edge_at_fromNode_is() {
-        int nodeToContract = 2;
+    @ParameterizedTest
+    @ValueSource(booleans = {true, false})
+    public void testContractNode_bidirectional_edge_at_fromNode(boolean edge1to2bidirectional) {
+        // 0 -> 1 <-> 5
+        //      v     v
+        //      2 --> 3 -> 4
+        graph.edge(0, 1, 1, false);
+        graph.edge(1, 2, 1, edge1to2bidirectional);
+        graph.edge(2, 3, 1, false);
+        graph.edge(3, 4, 1, false);
+        graph.edge(1, 5, 1, true);
+        graph.edge(5, 3, 1, false);
+        graph.freeze();
+        setMaxLevelOnAllNodes();
+        contractNodes(2, 0, 1, 5, 4, 3);
         // we might come from (5->1) so we still need a way back to (3->4) -> we need a shortcut
         Shortcut expectedShortcuts = createShortcut(1, 3, 1, 2, 1, 2, 2);
-        runTestWithBidirectionalEdgeAtFromNode(nodeToContract, true, expectedShortcuts);
+        checkShortcuts(expectedShortcuts);
     }
 
     @Test
     public void testContractNode_bidirectional_edge_at_fromNode_going_to_node() {
-        int nodeToContract = 5;
-        // wherever we come from we can always go via node 2 -> no shortcut needed
-        Shortcut[] expectedShortcuts = new Shortcut[0];
-        runTestWithBidirectionalEdgeAtFromNode(nodeToContract, false, expectedShortcuts);
-    }
-
-    private void runTestWithBidirectionalEdgeAtFromNode(int nodeToContract, boolean edge1to2bidirectional, Shortcut... expectedShortcuts) {
         // 0 -> 1 <-> 5
-        //      v     v 
+        //      v     v
         //      2 --> 3 -> 4
         graph.edge(0, 1, 1, false);
-        graph.edge(1, 2, 1, edge1to2bidirectional);
+        graph.edge(1, 2, 1, false);
         graph.edge(2, 3, 1, false);
         graph.edge(3, 4, 1, false);
         graph.edge(1, 5, 1, true);
         graph.edge(5, 3, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(nodeToContract);
-        checkShortcuts(expectedShortcuts);
+        contractNodes(5, 0, 4, 1, 2, 3);
+        // wherever we come from we can always go via node 2 -> no shortcut needed
+        checkShortcuts();
     }
 
     @Test
@@ -911,15 +921,15 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(7, 11, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2, 6, 3, 5, 4);
+        contractNodes(2, 6, 3, 5, 4, 0, 8, 10, 11, 1, 7, 9);
         // note that the shortcut edge ids depend on the insertion order which might change when changing the implementation
         checkShortcuts(
-                createShortcut(1, 3, 1, 2, 1, 2, 2),
-                createShortcut(1, 9, 1, 8, 1, 8, 2),
-                createShortcut(5, 7, 5, 6, 5, 6, 2),
-                createShortcut(9, 7, 9, 6, 9, 6, 2),
-                createShortcut(1, 4, 1, 3, 13, 3, 3),
-                createShortcut(4, 7, 4, 6, 4, 15, 3)
+                createShortcut(3, 1, 1, 2, 1, 2, 2, false, true),
+                createShortcut(1, 9, 1, 8, 1, 8, 2, true, false),
+                createShortcut(5, 7, 5, 6, 5, 6, 2, true, false),
+                createShortcut(7, 9, 9, 6, 9, 6, 2, false, true),
+                createShortcut(4, 1, 1, 3, 12, 3, 3, false, true),
+                createShortcut(4, 7, 4, 6, 4, 13, 3, true, false)
         );
     }
 
@@ -940,7 +950,7 @@ public class EdgeBasedNodeContractorTest {
         setTurnCost(5, 3, 4, 2);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 4, 1, 3, 5);
         checkShortcuts();
     }
 
@@ -963,9 +973,9 @@ public class EdgeBasedNodeContractorTest {
 
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(3);
+        contractNodes(3, 0, 5, 1, 4, 2);
         checkShortcuts(
-                createShortcut(2, 4, 2, 3, 2, 3, 2)
+                createShortcut(4, 2, 2, 3, 2, 3, 2, false, true)
         );
     }
 
@@ -987,7 +997,7 @@ public class EdgeBasedNodeContractorTest {
 
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 5, 1, 4, 3);
         checkShortcuts(
                 createShortcut(1, 3, 1, 2, 1, 2, 2)
         );
@@ -1004,7 +1014,7 @@ public class EdgeBasedNodeContractorTest {
         setTurnCost(edge1, edge0, 0, 2);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(0);
+        contractNodes(0, 2, 1);
         // it is sufficient to be able to travel the 1-0-1 loop in one (the cheaper) direction
         checkShortcuts(
                 createShortcut(1, 1, 0, 1, 0, 1, 7)
@@ -1032,23 +1042,23 @@ public class EdgeBasedNodeContractorTest {
         setTurnCost(e5, e2, 5, 1);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(4, 5);
+        contractNodes(4, 5, 1, 3, 2);
         // note that the shortcut edge ids depend on the insertion order which might change when changing the implementation
         checkNumShortcuts(11);
         checkShortcuts(
                 // from node 4 contraction
-                createShortcut(5, 3, 5, 4, 5, 4, 66),
-                createShortcut(3, 5, 4, 5, 4, 5, 66),
-                createShortcut(2, 3, 1, 4, 1, 4, 29),
-                createShortcut(3, 2, 4, 1, 4, 1, 29),
-                createShortcut(2, 5, 1, 5, 1, 5, 75),
-                createShortcut(5, 2, 5, 1, 5, 1, 75),
+                createShortcut(5, 3, 5, 4, 5, 4, 66, true, false),
+                createShortcut(5, 3, 4, 5, 4, 5, 66, false, true),
+                createShortcut(3, 2, 1, 4, 1, 4, 29, false, true),
+                createShortcut(3, 2, 4, 1, 4, 1, 29, true, false),
+                createShortcut(5, 2, 1, 5, 1, 5, 75, false, true),
+                createShortcut(5, 2, 5, 1, 5, 1, 75, true, false),
                 // from node 5 contraction
-                createShortcut(2, 2, 3, 2, 3, 2, 99),
-                createShortcut(2, 2, 3, 1, 3, 7, 134),
-                createShortcut(2, 2, 1, 2, 10, 2, 114),
-                createShortcut(2, 3, 2, 4, 2, 6, 106),
-                createShortcut(3, 2, 4, 2, 8, 2, 105)
+                createShortcut(2, 2, 3, 2, 3, 2, 99, true, false),
+                createShortcut(2, 2, 3, 1, 3, 6, 134, true, false),
+                createShortcut(2, 2, 1, 2, 9, 2, 114, true, false),
+                createShortcut(3, 2, 2, 4, 2, 7, 106, false, true),
+                createShortcut(3, 2, 4, 2, 8, 2, 105, true, false)
         );
     }
 
@@ -1059,7 +1069,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(0, 1, 3.5, true);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(1);
+        contractNodes(1, 0);
         checkShortcuts(
                 createShortcut(0, 0, 1, 2, 1, 2, 5.5),
                 createShortcut(0, 0, 0, 2, 0, 2, 4.5),
@@ -1080,7 +1090,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(1, 3, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 1, 3);
         checkShortcuts();
     }
 
@@ -1103,16 +1113,17 @@ public class EdgeBasedNodeContractorTest {
         setRestriction(0, 4, 1);
         setTurnCost(4, 2, 3, 4);
         setTurnCost(3, 2, 4, 2);
-        contractNodes(2);
+        contractNodes(2, 0, 1, 4, 3);
         checkShortcuts(
-                createShortcut(4, 3, 3, 2, 3, 2, 6),
-                createShortcut(3, 4, 2, 3, 2, 3, 4)
+                createShortcut(4, 3, 3, 2, 3, 2, 6, true, false),
+                createShortcut(4, 3, 2, 3, 2, 3, 4, false, true)
         );
     }
 
     @Test
     public void testFindPath_finiteUTurnCost() {
-        chGraph = PrepareCHGraph.edgeBased(graph.getCHGraph(chConfigs.get(1).getName()), chConfigs.get(1).getWeighting());
+        chGraph = graph.getCHGraph(chConfigs.get(1).getName());
+        weighting = chGraph.getCHConfig().getWeighting();
         // turning to 1 at node 3 when coming from 0 is forbidden, but taking the full loop 3-4-2-3 is very
         // expensive, so the best solution is to go straight to 4 and take a u-turn there
         //   1
@@ -1128,10 +1139,10 @@ public class EdgeBasedNodeContractorTest {
         graph.freeze();
         setMaxLevelOnAllNodes();
         setRestriction(0, 3, 1);
-        contractNodes(4);
+        contractNodes(4, 0, 1, 2, 3);
         checkShortcuts(
-                createShortcut(3, 2, 1, 2, 1, 2, 600),
-                createShortcut(3, 3, 1, 1, 1, 1, 260)
+                createShortcut(2, 3, 1, 2, 1, 2, 600, false, true),
+                createShortcut(3, 3, 1, 1, 1, 1, 260, true, false)
         );
     }
 
@@ -1148,7 +1159,7 @@ public class EdgeBasedNodeContractorTest {
         setRestriction(3, 2, 4);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(0);
+        contractNodes(0, 3, 4, 2, 1);
         checkNumShortcuts(1);
     }
 
@@ -1165,7 +1176,7 @@ public class EdgeBasedNodeContractorTest {
         setRestriction(edge0, edge2, 1);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 4, 1, 3);
         checkShortcuts(
                 // we need a shortcut going from 1 to 3, but this is not entirely trivial, because it is crucial that
                 // the loop at node 1 is recognized as an incoming edge at node 1 although it is only 'unidirectional',
@@ -1183,7 +1194,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(3, 4, 05.003, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 1, 3, 4);
         checkShortcuts(
                 createShortcut(1, 3, 1, 2, 1, 2, 145.847)
         );
@@ -1200,7 +1211,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(3, 3, 0, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 1, 3);
         checkShortcuts(
                 createShortcut(1, 3, 1, 2, 1, 2, 2)
         );
@@ -1219,7 +1230,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(3, 4, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 1, 4, 3);
         checkShortcuts(
                 createShortcut(1, 3, 1, 2, 1, 2, 2)
         );
@@ -1237,7 +1248,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(3, 3, 0, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 1, 3);
         checkShortcuts(
                 createShortcut(1, 3, 1, 2, 1, 2, 2)
         );
@@ -1257,7 +1268,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(3, 4, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 1, 4, 3);
         checkShortcuts(
                 createShortcut(1, 3, 1, 2, 1, 2, 2)
         );
@@ -1277,7 +1288,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(3, 4, 1, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 1, 4, 3);
         checkShortcuts(
                 createShortcut(1, 3, 1, 4, 1, 4, 2)
         );
@@ -1301,7 +1312,7 @@ public class EdgeBasedNodeContractorTest {
         graph.edge(3, 3, 0, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 1, 4, 3);
         checkShortcuts(
                 createShortcut(1, 3, 3, 5, 3, 5, 2)
         );
@@ -1326,7 +1337,7 @@ public class EdgeBasedNodeContractorTest {
         setRestriction(edge2, edge4, 3);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        contractNodes(2);
+        contractNodes(2, 0, 4, 1, 3);
         checkNumShortcuts(1);
     }
 
@@ -1344,6 +1355,7 @@ public class EdgeBasedNodeContractorTest {
         setMaxLevelOnAllNodes();
         EdgeBasedNodeContractor nodeContractor = createNodeContractor();
         nodeContractor.contractNode(0);
+        assertTrue(nodeContractor.getNumPolledEdges() > 0, "no polled edges, something is wrong");
         assertTrue(nodeContractor.getNumPolledEdges() <= 8, "too many edges polled: " + nodeContractor.getNumPolledEdges());
     }
 
@@ -1358,6 +1370,7 @@ public class EdgeBasedNodeContractorTest {
             nodeContractor.contractNode(node);
             chGraph.setLevel(node, node);
         }
+        nodeContractor.finishContraction();
     }
 
     /**
@@ -1370,10 +1383,15 @@ public class EdgeBasedNodeContractorTest {
             nodeContractor.contractNode(nodes[i]);
             chGraph.setLevel(nodes[i], i);
         }
+        nodeContractor.finishContraction();
     }
 
     private EdgeBasedNodeContractor createNodeContractor() {
-        EdgeBasedNodeContractor nodeContractor = new EdgeBasedNodeContractor(chGraph, new PMap());
+        CHPreparationGraph.TurnCostFunction turnCostFunction = CHPreparationGraph.buildTurnCostFunctionFromTurnCostStorage(graph, weighting);
+        CHPreparationGraph prepareGraph = CHPreparationGraph.edgeBased(graph.getNodes(), graph.getEdges(), turnCostFunction);
+        CHPreparationGraph.buildFromGraph(prepareGraph, graph, weighting);
+        EdgeBasedNodeContractor.ShortcutHandler shortcutInserter = new EdgeBasedShortcutInserter(chGraph);
+        EdgeBasedNodeContractor nodeContractor = new EdgeBasedNodeContractor(prepareGraph, shortcutInserter, new PMap());
         nodeContractor.initFromGraph();
         return nodeContractor;
     }
@@ -1400,12 +1418,18 @@ public class EdgeBasedNodeContractorTest {
     }
 
     private Shortcut createShortcut(int from, int to, EdgeIteratorState edge1, EdgeIteratorState edge2, double weight) {
-        return createShortcut(from, to, edge1.getEdge(), edge2.getEdge(), edge1.getEdge(), edge2.getEdge(), weight);
+        return createShortcut(from, to, edge1, edge2, weight, true, false);
+    }
+
+    private Shortcut createShortcut(int from, int to, EdgeIteratorState edge1, EdgeIteratorState edge2, double weight, boolean fwd, boolean bwd) {
+        return createShortcut(from, to, edge1.getEdge(), edge2.getEdge(), edge1.getEdge(), edge2.getEdge(), weight, fwd, bwd);
     }
 
     private Shortcut createShortcut(int from, int to, int firstOrigEdge, int lastOrigEdge, int skipEdge1, int skipEdge2, double weight) {
-        boolean fwd = true;
-        boolean bwd = false;
+        return createShortcut(from, to, firstOrigEdge, lastOrigEdge, skipEdge1, skipEdge2, weight, true, false);
+    }
+
+    private Shortcut createShortcut(int from, int to, int firstOrigEdge, int lastOrigEdge, int skipEdge1, int skipEdge2, double weight, boolean fwd, boolean bwd) {
         return new Shortcut(from, to, firstOrigEdge, lastOrigEdge, skipEdge1, skipEdge2, weight, fwd, bwd);
     }
 
diff --git a/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedWitnessPathSearcherTest.java b/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedWitnessPathSearcherTest.java
index 8d5601024..92b868947 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedWitnessPathSearcherTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedWitnessPathSearcherTest.java
@@ -60,10 +60,10 @@ public class EdgeBasedWitnessPathSearcherTest {
         setMaxLevelOnAllNodes();
         EdgeBasedWitnessPathSearcher finder = createFinder();
         finder.initSearch(2, 1, 0);
-        CHEntry result = finder.runSearch(3, 3);
-        CHEntry expected = new ExpectedResultBuilder(3, 2, 2, 2.0)
-                .withParent(2, 1, 1, 1.0)
-                .build(1);
+        PrepareCHEntry result = finder.runSearch(3, 3);
+        PrepareCHEntry expected = new ExpectedResultBuilder(3, 2, 4, 2.0)
+                .withParent(2, 1, 2, 1.0)
+                .build(2);
         assertFinderResult(expected, result);
     }
 
@@ -78,10 +78,10 @@ public class EdgeBasedWitnessPathSearcherTest {
         setMaxLevelOnAllNodes();
         EdgeBasedWitnessPathSearcher finder = createFinder();
         finder.initSearch(2, 1, 0);
-        CHEntry result = finder.runSearch(3, 3);
-        CHEntry expected = new ExpectedResultBuilder(3, 2, 2, 2.0)
-                .withParent(2, 1, 1, 1.0)
-                .build(1);
+        PrepareCHEntry result = finder.runSearch(3, 3);
+        PrepareCHEntry expected = new ExpectedResultBuilder(3, 2, 4, 2.0)
+                .withParent(2, 1, 2, 1.0)
+                .build(2);
         assertFinderResult(expected, result);
     }
 
@@ -100,7 +100,7 @@ public class EdgeBasedWitnessPathSearcherTest {
         setMaxLevelOnAllNodes();
         EdgeBasedWitnessPathSearcher finder = createFinder();
         finder.initSearch(2, 1, 0);
-        CHEntry result = finder.runSearch(3, 3);
+        PrepareCHEntry result = finder.runSearch(3, 3);
         assertNull(result);
     }
 
@@ -119,12 +119,14 @@ public class EdgeBasedWitnessPathSearcherTest {
         setMaxLevelOnAllNodes();
         EdgeBasedWitnessPathSearcher finder = createFinder();
         finder.initSearch(2, 1, 0);
-        CHEntry result = finder.runSearch(3, 3);
+        PrepareCHEntry result = finder.runSearch(3, 3);
         assertNull(result);
     }
 
     private EdgeBasedWitnessPathSearcher createFinder() {
-        PrepareCHGraph prepareGraph = PrepareCHGraph.edgeBased(chGraph, weighting);
+        CHPreparationGraph.TurnCostFunction turnCostFunction = CHPreparationGraph.buildTurnCostFunctionFromTurnCostStorage(graph, weighting);
+        CHPreparationGraph prepareGraph = CHPreparationGraph.edgeBased(graph.getNodes(), graph.getEdges(), turnCostFunction);
+        CHPreparationGraph.buildFromGraph(prepareGraph, graph, weighting);
         return new EdgeBasedWitnessPathSearcher(prepareGraph, new PMap());
     }
 
@@ -135,11 +137,11 @@ public class EdgeBasedWitnessPathSearcherTest {
         }
     }
 
-    private void assertFinderResult(CHEntry expected, CHEntry result) {
+    private void assertFinderResult(PrepareCHEntry expected, PrepareCHEntry result) {
         while (expected.parent != null) {
             assertEquals(expected.adjNode, result.adjNode);
-            assertEquals(expected.edge, result.edge);
-            assertEquals(expected.incEdge, result.incEdge);
+            assertEquals(expected.prepareEdge, result.prepareEdge);
+            assertEquals(expected.incEdgeKey, result.incEdgeKey);
             assertEquals(expected.weight, result.weight, 1.e-6);
             expected = expected.getParent();
             result = result.getParent();
@@ -147,23 +149,23 @@ public class EdgeBasedWitnessPathSearcherTest {
     }
 
     private static class ExpectedResultBuilder {
-        private CHEntry result;
-        private CHEntry last;
+        private final PrepareCHEntry result;
+        private PrepareCHEntry last;
 
-        private ExpectedResultBuilder(int adjNode, int edge, int incEdge, double weight) {
-            result = new CHEntry(edge, incEdge, adjNode, weight);
+        private ExpectedResultBuilder(int adjNode, int edge, int incKey, double weight) {
+            result = new PrepareCHEntry(edge, incKey, adjNode, weight);
             last = result;
         }
 
-        ExpectedResultBuilder withParent(int adjNode, int edge, int incEdge, double weight) {
-            CHEntry parent = new CHEntry(edge, incEdge, adjNode, weight);
+        ExpectedResultBuilder withParent(int adjNode, int edge, int incKey, double weight) {
+            PrepareCHEntry parent = new PrepareCHEntry(edge, incKey, adjNode, weight);
             last.parent = parent;
             last = parent;
             return this;
         }
 
-        CHEntry build(int firstEdge) {
-            last.parent = new CHEntry(EdgeIterator.NO_EDGE, firstEdge, -1, 0.0);
+        PrepareCHEntry build(int firstKey) {
+            last.parent = new PrepareCHEntry(EdgeIterator.NO_EDGE, firstKey, -1, 0.0);
             return result;
         }
 
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 3eb95ada7..6d760cf65 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/NodeBasedNodeContractorTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ch/NodeBasedNodeContractorTest.java
@@ -35,13 +35,15 @@ import com.graphhopper.util.CHEdgeIteratorState;
 import com.graphhopper.util.EdgeIteratorState;
 import com.graphhopper.util.PMap;
 import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
 
 import java.util.Arrays;
 import java.util.HashSet;
 import java.util.Objects;
 import java.util.Set;
 
-import static org.junit.jupiter.api.Assertions.*;
+import static org.junit.Assert.*;
 
 public class NodeBasedNodeContractorTest {
     // TODO integrate this into CHGraphImpl somehow
@@ -56,27 +58,29 @@ public class NodeBasedNodeContractorTest {
     private final Weighting weighting = new ShortestWeighting(encoder);
     private final GraphHopperStorage graph = new GraphBuilder(encodingManager).setCHConfigs(CHConfig.nodeBased("profile", weighting)).create();
     private final CHGraph lg = graph.getCHGraph();
-    private final PrepareCHGraph pg = PrepareCHGraph.nodeBased(lg, weighting);
 
     private NodeContractor createNodeContractor() {
-        return createNodeContractor(pg);
+        return createNodeContractor(lg);
     }
 
-    private NodeContractor createNodeContractor(PrepareCHGraph chGraph) {
-        NodeContractor nodeContractor = new NodeBasedNodeContractor(chGraph, new PMap());
+    private NodeContractor createNodeContractor(CHGraph chGraph) {
+        CHPreparationGraph prepareGraph = CHPreparationGraph.nodeBased(chGraph.getNodes(), chGraph.getOriginalEdges());
+        CHPreparationGraph.buildFromGraph(prepareGraph, chGraph.getBaseGraph(), chGraph.getCHConfig().getWeighting());
+        NodeBasedNodeContractor.ShortcutHandler shortcutInserter = new NodeBasedShortcutHandler(chGraph);
+        NodeContractor nodeContractor = new NodeBasedNodeContractor(prepareGraph, shortcutInserter, new PMap());
         nodeContractor.initFromGraph();
         nodeContractor.prepareContraction();
         return nodeContractor;
     }
 
-    @Test
-    public void testDirectedGraph() {
+    @ParameterizedTest
+    @ValueSource(booleans = {true, false})
+    public void testDirectedGraph(boolean reverse) {
         //5 6 7
         // \|/
         //4-3_1<-\ 10
         //     \_|/
         //   0___2_11
-
         graph.edge(0, 2, 2, true);
         graph.edge(10, 2, 2, true);
         graph.edge(11, 2, 2, true);
@@ -92,13 +96,16 @@ public class NodeBasedNodeContractorTest {
 
         setMaxLevelOnAllNodes();
 
-        // find all shortcuts if we contract node 1
-        NodeContractor nodeContractor = createNodeContractor();
-        nodeContractor.contractNode(1);
-        checkShortcuts(
-                expectedShortcut(3, 2, edge1to3, edge2to1bidirected, true, true),
-                expectedShortcut(2, 3, edge2to1directed, edge1to3, true, false)
-        );
+        // find all shortcuts if we contract node 1 first, the order in which we contract nodes 2 and 3 decides
+        // what kind of shortcut is added. in any case it uses the shorter bidirected edge instead of the longer
+        // directed one
+        if (reverse) {
+            contractInOrder(1, 0, 11, 10, 4, 5, 6, 7, 3, 2);
+            checkShortcuts(expectedShortcut(3, 2, edge1to3, edge2to1bidirected, true, true));
+        } else {
+            contractInOrder(1, 0, 11, 10, 4, 5, 6, 7, 2, 3);
+            checkShortcuts(expectedShortcut(2, 3, edge2to1bidirected, edge1to3, true, true));
+        }
     }
 
     @Test
@@ -115,58 +122,52 @@ public class NodeBasedNodeContractorTest {
         graph.edge(6, 7, 1, true);
         graph.freeze();
 
-        int sc1to4 = pg.shortcut(1, 4, PrepareEncoder.getScDirMask(), 2, iter1to3.getEdge(), iter3to4.getEdge());
-        int sc4to6 = pg.shortcut(4, 6, PrepareEncoder.getScFwdDir(), 2, iter4to5.getEdge(), iter5to6.getEdge());
-        int sc6to4 = pg.shortcut(6, 4, PrepareEncoder.getScFwdDir(), 3, iter6to8.getEdge(), iter8to4.getEdge());
-
-        setMaxLevelOnAllNodes();
-
-        pg.setLevel(3, 3);
-        pg.setLevel(5, 5);
-        pg.setLevel(7, 7);
-        pg.setLevel(8, 8);
-
-        Shortcut manualSc1 = expectedShortcut(1, 4, iter1to3, iter3to4, true, true);
-        Shortcut manualSc2 = expectedShortcut(4, 6, iter4to5, iter5to6, true, false);
-        Shortcut manualSc3 = expectedShortcut(6, 4, iter6to8, iter8to4, true, false);
-        checkShortcuts(manualSc1, manualSc2, manualSc3);
-
-        // after 'manual contraction' of nodes 3, 5, 8 the graph looks like:
+        contractInOrder(3, 5, 7, 8, 4, 1, 6);
+        // note: after contraction of nodes 3, 5, 8 the graph looks like this:
         // 1 -- 4 -->-- 6 -- 7
         //       \      |
         //        --<----
 
-        // contract node 4!
-        NodeContractor nodeContractor = createNodeContractor();
-        nodeContractor.contractNode(4);
-        checkShortcuts(manualSc1, manualSc2, manualSc3,
+        checkShortcuts(
+                expectedShortcut(4, 1, iter3to4, iter1to3, true, true),
+                expectedShortcut(4, 6, iter8to4, iter6to8, false, true),
+                expectedShortcut(4, 6, iter4to5, iter5to6, true, false),
                 // there should be two different shortcuts for both directions!
-                expectedShortcut(1, 6, lg.getEdgeIteratorState(sc1to4, 4), lg.getEdgeIteratorState(sc4to6, 6), true, false),
-                expectedShortcut(6, 1, lg.getEdgeIteratorState(sc6to4, 4), lg.getEdgeIteratorState(sc1to4, 1), true, false)
+                expectedShortcut(1, 6, lg.getEdgeIteratorState(7, 4), lg.getEdgeIteratorState(8, 6), true, false),
+                expectedShortcut(1, 6, lg.getEdgeIteratorState(7, 1), lg.getEdgeIteratorState(9, 4), false, true)
         );
     }
 
-    @Test
-    public void testShortcutMergeBug() {
+    @ParameterizedTest
+    @ValueSource(booleans = {true, false})
+    public void testShortcutMergeBug(boolean reverse) {
         // We refer to this real world situation http://www.openstreetmap.org/#map=19/52.71205/-1.77326
         // assume the following graph:
         //
         // ---1---->----2-----3
         //    \--------/
         //
-        // where there are two roads from 1 to 2 and the directed road has a smaller weight
-        // leading to two shortcuts sc1 (unidir) and sc2 (bidir) where the second should NOT be rejected due to the larger weight
+        // where there are two roads from 1 to 2 and the directed road has a smaller weight. to get from 2 to 1 we
+        // have to use the bidirectional edge despite the higher weight and therefore we need an extra shortcut for
+        // this.
         final EdgeIteratorState edge1to2bidirected = graph.edge(1, 2, 2, true);
         final EdgeIteratorState edge1to2directed = graph.edge(1, 2, 1, false);
         final EdgeIteratorState edge2to3 = graph.edge(2, 3, 1, true);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        NodeContractor nodeContractor = createNodeContractor();
-        nodeContractor.contractNode(2);
-        checkShortcuts(
-                expectedShortcut(3, 1, edge2to3, edge1to2bidirected, true, true),
-                expectedShortcut(1, 3, edge1to2directed, edge2to3, true, false)
-        );
+        if (reverse) {
+            contractInOrder(2, 1, 3);
+            checkShortcuts(
+                    expectedShortcut(1, 3, edge1to2directed, edge2to3, true, false),
+                    expectedShortcut(1, 3, edge1to2bidirected, edge2to3, false, true)
+            );
+        } else {
+            contractInOrder(2, 3, 1);
+            checkShortcuts(
+                    expectedShortcut(3, 1, edge2to3, edge1to2bidirected, true, false),
+                    expectedShortcut(3, 1, edge2to3, edge1to2directed, false, true)
+            );
+        }
     }
 
     @Test
@@ -176,7 +177,7 @@ public class NodeBasedNodeContractorTest {
         final EdgeIteratorState edge2 = graph.edge(1, 2, 2, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        createNodeContractor().contractNode(1);
+        contractInOrder(1, 0, 2);
         checkShortcuts(expectedShortcut(0, 2, edge1, edge2, true, false));
     }
 
@@ -187,7 +188,7 @@ public class NodeBasedNodeContractorTest {
         final EdgeIteratorState edge2 = graph.edge(1, 0, 2, false);
         graph.freeze();
         setMaxLevelOnAllNodes();
-        createNodeContractor().contractNode(1);
+        contractInOrder(1, 2, 0);
         checkShortcuts(expectedShortcut(2, 0, edge1, edge2, true, false));
     }
 
@@ -197,8 +198,7 @@ public class NodeBasedNodeContractorTest {
         final EdgeIteratorState edge1 = graph.edge(0, 1, 1, true);
         final EdgeIteratorState edge2 = graph.edge(1, 2, 2, true);
         graph.freeze();
-        setMaxLevelOnAllNodes();
-        createNodeContractor().contractNode(1);
+        contractInOrder(1, 2, 0);
         checkShortcuts(expectedShortcut(2, 0, edge2, edge1, true, true));
     }
 
@@ -217,7 +217,7 @@ public class NodeBasedNodeContractorTest {
 
     @Test
     public void testNodeContraction_shortcutDistanceRounding() {
-        assertTrue(weighting instanceof ShortestWeighting, "this test was constructed assuming we are using the ShortestWeighting");
+        assertTrue("this test was constructed assuming we are using the ShortestWeighting", weighting instanceof ShortestWeighting);
         // 0 ------------> 4
         //  \             /
         //   1 --> 2 --> 3
@@ -259,7 +259,7 @@ public class NodeBasedNodeContractorTest {
         // 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, 0, edge2, edge1, false, true),
                 expectedShortcut(2, 4, edge3, edge4, true, false)
         );
     }
@@ -274,7 +274,6 @@ public class NodeBasedNodeContractorTest {
         Weighting weighting = new FastestWeighting(encoder);
         GraphHopperStorage graph = new GraphBuilder(encodingManager).setCHConfigs(CHConfig.nodeBased("p1", weighting)).create();
         CHGraph lg = graph.getCHGraph();
-        PrepareCHGraph pg = PrepareCHGraph.nodeBased(lg, weighting);
         // 0 ------------> 4
         //  \             /
         //   1 --> 2 --> 3
@@ -286,10 +285,10 @@ public class NodeBasedNodeContractorTest {
         graph.edge(2, 3, distances[3], false);
         graph.edge(3, 4, distances[4], false);
         graph.freeze();
-        setMaxLevelOnAllNodes(pg);
+        setMaxLevelOnAllNodes(lg);
 
         // perform CH contraction
-        contractInOrder(pg, 1, 3, 2, 0, 4);
+        contractInOrder(lg, 1, 3, 2, 0, 4);
 
         // first we compare dijkstra with CH to make sure they produce the same results
         int from = 0;
@@ -313,7 +312,6 @@ public class NodeBasedNodeContractorTest {
         Weighting weighting = new FastestWeighting(encoder);
         GraphHopperStorage graph = new GraphBuilder(encodingManager).setCHConfigs(CHConfig.nodeBased("p1", weighting)).create();
         CHGraph lg = graph.getCHGraph();
-        PrepareCHGraph pg = PrepareCHGraph.nodeBased(lg, weighting);
         // 0 - 1 - 2 - 3
         // o           o
         graph.edge(0, 1, 1, true);
@@ -323,18 +321,18 @@ public class NodeBasedNodeContractorTest {
         graph.edge(3, 3, 1, true);
 
         graph.freeze();
-        setMaxLevelOnAllNodes(pg);
-        NodeContractor nodeContractor = createNodeContractor(pg);
+        setMaxLevelOnAllNodes(lg);
+        NodeContractor nodeContractor = createNodeContractor(lg);
         nodeContractor.contractNode(0);
         nodeContractor.contractNode(3);
-        checkNoShortcuts(pg);
+        checkNoShortcuts(lg);
     }
 
     private void contractInOrder(int... nodeIds) {
-        contractInOrder(pg, nodeIds);
+        contractInOrder(lg, nodeIds);
     }
 
-    private void contractInOrder(PrepareCHGraph chGraph, int... nodeIds) {
+    private void contractInOrder(CHGraph chGraph, int... nodeIds) {
         NodeContractor nodeContractor = createNodeContractor(chGraph);
         int level = 0;
         for (int n : nodeIds) {
@@ -342,16 +340,17 @@ public class NodeBasedNodeContractorTest {
             chGraph.setLevel(n, level);
             level++;
         }
+        nodeContractor.finishContraction();
     }
 
     /**
      * Queries the ch graph and checks if the graph's shortcuts match the given expected shortcuts.
      */
     private void checkShortcuts(Shortcut... expectedShortcuts) {
-        checkShortcuts(pg, expectedShortcuts);
+        checkShortcuts(lg, expectedShortcuts);
     }
 
-    private void checkShortcuts(PrepareCHGraph chGraph, Shortcut... expectedShortcuts) {
+    private void checkShortcuts(CHGraph chGraph, Shortcut... expectedShortcuts) {
         Set<Shortcut> expected = setOf(expectedShortcuts);
         if (expected.size() != expectedShortcuts.length) {
             fail("was given duplicate shortcuts");
@@ -370,10 +369,10 @@ public class NodeBasedNodeContractorTest {
     }
 
     private void checkNoShortcuts() {
-        checkShortcuts(pg);
+        checkShortcuts(lg);
     }
 
-    private void checkNoShortcuts(PrepareCHGraph chGraph) {
+    private void checkNoShortcuts(CHGraph chGraph) {
         checkShortcuts(chGraph);
     }
 
@@ -398,10 +397,10 @@ public class NodeBasedNodeContractorTest {
     }
 
     private void setMaxLevelOnAllNodes() {
-        setMaxLevelOnAllNodes(pg);
+        setMaxLevelOnAllNodes(lg);
     }
 
-    private void setMaxLevelOnAllNodes(PrepareCHGraph chGraph) {
+    private void setMaxLevelOnAllNodes(CHGraph chGraph) {
         int nodes = chGraph.getNodes();
         for (int node = 0; node < nodes; node++) {
             chGraph.setLevel(node, nodes);
diff --git a/core/src/test/java/com/graphhopper/routing/ch/NodeBasedWitnessPathSearcherTest.java b/core/src/test/java/com/graphhopper/routing/ch/NodeBasedWitnessPathSearcherTest.java
index 7a5602208..2bef69b5b 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/NodeBasedWitnessPathSearcherTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ch/NodeBasedWitnessPathSearcherTest.java
@@ -39,30 +39,14 @@ class NodeBasedWitnessPathSearcherTest {
     private final Weighting weighting = new ShortestWeighting(encoder);
     private final GraphHopperStorage graph = new GraphBuilder(encodingManager).setCHConfigs(CHConfig.nodeBased("profile", weighting)).create();
     private final CHGraph lg = graph.getCHGraph();
-    private final PrepareCHGraph pg = PrepareCHGraph.nodeBased(lg, weighting);
-
-    private void createExampleGraph() {
-        //5-1-----2
-        //   \ __/|
-        //    0   |
-        //   /    |
-        //  4-----3
-        //
-        graph.edge(0, 1, 1, true);
-        graph.edge(0, 2, 1, true);
-        graph.edge(0, 4, 3, true);
-        graph.edge(1, 2, 3, true);
-        graph.edge(2, 3, 1, true);
-        graph.edge(4, 3, 2, true);
-        graph.edge(5, 1, 2, true);
-        graph.freeze();
-    }
 
     @Test
     public void testShortestPathSkipNode() {
         createExampleGraph();
+        CHPreparationGraph prepareGraph = CHPreparationGraph.nodeBased(graph.getNodes(), graph.getEdges());
+        CHPreparationGraph.buildFromGraph(prepareGraph, graph, weighting);
         final double normalDist = new Dijkstra(graph, weighting, TraversalMode.NODE_BASED).calcPath(4, 2).getDistance();
-        NodeBasedWitnessPathSearcher algo = new NodeBasedWitnessPathSearcher(pg);
+        NodeBasedWitnessPathSearcher algo = new NodeBasedWitnessPathSearcher(prepareGraph);
 
         setMaxLevelOnAllNodes();
 
@@ -80,9 +64,11 @@ class NodeBasedWitnessPathSearcherTest {
     @Test
     public void testShortestPathSkipNode2() {
         createExampleGraph();
+        CHPreparationGraph prepareGraph = CHPreparationGraph.nodeBased(graph.getNodes(), graph.getEdges());
+        CHPreparationGraph.buildFromGraph(prepareGraph, graph, weighting);
         final double normalDist = new Dijkstra(graph, weighting, TraversalMode.NODE_BASED).calcPath(4, 2).getDistance();
         assertEquals(3, normalDist, 1e-5);
-        NodeBasedWitnessPathSearcher algo = new NodeBasedWitnessPathSearcher(pg);
+        NodeBasedWitnessPathSearcher algo = new NodeBasedWitnessPathSearcher(prepareGraph);
 
         setMaxLevelOnAllNodes();
 
@@ -98,7 +84,9 @@ class NodeBasedWitnessPathSearcherTest {
     @Test
     public void testShortestPathLimit() {
         createExampleGraph();
-        NodeBasedWitnessPathSearcher algo = new NodeBasedWitnessPathSearcher(pg);
+        CHPreparationGraph prepareGraph = CHPreparationGraph.nodeBased(graph.getNodes(), graph.getEdges());
+        CHPreparationGraph.buildFromGraph(prepareGraph, graph, weighting);
+        NodeBasedWitnessPathSearcher algo = new NodeBasedWitnessPathSearcher(prepareGraph);
 
         setMaxLevelOnAllNodes();
 
@@ -109,11 +97,27 @@ class NodeBasedWitnessPathSearcherTest {
         assertNotEquals(1, endNode);
     }
 
+    private void createExampleGraph() {
+        //5-1-----2
+        //   \ __/|
+        //    0   |
+        //   /    |
+        //  4-----3
+        //
+        graph.edge(0, 1, 1, true);
+        graph.edge(0, 2, 1, true);
+        graph.edge(0, 4, 3, true);
+        graph.edge(1, 2, 3, true);
+        graph.edge(2, 3, 1, true);
+        graph.edge(4, 3, 2, true);
+        graph.edge(5, 1, 2, true);
+        graph.freeze();
+    }
+
     private void setMaxLevelOnAllNodes() {
-        int nodes = pg.getNodes();
+        int nodes = lg.getNodes();
         for (int node = 0; node < nodes; node++) {
-            pg.setLevel(node, nodes);
+            lg.setLevel(node, nodes);
         }
     }
-
 }
\ No newline at end of file
diff --git a/core/src/test/java/com/graphhopper/routing/ch/PrepareEncoderTest.java b/core/src/test/java/com/graphhopper/routing/ch/PrepareEncoderTest.java
deleted file mode 100644
index 8fd7f249a..000000000
--- a/core/src/test/java/com/graphhopper/routing/ch/PrepareEncoderTest.java
+++ /dev/null
@@ -1,47 +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 org.junit.Test;
-
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertFalse;
-import static org.junit.Assert.assertTrue;
-
-/**
- * @author Peter Karich
- */
-public class PrepareEncoderTest {
-
-    @Test
-    public void testOverwrite() {
-        int forward = PrepareEncoder.getScFwdDir();
-        int backward = PrepareEncoder.getScFwdDir() ^ PrepareEncoder.getScDirMask();
-        int both = PrepareEncoder.getScDirMask();
-        assertEquals(1, PrepareEncoder.getScMergeStatus(forward, forward));
-        assertEquals(1, PrepareEncoder.getScMergeStatus(backward, backward));
-        assertEquals(2, PrepareEncoder.getScMergeStatus(forward, both));
-        assertEquals(2, PrepareEncoder.getScMergeStatus(backward, both));
-
-        assertEquals(1, PrepareEncoder.getScMergeStatus(both, both));
-        assertEquals(0, PrepareEncoder.getScMergeStatus(both, forward));
-        assertEquals(0, PrepareEncoder.getScMergeStatus(both, backward));
-        assertEquals(0, PrepareEncoder.getScMergeStatus(forward, backward));
-        assertEquals(0, PrepareEncoder.getScMergeStatus(backward, forward));
-    }
-}
diff --git a/core/src/test/java/com/graphhopper/routing/ch/SplitArray2DTest.java b/core/src/test/java/com/graphhopper/routing/ch/SplitArray2DTest.java
new file mode 100644
index 000000000..09ff7d0cb
--- /dev/null
+++ b/core/src/test/java/com/graphhopper/routing/ch/SplitArray2DTest.java
@@ -0,0 +1,143 @@
+/*
+ *  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.carrotsearch.hppc.IntArrayList;
+import org.junit.jupiter.api.Test;
+
+import java.util.stream.IntStream;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+class SplitArray2DTest {
+
+    @Test
+    void basic() {
+        SplitArray2D<Integer> arr = new SplitArray2D<>(5, 1);
+        final int n = 1;
+        IntStream.range(0, 5).forEach(i -> assertEquals(0, arr.size(i)));
+        IntStream.range(0, 5).forEach(i -> assertEquals(0, arr.mid(i)));
+        arr.addPartOne(n, 5);
+        arr.addPartTwo(n, 6);
+        arr.addPartOne(n, 4);
+        arr.addPartTwo(n, 5);
+        arr.addPartTwo(n, 7);
+        arr.addPartTwo(n, 6);
+        assertEquals(2, arr.mid(n));
+        assertEquals(6, arr.size(n));
+        assertEquals(IntArrayList.from(5, 4), getIn(arr, n));
+        assertEquals(IntArrayList.from(6, 5, 7, 6), getOut(arr, n));
+        arr.remove(n, 6);
+        assertEquals(2, arr.mid(n));
+        assertEquals(4, arr.size(n));
+        arr.remove(n, 5);
+        assertEquals(IntArrayList.from(4), getIn(arr, n));
+        assertEquals(IntArrayList.from(7), getOut(arr, n));
+        assertEquals(n, arr.mid(n));
+        assertEquals(2, arr.size(n));
+        arr.clear(n);
+        assertEquals(0, arr.mid(n));
+        assertEquals(0, arr.size(n));
+        arr.addPartTwo(n, 23);
+        arr.addPartOne(n, 17);
+        assertEquals(1, arr.mid(n));
+        assertEquals(2, arr.size(n));
+        assertEquals(17, arr.get(n, 0));
+        assertEquals(23, arr.get(n, 1));
+        assertEquals(IntArrayList.from(17), getIn(arr, n));
+        assertEquals(IntArrayList.from(23), getOut(arr, n));
+    }
+
+    @Test
+    void remove() {
+        SplitArray2D<Integer> arr = new SplitArray2D<>(3, 1);
+        arr.addPartOne(0, 3);
+        arr.addPartOne(0, 2);
+        arr.addPartOne(0, 4);
+        arr.addPartOne(0, 6);
+        arr.addPartTwo(0, 1);
+        arr.addPartTwo(0, 8);
+        arr.addPartTwo(0, 2);
+        assertEquals(IntArrayList.from(3, 2, 4, 6), getIn(arr, 0));
+        assertEquals(IntArrayList.from(1, 8, 2), getOut(arr, 0));
+        arr.remove(0, 2);
+        assertEquals(IntArrayList.from(3, 6, 4), getIn(arr, 0));
+        assertEquals(IntArrayList.from(8, 1), getOut(arr, 0));
+    }
+
+    @Test
+    void remove2() {
+        SplitArray2D<Integer> arr = new SplitArray2D<>(3, 1);
+        arr.addPartOne(0, 3);
+        arr.addPartOne(0, 2);
+        arr.addPartOne(0, 4);
+        arr.addPartOne(0, 4);
+        arr.addPartOne(0, 4);
+        arr.addPartOne(0, 6);
+        arr.addPartOne(0, 4);
+        arr.addPartTwo(0, 1);
+        arr.addPartTwo(0, 3);
+        arr.addPartTwo(0, 2);
+        arr.addPartTwo(0, 1);
+        arr.addPartTwo(0, 1);
+        arr.addPartTwo(0, 4);
+
+        assertEquals(IntArrayList.from(3, 2, 4, 4, 4, 6, 4), getIn(arr, 0));
+        assertEquals(IntArrayList.from(1, 3, 2, 1, 1, 4), getOut(arr, 0));
+        arr.remove(0, 4);
+        assertEquals(IntArrayList.from(3, 2, 6), getIn(arr, 0));
+        assertEquals(IntArrayList.from(2, 1, 1, 3, 1), getOut(arr, 0));
+        arr.remove(0, 1);
+        assertEquals(IntArrayList.from(3, 2, 6), getIn(arr, 0));
+        assertEquals(IntArrayList.from(2, 3), getOut(arr, 0));
+        arr.remove(0, 2);
+        assertEquals(IntArrayList.from(3, 6), getIn(arr, 0));
+        assertEquals(IntArrayList.from(3), getOut(arr, 0));
+    }
+
+    @Test
+    void remove3() {
+        SplitArray2D<Integer> arr = new SplitArray2D<>(3, 1);
+        arr.addPartOne(0, 1);
+        arr.addPartOne(0, 2);
+        arr.addPartTwo(0, 1);
+        arr.addPartTwo(0, 2);
+        assertEquals(IntArrayList.from(1, 2), getIn(arr, 0));
+        assertEquals(IntArrayList.from(1, 2), getOut(arr, 0));
+        arr.remove(0, 2);
+        assertEquals(IntArrayList.from(1), getIn(arr, 0));
+        assertEquals(IntArrayList.from(1), getOut(arr, 0));
+    }
+
+    private IntArrayList getIn(SplitArray2D<Integer> arr, int n) {
+        return getRange(arr, n, 0, arr.mid(n));
+    }
+
+    private IntArrayList getOut(SplitArray2D<Integer> arr, int n) {
+        return getRange(arr, n, arr.mid(n), arr.size(n));
+    }
+
+    private IntArrayList getRange(SplitArray2D<Integer> arr, int n, int start, int end) {
+        IntArrayList res = new IntArrayList();
+        for (int i = start; i < end; i++) {
+            res.add(arr.get(n, i));
+        }
+        return res;
+    }
+}
\ No newline at end of file
diff --git a/core/src/test/java/com/graphhopper/storage/GraphHopperStorageCHTest.java b/core/src/test/java/com/graphhopper/storage/GraphHopperStorageCHTest.java
index 619222f90..854da458d 100644
--- a/core/src/test/java/com/graphhopper/storage/GraphHopperStorageCHTest.java
+++ b/core/src/test/java/com/graphhopper/storage/GraphHopperStorageCHTest.java
@@ -23,7 +23,10 @@ import com.graphhopper.routing.util.*;
 import com.graphhopper.routing.weighting.DefaultTurnCostProvider;
 import com.graphhopper.routing.weighting.FastestWeighting;
 import com.graphhopper.routing.weighting.TurnCostProvider;
-import com.graphhopper.util.*;
+import com.graphhopper.util.CHEdgeIteratorState;
+import com.graphhopper.util.EdgeExplorer;
+import com.graphhopper.util.EdgeIteratorState;
+import com.graphhopper.util.GHUtility;
 import com.graphhopper.util.shapes.BBox;
 import org.junit.Test;
 
@@ -120,44 +123,30 @@ public class GraphHopperStorageCHTest extends GraphHopperStorageTest {
     }
 
     @Test
-    public void testDisconnectEdge() {
+    public void testShortcutConnection() {
         graph = createGHStorage();
         EdgeExplorer baseCarOutExplorer = graph.createEdgeExplorer(carOutFilter);
-        // only remove edges
         graph.edge(4, 1, 30, true);
         graph.freeze();
 
         CHGraph lg = getGraph(graph);
-        EdgeExplorer chCarOutExplorer = lg.createEdgeExplorer(carOutFilter);
-        EdgeExplorer tmpCarInExplorer = lg.createEdgeExplorer(carInFilter);
+        EdgeExplorer chOutExplorer = lg.createEdgeExplorer(carOutFilter);
+        EdgeExplorer chInExplorer = lg.createEdgeExplorer(carInFilter);
         lg.shortcut(1, 2, PrepareEncoder.getScDirMask(), 0, 10, 11);
         lg.shortcut(1, 0, PrepareEncoder.getScFwdDir(), 0, 12, 13);
         lg.shortcut(3, 1, PrepareEncoder.getScFwdDir(), 0, 14, 15);
-        // create every time a new independent iterator for disconnect method
-        EdgeIterator iter = lg.createEdgeExplorer().setBaseNode(1);
-        iter.next();
-        assertEquals(3, iter.getAdjNode());
-        assertEquals(1, GHUtility.count(chCarOutExplorer.setBaseNode(3)));
-        lg.disconnectEdge(iter.getEdge(), iter.getAdjNode(), -1);
-        assertEquals(0, GHUtility.count(chCarOutExplorer.setBaseNode(3)));
-        // no shortcuts visible
-        assertEquals(0, GHUtility.count(baseCarOutExplorer.setBaseNode(3)));
-
-        // even directed ways change!
-        assertTrue(iter.next());
-        assertEquals(0, iter.getAdjNode());
-        assertEquals(1, GHUtility.count(tmpCarInExplorer.setBaseNode(0)));
-        lg.disconnectEdge(iter.getEdge(), iter.getAdjNode(), -1);
-        assertEquals(0, GHUtility.count(tmpCarInExplorer.setBaseNode(0)));
-
-        iter.next();
-        assertEquals(2, iter.getAdjNode());
-        assertEquals(1, GHUtility.count(chCarOutExplorer.setBaseNode(2)));
-        lg.disconnectEdge(iter.getEdge(), iter.getAdjNode(), -1);
-        assertEquals(0, GHUtility.count(chCarOutExplorer.setBaseNode(2)));
-
-        assertEquals(GHUtility.asSet(0, 2, 4), GHUtility.getNeighbors(chCarOutExplorer.setBaseNode(1)));
+        // shortcuts are only visible from the base node, for example we do not see node 1 from node 2, or node
+        // 3 from node 1
+        assertEquals(0, GHUtility.count(chOutExplorer.setBaseNode(2)));
+        assertEquals(0, GHUtility.count(chInExplorer.setBaseNode(2)));
+
+        assertEquals(3, GHUtility.count(chOutExplorer.setBaseNode(1)));
+        assertEquals(2, GHUtility.count(chInExplorer.setBaseNode(1)));
+        assertEquals(GHUtility.asSet(0, 2, 4), GHUtility.getNeighbors(chOutExplorer.setBaseNode(1)));
         assertEquals(GHUtility.asSet(4), GHUtility.getNeighbors(baseCarOutExplorer.setBaseNode(1)));
+
+        assertEquals(1, GHUtility.count(chOutExplorer.setBaseNode(3)));
+        assertEquals(0, GHUtility.count(chInExplorer.setBaseNode(3)));
     }
 
     @Test
@@ -214,7 +203,6 @@ public class GraphHopperStorageCHTest extends GraphHopperStorageTest {
         assertEquals(100.123, lg.getEdgeIteratorState(sc1, 1).getWeight(), 1e-3);
         assertEquals(100.123, lg.getEdgeIteratorState(sc1, 0).getWeight(), 1e-3);
         assertEquals(100.123, GHUtility.getEdge(lg, 0, 1).getWeight(), 1e-3);
-        assertEquals(100.123, GHUtility.getEdge(lg, 1, 0).getWeight(), 1e-3);
 
         int sc2 = lg.shortcut(1, 0, PrepareEncoder.getScDirMask(), 1.011011, NO_EDGE, NO_EDGE);
         assertEquals(1.011011, lg.getEdgeIteratorState(sc2, 0).getWeight(), 1e-3);
diff --git a/reader-osm/src/test/java/com/graphhopper/GraphHopperTest.java b/reader-osm/src/test/java/com/graphhopper/GraphHopperTest.java
index c00dd6201..19a485c74 100644
--- a/reader-osm/src/test/java/com/graphhopper/GraphHopperTest.java
+++ b/reader-osm/src/test/java/com/graphhopper/GraphHopperTest.java
@@ -25,6 +25,7 @@ import com.graphhopper.reader.dem.ElevationProvider;
 import com.graphhopper.reader.dem.SRTMProvider;
 import com.graphhopper.reader.dem.SkadiProvider;
 import com.graphhopper.reader.osm.GraphHopperOSM;
+import com.graphhopper.routing.util.AllEdgesIterator;
 import com.graphhopper.routing.util.CarFlagEncoder;
 import com.graphhopper.routing.util.DefaultFlagEncoderFactory;
 import com.graphhopper.routing.util.EncodingManager;
@@ -89,8 +90,8 @@ public class GraphHopperTest {
             ASTAR + ",false,439",
             DIJKSTRA_BI + ",false,208",
             ASTAR_BI + ",false,172",
-            ASTAR_BI + ",true,36",
-            DIJKSTRA_BI + ",true,34"
+            ASTAR_BI + ",true,45",
+            DIJKSTRA_BI + ",true,43"
     })
     public void testMonacoDifferentAlgorithms(String algo, boolean withCH, int expectedVisitedNodes) {
         final String vehicle = "car";
@@ -1858,6 +1859,20 @@ public class GraphHopperTest {
         assertEquals(658, rsp.getBest().getDistance(), 1);
     }
 
+    @Test
+    public void testEdgeCount() {
+        GraphHopper hopper = createGraphHopper("car").
+                setOSMFile(BAYREUTH).
+                setMinNetworkSize(50).
+                setProfiles(new Profile("car").setVehicle("car").setWeighting("fastest"));
+        hopper.importOrLoad();
+        int count = 0;
+        AllEdgesIterator iter = hopper.getGraphHopperStorage().getAllEdges();
+        while (iter.next())
+            count++;
+        assertEquals(hopper.getGraphHopperStorage().getEdges(), count);
+    }
+
     @Test
     public void testCurbsides() {
         GraphHopper h = createGraphHopper("car|turn_costs=true").