Repository: graphhopper/graphhopper
Pull request #1751 (2019-10-15 20:49:19)

Extract GraphModification from QueryGraph
Here I have separated all the data that is needed to determine how the `EdgeExplorer`s of `QueryGraph` have to be modified (compared to the underlying `Graph`) when we insert virtual nodes from `QueryGraph`. Or, to put this in other words: So far we put a `List<QueryResult>` into `QueryGraph.lookup()` and got a `QueryGraph` that acts like a `Graph` with additional virtual nodes. With this PR we put a `List<QueryResult>` into `GraphModificationBuilder`, get back a `GraphModification` and use this to realize `QueryGraph`. Why ? Because I want to use `GraphModification`, but not `QueryGraph`. 
So far all this is (package) internal (in a new `routing.querygraph` package).

Possible (future) improvements: 

- [ ] do not create `GraphModification` *inside* `QueryGraph`, but rather pass it to it, so `QueryGraph` can deal with (more general/different (?)) modifications
- [ ] generalize `QueryGraph` to something like `WrapperGraph` (maybe thats the same as above)



Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/EdgeChangeBuilder.java b/core/src/main/java/com/graphhopper/routing/querygraph/EdgeChangeBuilder.java
new file mode 100644
index 000000000..d333f0670
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/EdgeChangeBuilder.java
@@ -0,0 +1,142 @@
+/*
+ *  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.querygraph;
+
+import com.carrotsearch.hppc.IntArrayList;
+import com.carrotsearch.hppc.IntObjectMap;
+import com.carrotsearch.hppc.procedures.IntProcedure;
+import com.graphhopper.coll.GHIntHashSet;
+import com.graphhopper.util.EdgeIteratorState;
+
+import java.util.List;
+
+import static com.graphhopper.routing.querygraph.QueryGraph.*;
+
+/**
+ * Helper class for {@link GraphModificationBuilder}
+ *
+ * @see #build(IntArrayList, List, int, IntObjectMap)
+ */
+class EdgeChangeBuilder {
+    private final IntArrayList closestEdges;
+    private final List<VirtualEdgeIteratorState> virtualEdges;
+    private final IntObjectMap<GraphModification.EdgeChanges> edgeChangesAtRealNodes;
+    private final int firstVirtualNodeId;
+
+    /**
+     * Builds a mapping between real node ids and the set of changes for their adjacent edges.
+     *
+     * @param edgeChangesAtRealNodes output parameter, you need to pass an empty & modifiable map and the results will
+     *                               be added to it
+     */
+    static void build(IntArrayList closestEdges, List<VirtualEdgeIteratorState> virtualEdges, int firstVirtualNodeId, IntObjectMap<GraphModification.EdgeChanges> edgeChangesAtRealNodes) {
+        new EdgeChangeBuilder(closestEdges, virtualEdges, firstVirtualNodeId, edgeChangesAtRealNodes).build();
+    }
+
+    private EdgeChangeBuilder(IntArrayList closestEdges, List<VirtualEdgeIteratorState> virtualEdges, int firstVirtualNodeId, IntObjectMap<GraphModification.EdgeChanges> edgeChangesAtRealNodes) {
+        this.closestEdges = closestEdges;
+        this.virtualEdges = virtualEdges;
+        this.firstVirtualNodeId = firstVirtualNodeId;
+        if (!edgeChangesAtRealNodes.isEmpty()) {
+            throw new IllegalArgumentException("real node modifications need to be empty");
+        }
+        this.edgeChangesAtRealNodes = edgeChangesAtRealNodes;
+    }
+
+    private void build() {
+        final GHIntHashSet towerNodesToChange = new GHIntHashSet(getNumVirtualNodes());
+
+        // 1. for every real node adjacent to a virtual one we collect the virtual edges, also build a set of
+        //    these adjacent real nodes so we can use them in the next step
+        for (int i = 0; i < getNumVirtualNodes(); i++) {
+            // base node
+            EdgeIteratorState baseRevEdge = getVirtualEdge(i * 4 + VE_BASE_REV);
+            int towerNode = baseRevEdge.getAdjNode();
+            if (!isVirtualNode(towerNode)) {
+                towerNodesToChange.add(towerNode);
+                addVirtualEdges(true, towerNode, i);
+            }
+
+            // adj node
+            EdgeIteratorState adjEdge = getVirtualEdge(i * 4 + VE_ADJ);
+            towerNode = adjEdge.getAdjNode();
+            if (!isVirtualNode(towerNode)) {
+                towerNodesToChange.add(towerNode);
+                addVirtualEdges(false, towerNode, i);
+            }
+        }
+
+        // 2. build the list of removed edges for all real nodes adjacent to virtual ones
+        towerNodesToChange.forEach(new IntProcedure() {
+            @Override
+            public void apply(int value) {
+                addRemovedEdges(value);
+            }
+        });
+    }
+
+    /**
+     * Adds the virtual edges adjacent to the real tower nodes
+     */
+    private void addVirtualEdges(boolean base, int node, int virtNode) {
+        GraphModification.EdgeChanges edgeChanges = edgeChangesAtRealNodes.get(node);
+        if (edgeChanges == null) {
+            edgeChanges = new GraphModification.EdgeChanges(2, 2);
+            edgeChangesAtRealNodes.put(node, edgeChanges);
+        }
+        EdgeIteratorState edge = base
+                ? getVirtualEdge(virtNode * 4 + VE_BASE)
+                : getVirtualEdge(virtNode * 4 + VE_ADJ_REV);
+        edgeChanges.getAdditionalEdges().add(edge);
+    }
+
+    /**
+     * Adds the ids of the removed edges at the real tower nodes. We need to do this such that we cannot 'skip'
+     * virtual nodes by just using the original edges and also to prevent u-turns at the real nodes adjacent to the
+     * virtual ones.
+     */
+    private void addRemovedEdges(int towerNode) {
+        if (isVirtualNode(towerNode))
+            throw new IllegalStateException("Node should not be virtual:" + towerNode + ", " + edgeChangesAtRealNodes);
+
+        GraphModification.EdgeChanges edgeChanges = edgeChangesAtRealNodes.get(towerNode);
+        List<EdgeIteratorState> existingEdges = edgeChanges.getAdditionalEdges();
+        IntArrayList removedEdges = edgeChanges.getRemovedEdges();
+        for (EdgeIteratorState existingEdge : existingEdges) {
+            removedEdges.add(getClosestEdge(existingEdge.getAdjNode()));
+        }
+    }
+
+    private boolean isVirtualNode(int nodeId) {
+        return nodeId >= firstVirtualNodeId;
+    }
+
+    private int getNumVirtualNodes() {
+        return closestEdges.size();
+    }
+
+    private int getClosestEdge(int node) {
+        return closestEdges.get(node - firstVirtualNodeId);
+    }
+
+    private VirtualEdgeIteratorState getVirtualEdge(int virtualEdgeId) {
+        return virtualEdges.get(virtualEdgeId);
+    }
+
+}
diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/GraphModification.java b/core/src/main/java/com/graphhopper/routing/querygraph/GraphModification.java
new file mode 100644
index 000000000..7bc5a1d48
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/GraphModification.java
@@ -0,0 +1,96 @@
+/*
+ *  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.querygraph;
+
+import com.carrotsearch.hppc.IntArrayList;
+import com.carrotsearch.hppc.IntObjectMap;
+import com.graphhopper.coll.GHIntObjectHashMap;
+import com.graphhopper.util.EdgeIteratorState;
+import com.graphhopper.util.PointList;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * This class holds the data that is necessary to add additional nodes and edges to an existing graph, as it is needed
+ * when we want to start/end a route at a location that is in between the actual nodes of the graph (virtual nodes+edges).
+ */
+class GraphModification {
+    // stores the coordinates of the additional/virtual nodes
+    private final PointList virtualNodes;
+    // stores the closest edge id for each virtual node
+    private final IntArrayList closestEdges;
+    // stores the virtual edges, for every virtual node there are four such edges: base-snap, snap-base, snap-adj, adj-snap.
+    private final List<VirtualEdgeIteratorState> virtualEdges;
+    // stores the changes that need to be done to the real nodes
+    private final IntObjectMap<EdgeChanges> edgeChangesAtRealNodes;
+
+    GraphModification(int numVirtualNodes, boolean is3D) {
+        this.virtualNodes = new PointList(numVirtualNodes, is3D);
+        this.virtualEdges = new ArrayList<>(numVirtualNodes * 2);
+        this.closestEdges = new IntArrayList(numVirtualNodes);
+        edgeChangesAtRealNodes = new GHIntObjectHashMap<>(numVirtualNodes * 3);
+    }
+
+    int getNumVirtualEdges() {
+        return virtualEdges.size();
+    }
+
+    void addVirtualEdge(VirtualEdgeIteratorState virtualEdge) {
+        virtualEdges.add(virtualEdge);
+    }
+
+    VirtualEdgeIteratorState getVirtualEdge(int edgeId) {
+        return virtualEdges.get(edgeId);
+    }
+
+    List<VirtualEdgeIteratorState> getVirtualEdges() {
+        return virtualEdges;
+    }
+
+    IntObjectMap<EdgeChanges> getEdgeChangesAtRealNodes() {
+        return edgeChangesAtRealNodes;
+    }
+
+    PointList getVirtualNodes() {
+        return virtualNodes;
+    }
+
+    IntArrayList getClosestEdges() {
+        return closestEdges;
+    }
+
+    static class EdgeChanges {
+        private final List<EdgeIteratorState> additionalEdges;
+        private final IntArrayList removedEdges;
+
+        EdgeChanges(int expectedNumAdditionalEdges, int expectedNumRemovedEdges) {
+            additionalEdges = new ArrayList<>(expectedNumAdditionalEdges);
+            removedEdges = new IntArrayList(expectedNumRemovedEdges);
+        }
+
+        List<EdgeIteratorState> getAdditionalEdges() {
+            return additionalEdges;
+        }
+
+        IntArrayList getRemovedEdges() {
+            return removedEdges;
+        }
+    }
+}
diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/GraphModificationBuilder.java b/core/src/main/java/com/graphhopper/routing/querygraph/GraphModificationBuilder.java
new file mode 100644
index 000000000..65ef0021e
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/GraphModificationBuilder.java
@@ -0,0 +1,248 @@
+/*
+ *  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.querygraph;
+
+import com.carrotsearch.hppc.predicates.IntObjectPredicate;
+import com.graphhopper.coll.GHIntObjectHashMap;
+import com.graphhopper.storage.Graph;
+import com.graphhopper.storage.IntsRef;
+import com.graphhopper.storage.index.QueryResult;
+import com.graphhopper.util.EdgeIteratorState;
+import com.graphhopper.util.GHUtility;
+import com.graphhopper.util.Helper;
+import com.graphhopper.util.PointList;
+import com.graphhopper.util.shapes.GHPoint;
+import com.graphhopper.util.shapes.GHPoint3D;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+
+/**
+ * Builds the data structures that represent the changes to a graph as realized by {@link QueryGraph}
+ */
+class GraphModificationBuilder {
+    private final int firstVirtualNodeId;
+    private final int firstVirtualEdgeId;
+    private final boolean is3D;
+    private GraphModification graphModification;
+
+    public static GraphModification build(Graph graph, List<QueryResult> queryResults) {
+        return build(graph.getNodes(), graph.getEdges(), graph.getNodeAccess().is3D(), queryResults);
+    }
+
+    public static GraphModification build(int firstVirtualNodeId, int firstVirtualEdgeId, boolean is3D, List<QueryResult> queryResults) {
+        return new GraphModificationBuilder(firstVirtualNodeId, firstVirtualEdgeId, is3D).build(queryResults);
+    }
+
+    private GraphModificationBuilder(int firstVirtualNodeId, int firstVirtualEdgeId, boolean is3D) {
+        this.firstVirtualNodeId = firstVirtualNodeId;
+        this.firstVirtualEdgeId = firstVirtualEdgeId;
+        this.is3D = is3D;
+    }
+
+    private GraphModification build(List<QueryResult> resList) {
+        graphModification = new GraphModification(resList.size(), is3D);
+        buildVirtualEdges(resList);
+        buildEdgeChangesAtRealNodes();
+        return graphModification;
+    }
+
+    /**
+     * For all specified query results calculate the snapped point and if necessary set the closest node
+     * to a virtual one and reverse the closest edge. Additionally the wayIndex can change if an edge is
+     * swapped.
+     */
+    private void buildVirtualEdges(List<QueryResult> resList) {
+        GHIntObjectHashMap<List<QueryResult>> edge2res = new GHIntObjectHashMap<>(resList.size());
+
+        // Phase 1
+        // calculate snapped point and swap direction of closest edge if necessary
+        for (QueryResult res : resList) {
+            // Do not create virtual node for a query result if it is directly on a tower node or not found
+            if (res.getSnappedPosition() == QueryResult.Position.TOWER)
+                continue;
+
+            EdgeIteratorState closestEdge = res.getClosestEdge();
+            if (closestEdge == null)
+                throw new IllegalStateException("Do not call QueryGraph.lookup with invalid QueryResult " + res);
+
+            int base = closestEdge.getBaseNode();
+
+            // Force the identical direction for all closest edges.
+            // It is important to sort multiple results for the same edge by its wayIndex
+            boolean doReverse = base > closestEdge.getAdjNode();
+            if (base == closestEdge.getAdjNode()) {
+                // check for special case #162 where adj == base and force direction via latitude comparison
+                PointList pl = closestEdge.fetchWayGeometry(0);
+                if (pl.size() > 1)
+                    doReverse = pl.getLatitude(0) > pl.getLatitude(pl.size() - 1);
+            }
+
+            if (doReverse) {
+                closestEdge = closestEdge.detach(true);
+                PointList fullPL = closestEdge.fetchWayGeometry(3);
+                res.setClosestEdge(closestEdge);
+                if (res.getSnappedPosition() == QueryResult.Position.PILLAR)
+                    // ON pillar node
+                    res.setWayIndex(fullPL.getSize() - res.getWayIndex() - 1);
+                else
+                    // for case "OFF pillar node"
+                    res.setWayIndex(fullPL.getSize() - res.getWayIndex() - 2);
+
+                if (res.getWayIndex() < 0)
+                    throw new IllegalStateException("Problem with wayIndex while reversing closest edge:" + closestEdge + ", " + res);
+            }
+
+            // find multiple results on same edge
+            int edgeId = closestEdge.getEdge();
+            List<QueryResult> list = edge2res.get(edgeId);
+            if (list == null) {
+                list = new ArrayList<>(5);
+                edge2res.put(edgeId, list);
+            }
+            list.add(res);
+        }
+
+        // Phase 2 - now it is clear which points cut one edge
+        // 1. create point lists
+        // 2. create virtual edges between virtual nodes and its neighbor (virtual or normal nodes)
+        edge2res.forEach(new IntObjectPredicate<List<QueryResult>>() {
+            @Override
+            public boolean apply(int edgeId, List<QueryResult> results) {
+                // we can expect at least one entry in the results
+                EdgeIteratorState closestEdge = results.get(0).getClosestEdge();
+                final PointList fullPL = closestEdge.fetchWayGeometry(3);
+                int baseNode = closestEdge.getBaseNode();
+                Collections.sort(results, new Comparator<QueryResult>() {
+                    @Override
+                    public int compare(QueryResult o1, QueryResult o2) {
+                        int diff = Integer.compare(o1.getWayIndex(), o2.getWayIndex());
+                        if (diff == 0) {
+                            return Double.compare(distanceOfSnappedPointToPillarNode(o1), distanceOfSnappedPointToPillarNode(o2));
+                        } else {
+                            return diff;
+                        }
+                    }
+
+                    private double distanceOfSnappedPointToPillarNode(QueryResult o) {
+                        GHPoint snappedPoint = o.getSnappedPoint();
+                        double fromLat = fullPL.getLatitude(o.getWayIndex());
+                        double fromLon = fullPL.getLongitude(o.getWayIndex());
+                        return Helper.DIST_PLANE.calcNormalizedDist(fromLat, fromLon, snappedPoint.lat, snappedPoint.lon);
+                    }
+                });
+
+                GHPoint3D prevPoint = fullPL.get(0);
+                int adjNode = closestEdge.getAdjNode();
+                int origEdgeKey = GHUtility.createEdgeKey(baseNode, adjNode, closestEdge.getEdge(), false);
+                int origRevEdgeKey = GHUtility.createEdgeKey(baseNode, adjNode, closestEdge.getEdge(), true);
+                int prevWayIndex = 1;
+                int prevNodeId = baseNode;
+                int virtNodeId = graphModification.getVirtualNodes().getSize() + firstVirtualNodeId;
+                boolean addedEdges = false;
+
+                // Create base and adjacent PointLists for all non-equal virtual nodes.
+                // We do so via inserting them at the correct position of fullPL and cutting the
+                // fullPL into the right pieces.
+                for (QueryResult res : results) {
+                    if (res.getClosestEdge().getBaseNode() != baseNode)
+                        throw new IllegalStateException("Base nodes have to be identical but were not: " + closestEdge + " vs " + res.getClosestEdge());
+
+                    GHPoint3D currSnapped = res.getSnappedPoint();
+
+                    // no new virtual nodes if exactly the same snapped point
+                    if (prevPoint.equals(currSnapped)) {
+                        res.setClosestNode(prevNodeId);
+                        continue;
+                    }
+
+                    graphModification.getClosestEdges().add(res.getClosestEdge().getEdge());
+                    boolean isPillar = res.getSnappedPosition() == QueryResult.Position.PILLAR;
+                    createEdges(origEdgeKey, origRevEdgeKey,
+                            prevPoint, prevWayIndex, isPillar,
+                            res.getSnappedPoint(), res.getWayIndex(),
+                            fullPL, closestEdge, prevNodeId, virtNodeId);
+
+                    graphModification.getVirtualNodes().add(currSnapped.lat, currSnapped.lon, currSnapped.ele);
+
+                    // add edges again to set adjacent edges for newVirtNodeId
+                    if (addedEdges) {
+                        graphModification.addVirtualEdge(graphModification.getVirtualEdge(graphModification.getNumVirtualEdges() - 2));
+                        graphModification.addVirtualEdge(graphModification.getVirtualEdge(graphModification.getNumVirtualEdges() - 2));
+                    }
+
+                    addedEdges = true;
+                    res.setClosestNode(virtNodeId);
+                    prevNodeId = virtNodeId;
+                    prevWayIndex = res.getWayIndex() + 1;
+                    prevPoint = currSnapped;
+                    virtNodeId++;
+                }
+
+                // two edges between last result and adjacent node are still missing if not all points skipped
+                if (addedEdges)
+                    createEdges(origEdgeKey, origRevEdgeKey,
+                            prevPoint, prevWayIndex, false,
+                            fullPL.get(fullPL.getSize() - 1), fullPL.getSize() - 2,
+                            fullPL, closestEdge, virtNodeId - 1, adjNode);
+
+                return true;
+            }
+        });
+    }
+
+    private void createEdges(int origEdgeKey, int origRevEdgeKey,
+                             GHPoint3D prevSnapped, int prevWayIndex, boolean isPillar, GHPoint3D currSnapped, int wayIndex,
+                             PointList fullPL, EdgeIteratorState closestEdge,
+                             int prevNodeId, int nodeId) {
+        int max = wayIndex + 1;
+        PointList basePoints = new PointList(max - prevWayIndex + 1, is3D);
+        basePoints.add(prevSnapped.lat, prevSnapped.lon, prevSnapped.ele);
+        for (int i = prevWayIndex; i < max; i++) {
+            basePoints.add(fullPL, i);
+        }
+        if (!isPillar) {
+            basePoints.add(currSnapped.lat, currSnapped.lon, currSnapped.ele);
+        }
+        // basePoints must have at least the size of 2 to make sure fetchWayGeometry(3) returns at least 2
+        assert basePoints.size() >= 2 : "basePoints must have at least two points";
+
+        PointList baseReversePoints = basePoints.clone(true);
+        double baseDistance = basePoints.calcDistance(Helper.DIST_PLANE);
+        int virtEdgeId = firstVirtualEdgeId + graphModification.getNumVirtualEdges();
+
+        boolean reverse = closestEdge.get(EdgeIteratorState.REVERSE_STATE);
+        // edges between base and snapped point
+        VirtualEdgeIteratorState baseEdge = new VirtualEdgeIteratorState(origEdgeKey,
+                virtEdgeId, prevNodeId, nodeId, baseDistance, closestEdge.getFlags(), closestEdge.getName(), basePoints, reverse);
+        VirtualEdgeIteratorState baseReverseEdge = new VirtualEdgeIteratorState(origRevEdgeKey,
+                virtEdgeId, nodeId, prevNodeId, baseDistance, IntsRef.deepCopyOf(closestEdge.getFlags()), closestEdge.getName(), baseReversePoints, !reverse);
+
+        baseEdge.setReverseEdge(baseReverseEdge);
+        baseReverseEdge.setReverseEdge(baseEdge);
+        graphModification.addVirtualEdge(baseEdge);
+        graphModification.addVirtualEdge(baseReverseEdge);
+    }
+
+    private void buildEdgeChangesAtRealNodes() {
+        EdgeChangeBuilder.build(graphModification.getClosestEdges(), graphModification.getVirtualEdges(), firstVirtualNodeId, graphModification.getEdgeChangesAtRealNodes());
+    }
+}
\ No newline at end of file
diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/QueryGraph.java b/core/src/main/java/com/graphhopper/routing/querygraph/QueryGraph.java
index e339d925c..25cfada0a 100644
--- a/core/src/main/java/com/graphhopper/routing/querygraph/QueryGraph.java
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/QueryGraph.java
@@ -17,11 +17,8 @@
  */
 package com.graphhopper.routing.querygraph;
 
