Repository: graphhopper/graphhopper
Pull request #2118 (2020-09-07 14:41:06)

Remove graph compacting
Let's see if this works out..

easbar: I checked the performance stats and it looks like the CH preparation even runs a bit faster with this PR. The routing speed is a bit slower, but this is probably due to a weakness of our measurements: We use random query samples based on the node-ids, so if we change the node-ids we run the benchmarks with different routes unfortunately. It would be better to run the benchmarks using random gps coordinates.
michaz: Can‘t we run all benchmarks long enough that enough routes are sampled so that it doesn‘t matter if they are different? Wouldn‘t it be even more meaningful then? If I understand it correctly, benchmarks need confidence intervals anyway, like in the „Microbenchmark Harness“..
easbar: Yes that would be ideal, but in practice I feel like this is not so easy to do. Also we aren't necessarily interested in the 'real' average speed, but its enough to compare different versions on a fixed set of sample routes IMO.
michaz: I‘m fine with something like „I‘m 95% sure that this is not more than 5% slower“. :-)
easbar: > I‘m fine with something like „I‘m 95% sure that this is not more than 5% slower“. :-)

Yes me too, but its hard do make sure this is the case. I think we should just sample the gps coordinates instead of the node Ids (#2121), it should be no problem to do, I can do it today. This will 'break/change' our measurement results, but afterwards they should be more stable to such changes. But no need to hold back this PR because of this.
michaz: What would happen if we just used a new random sample every time we run the benchmark?

 Then we would get some (large?) variability in results, and isn‘t that approximately the range we can (should?) ignore when deciding if some code change is bad or good?

Or is it that for any practical value, the variability would be so big that we would miss actually meaningful performance hits?
michaz: Okay, the _amount of work_, measured in, like, sum of all route lengths, must have less variability than the phenomenon we‘re interested in.
easbar: > Or is it that for any practical value, the variability would be so big that we would miss actually meaningful performance hits?

For CH maybe not so much, but for some of the slower measurements with smaller sample sizes yes (AStar and alternatives for example). Using different samples certainly has the potential to 'hide' real performance changes (or make you think there is a change when really there is not). What / how large a real performance change is is of course another question. 

Another benefit we get from using the same sample is that we can look at the distance checksum of all queries to see if the results/routes are still the same.

Patch:
diff --git a/core/src/main/java/com/graphhopper/coll/SparseIntIntArray.java b/core/src/main/java/com/graphhopper/coll/SparseIntIntArray.java
deleted file mode 100644
index 066a66c70..000000000
--- a/core/src/main/java/com/graphhopper/coll/SparseIntIntArray.java
+++ /dev/null
@@ -1,309 +0,0 @@
-/*
- * Copyright (C) 2009 The Android Open Source Project
- *
- * Licensed 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.coll;
-
-import com.graphhopper.util.Helper;
-
-/**
- * Copied from Android project. android.util.SparseArray.java
- * <p>
- * SparseArrays map ints to ints. Unlike a normal array of ints, there can be gaps in the indices.
- */
-public class SparseIntIntArray {
-    private static final int DELETED = Integer.MIN_VALUE;
-    private boolean mGarbage = false;
-    private int[] mKeys;
-    private int[] mValues;
-    private int mSize;
-
-    /**
-     * Creates a new SparseIntIntArray containing no mappings.
-     */
-    public SparseIntIntArray() {
-        this(10);
-    }
-
-    /**
-     * Creates a new SparseIntIntArray containing no mappings that will not require any additional
-     * memory allocation to store the specified number of mappings.
-     */
-    public SparseIntIntArray(int cap) {
-        try {
-            cap = Helper.idealIntArraySize(cap);
-            mKeys = new int[cap];
-            mValues = new int[cap];
-            mSize = 0;
-        } catch (OutOfMemoryError err) {
-            System.err.println("requested capacity " + cap);
-            throw err;
-        }
-    }
-
-    static int binarySearch(int[] a, int start, int len, int key) {
-        int high = start + len, low = start - 1, guess;
-        while (high - low > 1) {
-            // use >>> for average or we could get an integer overflow.
-            guess = (high + low) >>> 1;
-
-            if (a[guess] < key) {
-                low = guess;
-            } else {
-                high = guess;
-            }
-        }
-
-        if (high == start + len) {
-            return ~(start + len);
-        } else if (a[high] == key) {
-            return high;
-        } else {
-            return ~high;
-        }
-    }
-
-    /**
-     * Gets the Object mapped from the specified key, or <code>-1</code> if no such mapping has
-     * been made.
-     */
-    public int get(int key) {
-        return get(key, -1);
-    }
-
-    /**
-     * Gets the Object mapped from the specified key, or the specified Object if no such mapping has
-     * been made.
-     */
-    private int get(int key, int valueIfKeyNotFound) {
-        int i = binarySearch(mKeys, 0, mSize, key);
-        if (i < 0 || mValues[i] == DELETED) {
-            return valueIfKeyNotFound;
-        } else {
-            return mValues[i];
-        }
-    }
-
-    /**
-     * Removes the mapping from the specified key, if there was any.
-     */
-    public void remove(int key) {
-        int i = binarySearch(mKeys, 0, mSize, key);
-        if (i >= 0 && mValues[i] != DELETED) {
-            mValues[i] = DELETED;
-            mGarbage = true;
-        }
-    }
-
-    private void gc() {
-        int n = mSize;
-        int o = 0;
-        int[] keys = mKeys;
-        int[] values = mValues;
-
-        for (int i = 0; i < n; i++) {
-            int val = values[i];
-            if (val != DELETED) {
-                if (i != o) {
-                    keys[o] = keys[i];
-                    values[o] = val;
-                }
-
-                o++;
-            }
-        }
-
-        mGarbage = false;
-        mSize = o;
-    }
-
-    /**
-     * Adds a mapping from the specified key to the specified value, replacing the previous mapping
-     * from the specified key if there was one.
-     */
-    public int put(int key, int value) {
-        int i = binarySearch(mKeys, 0, mSize, key);
-
-        if (i >= 0) {
-            mValues[i] = value;
-        } else {
-            i = ~i;
-
-            if (i < mSize && mValues[i] == DELETED) {
-                mKeys[i] = key;
-                mValues[i] = value;
-                return i;
-            }
-
-            if (mGarbage && mSize >= mKeys.length) {
-                gc();
-
-                // Search again because indices may have changed.
-                i = ~binarySearch(mKeys, 0, mSize, key);
-            }
-
-            if (mSize >= mKeys.length) {
-                int n = Helper.idealIntArraySize(mSize + 1);
-
-                int[] nkeys = new int[n];
-                int[] nvalues = new int[n];
-
-                System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-                System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-                mKeys = nkeys;
-                mValues = nvalues;
-            }
-
-            if (mSize - i != 0) {
-                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
-                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
-            }
-
-            mKeys[i] = key;
-            mValues[i] = value;
-            mSize++;
-        }
-        return i;
-    }
-
-    /**
-     * Returns the number of key-value mappings that this SparseIntIntArray currently stores.
-     */
-    public int getSize() {
-        if (mGarbage) {
-            gc();
-        }
-
-        return mSize;
-    }
-
-    /**
-     * Given an index in the range <code>0...size()-1</code>, returns the key from the
-     * <code>index</code>th key-value mapping that this SparseIntIntArray stores.
-     */
-    public int keyAt(int index) {
-        if (mGarbage) {
-            gc();
-        }
-
-        return mKeys[index];
-    }
-
-    /**
-     * Given an index in the range <code>0...size()-1</code>, sets a new key for the
-     * <code>index</code>th key-value mapping that this SparseIntIntArray stores.
-     */
-    public void setKeyAt(int index, int key) {
-        if (mGarbage) {
-            gc();
-        }
-
-        mKeys[index] = key;
-    }
-
-    /**
-     * Given an index in the range <code>0...size()-1</code>, returns the value from the
-     * <code>index</code>th key-value mapping that this SparseIntIntArray stores.
-     */
-    public int valueAt(int index) {
-        if (mGarbage) {
-            gc();
-        }
-
-        return mValues[index];
-    }
-
-    /**
-     * Given an index in the range <code>0...size()-1</code>, sets a new value for the
-     * <code>index</code>th key-value mapping that this SparseIntIntArray stores.
-     */
-    public void setValueAt(int index, int value) {
-        if (mGarbage) {
-            gc();
-        }
-
-        mValues[index] = value;
-    }
-
-    /**
-     * Removes all key-value mappings from this SparseIntIntArray.
-     */
-    public void clear() {
-        int n = mSize;
-        int[] values = mValues;
-        for (int i = 0; i < n; i++) {
-            values[i] = -1;
-        }
-
-        mSize = 0;
-        mGarbage = false;
-    }
-
-    /**
-     * Puts a key/value pair into the array, optimizing for the case where the key is greater than
-     * all existing keys in the array.
-     */
-    public int append(int key, int value) {
-        if (mSize != 0 && key <= mKeys[mSize - 1]) {
-            return put(key, value);
-        }
-
-        if (mGarbage && mSize >= mKeys.length) {
-            gc();
-        }
-
-        int pos = mSize;
-        if (pos >= mKeys.length) {
-            int n = Helper.idealIntArraySize(pos + 1);
-
-            int[] nkeys = new int[n];
-            int[] nvalues = new int[n];
-
-            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-            mKeys = nkeys;
-            mValues = nvalues;
-        }
-
-        mKeys[pos] = key;
-        mValues[pos] = value;
-        mSize = pos + 1;
-        return pos;
-    }
-
-    @Override
-    public String toString() {
-        StringBuilder sb = new StringBuilder();
-        for (int i = 0; i < getSize(); i++) {
-            int k = mKeys[i];
-            int v = mValues[i];
-            if (i > 0) {
-                sb.append(",");
-            }
-            sb.append(k);
-            sb.append(":");
-            sb.append(v);
-        }
-        return sb.toString();
-    }
-
-    /**
-     * Warning: returns ~index and not -(index+1) like trove and jdk do
-     */
-    public int binarySearch(int key) {
-        return binarySearch(mKeys, 0, mSize, key);
-    }
-}
diff --git a/core/src/main/java/com/graphhopper/routing/subnetwork/PrepareRoutingSubnetworks.java b/core/src/main/java/com/graphhopper/routing/subnetwork/PrepareRoutingSubnetworks.java
index 3c1c48a0a..1ab8cd809 100644
--- a/core/src/main/java/com/graphhopper/routing/subnetwork/PrepareRoutingSubnetworks.java
+++ b/core/src/main/java/com/graphhopper/routing/subnetwork/PrepareRoutingSubnetworks.java
@@ -77,17 +77,9 @@ public class PrepareRoutingSubnetworks {
         for (PrepareJob job : prepareJobs) {
             removeSmallSubNetworks(job);
         }
-        markNodesRemovedIfUnreachable();
-        optimize();
         logger.info("Finished finding and removing subnetworks for " + prepareJobs.size() + " vehicles, took: " + sw.stop().getSeconds() + "s, " + Helper.getMemInfo());
     }
 
-    private void optimize() {
-        StopWatch sw = new StopWatch().start();
-        ghStorage.optimize();
-        logger.info("Optimized storage after subnetwork removal, took: " + sw.stop().getSeconds() + "s," + Helper.getMemInfo());
-    }
-
     /**
      * The biggest component is always kept regardless of its size. For edge-based routing with turn restrictions the
      * subnetwork search has to consider the turn restrictions as well to make sure components that are not reachable
@@ -251,23 +243,6 @@ public class PrepareRoutingSubnetworks {
         return 0;
     }
 
-    /**
-     * Removes nodes if all edges are not accessible. I.e. removes zero degree nodes. Note that so far we are not
-     * removing any edges entirely from the graph (we could probably do this for edges that are blocked for *all*
-     * vehicles.
-     */
-    void markNodesRemovedIfUnreachable() {
-        EdgeExplorer edgeExplorer = ghStorage.createEdgeExplorer();
-        int removedNodes = 0;
-        for (int nodeIndex = 0; nodeIndex < ghStorage.getNodes(); nodeIndex++) {
-            if (detectNodeRemovedForAllEncoders(edgeExplorer, nodeIndex)) {
-                ghStorage.markNodeRemoved(nodeIndex);
-                removedNodes++;
-            }
-        }
-        logger.info("Removed " + removedNodes + " nodes from the graph as they aren't used by any vehicle after removing subnetworks");
-    }
-
     /**
      * This method checks if the node is removed or inaccessible for ALL encoders.
      *
diff --git a/core/src/main/java/com/graphhopper/routing/subnetwork/TarjanSCC.java b/core/src/main/java/com/graphhopper/routing/subnetwork/TarjanSCC.java
index f0a4ce079..7fd044b86 100644
--- a/core/src/main/java/com/graphhopper/routing/subnetwork/TarjanSCC.java
+++ b/core/src/main/java/com/graphhopper/routing/subnetwork/TarjanSCC.java
@@ -188,7 +188,7 @@ public class TarjanSCC {
      */
     public ConnectedComponents findComponents() {
         for (int node = 0; node < graph.getNodes(); ++node) {
-            if (nodeIndex[node] != -1 || ((GraphHopperStorage) graph).isNodeRemoved(node))
+            if (nodeIndex[node] != -1)
                 continue;
 
             pushFindComponentForNode(node);
diff --git a/core/src/main/java/com/graphhopper/storage/BaseGraph.java b/core/src/main/java/com/graphhopper/storage/BaseGraph.java
index 868c0f957..f59bb7ca1 100644
--- a/core/src/main/java/com/graphhopper/storage/BaseGraph.java
+++ b/core/src/main/java/com/graphhopper/storage/BaseGraph.java
@@ -17,9 +17,6 @@
  */
 package com.graphhopper.storage;
 
-import com.graphhopper.coll.GHBitSet;
-import com.graphhopper.coll.GHBitSetImpl;
-import com.graphhopper.coll.SparseIntIntArray;
 import com.graphhopper.routing.ev.BooleanEncodedValue;
 import com.graphhopper.routing.ev.DecimalEncodedValue;
 import com.graphhopper.routing.ev.EnumEncodedValue;
@@ -31,7 +28,6 @@ import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.search.StringIndex;
 import com.graphhopper.util.*;
 import com.graphhopper.util.shapes.BBox;
-import org.slf4j.LoggerFactory;
 
 import java.util.Collections;
 import java.util.Locale;
@@ -94,8 +90,6 @@ class BaseGraph implements Graph {
      * interval [0,n)
      */
     private int nodeCount;
-    // remove markers are not yet persistent!
-    private GHBitSet removedNodes;
     private int edgeEntryIndex, nodeEntryIndex;
     private long maxGeoRef;
     private boolean frozen = false;
@@ -644,185 +638,6 @@ class BaseGraph implements Graph {
         if (supportsTurnCosts()) {
             turnCostStorage.copyTo(clonedG.turnCostStorage);
         }
-
-        if (removedNodes == null)
-            clonedG.removedNodes = null;
-        else
-            clonedG.removedNodes = removedNodes.copyTo(new GHBitSetImpl());
-    }
-
-    protected void trimToSize() {
-        long nodeCap = (long) nodeCount * nodeEntryBytes;
-        nodes.trimTo(nodeCap);
-//        long edgeCap = (long) (edgeCount + 1) * edgeEntrySize;
-//        edges.trimTo(edgeCap * 4);
-    }
-
-    /**
-     * This methods disconnects all edges from removed nodes. It does no edge compaction. Then it
-     * moves the last nodes into the deleted nodes, where it needs to update the node ids in every
-     * edge.
-     */
-    void inPlaceNodeRemove(int removeNodeCount) {
-        // Prepare edge-update of nodes which are connected to deleted nodes
-        int toMoveNodes = getNodes();
-        int itemsToMove = 0;
-
-        // sorted map when we access it via keyAt and valueAt - see below!
-        final SparseIntIntArray oldToNewMap = new SparseIntIntArray(removeNodeCount);
-        GHBitSet toRemoveSet = new GHBitSetImpl(removeNodeCount);
-        removedNodes.copyTo(toRemoveSet);
-
-        if (removeNodeCount > getNodes() / 2.0)
-            LoggerFactory.getLogger(getClass()).warn("More than a half of the network should be removed!? "
-                    + "Nodes:" + getNodes() + ", remove:" + removeNodeCount);
-
-        EdgeExplorer delExplorer = createEdgeExplorer();
-        // create map of old node ids pointing to new ids
-        for (int removeNode = removedNodes.next(0);
-             removeNode >= 0;
-             removeNode = removedNodes.next(removeNode + 1)) {
-            EdgeIterator delEdgesIter = delExplorer.setBaseNode(removeNode);
-            while (delEdgesIter.next()) {
-                toRemoveSet.add(delEdgesIter.getAdjNode());
-            }
-
-            toMoveNodes--;
-            // move only nodes that are not removed
-            for (; toMoveNodes >= 0; toMoveNodes--) {
-                if (!removedNodes.contains(toMoveNodes))
-                    break;
-            }
-
-            if (toMoveNodes >= removeNode)
-                oldToNewMap.put(toMoveNodes, removeNode);
-
-            itemsToMove++;
-        }
-
-        EdgeIteratorImpl adjNodesToDelIter = (EdgeIteratorImpl) createEdgeExplorer();
-        // now similar process to disconnectEdges but only for specific nodes
-        // all deleted nodes could be connected to existing. remove the connections
-        for (int removeNode = toRemoveSet.next(0);
-             removeNode >= 0;
-             removeNode = toRemoveSet.next(removeNode + 1)) {
-            // remove all edges connected to the deleted nodes
-            adjNodesToDelIter.setBaseNode(removeNode);
-            long prevPointer = EdgeIterator.NO_EDGE;
-            while (adjNodesToDelIter.next()) {
-                int nodeId = adjNodesToDelIter.getAdjNode();
-                // already invalidated
-                if (!EdgeAccess.isInvalidNodeB(nodeId) && removedNodes.contains(nodeId)) {
-                    int edgeToRemove = adjNodesToDelIter.getEdge();
-                    long edgeToRemovePointer = edgeAccess.toPointer(edgeToRemove);
-                    edgeAccess.internalEdgeDisconnect(edgeToRemove, prevPointer, removeNode);
-                    edgeAccess.invalidateEdge(edgeToRemovePointer);
-                } else {
-                    prevPointer = adjNodesToDelIter.edgePointer;
-                }
-            }
-        }
-
-        GHBitSet toMoveSet = new GHBitSetImpl(removeNodeCount * 3);
-        EdgeExplorer movedEdgeExplorer = createEdgeExplorer();
-        // marks connected nodes to rewrite the edges
-        for (int i = 0; i < itemsToMove; i++) {
-            int oldI = oldToNewMap.keyAt(i);
-            EdgeIterator movedEdgeIter = movedEdgeExplorer.setBaseNode(oldI);
-            while (movedEdgeIter.next()) {
-                int nodeId = movedEdgeIter.getAdjNode();
-                if (EdgeAccess.isInvalidNodeB(nodeId))
-                    continue;
-
-                if (removedNodes.contains(nodeId))
-                    throw new IllegalStateException("shouldn't happen as the edge to the node "
-                            + nodeId + " should be already deleted. " + oldI);
-
-                toMoveSet.add(nodeId);
-            }
-        }
-
-        // move nodes into deleted nodes
-        for (int i = 0; i < itemsToMove; i++) {
-            int oldI = oldToNewMap.keyAt(i);
-            int newI = oldToNewMap.valueAt(i);
-            long newOffset = (long) newI * nodeEntryBytes;
-            long oldOffset = (long) oldI * nodeEntryBytes;
-            for (long j = 0; j < nodeEntryBytes; j += 4) {
-                nodes.setInt(newOffset + j, nodes.getInt(oldOffset + j));
-            }
-        }
-
-        // *rewrites* all edges connected to moved nodes
-        // go through all edges and pick the necessary <- this is easier to implement than
-        // a more efficient (?) breadth-first search
-        EdgeIterator iter = getAllEdges();
-        while (iter.next()) {
-            int nodeA = iter.getBaseNode();
-            int nodeB = iter.getAdjNode();
-            if (!toMoveSet.contains(nodeA) && !toMoveSet.contains(nodeB))
-                continue;
-
-            // now overwrite exiting edge with new node ids
-            int updatedA = oldToNewMap.get(nodeA);
-            if (updatedA < 0)
-                updatedA = nodeA;
-
-            int updatedB = oldToNewMap.get(nodeB);
-            if (updatedB < 0)
-                updatedB = nodeB;
-
-            // no need to rewrite flags or other properties as they are independent of the node order unlike in <= 0.11
-            int edgeId = iter.getEdge();
-            long edgePointer = edgeAccess.toPointer(edgeId);
-            int linkA = edgeAccess.getLinkA(edgePointer);
-            int linkB = edgeAccess.getLinkB(edgePointer);
-            edgeAccess.writeEdge(edgeId, updatedA, updatedB, linkA, linkB);
-        }
-
-        if (removeNodeCount >= nodeCount)
-            throw new IllegalStateException("graph is empty after in-place removal but was " + removeNodeCount);
-
-        // clear N_EDGE_REF
-        initNodeRefs(((long) nodeCount - removeNodeCount) * nodeEntryBytes, (long) nodeCount * nodeEntryBytes);
-
-        // we do not remove the invalid edges => edgeCount stays the same!
-        nodeCount -= removeNodeCount;
-
-        // health check
-        if (isTestingEnabled()) {
-            EdgeExplorer explorer = createEdgeExplorer();
-            iter = getAllEdges();
-            while (iter.next()) {
-                int base = iter.getBaseNode();
-                int adj = iter.getAdjNode();
-                String str = iter.getEdge()
-                        + ", r.contains(" + base + "):" + removedNodes.contains(base)
-                        + ", r.contains(" + adj + "):" + removedNodes.contains(adj)
-                        + ", tr.contains(" + base + "):" + toRemoveSet.contains(base)
-                        + ", tr.contains(" + adj + "):" + toRemoveSet.contains(adj)
-                        + ", base:" + base + ", adj:" + adj + ", nodeCount:" + nodeCount;
-                if (adj >= nodeCount)
-                    throw new RuntimeException("Adj.node problem with edge " + str);
-
-                if (base >= nodeCount)
-                    throw new RuntimeException("Base node problem with edge " + str);
-
-                try {
-                    explorer.setBaseNode(adj).toString();
-                } catch (Exception ex) {
-                    org.slf4j.LoggerFactory.getLogger(getClass()).error("adj:" + adj);
-                }
-                try {
-                    explorer.setBaseNode(base).toString();
-                } catch (Exception ex) {
-                    org.slf4j.LoggerFactory.getLogger(getClass()).error("base:" + base);
-                }
-            }
-            // access last node -> no error
-            explorer.setBaseNode(nodeCount - 1).toString();
-        }
-        removedNodes = null;
     }
 
     @Override
@@ -1013,13 +828,6 @@ class BaseGraph implements Graph {
         edges.setInt(edgePointer + E_NAME, stringIndexRef);
     }
 
-    GHBitSet getRemovedNodes() {
-        if (removedNodes == null)
-            removedNodes = new GHBitSetImpl(getNodes());
-
-        return removedNodes;
-    }
-
     private void ensureGeometry(long bytePos, int byteLength) {
         wayGeometry.ensureCapacity(bytePos + byteLength);
     }
@@ -1122,9 +930,6 @@ class BaseGraph implements Graph {
 
                 edgePointer = edgeAccess.toPointer(edgeId);
                 adjNode = edgeAccess.getNodeB(edgePointer);
-                // some edges are deleted and are marked via a negative node
-                if (EdgeAccess.isInvalidNodeB(adjNode))
-                    continue;
 
                 baseNode = edgeAccess.getNodeA(edgePointer);
                 freshFlags = false;
@@ -1183,8 +988,6 @@ class BaseGraph implements Graph {
             baseNode = edgeAccess.getNodeA(edgePointer);
             adjNode = edgeAccess.getNodeB(edgePointer);
             freshFlags = false;
-            if (EdgeAccess.isInvalidNodeB(adjNode))
-                throw new IllegalStateException("content of edgeId " + this.edgeId + " is marked as invalid - ie. the edge is already removed!");
 
             if (expectedAdjNode == adjNode || expectedAdjNode == Integer.MIN_VALUE) {
                 reverse = false;
diff --git a/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java b/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
index 10e34bb44..e14eb6ca1 100644
--- a/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
+++ b/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java
@@ -459,10 +459,6 @@ public class CHGraphImpl implements CHGraph, Storable<CHGraph> {
                     return false;
 
                 allEdgeIterator.adjNode = allEdgeIterator.edgeAccess.getNodeB(allEdgeIterator.edgePointer);
-                // some edges are deleted and are marked via a negative node
-                if (EdgeAccess.isInvalidNodeB(allEdgeIterator.adjNode))
-                    continue;
-
                 allEdgeIterator.baseNode = allEdgeIterator.edgeAccess.getNodeA(allEdgeIterator.edgePointer);
                 allEdgeIterator.freshFlags = false;
                 allEdgeIterator.reverse = false;
diff --git a/core/src/main/java/com/graphhopper/storage/DataAccess.java b/core/src/main/java/com/graphhopper/storage/DataAccess.java
index d1aa3b15d..741ea43c6 100644
--- a/core/src/main/java/com/graphhopper/storage/DataAccess.java
+++ b/core/src/main/java/com/graphhopper/storage/DataAccess.java
@@ -106,12 +106,6 @@ public interface DataAccess extends Storable<DataAccess> {
      */
     boolean ensureCapacity(long bytes);
 
-    /**
-     * Reduces the allocate space to the specified bytes. Warning: it'll free the space even if it
-     * is in use!
-     */
-    void trimTo(long bytes);
-
     /**
      * Copies the content from this object into the specified one.
      */
diff --git a/core/src/main/java/com/graphhopper/storage/EdgeAccess.java b/core/src/main/java/com/graphhopper/storage/EdgeAccess.java
index b07fdc9d0..a31560b19 100644
--- a/core/src/main/java/com/graphhopper/storage/EdgeAccess.java
+++ b/core/src/main/java/com/graphhopper/storage/EdgeAccess.java
@@ -23,7 +23,6 @@ import com.graphhopper.util.EdgeIterator;
  * @author Peter Karich
  */
 abstract class EdgeAccess {
-    private static final int NO_NODE = -1;
     final DataAccess edges;
     int E_NODEA, E_NODEB, E_LINKA, E_LINKB, E_FLAGS;
 
@@ -49,14 +48,6 @@ abstract class EdgeAccess {
 
     abstract int getEntryBytes();
 
-    final void invalidateEdge(long edgePointer) {
-        edges.setInt(edgePointer + E_NODEB, NO_NODE);
-    }
-
-    static boolean isInvalidNodeB(int node) {
-        return node == EdgeAccess.NO_NODE;
-    }
-
     final void readFlags(long edgePointer, IntsRef edgeFlags) {
         int size = edgeFlags.ints.length;
         for (int i = 0; i < size; i++) {
diff --git a/core/src/main/java/com/graphhopper/storage/GraphHopperStorage.java b/core/src/main/java/com/graphhopper/storage/GraphHopperStorage.java
index 2f04d9e59..953ef28a1 100644
--- a/core/src/main/java/com/graphhopper/storage/GraphHopperStorage.java
+++ b/core/src/main/java/com/graphhopper/storage/GraphHopperStorage.java
@@ -223,33 +223,6 @@ public final class GraphHopperStorage implements GraphStorage, Graph {
         return properties;
     }
 
-    @Override
-    public void markNodeRemoved(int index) {
-        baseGraph.getRemovedNodes().add(index);
-    }
-
-    @Override
-    public boolean isNodeRemoved(int index) {
-        return baseGraph.getRemovedNodes().contains(index);
-    }
-
-    @Override
-    public void optimize() {
-        if (isFrozen())
-            throw new IllegalStateException("do not optimize after graph was frozen");
-
-        int delNodes = baseGraph.getRemovedNodes().getCardinality();
-        if (delNodes <= 0)
-            return;
-
-        // Deletes only nodes.
-        // It reduces the fragmentation of the node space but introduces new unused edges.
-        baseGraph.inPlaceNodeRemove(delNodes);
-
-        // Reduce memory usage
-        baseGraph.trimToSize();
-    }
-
     @Override
     public boolean loadExisting() {
         baseGraph.checkNotInitialized();
diff --git a/core/src/main/java/com/graphhopper/storage/GraphStorage.java b/core/src/main/java/com/graphhopper/storage/GraphStorage.java
index fe9a4fe0b..fc1cb73a6 100644
--- a/core/src/main/java/com/graphhopper/storage/GraphStorage.java
+++ b/core/src/main/java/com/graphhopper/storage/GraphStorage.java
@@ -27,19 +27,4 @@ public interface GraphStorage extends Storable<GraphStorage> {
     String toDetailsString();
 
     StorableProperties getProperties();
-
-    /**
-     * Schedule the deletion of the specified node until an optimize() call happens
-     */
-    void markNodeRemoved(int index);
-
-    /**
-     * Checks if the specified node is marked as removed.
-     */
-    boolean isNodeRemoved(int index);
-
-    /**
-     * Performs optimization routines like deletion or node rearrangements.
-     */
-    void optimize();
 }
diff --git a/core/src/main/java/com/graphhopper/storage/MMapDataAccess.java b/core/src/main/java/com/graphhopper/storage/MMapDataAccess.java
index 4dfaad145..67c3e0332 100644
--- a/core/src/main/java/com/graphhopper/storage/MMapDataAccess.java
+++ b/core/src/main/java/com/graphhopper/storage/MMapDataAccess.java
@@ -493,30 +493,6 @@ public final class MMapDataAccess extends AbstractDataAccess {
         }
     }
 
-    @Override
-    public void trimTo(long capacity) {
-        if (capacity < segmentSizeInBytes) {
-            capacity = segmentSizeInBytes;
-        }
-        int remainingSegNo = (int) (capacity / segmentSizeInBytes);
-        if (capacity % segmentSizeInBytes != 0) {
-            remainingSegNo++;
-        }
-
-        clean(remainingSegNo, segments.size());
-        segments = new ArrayList<>(segments.subList(0, remainingSegNo));
-
-        try {
-            // windows does not allow changing the length of an open files
-            if (!Constants.WINDOWS) {
-                // reduce file size
-                raFile.setLength(HEADER_OFFSET + (long) remainingSegNo * segmentSizeInBytes);
-            }
-        } catch (Exception ex) {
-            throw new RuntimeException(ex);
-        }
-    }
-
     @Override
     public void rename(String newName) {
         if (!checkBeforeRename(newName)) {
diff --git a/core/src/main/java/com/graphhopper/storage/RAMDataAccess.java b/core/src/main/java/com/graphhopper/storage/RAMDataAccess.java
index 5bd006953..a573fff3e 100644
--- a/core/src/main/java/com/graphhopper/storage/RAMDataAccess.java
+++ b/core/src/main/java/com/graphhopper/storage/RAMDataAccess.java
@@ -296,24 +296,6 @@ public class RAMDataAccess extends AbstractDataAccess {
         return segments.length;
     }
 
-    @Override
-    public void trimTo(long capacity) {
-        if (capacity > getCapacity()) {
-            throw new IllegalStateException("Cannot increase capacity (" + getCapacity() + ") to " + capacity
-                    + " via trimTo. Use ensureCapacity instead. ");
-        }
-
-        if (capacity < segmentSizeInBytes)
-            capacity = segmentSizeInBytes;
-
-        int remainingSegments = (int) (capacity / segmentSizeInBytes);
-        if (capacity % segmentSizeInBytes != 0) {
-            remainingSegments++;
-        }
-
-        segments = Arrays.copyOf(segments, remainingSegments);
-    }
-
     @Override
     public void rename(String newName) {
         if (!checkBeforeRename(newName)) {
diff --git a/core/src/main/java/com/graphhopper/storage/RAMIntDataAccess.java b/core/src/main/java/com/graphhopper/storage/RAMIntDataAccess.java
index 8e6831fa1..b5ce89f51 100644
--- a/core/src/main/java/com/graphhopper/storage/RAMIntDataAccess.java
+++ b/core/src/main/java/com/graphhopper/storage/RAMIntDataAccess.java
@@ -284,19 +284,6 @@ class RAMIntDataAccess extends AbstractDataAccess {
         return this;
     }
 
-    @Override
-    public void trimTo(long capacity) {
-        if (capacity < segmentSizeInBytes) {
-            capacity = segmentSizeInBytes;
-        }
-        int remainingSegments = (int) (capacity / segmentSizeInBytes);
-        if (capacity % segmentSizeInBytes != 0) {
-            remainingSegments++;
-        }
-
-        segments = Arrays.copyOf(segments, remainingSegments);
-    }
-
     boolean releaseSegment(int segNumber) {
         segments[segNumber] = null;
         return true;


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/subnetwork/PrepareRoutingSubnetworksTest.java b/core/src/test/java/com/graphhopper/routing/subnetwork/PrepareRoutingSubnetworksTest.java
index 9beebc563..fc7850d9e 100644
--- a/core/src/test/java/com/graphhopper/routing/subnetwork/PrepareRoutingSubnetworksTest.java
+++ b/core/src/test/java/com/graphhopper/routing/subnetwork/PrepareRoutingSubnetworksTest.java
@@ -69,17 +69,16 @@ public class PrepareRoutingSubnetworksTest {
 
     @Test
     public void testRemoveSubnetworkIfOnlyOneVehicle() {
+        FlagEncoder encoder = em.fetchEdgeEncoders().iterator().next();
         GraphHopperStorage g = createSubnetworkTestStorage(em);
         PrepareRoutingSubnetworks instance = new PrepareRoutingSubnetworks(g, Collections.singletonList(
                 new PrepareRoutingSubnetworks.PrepareJob("car", accessEnc, null)));
         // this rules out the upper small network
         instance.setMinNetworkSize(4);
         instance.doWork();
-        g.optimize();
-        assertEquals(6, g.getNodes());
         assertTrue(GHUtility.getProblems(g).isEmpty());
-        EdgeExplorer explorer = g.createEdgeExplorer();
-        assertEquals(GHUtility.asSet(2, 1, 5), GHUtility.getNeighbors(explorer.setBaseNode(3)));
+        EdgeExplorer explorer = g.createEdgeExplorer(DefaultEdgeFilter.allEdges(encoder));
+        assertEquals(GHUtility.asSet(), GHUtility.getNeighbors(explorer.setBaseNode(4)));
 
         // this time we lower the threshold and the small network will remain
         g = createSubnetworkTestStorage(em);
@@ -87,8 +86,8 @@ public class PrepareRoutingSubnetworksTest {
                 new PrepareRoutingSubnetworks.PrepareJob("car", accessEnc, null)));
         instance.setMinNetworkSize(3);
         instance.doWork();
-        g.optimize();
-        assertEquals(9, g.getNodes());
+        explorer = g.createEdgeExplorer(DefaultEdgeFilter.allEdges(encoder));
+        assertEquals(GHUtility.asSet(5, 6), GHUtility.getNeighbors(explorer.setBaseNode(4)));
     }
 
     @Test
@@ -101,11 +100,9 @@ public class PrepareRoutingSubnetworksTest {
         // this rules out the upper small network
         instance.setMinNetworkSize(4);
         instance.doWork();
-        g.optimize();
-        assertEquals(6, g.getNodes());
         assertTrue(GHUtility.getProblems(g).isEmpty());
-        EdgeExplorer explorer = g.createEdgeExplorer();
-        assertEquals(GHUtility.asSet(2, 1, 5), GHUtility.getNeighbors(explorer.setBaseNode(3)));
+        EdgeExplorer explorer = g.createEdgeExplorer(DefaultEdgeFilter.allEdges(encoder));
+        assertEquals(GHUtility.asSet(), GHUtility.getNeighbors(explorer.setBaseNode(4)));
 
         // this time we lower the threshold and the small network will remain
         g = createSubnetworkTestStorage(em);
@@ -113,8 +110,8 @@ public class PrepareRoutingSubnetworksTest {
                 new PrepareRoutingSubnetworks.PrepareJob("car", accessEnc, null)));
         instance.setMinNetworkSize(3);
         instance.doWork();
-        g.optimize();
-        assertEquals(9, g.getNodes());
+        explorer = g.createEdgeExplorer(DefaultEdgeFilter.allEdges(encoder));
+        assertEquals(GHUtility.asSet(5, 6), GHUtility.getNeighbors(explorer.setBaseNode(4)));
     }
 
     @Test
@@ -166,9 +163,6 @@ public class PrepareRoutingSubnetworksTest {
         PrepareRoutingSubnetworks instance = new PrepareRoutingSubnetworks(g, prepareJobs);
         instance.setMinNetworkSize(5);
         instance.doWork();
-        g.optimize();
-        // remove nothing because of two vehicles with different subnetworks
-        assertEquals(9, g.getNodes());
 
         EdgeExplorer carExplorer = g.createEdgeExplorer(DefaultEdgeFilter.allEdges(carEncoder));
         assertEquals(GHUtility.asSet(7, 2, 1), GHUtility.getNeighbors(carExplorer.setBaseNode(3)));
@@ -182,8 +176,6 @@ public class PrepareRoutingSubnetworksTest {
         instance = new PrepareRoutingSubnetworks(g, prepareJobs);
         instance.setMinNetworkSize(5);
         instance.doWork();
-        g.optimize();
-        assertEquals(6, g.getNodes());
     }
 
     GraphHopperStorage createSubnetworkTestStorageWithOneWays(EncodingManager em) {
@@ -217,10 +209,6 @@ public class PrepareRoutingSubnetworksTest {
         // the (7) and the (5,6) components get removed -> 2 remaining components and
         // 3 removed edges total
         assertEquals(3, removed);
-        instance.markNodesRemovedIfUnreachable();
-        g.optimize();
-
-        assertEquals(8, g.getNodes());
     }
 
     @Test
@@ -234,11 +222,6 @@ public class PrepareRoutingSubnetworksTest {
         int removed = instance.removeSmallSubNetworks(job);
 
         assertEquals(3, removed);
-        instance.markNodesRemovedIfUnreachable();
-        g.optimize();
-
-        assertEquals(8, g.getNodes());
-
         assertTrue(isConsistent(g));
         g.edge(7, 8);
         assertTrue(isConsistent(g));
diff --git a/core/src/test/java/com/graphhopper/storage/AbstractGraphStorageTester.java b/core/src/test/java/com/graphhopper/storage/AbstractGraphStorageTester.java
index f8c559e08..b2d192fce 100644
--- a/core/src/test/java/com/graphhopper/storage/AbstractGraphStorageTester.java
+++ b/core/src/test/java/com/graphhopper/storage/AbstractGraphStorageTester.java
@@ -443,103 +443,6 @@ public abstract class AbstractGraphStorageTester {
         assertEquals(1, getCountAll(1));
     }
 
-    @Test
-    public void testDeleteNodeForUnidir() {
-        graph = createGHStorage();
-        NodeAccess na = graph.getNodeAccess();
-        na.setNode(10, 10, 1);
-        na.setNode(6, 6, 1);
-        na.setNode(20, 20, 1);
-        na.setNode(21, 21, 1);
-
-        graph.edge(10, 20, 10, false);
-        graph.edge(21, 6, 10, false);
-
-        graph.markNodeRemoved(0);
-        graph.markNodeRemoved(7);
-        assertEquals(22, graph.getNodes());
-        graph.optimize();
-        assertEquals(20, graph.getNodes());
-
-        assertEquals(1, getCountIn(getIdOf(graph, 20)));
-        assertEquals(0, getCountOut(getIdOf(graph, 20)));
-
-        assertEquals(1, getCountOut(getIdOf(graph, 10)));
-        assertEquals(0, getCountIn(getIdOf(graph, 10)));
-
-        assertEquals(1, getCountIn(getIdOf(graph, 6)));
-        assertEquals(0, getCountOut(getIdOf(graph, 6)));
-
-        assertEquals(1, getCountOut(getIdOf(graph, 21)));
-        assertEquals(0, getCountIn(getIdOf(graph, 21)));
-    }
-
-    @Test
-    public void testComplexDeleteNode() {
-        testDeleteNodes(21);
-    }
-
-    @Test
-    public void testComplexDeleteNode2() {
-        testDeleteNodes(6);
-    }
-
-    public void testDeleteNodes(int fillToSize) {
-        graph = createGHStorage();
-        NodeAccess na = graph.getNodeAccess();
-        na.setNode(0, 12, 23);
-        na.setNode(1, 38.33f, 135.3f);
-        na.setNode(2, 3, 3);
-        na.setNode(3, 78, 89);
-        na.setNode(4, 2, 1);
-        na.setNode(5, 2.5f, 1);
-
-        int deleted = 2;
-        for (int i = 6; i < fillToSize; i++) {
-            na.setNode(i, i * 1.5, i * 1.6);
-            if (i % 3 == 0) {
-                graph.markNodeRemoved(i);
-                deleted++;
-            } else {
-                // connect to
-                // ... a deleted node
-                graph.edge(i, 0, 10 * i, true);
-                // ... a non-deleted and non-moved node
-                graph.edge(i, 2, 10 * i, true);
-                // ... a moved node
-                graph.edge(i, fillToSize - 1, 10 * i, true);
-            }
-        }
-
-        graph.edge(0, 1, 10, true);
-        graph.edge(0, 3, 20, false);
-        graph.edge(3, 5, 20, true);
-        graph.edge(1, 5, 20, false);
-
-        graph.markNodeRemoved(0);
-        graph.markNodeRemoved(2);
-        // no deletion happened
-        assertEquals(fillToSize, graph.getNodes());
-
-        assertTrue(GHUtility.getProblems(graph).isEmpty());
-
-        // now actually perform deletion
-        graph.optimize();
-
-        assertTrue(GHUtility.getProblems(graph).isEmpty());
-
-        assertEquals(fillToSize - deleted, graph.getNodes());
-        int id1 = getIdOf(graph, 38.33f);
-        assertEquals(135.3f, na.getLongitude(id1), 1e-4);
-        assertTrue(containsLatitude(graph, carAllExplorer.setBaseNode(id1), 2.5));
-        assertFalse(containsLatitude(graph, carAllExplorer.setBaseNode(id1), 12));
-
-        int id3 = getIdOf(graph, 78);
-        assertEquals(89, na.getLongitude(id3), 1e-4);
-        assertTrue(containsLatitude(graph, carAllExplorer.setBaseNode(id3), 2.5));
-        assertFalse(containsLatitude(graph, carAllExplorer.setBaseNode(id3), 12));
-    }
-
     public boolean containsLatitude(Graph g, EdgeIterator iter, double latitude) {
         NodeAccess na = g.getNodeAccess();
         while (iter.next()) {
@@ -549,126 +452,6 @@ public abstract class AbstractGraphStorageTester {
         return false;
     }
 
-    @Test
-    public void testSimpleDelete() {
-        graph = createGHStorage();
-        NodeAccess na = graph.getNodeAccess();
-        na.setNode(0, 12, 23);
-        na.setNode(1, 38.33f, 135.3f);
-        na.setNode(2, 3, 3);
-        na.setNode(3, 78, 89);
-
-        graph.edge(3, 0, 21, true);
-        graph.edge(5, 0, 22, true);
-        graph.edge(5, 3, 23, true);
-
-        graph.markNodeRemoved(0);
-        graph.markNodeRemoved(3);
-
-        assertEquals(6, graph.getNodes());
-        assertTrue(GHUtility.getProblems(graph).isEmpty());
-
-        // now actually perform deletion
-        graph.optimize();
-
-        assertEquals(4, graph.getNodes());
-        assertTrue(GHUtility.getProblems(graph).isEmpty());
-        // shouldn't change anything
-        graph.optimize();
-        assertEquals(4, graph.getNodes());
-        assertTrue(GHUtility.getProblems(graph).isEmpty());
-    }
-
-    @Test
-    public void testSimpleDelete2() {
-        graph = createGHStorage();
-        NodeAccess na = graph.getNodeAccess();
-        assertEquals(-1, getIdOf(graph, 12));
-        na.setNode(9, 9, 1);
-        assertEquals(-1, getIdOf(graph, 12));
-
-        na.setNode(11, 11, 1);
-        na.setNode(12, 12, 1);
-
-        // mini subnetwork which gets completely removed:
-        graph.edge(5, 10, 510, true);
-        graph.markNodeRemoved(5);
-        graph.markNodeRemoved(10);
-
-        PointList pl = new PointList();
-        pl.add(1, 2, Double.NaN);
-        pl.add(1, 3, Double.NaN);
-        graph.edge(9, 11, 911, true).setWayGeometry(pl);
-        graph.edge(9, 12, 912, true).setWayGeometry(pl);
-
-        assertEquals(13, graph.getNodes());
-        assertTrue(GHUtility.getProblems(graph).isEmpty());
-
-        // perform deletion
-        graph.optimize();
-
-        assertEquals(11, graph.getNodes());
-        assertTrue(GHUtility.getProblems(graph).isEmpty());
-
-        int id11 = getIdOf(graph, 11); // is now 10
-        int id12 = getIdOf(graph, 12); // is now 5
-        int id9 = getIdOf(graph, 9); // is now 9
-        assertEquals(GHUtility.asSet(id12, id11), GHUtility.getNeighbors(carAllExplorer.setBaseNode(id9)));
-        assertEquals(GHUtility.asSet(id9), GHUtility.getNeighbors(carAllExplorer.setBaseNode(id11)));
-        assertEquals(GHUtility.asSet(id9), GHUtility.getNeighbors(carAllExplorer.setBaseNode(id12)));
-
-        EdgeIterator iter = carAllExplorer.setBaseNode(id9);
-        assertTrue(iter.next());
-        assertEquals(id12, iter.getAdjNode());
-        assertEquals(2, iter.fetchWayGeometry(FetchMode.PILLAR_ONLY).getLongitude(0), 1e-7);
-
-        assertTrue(iter.next());
-        assertEquals(id11, iter.getAdjNode());
-        assertEquals(2, iter.fetchWayGeometry(FetchMode.PILLAR_ONLY).getLongitude(0), 1e-7);
-    }
-
-    @Test
-    public void testSimpleDelete3() {
-        graph = createGHStorage();
-        NodeAccess na = graph.getNodeAccess();
-        na.setNode(7, 7, 1);
-        na.setNode(8, 8, 1);
-        na.setNode(9, 9, 1);
-        na.setNode(11, 11, 1);
-
-        // mini subnetwork which gets completely removed:
-        graph.edge(5, 10, 510, true);
-        graph.markNodeRemoved(3);
-        graph.markNodeRemoved(4);
-        graph.markNodeRemoved(5);
-        graph.markNodeRemoved(10);
-
-        graph.edge(9, 11, 911, true);
-        graph.edge(7, 9, 78, true);
-        graph.edge(8, 9, 89, true);
-
-        // perform deletion
-        graph.optimize();
-
-        assertTrue(GHUtility.getProblems(graph).isEmpty());
-
-        assertEquals(3, getCountAll(getIdOf(graph, 9)));
-        assertEquals(1, getCountAll(getIdOf(graph, 7)));
-        assertEquals(1, getCountAll(getIdOf(graph, 8)));
-        assertEquals(1, getCountAll(getIdOf(graph, 11)));
-    }
-
-    @Test
-    public void testDeleteAndOptimize() {
-        graph = createGHStorage();
-        NodeAccess na = graph.getNodeAccess();
-        na.setNode(20, 10, 10);
-        na.setNode(21, 10, 11);
-        graph.markNodeRemoved(20);
-        graph.optimize();
-        assertEquals(11, na.getLongitude(20), 1e-5);
-    }
-
     @Test
     public void testBounds() {
         graph = createGHStorage();
@@ -739,17 +522,6 @@ public abstract class AbstractGraphStorageTester {
         assertEquals(2, iter.getAdjNode());
         iter = graph.getEdgeIteratorState(edgeId, 1);
         assertNull(iter);
-
-        // delete
-        graph.markNodeRemoved(1);
-        graph.optimize();
-
-        // throw exception if accessing deleted edge
-        try {
-            graph.getEdgeIteratorState(iter1.getEdge(), -1);
-            fail();
-        } catch (Exception ex) {
-        }
     }
 
     @Test
@@ -913,42 +685,6 @@ public abstract class AbstractGraphStorageTester {
         assertFalse(iter.next());
     }
 
-    @Test
-    public void testGetAllEdgesWithDelete() {
-        graph = createGHStorage();
-        NodeAccess na = graph.getNodeAccess();
-        na.setNode(0, 0, 5);
-        na.setNode(1, 1, 5);
-        na.setNode(2, 2, 5);
-        na.setNode(3, 3, 5);
-        graph.edge(0, 1, 1, true);
-        graph.edge(0, 2, 1, true);
-        graph.edge(1, 2, 1, true);
-        graph.edge(2, 3, 1, true);
-        AllEdgesIterator iter = graph.getAllEdges();
-        assertEquals(4, GHUtility.count(iter));
-        assertEquals(4, iter.length());
-
-        // delete
-        graph.markNodeRemoved(1);
-        graph.optimize();
-        iter = graph.getAllEdges();
-        assertEquals(2, GHUtility.count(iter));
-        assertEquals(4, iter.length());
-
-        iter = graph.getAllEdges();
-        assertTrue(iter.next());
-        EdgeIteratorState eState = iter.detach(false);
-        assertEquals(iter.toString(), eState.toString());
-        assertTrue(iter.next());
-        assertNotEquals(iter.toString(), eState.toString());
-
-        EdgeIteratorState eState2 = iter.detach(true);
-        assertEquals(iter.getAdjNode(), eState2.getBaseNode());
-        assertEquals(iter.getBaseNode(), eState2.getAdjNode());
-        assertFalse(iter.next());
-    }
-
     @Test
     public void testStringIndex() {
         graph = createGHStorage();
diff --git a/core/src/test/java/com/graphhopper/storage/DataAccessTest.java b/core/src/test/java/com/graphhopper/storage/DataAccessTest.java
index 0734e4a5b..dc6eea0c3 100644
--- a/core/src/test/java/com/graphhopper/storage/DataAccessTest.java
+++ b/core/src/test/java/com/graphhopper/storage/DataAccessTest.java
@@ -200,70 +200,6 @@ public abstract class DataAccessTest {
         da.close();
     }
 
-    @Test
-    public void testTrimTo() {
-        DataAccess da = createDataAccess(name);
-        da.setSegmentSize(128);
-        da.create(128 * 11);
-        da.setInt(1 * 4, 10);
-        da.setInt(27 * 4, 200);
-        da.setInt(31 * 4, 301);
-        da.setInt(32 * 4, 302);
-        da.setInt(337 * 4, 4000);
-
-        // now 11 segments: (337 + 1) * 4 = 1352
-        assertEquals(11, da.getSegments());
-        assertEquals(11 * 128, da.getCapacity());
-
-        // now 3 segments
-        da.trimTo(128 * 2 + 1);
-        assertEquals(3, da.getSegments());
-
-        // now 2 segments
-        da.trimTo(128 * 2);
-        assertEquals(2, da.getSegments());
-        assertEquals(301, da.getInt(31 * 4));
-        assertEquals(302, da.getInt(32 * 4));
-
-        // now only one segment
-        da.trimTo(128 * 1);
-        assertEquals(1, da.getSegments());
-        assertEquals(301, da.getInt(31 * 4));
-
-        // at least one segment
-        da.trimTo(0);
-        assertEquals(1, da.getSegments());
-        da.close();
-    }
-
-    @Test
-    public void testBoundsCheck() {
-        DataAccess da = createDataAccess(name);
-        da.setSegmentSize(128);
-        da.create(128 * 11);
-        da.setInt(32 * 4, 302);
-
-        // make smaller
-        da.trimTo(128 * 1);
-        try {
-            assertEquals(302, da.getInt(32 * 4));
-            assertTrue(false);
-        } catch (Exception ex) {
-        }
-        da.close();
-
-        da = createDataAccess(name);
-        da.create(128);
-        da.setInt(31 * 4, 200);
-        try {
-            // this should fail with an index out of bounds exception
-            da.setInt(32 * 4, 220);
-            assertFalse(true);
-        } catch (Exception ex) {
-        }
-        da.close();
-    }
-
     @Test
     public void testSegmentSize() {
         DataAccess da = createDataAccess(name);
diff --git a/core/src/test/java/com/graphhopper/storage/GraphHopperStorageTest.java b/core/src/test/java/com/graphhopper/storage/GraphHopperStorageTest.java
index d0bf7b9c8..72e2cc5ba 100644
--- a/core/src/test/java/com/graphhopper/storage/GraphHopperStorageTest.java
+++ b/core/src/test/java/com/graphhopper/storage/GraphHopperStorageTest.java
@@ -186,19 +186,6 @@ public class GraphHopperStorageTest extends AbstractGraphStorageTester {
         storage.close();
     }
 
-    @Test
-    public void testEnsureSize() {
-        Directory dir = new RAMDirectory();
-        graph = newGHStorage(dir, false).create(defaultSize);
-        int roughEdgeRowLength = 4 * 8;
-        int testIndex = dir.find("edges", DAType.RAM_INT).getSegmentSize() * 3 / roughEdgeRowLength;
-        // we need a big node index to trigger multiple segments, but low enough to avoid OOM
-        graph.edge(0, testIndex, 10, true);
-
-        // test if optimize works without error
-        graph.optimize();
-    }
-
     @Test
     public void testBigDataEdge() {
         Directory dir = new RAMDirectory();
diff --git a/reader-osm/src/test/java/com/graphhopper/reader/osm/GraphHopperOSMTest.java b/reader-osm/src/test/java/com/graphhopper/reader/osm/GraphHopperOSMTest.java
index adb019a59..704eaba58 100644
--- a/reader-osm/src/test/java/com/graphhopper/reader/osm/GraphHopperOSMTest.java
+++ b/reader-osm/src/test/java/com/graphhopper/reader/osm/GraphHopperOSMTest.java
@@ -195,7 +195,7 @@ public class GraphHopperOSMTest {
             }
         });
 
-        assertEquals(47, indexNodeList.size());
+        assertEquals(57, indexNodeList.size());
         for (int nodeId : indexNodeList) {
             if (!bbox.contains(na.getLatitude(nodeId), na.getLongitude(nodeId)))
                 fail("bbox " + bbox + " should contain " + nodeId);
diff --git a/web/src/test/java/com/graphhopper/http/resources/SPTResourceTest.java b/web/src/test/java/com/graphhopper/http/resources/SPTResourceTest.java
index 54ec094e6..2f0a748c4 100644
--- a/web/src/test/java/com/graphhopper/http/resources/SPTResourceTest.java
+++ b/web/src/test/java/com/graphhopper/http/resources/SPTResourceTest.java
@@ -96,9 +96,9 @@ public class SPTResourceTest {
         String[] lines = rspCsvString.split("\n");
         assertTrue(lines.length > 500);
         assertEquals("prev_node_id,edge_id,node_id,time,distance", lines[0]);
-        assertEquals("-1,-1,1884,0,0", lines[1]);
-        assertEquals("1884,2273,1324,3817,74", lines[2]);
-        assertEquals("1884,2272,263,13496,262", lines[3]);
+        assertEquals("-1,-1,1944,0,0", lines[1]);
+        assertEquals("1944,2273,1324,3817,74", lines[2]);
+        assertEquals("1944,2272,263,13496,262", lines[3]);
     }
 
     @Test