Repository: graphhopper/graphhopper
Pull request #1950 (2020-03-10 10:43:31)

Avoid graph dependency
I think I found a good solution to the graph-dependency problem with always have in the Weighting: now we can fetch the tower nodes only (should be similar fast) without a NodeAccess only via the EdgeIteratorState without introducing a new method.

And additionally I found a minor speed improvement (moved BBox creation out of the loop).

This also helps making stuff in #1776 easier.


Patch:
diff --git a/core/src/main/java/com/graphhopper/GraphHopper.java b/core/src/main/java/com/graphhopper/GraphHopper.java
index 63f9b4bd8..d54287198 100644
--- a/core/src/main/java/com/graphhopper/GraphHopper.java
+++ b/core/src/main/java/com/graphhopper/GraphHopper.java
@@ -1120,8 +1120,6 @@ public class GraphHopper implements GraphHopperAPI {
                 return Collections.emptyList();
 
             QueryGraph queryGraph = QueryGraph.lookup(graph, qResults);
-            if (weighting instanceof BlockAreaWeighting)
-                ((BlockAreaWeighting) weighting).setQueryGraph(queryGraph);
 
             int maxVisitedNodesForRequest = hints.getInt(Routing.MAX_VISITED_NODES, routingConfig.getMaxVisitedNodes());
             if (maxVisitedNodesForRequest > routingConfig.getMaxVisitedNodes())
@@ -1166,9 +1164,9 @@ public class GraphHopper implements GraphHopperAPI {
         if (ROUND_TRIP.equalsIgnoreCase(algoStr))
             routingTemplate = new RoundTripRoutingTemplate(request, ghRsp, locationIndex, encodingManager, weighting, routingConfig.getMaxRoundTripRetries());
         else if (ALT_ROUTE.equalsIgnoreCase(algoStr))
-            routingTemplate = new AlternativeRoutingTemplate(request, ghRsp, locationIndex, ghStorage.getNodeAccess(), encodingManager, weighting);
+            routingTemplate = new AlternativeRoutingTemplate(request, ghRsp, locationIndex, encodingManager, weighting);
         else
-            routingTemplate = new ViaRoutingTemplate(request, ghRsp, locationIndex, ghStorage.getNodeAccess(), encodingManager, weighting);
+            routingTemplate = new ViaRoutingTemplate(request, ghRsp, locationIndex, encodingManager, weighting);
         return routingTemplate;
     }
 
diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIteratorState.java b/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIteratorState.java
index 5332c34fa..376e11c97 100644
--- a/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIteratorState.java
+++ b/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIteratorState.java
@@ -90,7 +90,14 @@ public class VirtualEdgeIteratorState implements EdgeIteratorState, CHEdgeIterat
         if (pointList.getSize() == 0)
             return PointList.EMPTY;
         // due to API we need to create a new instance per call!
-        if (mode == 3)
+        if (mode == 4) {
+            if (pointList.getSize() < 3)
+                return pointList.clone(false);
+            PointList towerNodes = new PointList(2, pointList.is3D());
+            towerNodes.add(pointList, 0);
+            towerNodes.add(pointList, pointList.getSize() - 1);
+            return towerNodes;
+        } else if (mode == 3)
             return pointList.clone(false);
         else if (mode == 1)
             return pointList.copy(0, pointList.getSize() - 1);
diff --git a/core/src/main/java/com/graphhopper/routing/template/AlternativeRoutingTemplate.java b/core/src/main/java/com/graphhopper/routing/template/AlternativeRoutingTemplate.java
index cc65d06df..1c19b1b58 100644
--- a/core/src/main/java/com/graphhopper/routing/template/AlternativeRoutingTemplate.java
+++ b/core/src/main/java/com/graphhopper/routing/template/AlternativeRoutingTemplate.java
@@ -47,8 +47,8 @@ import static com.graphhopper.util.Parameters.Routing.PASS_THROUGH;
  */
 final public class AlternativeRoutingTemplate extends ViaRoutingTemplate {
     public AlternativeRoutingTemplate(GHRequest ghRequest, GHResponse ghRsp, LocationIndex locationIndex,
-                                      NodeAccess nodeAccess, EncodedValueLookup lookup, Weighting weighting) {
-        super(ghRequest, ghRsp, locationIndex, nodeAccess, lookup, weighting);
+                                      EncodedValueLookup lookup, Weighting weighting) {
+        super(ghRequest, ghRsp, locationIndex, lookup, weighting);
     }
 
     @Override
diff --git a/core/src/main/java/com/graphhopper/routing/template/ViaRoutingTemplate.java b/core/src/main/java/com/graphhopper/routing/template/ViaRoutingTemplate.java
index 819306dfb..c7a8f6b7a 100644
--- a/core/src/main/java/com/graphhopper/routing/template/ViaRoutingTemplate.java
+++ b/core/src/main/java/com/graphhopper/routing/template/ViaRoutingTemplate.java
@@ -58,15 +58,14 @@ public class ViaRoutingTemplate extends AbstractRoutingTemplate implements Routi
     // result from route
     protected List<Path> pathList;
     protected final PathWrapper altResponse = new PathWrapper();
-    private final NodeAccess nodeAccess;
     private final EnumEncodedValue<RoadClass> roadClassEnc;
     private final EnumEncodedValue<RoadEnvironment> roadEnvEnc;
 
-    public ViaRoutingTemplate(GHRequest ghRequest, GHResponse ghRsp, LocationIndex locationIndex, NodeAccess nodeAccess, EncodedValueLookup lookup, final Weighting weighting) {
+    public ViaRoutingTemplate(GHRequest ghRequest, GHResponse ghRsp, LocationIndex locationIndex,
+                              EncodedValueLookup lookup, final Weighting weighting) {
         super(locationIndex, lookup, weighting);
         this.ghRequest = ghRequest;
         this.ghResponse = ghRsp;
-        this.nodeAccess = nodeAccess;
         this.roadClassEnc = lookup.getEnumEncodedValue(RoadClass.KEY, RoadClass.class);
         this.roadEnvEnc = lookup.getEnumEncodedValue(RoadEnvironment.KEY, RoadEnvironment.class);
     }
@@ -85,7 +84,7 @@ public class ViaRoutingTemplate extends AbstractRoutingTemplate implements Routi
             QueryResult qr = null;
             if (ghRequest.hasPointHints())
                 qr = locationIndex.findClosest(point.lat, point.lon, new NameSimilarityEdgeFilter(strictEdgeFilter,
-                        nodeAccess, ghRequest.getPointHints().get(placeIndex), point, 100));
+                        ghRequest.getPointHints().get(placeIndex), point, 100));
             else if (ghRequest.hasSnapPreventions())
                 qr = locationIndex.findClosest(point.lat, point.lon, strictEdgeFilter);
             if (qr == null || !qr.isValid())
diff --git a/core/src/main/java/com/graphhopper/routing/util/NameSimilarityEdgeFilter.java b/core/src/main/java/com/graphhopper/routing/util/NameSimilarityEdgeFilter.java
index 7f88656b2..6a413ec00 100644
--- a/core/src/main/java/com/graphhopper/routing/util/NameSimilarityEdgeFilter.java
+++ b/core/src/main/java/com/graphhopper/routing/util/NameSimilarityEdgeFilter.java
@@ -21,6 +21,7 @@ import com.graphhopper.apache.commons.lang3.StringUtils;
 import com.graphhopper.debatty.java.stringsimilarity.JaroWinkler;
 import com.graphhopper.storage.NodeAccess;
 import com.graphhopper.util.EdgeIteratorState;
+import com.graphhopper.util.GHUtility;
 import com.graphhopper.util.shapes.BBox;
 import com.graphhopper.util.shapes.Circle;
 import com.graphhopper.util.shapes.GHPoint;
@@ -89,20 +90,18 @@ public class NameSimilarityEdgeFilter implements EdgeFilter {
     private final String pointHint;
     private final Map<String, String> rewriteMap;
     private final Circle pointCircle;
-    private final NodeAccess nodeAccess;
 
-    public NameSimilarityEdgeFilter(EdgeFilter edgeFilter, NodeAccess nodeAccess, String pointHint, GHPoint point, double radius) {
-        this(edgeFilter, nodeAccess, pointHint, point, radius, DEFAULT_REWRITE_MAP);
+    public NameSimilarityEdgeFilter(EdgeFilter edgeFilter, String pointHint, GHPoint point, double radius) {
+        this(edgeFilter, pointHint, point, radius, DEFAULT_REWRITE_MAP);
     }
 
     /**
      * @param radius     the searchable region about the point in meters
      * @param rewriteMap maps abbreviations to its longer form
      */
-    public NameSimilarityEdgeFilter(EdgeFilter edgeFilter, NodeAccess nodeAccess, String pointHint, GHPoint point, double radius, Map<String, String> rewriteMap) {
+    public NameSimilarityEdgeFilter(EdgeFilter edgeFilter, String pointHint, GHPoint point, double radius, Map<String, String> rewriteMap) {
         this.edgeFilter = edgeFilter;
         this.rewriteMap = rewriteMap;
-        this.nodeAccess = nodeAccess;
         this.pointHint = prepareName(removeRelation(pointHint == null ? "" : pointHint));
         this.pointCircle = new Circle(point.lat, point.lon, radius);
     }
@@ -157,7 +156,7 @@ public class NameSimilarityEdgeFilter implements EdgeFilter {
             return false;
         }
 
-        BBox bbox = createBBox(nodeAccess, iter);
+        BBox bbox = GHUtility.createBBox(iter);
         if (!pointCircle.intersects(bbox)) {
             return false;
         }
diff --git a/core/src/main/java/com/graphhopper/routing/weighting/BlockAreaWeighting.java b/core/src/main/java/com/graphhopper/routing/weighting/BlockAreaWeighting.java
index 0b2e2df97..b1ceb8916 100644
--- a/core/src/main/java/com/graphhopper/routing/weighting/BlockAreaWeighting.java
+++ b/core/src/main/java/com/graphhopper/routing/weighting/BlockAreaWeighting.java
@@ -16,11 +16,6 @@ public class BlockAreaWeighting extends AbstractAdjustedWeighting {
         this.blockArea = blockArea;
     }
 
-    public BlockAreaWeighting setQueryGraph(QueryGraph queryGraph) {
-        blockArea.setQueryGraph(queryGraph);
-        return this;
-    }
-
     @Override
     public double calcEdgeWeight(EdgeIteratorState edgeState, boolean reverse) {
         if (blockArea.intersects(edgeState))
diff --git a/core/src/main/java/com/graphhopper/storage/BaseGraph.java b/core/src/main/java/com/graphhopper/storage/BaseGraph.java
index a5163b773..3b0e2865f 100644
--- a/core/src/main/java/com/graphhopper/storage/BaseGraph.java
+++ b/core/src/main/java/com/graphhopper/storage/BaseGraph.java
@@ -951,6 +951,13 @@ class BaseGraph implements Graph {
     }
 
     private PointList fetchWayGeometry_(long edgePointer, boolean reverse, int mode, int baseNode, int adjNode) {
+        if (mode == 4) {
+            // no reverse handling required as adjNode and baseNode is already properly switched
+            PointList pillarNodes = new PointList(2, nodeAccess.is3D());
+            pillarNodes.add(nodeAccess, baseNode);
+            pillarNodes.add(nodeAccess, adjNode);
+            return pillarNodes;
+        }
         long geoRef = Helper.toUnsignedLong(edges.getInt(edgePointer + E_GEO));
         int count = 0;
         byte[] bytes = null;
diff --git a/core/src/main/java/com/graphhopper/storage/Graph.java b/core/src/main/java/com/graphhopper/storage/Graph.java
index 85b47acbd..ba47999a7 100644
--- a/core/src/main/java/com/graphhopper/storage/Graph.java
+++ b/core/src/main/java/com/graphhopper/storage/Graph.java
@@ -48,7 +48,7 @@ public interface Graph {
     int getEdges();
 
     /**
-     * Creates a node explorer to access node properties.
+     * Creates an object to access node properties.
      */
     NodeAccess getNodeAccess();
 
diff --git a/core/src/main/java/com/graphhopper/storage/GraphEdgeIdFinder.java b/core/src/main/java/com/graphhopper/storage/GraphEdgeIdFinder.java
index c38c31c4d..c6a4094b8 100644
--- a/core/src/main/java/com/graphhopper/storage/GraphEdgeIdFinder.java
+++ b/core/src/main/java/com/graphhopper/storage/GraphEdgeIdFinder.java
@@ -19,11 +19,11 @@ package com.graphhopper.storage;
 
 import com.carrotsearch.hppc.cursors.IntCursor;
 import com.graphhopper.coll.GHIntHashSet;
-import com.graphhopper.routing.querygraph.QueryGraph;
 import com.graphhopper.routing.util.EdgeFilter;
 import com.graphhopper.routing.util.HintsMap;
 import com.graphhopper.storage.index.LocationIndex;
 import com.graphhopper.util.EdgeIteratorState;
+import com.graphhopper.util.GHUtility;
 import com.graphhopper.util.Parameters;
 import com.graphhopper.util.PointList;
 import com.graphhopper.util.shapes.Polygon;
@@ -165,13 +165,10 @@ public class GraphEdgeIdFinder {
     public static class BlockArea {
         private final List<GHIntHashSet> edgesList = new ArrayList<>();
         private final List<Shape> blockedShapes = new ArrayList<>();
-        private NodeAccess na;
         private final int baseEdgeCount;
-        private boolean prepared;
 
         public BlockArea(Graph g) {
             baseEdgeCount = g.getAllEdges().length();
-            na = g.getNodeAccess();
         }
 
         public boolean hasCachedEdgeIds(int shapeIndex) {
@@ -207,6 +204,7 @@ public class GraphEdgeIdFinder {
          */
         public final boolean intersects(EdgeIteratorState edgeState) {
             PointList pointList = null;
+            BBox bbox = null;
             for (int shapeIdx = 0; shapeIdx < blockedShapes.size(); shapeIdx++) {
                 GHIntHashSet blockedEdges = edgesList.get(shapeIdx);
                 // blockedEdges acts as cache that is only useful when filled and for non-virtual edges
@@ -216,8 +214,10 @@ public class GraphEdgeIdFinder {
                     continue;
                 }
 
-                // compromise: mostly avoid expensive fetchWayGeometry which isn't yet fast for being used in Weighting.calc
-                BBox bbox = createBBox(na, edgeState);
+                // compromise: avoid expensive fetch of pillar nodes, which isn't yet fast for being used in Weighting.calc
+                if (bbox == null)
+                    bbox = GHUtility.createBBox(edgeState);
+
                 Shape shape = blockedShapes.get(shapeIdx);
                 if (shape.getBounds().intersects(bbox)) {
                     if (pointList == null)
@@ -228,19 +228,5 @@ public class GraphEdgeIdFinder {
             }
             return false;
         }
-
-        public BlockArea setQueryGraph(QueryGraph queryGraph) {
-            if (prepared)
-                throw new IllegalStateException("setGraph cannot be called multiple times");
-
-            prepared = true;
-            na = queryGraph.getNodeAccess();
-            return this;
-        }
-    }
-
-    private static BBox createBBox(NodeAccess na, EdgeIteratorState edgeState) {
-        return BBox.fromPoints(na.getLatitude(edgeState.getBaseNode()), na.getLongitude(edgeState.getBaseNode()),
-                na.getLatitude(edgeState.getAdjNode()), na.getLongitude(edgeState.getAdjNode()));
     }
 }
\ No newline at end of file
diff --git a/core/src/main/java/com/graphhopper/util/EdgeIteratorState.java b/core/src/main/java/com/graphhopper/util/EdgeIteratorState.java
index 4b87eb712..c0ba8f97e 100644
--- a/core/src/main/java/com/graphhopper/util/EdgeIteratorState.java
+++ b/core/src/main/java/com/graphhopper/util/EdgeIteratorState.java
@@ -106,9 +106,13 @@ public interface EdgeIteratorState {
      * (docs/core/low-level-api.md#what-are-pillar-and-tower-nodes). Updates to the returned list
      * are not reflected in the graph, for that you've to use setWayGeometry.
      *
-     * @param mode can be <ul> <li>0 = only pillar nodes, no tower nodes</li> <li>1 = inclusive the
-     *             base tower node only</li> <li>2 = inclusive the adjacent tower node only</li> <li>3 =
-     *             inclusive the base and adjacent tower node</li> </ul>
+     * @param mode can be <ul>
+     *             <li>0 = only pillar nodes, no tower nodes</li>
+     *             <li>1 = inclusive the base tower node only</li>
+     *             <li>2 = inclusive the adjacent tower node only</li>
+     *             <li>3 = inclusive the base and adjacent tower node</li>
+     *             <li>4 = only tower nodes, no pillar nodes</li>
+     *             </ul>
      * @return pillar nodes
      */
     PointList fetchWayGeometry(int mode);
diff --git a/core/src/main/java/com/graphhopper/util/GHUtility.java b/core/src/main/java/com/graphhopper/util/GHUtility.java
index 0481d0a53..e189ae6e3 100644
--- a/core/src/main/java/com/graphhopper/util/GHUtility.java
+++ b/core/src/main/java/com/graphhopper/util/GHUtility.java
@@ -967,4 +967,11 @@ public class GHUtility {
             throw new UnsupportedOperationException("Not supported.");
         }
     }
+
+    public static BBox createBBox(EdgeIteratorState edgeState) {
+        PointList towerNodes = edgeState.fetchWayGeometry(4);
+        int secondIndex = towerNodes.getSize() == 1 ? 0 : 1;
+        return BBox.fromPoints(towerNodes.getLatitude(0), towerNodes.getLongitude(0),
+                towerNodes.getLatitude(secondIndex), towerNodes.getLongitude(secondIndex));
+    }
 }


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/util/NameSimilarityEdgeFilterTest.java b/core/src/test/java/com/graphhopper/routing/util/NameSimilarityEdgeFilterTest.java
index d11f208f1..6adc8f079 100644
--- a/core/src/test/java/com/graphhopper/routing/util/NameSimilarityEdgeFilterTest.java
+++ b/core/src/test/java/com/graphhopper/routing/util/NameSimilarityEdgeFilterTest.java
@@ -22,6 +22,7 @@ import com.graphhopper.storage.GraphBuilder;
 import com.graphhopper.storage.NodeAccess;
 import com.graphhopper.util.EdgeIteratorState;
 import com.graphhopper.util.GHUtility;
+import com.graphhopper.util.PointList;
 import com.graphhopper.util.shapes.GHPoint;
 import org.junit.Test;
 
@@ -102,13 +103,12 @@ public class NameSimilarityEdgeFilterTest {
         na.setNode(nodeID200, point200mAway.lat, point200mAway.lon);
 
         // Check that it matches a street 50m away
-        assertTrue(createNameSimilarityEdgeFilter(na, "Wentworth Street").
-                accept(createTestEdgeIterator("Wentworth Street", nodeId50, farAwayId)));
+        EdgeIteratorState edge1 = g.edge(nodeId50, farAwayId).setName("Wentworth Street");
+        assertTrue(createNameSimilarityEdgeFilter("Wentworth Street").accept(edge1));
 
         // Check that it doesn't match streets 200m away
-        assertFalse(createNameSimilarityEdgeFilter(na, "Wentworth Street").
-                accept(createTestEdgeIterator("Wentworth Street", nodeID200, farAwayId)));
-
+        EdgeIteratorState edge2 = g.edge(nodeID200, farAwayId).setName("Wentworth Street");
+        assertFalse(createNameSimilarityEdgeFilter("Wentworth Street").accept(edge2));
     }
 
     /**
@@ -231,26 +231,12 @@ public class NameSimilarityEdgeFilterTest {
      * so distance is not used when matching
      */
     private NameSimilarityEdgeFilter createNameSimilarityEdgeFilter(String pointHint) {
-        return createNameSimilarityEdgeFilter(new GHUtility.DisabledNodeAccess() {
-            @Override
-            public double getLatitude(int nodeId) {
-                return basePoint.lat;
-            }
-
-            @Override
-            public double getLongitude(int nodeId) {
-                return basePoint.lon;
-            }
-        }, pointHint);
-    }
-
-    private NameSimilarityEdgeFilter createNameSimilarityEdgeFilter(NodeAccess nodeAccess, String pointHint) {
         return new NameSimilarityEdgeFilter(new EdgeFilter() {
             @Override
             public boolean accept(EdgeIteratorState edgeState) {
                 return true;
             }
-        }, nodeAccess, pointHint, basePoint, 100);
+        }, pointHint, basePoint, 100);
     }
 
     private EdgeIteratorState createTestEdgeIterator(final String name, final int baseNodeId, final int adjNodeId) {
@@ -269,6 +255,13 @@ public class NameSimilarityEdgeFilterTest {
             public int getAdjNode() {
                 return adjNodeId;
             }
+
+            @Override
+            public PointList fetchWayGeometry(int type) {
+                PointList list = new PointList();
+                list.add(basePoint);
+                return list;
+            }
         };
     }
 
diff --git a/core/src/test/java/com/graphhopper/routing/weighting/BlockAreaWeightingTest.java b/core/src/test/java/com/graphhopper/routing/weighting/BlockAreaWeightingTest.java
index 214a50927..cc6948a90 100644
--- a/core/src/test/java/com/graphhopper/routing/weighting/BlockAreaWeightingTest.java
+++ b/core/src/test/java/com/graphhopper/routing/weighting/BlockAreaWeightingTest.java
@@ -80,7 +80,6 @@ public class BlockAreaWeightingTest {
         LocationIndex index = new LocationIndexTree(graph, graph.getDirectory()).prepareIndex();
         QueryResult qr = index.findClosest(0.005, 0.005, EdgeFilter.ALL_EDGES);
         QueryGraph queryGraph = QueryGraph.lookup(graph, qr);
-        bArea.setQueryGraph(queryGraph);
 
         BlockAreaWeighting instance = new BlockAreaWeighting(new FastestWeighting(encoder), bArea);
         EdgeIterator iter = queryGraph.createEdgeExplorer().setBaseNode(qr.getClosestNode());
diff --git a/core/src/test/java/com/graphhopper/storage/GraphHopperStorageTest.java b/core/src/test/java/com/graphhopper/storage/GraphHopperStorageTest.java
index 3766633d0..7b9d7c7bc 100644
--- a/core/src/test/java/com/graphhopper/storage/GraphHopperStorageTest.java
+++ b/core/src/test/java/com/graphhopper/storage/GraphHopperStorageTest.java
@@ -136,6 +136,8 @@ public class GraphHopperStorageTest extends AbstractGraphStorageTester {
         assertEquals(Helper.createPointList3D(1.5, 1, 0, 2, 3, 0), iter.fetchWayGeometry(0));
         assertEquals(Helper.createPointList3D(10, 10, 0, 1.5, 1, 0, 2, 3, 0), iter.fetchWayGeometry(1));
         assertEquals(Helper.createPointList3D(1.5, 1, 0, 2, 3, 0, 11, 20, 1), iter.fetchWayGeometry(2));
+        assertEquals(Helper.createPointList3D(10, 10, 0, 11, 20, 1), iter.fetchWayGeometry(4));
+        assertEquals(Helper.createPointList3D(11, 20, 1, 10, 10, 0), iter.detach(true).fetchWayGeometry(4));
 
         assertEquals(11, na.getLatitude(1), 1e-2);
         assertEquals(20, na.getLongitude(1), 1e-2);