-import com.carrotsearch.hppc.IntArrayList;
 import com.carrotsearch.hppc.IntObjectMap;
-import com.carrotsearch.hppc.predicates.IntObjectPredicate;
-import com.carrotsearch.hppc.procedures.IntProcedure;
-import com.graphhopper.coll.GHIntHashSet;
+import com.carrotsearch.hppc.procedures.IntObjectProcedure;
 import com.graphhopper.coll.GHIntObjectHashMap;
 import com.graphhopper.routing.util.AllEdgesIterator;
 import com.graphhopper.routing.util.EdgeFilter;
@@ -29,8 +26,6 @@ import com.graphhopper.storage.*;
 import com.graphhopper.storage.index.QueryResult;
 import com.graphhopper.util.*;
 import com.graphhopper.util.shapes.BBox;
-import com.graphhopper.util.shapes.GHPoint;
-import com.graphhopper.util.shapes.GHPoint3D;
 
 import java.util.*;
 
@@ -51,99 +46,20 @@ public class QueryGraph implements Graph {
     static final int VE_BASE = 0, VE_BASE_REV = 1, VE_ADJ = 2, VE_ADJ_REV = 3;
     private static final AngleCalc AC = Helper.ANGLE_CALC;
     private final Graph mainGraph;
-    private final NodeAccess mainNodeAccess;
     private final int mainNodes;
     private final int mainEdges;
+    // todo: why do we need this and do we still need it when we stop wrapping CHGraph with QueryGraph ?
     private final QueryGraph baseGraph;
     private final GraphExtension wrappedExtension;
     private final Map<EdgeFilter, EdgeExplorer> cacheMap = new HashMap<>(4);
-
-    // For every virtual node there are 4 edges: base-snap, snap-base, snap-adj, adj-snap.
-    List<VirtualEdgeIteratorState> virtualEdges;
-    private List<QueryResult> queryResults;
-    /**
-     * Store lat,lon of virtual tower nodes.
-     */
-    private PointList virtualNodes;
-    private final NodeAccess nodeAccess = new NodeAccess() {
-        @Override
-        public void ensureNode(int nodeId) {
-            mainNodeAccess.ensureNode(nodeId);
-        }
-
-        @Override
-        public boolean is3D() {
-            return mainNodeAccess.is3D();
-        }
-
-        @Override
-        public int getDimension() {
-            return mainNodeAccess.getDimension();
-        }
-
-        @Override
-        public double getLatitude(int nodeId) {
-            if (isVirtualNode(nodeId))
-                return virtualNodes.getLatitude(nodeId - mainNodes);
-            return mainNodeAccess.getLatitude(nodeId);
-        }
-
-        @Override
-        public double getLongitude(int nodeId) {
-            if (isVirtualNode(nodeId))
-                return virtualNodes.getLongitude(nodeId - mainNodes);
-            return mainNodeAccess.getLongitude(nodeId);
-        }
-
-        @Override
-        public double getElevation(int nodeId) {
-            if (isVirtualNode(nodeId))
-                return virtualNodes.getElevation(nodeId - mainNodes);
-            return mainNodeAccess.getElevation(nodeId);
-        }
-
-        @Override
-        public int getAdditionalNodeField(int nodeId) {
-            if (isVirtualNode(nodeId))
-                return 0;
-            return mainNodeAccess.getAdditionalNodeField(nodeId);
-        }
-
-        @Override
-        public void setNode(int nodeId, double lat, double lon) {
-            throw new UnsupportedOperationException("Not supported yet.");
-        }
-
-        @Override
-        public void setNode(int nodeId, double lat, double lon, double ele) {
-            throw new UnsupportedOperationException("Not supported yet.");
-        }
-
-        @Override
-        public void setAdditionalNodeField(int nodeId, int additionalValue) {
-            throw new UnsupportedOperationException("Not supported yet.");
-        }
-
-        @Override
-        public double getLat(int nodeId) {
-            return getLatitude(nodeId);
-        }
-
-        @Override
-        public double getLon(int nodeId) {
-            return getLongitude(nodeId);
-        }
-
-        @Override
-        public double getEle(int nodeId) {
-            return getElevation(nodeId);
-        }
-    };
+    private final NodeAccess nodeAccess;
+    private final GraphModification graphModification;
 
     // Use LinkedHashSet for predictable iteration order.
     private final Set<VirtualEdgeIteratorState> unfavoredEdges = new LinkedHashSet<>(5);
-
     private boolean useEdgeExplorerCache = false;
+    private final IntObjectMap<List<EdgeIteratorState>> virtualEdgesAtRealNodes;
+    private final List<List<EdgeIteratorState>> virtualEdgesAtVirtualNodes;
 
     public static QueryGraph lookup(Graph graph, QueryResult qr) {
         return QueryGraph.lookup(graph, Collections.singletonList(qr));
@@ -154,22 +70,28 @@ public class QueryGraph implements Graph {
     }
 
     public static QueryGraph lookup(Graph graph, List<QueryResult> queryResults) {
-        QueryGraph result = new QueryGraph(graph);
-        result.lookup(queryResults);
-        return result;
+        return new QueryGraph(graph, queryResults);
     }
 
-    public QueryGraph(Graph graph) {
+    private QueryGraph(Graph graph, List<QueryResult> queryResults) {
         mainGraph = graph;
-        mainNodeAccess = graph.getNodeAccess();
         mainNodes = graph.getNodes();
-        mainEdges = graph.getAllEdges().length();
+        mainEdges = graph.getEdges();
+
+        graphModification = GraphModificationBuilder.build(graph, queryResults);
+        nodeAccess = new ExtendedNodeAccess(graph.getNodeAccess(), graphModification.getVirtualNodes(), mainNodes);
 
         if (mainGraph.getExtension() instanceof TurnCostExtension)
-            wrappedExtension = new QueryGraphTurnExt();
+            wrappedExtension = new QueryGraphTurnExt(mainGraph, graphModification.getClosestEdges());
         else
             wrappedExtension = mainGraph.getExtension();
 
+        // build data structures holding the virtual edges at all real/virtual nodes that are modified compared to the
+        // mainGraph.
+        final EdgeExplorer mainExplorer = mainGraph.createEdgeExplorer();
+        virtualEdgesAtRealNodes = buildVirtualEdgesAtRealNodes(mainExplorer);
+        virtualEdgesAtVirtualNodes = buildVirtualEdgesAtVirtualNodes();
+
         // create very lightweight QueryGraph which uses variables from this QueryGraph (same virtual edges)
         baseGraph = new QueryGraph(graph.getBaseGraph(), this) {
             // override method to avoid stackoverflow
@@ -188,178 +110,12 @@ public class QueryGraph implements Graph {
         mainGraph = graph;
         baseGraph = this;
         wrappedExtension = superQueryGraph.wrappedExtension;
-        mainNodeAccess = graph.getNodeAccess();
         mainNodes = superQueryGraph.mainNodes;
         mainEdges = superQueryGraph.mainEdges;
-    }
-
-    /**
-     * Convenient method to initialize this QueryGraph with the two specified query results.
-     *
-     * @see #lookup(List)
-     */
-    public QueryGraph lookup(QueryResult fromRes, QueryResult toRes) {
-        List<QueryResult> results = new ArrayList<>(2);
-        results.add(fromRes);
-        results.add(toRes);
-        lookup(results);
-        return this;
-    }
-
-    /**
-     * For all specified query results calculate snapped point and if necessary set closest node
-     * to a virtual one and reverse closest edge. Additionally the wayIndex can change if an edge is
-     * swapped.
-     *
-     * @see QueryGraph
-     */
-    public void lookup(List<QueryResult> resList) {
-        if (isInitialized())
-            throw new IllegalStateException("Call lookup only once. Otherwise you'll have problems for queries sharing the same edge.");
-
-        // initialize all none-final variables
-        virtualEdges = new ArrayList<>(resList.size() * 2);
-        virtualNodes = new PointList(resList.size(), mainNodeAccess.is3D());
-        queryResults = new ArrayList<>(resList.size());
-        baseGraph.virtualEdges = virtualEdges;
-        baseGraph.virtualNodes = virtualNodes;
-        baseGraph.queryResults = queryResults;
-
-        GHIntObjectHashMap<List<QueryResult>> edge2res = new GHIntObjectHashMap<>(resList.size());
-
-        // Phase 1
-        // calculate snapped point and swap direction of closest edge if necessary
-        for (QueryResult res : resList) {
-            // Do not create virtual node for a query result if it is directly on a tower node or not found
-            if (res.getSnappedPosition() == QueryResult.Position.TOWER)
-                continue;
-
-            EdgeIteratorState closestEdge = res.getClosestEdge();
-            if (closestEdge == null)
-                throw new IllegalStateException("Do not call QueryGraph.lookup with invalid QueryResult " + res);
-
-            int base = closestEdge.getBaseNode();
-
-            // Force the identical direction for all closest edges.
-            // It is important to sort multiple results for the same edge by its wayIndex
-            boolean doReverse = base > closestEdge.getAdjNode();
-            if (base == closestEdge.getAdjNode()) {
-                // check for special case #162 where adj == base and force direction via latitude comparison
-                PointList pl = closestEdge.fetchWayGeometry(0);
-                if (pl.size() > 1)
-                    doReverse = pl.getLatitude(0) > pl.getLatitude(pl.size() - 1);
-            }
-
-            if (doReverse) {
-                closestEdge = closestEdge.detach(true);
-                PointList fullPL = closestEdge.fetchWayGeometry(3);
-                res.setClosestEdge(closestEdge);
-                if (res.getSnappedPosition() == QueryResult.Position.PILLAR)
-                    // ON pillar node
-                    res.setWayIndex(fullPL.getSize() - res.getWayIndex() - 1);
-                else
-                    // for case "OFF pillar node"
-                    res.setWayIndex(fullPL.getSize() - res.getWayIndex() - 2);
-
-                if (res.getWayIndex() < 0)
-                    throw new IllegalStateException("Problem with wayIndex while reversing closest edge:" + closestEdge + ", " + res);
-            }
-
-            // find multiple results on same edge
-            int edgeId = closestEdge.getEdge();
-            List<QueryResult> list = edge2res.get(edgeId);
-            if (list == null) {
-                list = new ArrayList<>(5);
-                edge2res.put(edgeId, list);
-            }
-            list.add(res);
-        }
-
-        // Phase 2 - now it is clear which points cut one edge
-        // 1. create point lists
-        // 2. create virtual edges between virtual nodes and its neighbor (virtual or normal nodes)
-        edge2res.forEach(new IntObjectPredicate<List<QueryResult>>() {
-            @Override
-            public boolean apply(int edgeId, List<QueryResult> results) {
-                // we can expect at least one entry in the results
-                EdgeIteratorState closestEdge = results.get(0).getClosestEdge();
-                final PointList fullPL = closestEdge.fetchWayGeometry(3);
-                int baseNode = closestEdge.getBaseNode();
-                Collections.sort(results, new Comparator<QueryResult>() {
-                    @Override
-                    public int compare(QueryResult o1, QueryResult o2) {
-                        int diff = Integer.compare(o1.getWayIndex(), o2.getWayIndex());
-                        if (diff == 0) {
-                            return Double.compare(distanceOfSnappedPointToPillarNode(o1), distanceOfSnappedPointToPillarNode(o2));
-                        } else {
-                            return diff;
-                        }
-                    }
-                    private double distanceOfSnappedPointToPillarNode(QueryResult o) {
-                        GHPoint snappedPoint = o.getSnappedPoint();
-                        double fromLat = fullPL.getLatitude(o.getWayIndex());
-                        double fromLon = fullPL.getLongitude(o.getWayIndex());
-                        return Helper.DIST_PLANE.calcNormalizedDist(fromLat, fromLon, snappedPoint.lat, snappedPoint.lon);
-                    }
-                });
-
-                GHPoint3D prevPoint = fullPL.get(0);
-                int adjNode = closestEdge.getAdjNode();
-                int origEdgeKey = GHUtility.createEdgeKey(baseNode, adjNode, closestEdge.getEdge(), false);
-                int origRevEdgeKey = GHUtility.createEdgeKey(baseNode, adjNode, closestEdge.getEdge(), true);
-                int prevWayIndex = 1;
-                int prevNodeId = baseNode;
-                int virtNodeId = virtualNodes.getSize() + mainNodes;
-                boolean addedEdges = false;
-
-                // Create base and adjacent PointLists for all none-equal virtual nodes.
-                // We do so via inserting them at the correct position of fullPL and cutting the
-                // fullPL into the right pieces.
-                for (QueryResult res : results) {
-                    if (res.getClosestEdge().getBaseNode() != baseNode)
-                        throw new IllegalStateException("Base nodes have to be identical but were not: " + closestEdge + " vs " + res.getClosestEdge());
-
-                    GHPoint3D currSnapped = res.getSnappedPoint();
-
-                    // no new virtual nodes if exactly the same snapped point
-                    if (prevPoint.equals(currSnapped)) {
-                        res.setClosestNode(prevNodeId);
-                        continue;
-                    }
-
-                    queryResults.add(res);
-                    boolean isPillar = res.getSnappedPosition() == QueryResult.Position.PILLAR;
-                    createEdges(origEdgeKey, origRevEdgeKey,
-                            prevPoint, prevWayIndex, isPillar,
-                            res.getSnappedPoint(), res.getWayIndex(),
-                            fullPL, closestEdge, prevNodeId, virtNodeId);
-
-                    virtualNodes.add(currSnapped.lat, currSnapped.lon, currSnapped.ele);
-
-                    // add edges again to set adjacent edges for newVirtNodeId
-                    if (addedEdges) {
-                        virtualEdges.add(virtualEdges.get(virtualEdges.size() - 2));
-                        virtualEdges.add(virtualEdges.get(virtualEdges.size() - 2));
-                    }
-
-                    addedEdges = true;
-                    res.setClosestNode(virtNodeId);
-                    prevNodeId = virtNodeId;
-                    prevWayIndex = res.getWayIndex() + 1;
-                    prevPoint = currSnapped;
-                    virtNodeId++;
-                }
-
-                // two edges between last result and adjacent node are still missing if not all points skipped
-                if (addedEdges)
-                    createEdges(origEdgeKey, origRevEdgeKey,
-                            prevPoint, prevWayIndex, false,
-                            fullPL.get(fullPL.getSize() - 1), fullPL.getSize() - 2,
-                            fullPL, closestEdge, virtNodeId - 1, adjNode);
-
-                return true;
-            }
-        });
+        graphModification = superQueryGraph.graphModification;
+        nodeAccess = superQueryGraph.nodeAccess;
+        virtualEdgesAtRealNodes = buildVirtualEdgesAtRealNodes(graph.createEdgeExplorer());
+        virtualEdgesAtVirtualNodes = buildVirtualEdgesAtVirtualNodes();
     }
 
     @Override
@@ -371,7 +127,7 @@ public class QueryGraph implements Graph {
     }
 
     public EdgeIteratorState getOriginalEdgeFromVirtNode(int nodeId) {
-        return queryResults.get(nodeId - mainNodes).getClosestEdge();
+        return getEdgeIteratorState(graphModification.getClosestEdges().get(nodeId - mainNodes), Integer.MIN_VALUE);
     }
 
     public boolean isVirtualEdge(int edgeId) {
@@ -396,39 +152,6 @@ public class QueryGraph implements Graph {
         return this;
     }
 
-    private void createEdges(int origEdgeKey, int origRevEdgeKey,
-                             GHPoint3D prevSnapped, int prevWayIndex, boolean isPillar, GHPoint3D currSnapped, int wayIndex,
-                             PointList fullPL, EdgeIteratorState closestEdge,
-                             int prevNodeId, int nodeId) {
-        int max = wayIndex + 1;
-        PointList basePoints = new PointList(max - prevWayIndex + 1, mainNodeAccess.is3D());
-        basePoints.add(prevSnapped.lat, prevSnapped.lon, prevSnapped.ele);
-        for (int i = prevWayIndex; i < max; i++) {
-            basePoints.add(fullPL, i);
-        }
-        if (!isPillar) {
-            basePoints.add(currSnapped.lat, currSnapped.lon, currSnapped.ele);
-        }
-        // basePoints must have at least the size of 2 to make sure fetchWayGeometry(3) returns at least 2
-        assert basePoints.size() >= 2 : "basePoints must have at least two points";
-
-        PointList baseReversePoints = basePoints.clone(true);
-        double baseDistance = basePoints.calcDistance(Helper.DIST_PLANE);
-        int virtEdgeId = mainEdges + virtualEdges.size();
-
-        boolean reverse = closestEdge.get(EdgeIteratorState.REVERSE_STATE);
-        // edges between base and snapped point
-        VirtualEdgeIteratorState baseEdge = new VirtualEdgeIteratorState(origEdgeKey,
-                virtEdgeId, prevNodeId, nodeId, baseDistance, closestEdge.getFlags(), closestEdge.getName(), basePoints, reverse);
-        VirtualEdgeIteratorState baseReverseEdge = new VirtualEdgeIteratorState(origRevEdgeKey,
-                virtEdgeId, nodeId, prevNodeId, baseDistance, IntsRef.deepCopyOf(closestEdge.getFlags()), closestEdge.getName(), baseReversePoints, !reverse);
-
-        baseEdge.setReverseEdge(baseReverseEdge);
-        baseReverseEdge.setReverseEdge(baseEdge);
-        virtualEdges.add(baseEdge);
-        virtualEdges.add(baseReverseEdge);
-    }
-
     /**
      * Set those edges at the virtual node (nodeId) to 'unfavored' that require at least a turn of
      * 100° from favoredHeading.
@@ -453,7 +176,7 @@ public class QueryGraph implements Graph {
         int[] edgePositions = incoming ? new int[]{VE_BASE, VE_ADJ_REV} : new int[]{VE_BASE_REV, VE_ADJ};
         boolean enforcementOccurred = false;
         for (int edgePos : edgePositions) {
-            VirtualEdgeIteratorState edge = virtualEdges.get(virtNodeIDintern * 4 + edgePos);
+            VirtualEdgeIteratorState edge = getVirtualEdge(virtNodeIDintern * 4 + edgePos);
 
             PointList wayGeo = edge.fetchWayGeometry(3);
             double edgeOrientation;
@@ -474,7 +197,7 @@ public class QueryGraph implements Graph {
                 edge.setUnfavored(true);
                 unfavoredEdges.add(edge);
                 //also apply to opposite edge for reverse routing
-                VirtualEdgeIteratorState reverseEdge = virtualEdges.get(virtNodeIDintern * 4 + getPosOfReverseEdge(edgePos));
+                VirtualEdgeIteratorState reverseEdge = getVirtualEdge(virtNodeIDintern * 4 + getPosOfReverseEdge(edgePos));
                 reverseEdge.setUnfavored(true);
                 unfavoredEdges.add(reverseEdge);
                 enforcementOccurred = true;
@@ -532,12 +255,12 @@ public class QueryGraph implements Graph {
 
     @Override
     public int getNodes() {
-        return virtualNodes.getSize() + mainNodes;
+        return graphModification.getVirtualNodes().getSize() + mainNodes;
     }
 
     @Override
     public int getEdges() {
-        return virtualEdges.size() + mainEdges;
+        return graphModification.getNumVirtualEdges() + mainEdges;
     }
 
     @Override
@@ -556,18 +279,22 @@ public class QueryGraph implements Graph {
             return mainGraph.getEdgeIteratorState(origEdgeId, adjNode);
 
         int edgeId = origEdgeId - mainEdges;
-        EdgeIteratorState eis = virtualEdges.get(edgeId);
+        EdgeIteratorState eis = getVirtualEdge(edgeId);
         if (eis.getAdjNode() == adjNode || adjNode == Integer.MIN_VALUE)
             return eis;
         edgeId = getPosOfReverseEdge(edgeId);
 
-        EdgeIteratorState eis2 = virtualEdges.get(edgeId);
+        EdgeIteratorState eis2 = getVirtualEdge(edgeId);
         if (eis2.getAdjNode() == adjNode)
             return eis2;
         throw new IllegalStateException("Edge " + origEdgeId + " not found with adjNode:" + adjNode
                 + ". found edges were:" + eis + ", " + eis2);
     }
 
+    private VirtualEdgeIteratorState getVirtualEdge(int edgeId) {
+        return graphModification.getVirtualEdge(edgeId);
+    }
+
     private int getPosOfReverseEdge(int edgeId) {
         // find reverse edge via convention. see virtualEdges comment above
         if (edgeId % 2 == 0)
@@ -592,108 +319,58 @@ public class QueryGraph implements Graph {
         }
     }
 
-    private EdgeExplorer createUncachedEdgeExplorer(EdgeFilter edgeFilter) {
-        // Iteration over virtual nodes needs to be thread safe if done from different explorer
-        // so we need to create the mapping on EVERY call!
-        // This needs to be a HashMap (and cannot be an array) as we also need to tweak edges for some mainNodes!
-        // The more query points we have the more inefficient this map could be. Hmmh.
-        final IntObjectMap<VirtualEdgeIterator> node2EdgeMap
-                = new GHIntObjectHashMap<>(queryResults.size() * 3);
-
+    private EdgeExplorer createUncachedEdgeExplorer(final EdgeFilter edgeFilter) {
+        // re-use these objects between setBaseNode calls to prevent GC
         final EdgeExplorer mainExplorer = mainGraph.createEdgeExplorer(edgeFilter);
-        final GHIntHashSet towerNodesToChange = new GHIntHashSet(queryResults.size());
-
-        // 1. virtualEdges should also get fresh EdgeIterators on every createEdgeExplorer call!
-        for (int i = 0; i < queryResults.size(); i++) {
-            // create outgoing edges
-            VirtualEdgeIterator virtEdgeIter = new VirtualEdgeIterator(2);
-            EdgeIteratorState baseRevEdge = virtualEdges.get(i * 4 + VE_BASE_REV);
-            if (edgeFilter.accept(baseRevEdge))
-                virtEdgeIter.add(baseRevEdge);
-            EdgeIteratorState adjEdge = virtualEdges.get(i * 4 + VE_ADJ);
-            if (edgeFilter.accept(adjEdge))
-                virtEdgeIter.add(adjEdge);
-
-            int virtNode = mainNodes + i;
-            node2EdgeMap.put(virtNode, virtEdgeIter);
-
-            // replace edge list of neighboring tower nodes:
-            // add virtual edges only and collect tower nodes where real edges will be added in step 2.
-            //
-            // base node
-            int towerNode = baseRevEdge.getAdjNode();
-            if (!isVirtualNode(towerNode)) {
-                towerNodesToChange.add(towerNode);
-                addVirtualEdges(node2EdgeMap, edgeFilter, true, towerNode, i);
-            }
-
-            // adj node
-            towerNode = adjEdge.getAdjNode();
-            if (!isVirtualNode(towerNode)) {
-                towerNodesToChange.add(towerNode);
-                addVirtualEdges(node2EdgeMap, edgeFilter, false, towerNode, i);
-            }
-        }
-
-        // 2. the connected tower nodes from mainGraph need fresh EdgeIterators with possible fakes
-        // where 'fresh' means independent of previous call and respecting the edgeFilter
-        // -> setup fake iterators of detected tower nodes (virtual edges are already added)
-        towerNodesToChange.forEach(new IntProcedure() {
-            @Override
-            public void apply(int value) {
-                fillVirtualEdges(node2EdgeMap, value, mainExplorer);
-            }
-        });
-
+        final VirtualEdgeIterator virtualEdgeIterator = new VirtualEdgeIterator(edgeFilter, null);
         return new EdgeExplorer() {
             @Override
             public EdgeIterator setBaseNode(int baseNode) {
-                VirtualEdgeIterator iter = node2EdgeMap.get(baseNode);
-                if (iter != null)
-                    return iter.reset();
-
-                return mainExplorer.setBaseNode(baseNode);
+                if (isVirtualNode(baseNode)) {
+                    List<EdgeIteratorState> virtualEdges = virtualEdgesAtVirtualNodes.get(baseNode - mainNodes);
+                    return virtualEdgeIterator.reset(virtualEdges);
+                } else {
+                    List<EdgeIteratorState> virtualEdges = virtualEdgesAtRealNodes.get(baseNode);
+                    if (virtualEdges == null) {
+                        return mainExplorer.setBaseNode(baseNode);
+                    } else {
+                        return virtualEdgeIterator.reset(virtualEdges);
+                    }
+                }
             }
         };
     }
 
-    /**
-     * Creates a fake edge iterator pointing to multiple edge states.
-     */
-    private void addVirtualEdges(IntObjectMap<VirtualEdgeIterator> node2EdgeMap, EdgeFilter filter, boolean base,
-                                 int node, int virtNode) {
-        VirtualEdgeIterator existingIter = node2EdgeMap.get(node);
-        if (existingIter == null) {
-            existingIter = new VirtualEdgeIterator(10);
-            node2EdgeMap.put(node, existingIter);
-        }
-        EdgeIteratorState edge = base
-                ? virtualEdges.get(virtNode * 4 + VE_BASE)
-                : virtualEdges.get(virtNode * 4 + VE_ADJ_REV);
-        if (filter.accept(edge))
-            existingIter.add(edge);
-    }
-
-    void fillVirtualEdges(IntObjectMap<VirtualEdgeIterator> node2Edge, int towerNode, EdgeExplorer mainExpl) {
-        if (isVirtualNode(towerNode))
-            throw new IllegalStateException("Node should not be virtual:" + towerNode + ", " + node2Edge);
-
-        VirtualEdgeIterator vIter = node2Edge.get(towerNode);
-        IntArrayList ignoreEdges = new IntArrayList(vIter.count() * 2);
-        while (vIter.next()) {
-            EdgeIteratorState edge = queryResults.get(vIter.getAdjNode() - mainNodes).getClosestEdge();
-            ignoreEdges.add(edge.getEdge());
-        }
-        vIter.reset();
-        EdgeIterator iter = mainExpl.setBaseNode(towerNode);
-        while (iter.next()) {
-            if (!ignoreEdges.contains(iter.getEdge()))
-                vIter.add(iter.detach(false));
-        }
+    private IntObjectMap<List<EdgeIteratorState>> buildVirtualEdgesAtRealNodes(final EdgeExplorer mainExplorer) {
+        final IntObjectMap<List<EdgeIteratorState>> virtualEdgesAtRealNodes =
+                new GHIntObjectHashMap<>(graphModification.getEdgeChangesAtRealNodes().size());
+        graphModification.getEdgeChangesAtRealNodes().forEach(new IntObjectProcedure<GraphModification.EdgeChanges>() {
+            @Override
+            public void apply(int node, GraphModification.EdgeChanges edgeChanges) {
+                List<EdgeIteratorState> virtualEdges = new ArrayList<>(edgeChanges.getAdditionalEdges());
+                EdgeIterator mainIter = mainExplorer.setBaseNode(node);
+                while (mainIter.next()) {
+                    if (!edgeChanges.getRemovedEdges().contains(mainIter.getEdge())) {
+                        virtualEdges.add(mainIter.detach(false));
+                    }
+                }
+                virtualEdgesAtRealNodes.put(node, virtualEdges);
+            }
+        });
+        return virtualEdgesAtRealNodes;
     }
 
-    private boolean isInitialized() {
-        return queryResults != null;
+    private List<List<EdgeIteratorState>> buildVirtualEdgesAtVirtualNodes() {
+        final List<List<EdgeIteratorState>> virtualEdgesAtVirtualNodes = new ArrayList<>();
+        final int[] vEdges = {VE_BASE_REV, VE_ADJ};
+        for (int i = 0; i < graphModification.getVirtualNodes().size(); i++) {
+            List<EdgeIteratorState> filteredEdges = new ArrayList<>(2);
+            for (int vEdge : vEdges) {
+                filteredEdges.add(graphModification.getVirtualEdge(i * 4 + vEdge));
+            }
+            virtualEdgesAtVirtualNodes.add(filteredEdges);
+        }
+        return virtualEdgesAtVirtualNodes;
     }
 
     @Override
@@ -747,56 +424,12 @@ public class QueryGraph implements Graph {
         return mainGraph.isAdjacentToNode(edge, node);
     }
 
+    List<VirtualEdgeIteratorState> getVirtualEdges() {
+        return graphModification.getVirtualEdges();
+    }
+
     private UnsupportedOperationException exc() {
         return new UnsupportedOperationException("QueryGraph cannot be modified.");
     }
 
-    class QueryGraphTurnExt extends TurnCostExtension {
-        private final TurnCostExtension mainTurnExtension;
-
-        public QueryGraphTurnExt() {
-            this.mainTurnExtension = (TurnCostExtension) mainGraph.getExtension();
-        }
-
-        @Override
-        public long getTurnCostFlags(int edgeFrom, int nodeVia, int edgeTo) {
-            if (isVirtualNode(nodeVia)) {
-                return 0;
-            } else if (isVirtualEdge(edgeFrom) || isVirtualEdge(edgeTo)) {
-                if (isVirtualEdge(edgeFrom)) {
-                    edgeFrom = getOriginalEdge(edgeFrom);
-                }
-                if (isVirtualEdge(edgeTo)) {
-                    edgeTo = getOriginalEdge(edgeTo);
-                }
-                return mainTurnExtension.getTurnCostFlags(edgeFrom, nodeVia, edgeTo);
-            } else {
-                return mainTurnExtension.getTurnCostFlags(edgeFrom, nodeVia, edgeTo);
-            }
-        }
-
-        @Override
-        public boolean isUTurn(int edgeFrom, int edgeTo) {
-            // detecting a u-turn from a virtual to a non-virtual edge requires looking at the original edge of the
-            // virtual edge. however when we are turning between virtual edges we need to compare the virtual edge ids
-            // see #1593
-            if (isVirtualEdge(edgeFrom) && !isVirtualEdge(edgeTo)) {
-                edgeFrom = getOriginalEdge(edgeFrom);
-            } else if (!isVirtualEdge(edgeFrom) && isVirtualEdge(edgeTo)) {
-                edgeTo = getOriginalEdge(edgeTo);
-            }
-            return mainTurnExtension.isUTurn(edgeFrom, edgeTo);
-        }
-
-        @Override
-        public boolean isUTurnAllowed(int node) {
-            // do not allow u-turns at virtual nodes, otherwise the route depends on whether or not there are virtual
-            // via nodes, see #1672
-            return !isVirtualNode(node);
-        }
-
-        private int getOriginalEdge(int edgeFrom) {
-            return queryResults.get((edgeFrom - mainEdges) / 4).getClosestEdge().getEdge();
-        }
-    }
 }
diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/QueryGraphTurnExt.java b/core/src/main/java/com/graphhopper/routing/querygraph/QueryGraphTurnExt.java
new file mode 100644
index 000000000..987f1972d
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/QueryGraphTurnExt.java
@@ -0,0 +1,89 @@
+/*
+ *  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.querygraph;
+
+import com.carrotsearch.hppc.IntArrayList;
+import com.graphhopper.storage.Graph;
+import com.graphhopper.storage.TurnCostExtension;
+
+/**
+ * special {@link TurnCostExtension} that handles virtual nodes and edges
+ */
+class QueryGraphTurnExt extends TurnCostExtension {
+    private final TurnCostExtension mainTurnExtension;
+    private final int firstVirtualNodeId;
+    private final int firstVirtualEdgeId;
+    private final IntArrayList closestEdges;
+
+    QueryGraphTurnExt(Graph mainGraph, IntArrayList closestEdges) {
+        this.mainTurnExtension = (TurnCostExtension) mainGraph.getExtension();
+        this.firstVirtualNodeId = mainGraph.getNodes();
+        this.firstVirtualEdgeId = mainGraph.getEdges();
+        this.closestEdges = closestEdges;
+    }
+
+    @Override
+    public long getTurnCostFlags(int edgeFrom, int nodeVia, int edgeTo) {
+        if (isVirtualNode(nodeVia)) {
+            return 0;
+        } else if (isVirtualEdge(edgeFrom) || isVirtualEdge(edgeTo)) {
+            if (isVirtualEdge(edgeFrom)) {
+                edgeFrom = getOriginalEdge(edgeFrom);
+            }
+            if (isVirtualEdge(edgeTo)) {
+                edgeTo = getOriginalEdge(edgeTo);
+            }
+            return mainTurnExtension.getTurnCostFlags(edgeFrom, nodeVia, edgeTo);
+        } else {
+            return mainTurnExtension.getTurnCostFlags(edgeFrom, nodeVia, edgeTo);
+        }
+    }
+
+    @Override
+    public boolean isUTurn(int edgeFrom, int edgeTo) {
+        // detecting a u-turn from a virtual to a non-virtual edge requires looking at the original edge of the
+        // virtual edge. however when we are turning between virtual edges we need to compare the virtual edge ids
+        // see #1593
+        if (isVirtualEdge(edgeFrom) && !isVirtualEdge(edgeTo)) {
+            edgeFrom = getOriginalEdge(edgeFrom);
+        } else if (!isVirtualEdge(edgeFrom) && isVirtualEdge(edgeTo)) {
+            edgeTo = getOriginalEdge(edgeTo);
+        }
+        return mainTurnExtension.isUTurn(edgeFrom, edgeTo);
+    }
+
+    @Override
+    public boolean isUTurnAllowed(int node) {
+        // do not allow u-turns at virtual nodes, otherwise the route depends on whether or not there are virtual
+        // via nodes, see #1672
+        return !isVirtualNode(node);
+    }
+
+    private int getOriginalEdge(int edge) {
+        return closestEdges.get((edge - firstVirtualEdgeId) / 4);
+    }
+
+    private boolean isVirtualNode(int nodeId) {
+        return nodeId >= firstVirtualNodeId;
+    }
+
+    private boolean isVirtualEdge(int edgeId) {
+        return edgeId >= firstVirtualEdgeId;
+    }
+}
diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIterator.java b/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIterator.java
index 2aa170a7d..93a7b620f 100644
--- a/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIterator.java
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIterator.java
@@ -21,43 +21,41 @@ import com.graphhopper.routing.profiles.BooleanEncodedValue;
 import com.graphhopper.routing.profiles.DecimalEncodedValue;
 import com.graphhopper.routing.profiles.EnumEncodedValue;
 import com.graphhopper.routing.profiles.IntEncodedValue;
+import com.graphhopper.routing.util.EdgeFilter;
 import com.graphhopper.storage.IntsRef;
 import com.graphhopper.util.CHEdgeIteratorState;
 import com.graphhopper.util.EdgeIterator;
 import com.graphhopper.util.EdgeIteratorState;
 import com.graphhopper.util.PointList;
 
-import java.util.ArrayList;
 import java.util.List;
 
 /**
  * @author Peter Karich
  */
 class VirtualEdgeIterator implements EdgeIterator, CHEdgeIteratorState {
-    private final List<EdgeIteratorState> edges;
+    private final EdgeFilter edgeFilter;
+    private List<EdgeIteratorState> edges;
     private int current;
 
-    VirtualEdgeIterator(int edgeCount) {
-        edges = new ArrayList<>(edgeCount);
-        reset();
+    VirtualEdgeIterator(EdgeFilter edgeFilter, List<EdgeIteratorState> edges) {
+        this.edges = edges;
+        this.current = -1;
+        this.edgeFilter = edgeFilter;
     }
 
-    void add(EdgeIteratorState edge) {
-        edges.add(edge);
-    }
-
-    EdgeIterator reset() {
+    EdgeIterator reset(List<EdgeIteratorState> edges) {
+        this.edges = edges;
         current = -1;
         return this;
     }
 
-    int count() {
-        return edges.size();
-    }
-
     @Override
     public boolean next() {
         current++;
+        while (current < edges.size() && !edgeFilter.accept(edges.get(current))) {
+            current++;
+        }
         return current < edges.size();
     }
 
@@ -65,156 +63,156 @@ class VirtualEdgeIterator implements EdgeIterator, CHEdgeIteratorState {
     public EdgeIteratorState detach(boolean reverse) {
         if (reverse)
             throw new IllegalStateException("Not yet supported");
-        return edges.get(current);
+        return getCurrentEdge();
     }
 
     @Override
     public int getEdge() {
-        return edges.get(current).getEdge();
+        return getCurrentEdge().getEdge();
     }
 
     @Override
     public int getBaseNode() {
-        return edges.get(current).getBaseNode();
+        return getCurrentEdge().getBaseNode();
     }
 
     @Override
     public int getAdjNode() {
-        return edges.get(current).getAdjNode();
+        return getCurrentEdge().getAdjNode();
     }
 
     @Override
     public PointList fetchWayGeometry(int mode) {
-        return edges.get(current).fetchWayGeometry(mode);
+        return getCurrentEdge().fetchWayGeometry(mode);
     }
 
     @Override
     public EdgeIteratorState setWayGeometry(PointList list) {
-        return edges.get(current).setWayGeometry(list);
+        return getCurrentEdge().setWayGeometry(list);
     }
 
     @Override
     public double getDistance() {
-        return edges.get(current).getDistance();
+        return getCurrentEdge().getDistance();
     }
 
     @Override
     public EdgeIteratorState setDistance(double dist) {
-        return edges.get(current).setDistance(dist);
+        return getCurrentEdge().setDistance(dist);
     }
 
     @Override
     public IntsRef getFlags() {
-        return edges.get(current).getFlags();
+        return getCurrentEdge().getFlags();
     }
 
     @Override
     public EdgeIteratorState setFlags(IntsRef flags) {
-        return edges.get(current).setFlags(flags);
+        return getCurrentEdge().setFlags(flags);
     }
 
     @Override
     public EdgeIteratorState set(BooleanEncodedValue property, boolean value) {
-        edges.get(current).set(property, value);
+        getCurrentEdge().set(property, value);
         return this;
     }
 
     @Override
     public boolean get(BooleanEncodedValue property) {
-        return edges.get(current).get(property);
+        return getCurrentEdge().get(property);
     }
 
     @Override
     public EdgeIteratorState setReverse(BooleanEncodedValue property, boolean value) {
-        edges.get(current).setReverse(property, value);
+        getCurrentEdge().setReverse(property, value);
         return this;
     }
 
     @Override
     public boolean getReverse(BooleanEncodedValue property) {
-        return edges.get(current).getReverse(property);
+        return getCurrentEdge().getReverse(property);
     }
 
     @Override
     public EdgeIteratorState set(IntEncodedValue property, int value) {
-        edges.get(current).set(property, value);
+        getCurrentEdge().set(property, value);
         return this;
     }
 
     @Override
     public int get(IntEncodedValue property) {
-        return edges.get(current).get(property);
+        return getCurrentEdge().get(property);
     }
 
     @Override
     public EdgeIteratorState setReverse(IntEncodedValue property, int value) {
-        edges.get(current).setReverse(property, value);
+        getCurrentEdge().setReverse(property, value);
         return this;
     }
 
     @Override
     public int getReverse(IntEncodedValue property) {
-        return edges.get(current).getReverse(property);
+        return getCurrentEdge().getReverse(property);
     }
 
     @Override
     public EdgeIteratorState set(DecimalEncodedValue property, double value) {
-        edges.get(current).set(property, value);
+        getCurrentEdge().set(property, value);
         return this;
     }
 
     @Override
     public double get(DecimalEncodedValue property) {
-        return edges.get(current).get(property);
+        return getCurrentEdge().get(property);
     }
 
     @Override
     public EdgeIteratorState setReverse(DecimalEncodedValue property, double value) {
-        edges.get(current).setReverse(property, value);
+        getCurrentEdge().setReverse(property, value);
         return this;
     }
 
     @Override
     public double getReverse(DecimalEncodedValue property) {
-        return edges.get(current).getReverse(property);
+        return getCurrentEdge().getReverse(property);
     }
 
     @Override
     public <T extends Enum> EdgeIteratorState set(EnumEncodedValue<T> property, T value) {
-        edges.get(current).set(property, value);
+        getCurrentEdge().set(property, value);
         return this;
     }
 
     @Override
     public <T extends Enum> T get(EnumEncodedValue<T> property) {
-        return edges.get(current).get(property);
+        return getCurrentEdge().get(property);
     }
 
     @Override
     public <T extends Enum> EdgeIteratorState setReverse(EnumEncodedValue<T> property, T value) {
-        edges.get(current).setReverse(property, value);
+        getCurrentEdge().setReverse(property, value);
         return this;
     }
 
     @Override
     public <T extends Enum> T getReverse(EnumEncodedValue<T> property) {
-        return edges.get(current).getReverse(property);
+        return getCurrentEdge().getReverse(property);
     }
 
     @Override
     public String getName() {
-        return edges.get(current).getName();
+        return getCurrentEdge().getName();
     }
 
     @Override
     public EdgeIteratorState setName(String name) {
-        return edges.get(current).setName(name);
+        return getCurrentEdge().setName(name);
     }
 
     @Override
     public String toString() {
         if (current >= 0 && current < edges.size()) {
-            return "virtual edge: " + edges.get(current) + ", all: " + edges.toString();
+            return "virtual edge: " + getCurrentEdge() + ", all: " + edges.toString();
         } else {
             return "virtual edge: (invalid)" + ", all: " + edges.toString();
         }
@@ -222,29 +220,29 @@ class VirtualEdgeIterator implements EdgeIterator, CHEdgeIteratorState {
 
     @Override
     public int getAdditionalField() {
-        return edges.get(current).getAdditionalField();
+        return getCurrentEdge().getAdditionalField();
     }
 
     @Override
     public EdgeIteratorState setAdditionalField(int value) {
-        return edges.get(current).setAdditionalField(value);
+        return getCurrentEdge().setAdditionalField(value);
     }
 
     @Override
     public EdgeIteratorState copyPropertiesFrom(EdgeIteratorState edge) {
-        return edges.get(current).copyPropertiesFrom(edge);
+        return getCurrentEdge().copyPropertiesFrom(edge);
     }
 
     @Override
     public boolean isShortcut() {
-        EdgeIteratorState edge = edges.get(current);
+        EdgeIteratorState edge = getCurrentEdge();
         return edge instanceof CHEdgeIteratorState && ((CHEdgeIteratorState) edge).isShortcut();
     }
 
     @Override
     public double getWeight() {
         // will be called only from PreparationWeighting and if isShortcut is true
-        return ((CHEdgeIteratorState) edges.get(current)).getWeight();
+        return ((CHEdgeIteratorState) getCurrentEdge()).getWeight();
     }
 
     @Override
@@ -279,16 +277,24 @@ class VirtualEdgeIterator implements EdgeIterator, CHEdgeIteratorState {
 
     @Override
     public int getOrigEdgeFirst() {
-        return edges.get(current).getOrigEdgeFirst();
+        return getCurrentEdge().getOrigEdgeFirst();
     }
 
     @Override
     public int getOrigEdgeLast() {
-        return edges.get(current).getOrigEdgeLast();
+        return getCurrentEdge().getOrigEdgeLast();
     }
 
     @Override
     public int getMergeStatus(int flags) {
         throw new UnsupportedOperationException("Not supported.");
     }
+
+    private EdgeIteratorState getCurrentEdge() {
+        return edges.get(current);
+    }
+
+    public List<EdgeIteratorState> getEdges() {
+        return edges;
+    }
 }
diff --git a/core/src/main/java/com/graphhopper/storage/ExtendedNodeAccess.java b/core/src/main/java/com/graphhopper/storage/ExtendedNodeAccess.java
new file mode 100644
index 000000000..8212ec8c7
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/storage/ExtendedNodeAccess.java
@@ -0,0 +1,119 @@
+/*
+ *  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.storage;
+
+import com.graphhopper.util.PointList;
+
+/**
+ * {@link NodeAccess} that allows adding additional points
+ */
+public class ExtendedNodeAccess implements NodeAccess {
+    private final NodeAccess nodeAccess;
+    private final PointList additionalNodes;
+    private final int firstAdditionalNodeId;
+
+    /**
+     * @param nodeAccess            the node access this class delegates to
+     * @param additionalNodes       the additional points that should be used
+     * @param firstAdditionalNodeId the node id that is used for the first additional point (all other nodes will
+     *                              use consecutive ids)
+     */
+    public ExtendedNodeAccess(NodeAccess nodeAccess, PointList additionalNodes, int firstAdditionalNodeId) {
+        this.nodeAccess = nodeAccess;
+        this.firstAdditionalNodeId = firstAdditionalNodeId;
+        this.additionalNodes = additionalNodes;
+    }
+
+    @Override
+    public void ensureNode(int nodeId) {
+        nodeAccess.ensureNode(nodeId);
+    }
+
+    @Override
+    public boolean is3D() {
+        return nodeAccess.is3D();
+    }
+
+    @Override
+    public int getDimension() {
+        return nodeAccess.getDimension();
+    }
+
+    @Override
+    public double getLatitude(int nodeId) {
+        if (isAdditionalNode(nodeId))
+            return additionalNodes.getLatitude(nodeId - firstAdditionalNodeId);
+        return nodeAccess.getLatitude(nodeId);
+    }
+
+    @Override
+    public double getLongitude(int nodeId) {
+        if (isAdditionalNode(nodeId))
+            return additionalNodes.getLongitude(nodeId - firstAdditionalNodeId);
+        return nodeAccess.getLongitude(nodeId);
+    }
+
+    @Override
+    public double getElevation(int nodeId) {
+        if (isAdditionalNode(nodeId))
+            return additionalNodes.getElevation(nodeId - firstAdditionalNodeId);
+        return nodeAccess.getElevation(nodeId);
+    }
+
+    @Override
+    public int getAdditionalNodeField(int nodeId) {
+        if (isAdditionalNode(nodeId))
+            return 0;
+        return nodeAccess.getAdditionalNodeField(nodeId);
+    }
+
+    @Override
+    public void setNode(int nodeId, double lat, double lon) {
+        throw new UnsupportedOperationException("Not supported yet.");
+    }
+
+    @Override
+    public void setNode(int nodeId, double lat, double lon, double ele) {
+        throw new UnsupportedOperationException("Not supported yet.");
+    }
+
+    @Override
+    public void setAdditionalNodeField(int nodeId, int additionalValue) {
+        throw new UnsupportedOperationException("Not supported yet.");
+    }
+
+    @Override
+    public double getLat(int nodeId) {
+        return getLatitude(nodeId);
+    }
+
+    @Override
+    public double getLon(int nodeId) {
+        return getLongitude(nodeId);
+    }
+
+    @Override
+    public double getEle(int nodeId) {
+        return getElevation(nodeId);
+    }
+
+    private boolean isAdditionalNode(int nodeId) {
+        return nodeId >= firstAdditionalNodeId;
+    }
+}
diff --git a/core/src/main/java/com/graphhopper/storage/index/QueryResult.java b/core/src/main/java/com/graphhopper/storage/index/QueryResult.java
index 68488588b..df930677d 100644
--- a/core/src/main/java/com/graphhopper/storage/index/QueryResult.java
+++ b/core/src/main/java/com/graphhopper/storage/index/QueryResult.java
@@ -18,6 +18,7 @@
 package com.graphhopper.storage.index;
 
 import com.graphhopper.routing.querygraph.QueryGraph;
+import com.graphhopper.storage.Graph;
 import com.graphhopper.util.DistanceCalc;
 import com.graphhopper.util.EdgeIteratorState;
 import com.graphhopper.util.PointList;
@@ -54,7 +55,7 @@ public class QueryResult {
 
     /**
      * Returns the closest matching node. This is either a tower node of the base graph
-     * or a virtual node (see also {@link QueryGraph#lookup(List)}).
+     * or a virtual node (see also {@link QueryGraph#lookup(Graph, List)}).
      *
      * @return {@link #INVALID_NODE} if nothing found, this should be avoided via a call of 'isValid'
      */


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java b/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java
index 944499efd..0a95be6e6 100644
--- a/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java
+++ b/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java
@@ -139,35 +139,47 @@ public class QueryGraphTest {
 
     @Test
     public void testFillVirtualEdges() {
-        initGraph(g);
-        g.getNodeAccess().setNode(3, 0, 1);
+        //       x (4)
+        //  /*-*\
+        // 0     1
+        // |    /
+        // 2  3
+        NodeAccess na = g.getNodeAccess();
+        na.setNode(0, 1, 0);
+        na.setNode(1, 1, 2.5);
+        na.setNode(2, 0, 0);
+        na.setNode(3, 0, 1);
+        g.edge(0, 2, 10, true);
+        g.edge(0, 1, 10, true).setWayGeometry(Helper.createPointList(1.5, 1, 1.5, 1.5));
         g.edge(1, 3);
 
         final int baseNode = 1;
         EdgeIterator iter = g.createEdgeExplorer().setBaseNode(baseNode);
         iter.next();
-        QueryResult res1 = createLocationResult(2, 1.7, iter, 1, PILLAR);
-        QueryGraph queryGraph = new QueryGraph(g) {
-
-            @Override
-            void fillVirtualEdges(IntObjectMap<VirtualEdgeIterator> node2Edge, int towerNode, EdgeExplorer mainExpl) {
-                super.fillVirtualEdges(node2Edge, towerNode, mainExpl);
-                // ignore nodes should include baseNode == 1
-                if (towerNode == 3)
-                    assertEquals("virtual edge: (invalid), all: [3->4]", node2Edge.get(towerNode).toString());
-                else if (towerNode == 1)
-                    assertEquals("virtual edge: (invalid), all: [1->4, 1 1-0]", node2Edge.get(towerNode).toString());
-                else
-                    throw new IllegalStateException("not allowed " + towerNode);
-            }
-        };
-        queryGraph.lookup(Arrays.asList(res1));
+        // note that we do not really do a location index lookup, but rather create a query result artificially, also
+        // this query result is not very intuitive as we would expect snapping to the 1-0 edge, but this is how this
+        // test was written initially...
+        QueryResult qr = createLocationResult(2, 1.7, iter, 1, PILLAR);
+        GraphModification graphModification = GraphModificationBuilder.build(g, Collections.singletonList(qr));
+        IntObjectMap<GraphModification.EdgeChanges> realNodeModifications = graphModification.getEdgeChangesAtRealNodes();
+        assertEquals(2, realNodeModifications.size());
+        // ignore nodes should include baseNode == 1
+        assertEquals("[3->4]", realNodeModifications.get(3).getAdditionalEdges().toString());
+        assertEquals("[2]", realNodeModifications.get(3).getRemovedEdges().toString());
+        assertEquals("[1->4]", realNodeModifications.get(1).getAdditionalEdges().toString());
+        assertEquals("[2]", realNodeModifications.get(1).getRemovedEdges().toString());
+
+        QueryGraph queryGraph = QueryGraph.lookup(g, qr);
         EdgeIteratorState state = GHUtility.getEdge(queryGraph, 0, 1);
         assertEquals(4, state.fetchWayGeometry(3).size());
 
-        // fetch virtual edge and check way geometry
+        //  fetch virtual edge and check way geometry
         state = GHUtility.getEdge(queryGraph, 4, 3);
         assertEquals(2, state.fetchWayGeometry(3).size());
+
+        // now we actually test the edges at the real tower nodes (virtual ones should be added and some real ones removed)
+        assertEquals("[1->4, 1 1-0]", ((VirtualEdgeIterator) queryGraph.createEdgeExplorer().setBaseNode(1)).getEdges().toString());
+        assertEquals("[3->4]", ((VirtualEdgeIterator) queryGraph.createEdgeExplorer().setBaseNode(3)).getEdges().toString());
     }
 
     @Test
@@ -242,10 +254,8 @@ public class QueryGraphTest {
 
         EdgeIterator iter = g.createEdgeExplorer().setBaseNode(0);
         iter.next();
-
-        VirtualEdgeIterator vi = new VirtualEdgeIterator(2);
-        vi.add(iter.detach(false));
-
+        List<EdgeIteratorState> vEdges = Collections.singletonList(iter.detach(false));
+        VirtualEdgeIterator vi = new VirtualEdgeIterator(EdgeFilter.ALL_EDGES, vEdges);
         assertTrue(vi.next());
     }
 
@@ -490,20 +500,21 @@ public class QueryGraphTest {
         EdgeIteratorState edge0 = graphWithTurnCosts.edge(0, 1, 10, true);
         EdgeIteratorState edge1 = graphWithTurnCosts.edge(2, 1, 10, true);
 
-        QueryGraph qGraph = new QueryGraph(graphWithTurnCosts);
         FastestWeighting weighting = new FastestWeighting(encoder);
-        TurnWeighting turnWeighting = new TurnWeighting(weighting, (TurnCostExtension) qGraph.getExtension());
+        TurnWeighting turnWeighting = new TurnWeighting(weighting, (TurnCostExtension) graphWithTurnCosts.getExtension());
 
+        // no turn costs initially
         assertEquals(0, turnWeighting.calcTurnWeight(edge0.getEdge(), 1, edge1.getEdge()), .1);
 
-        // now use turn costs and QueryGraph
+        //  now use turn costs
         turnExt.addTurnInfo(edge0.getEdge(), 1, edge1.getEdge(), encoder.getTurnFlags(false, 10));
         assertEquals(10, turnWeighting.calcTurnWeight(edge0.getEdge(), 1, edge1.getEdge()), .1);
 
+        // now use turn costs with query graph
         QueryResult res1 = createLocationResult(0.000, 0.005, edge0, 0, QueryResult.Position.EDGE);
         QueryResult res2 = createLocationResult(0.005, 0.010, edge1, 0, QueryResult.Position.EDGE);
-
-        qGraph.lookup(Arrays.asList(res1, res2));
+        QueryGraph qGraph = QueryGraph.lookup(graphWithTurnCosts, res1, res2);
+        turnWeighting = new TurnWeighting(weighting, (TurnCostExtension) qGraph.getExtension());
 
         int fromQueryEdge = GHUtility.getEdge(qGraph, res1.getClosestNode(), 1).getEdge();
         int toQueryEdge = GHUtility.getEdge(qGraph, res2.getClosestNode(), 1).getEdge();
@@ -535,7 +546,7 @@ public class QueryGraphTest {
     }
 
     private boolean isAvoidEdge(QueryGraph queryGraph, int virtualEdgeTypeId) {
-        return queryGraph.virtualEdges.get(virtualEdgeTypeId).get(EdgeIteratorState.UNFAVORED_EDGE);
+        return queryGraph.getVirtualEdges().get(virtualEdgeTypeId).get(EdgeIteratorState.UNFAVORED_EDGE);
     }
 
     @Test