Repository: graphhopper/graphhopper
Pull request #1158 (2017-09-18 19:50:20)

Allows setting initial heading for round trips via GHRequest.
Implements suggestions in #786.
For now both using a request hint and using the GHRequest API is supported to set the initial heading for roundtrips. Setting it via GHRequest takes precedence.

ammagamma: Shall we remove/deprecate/undocument the possibility to set the heading via a request hint ?
karussell: Thanks! Yeah I think we might remove RoundTrip.HEADING and related or what do you think @devemux86 ?
devemux86: > I think we might remove RoundTrip.HEADING and related or what do you think @devemux86 ?

Probably yes, unless support backwards compatibility or allow both API and hints for convenience.
ammagamma: Ok, I removed RoundTrip.HEADING in the last commit. Within Java one now needs to use `favoredHeadings` instead of the `HintsMap` to set the initial heading of a round trip.
However, the server API is basically unchanged: Setting a heading is done by passing e.g. `heading=123` as request parameter. In `GraphHopperServlet#doGet` the heading is added to `favoredHeadings` of the GHRequest, which is now used by `RoundTripRoutingTemplate`. Before this PR this was the same except that `RoundTripRoutingTemplate` did not take the heading from `favoredHeadings` but parsed the request parameters again looking for the 'heading' request parameter. Consequently the documentation in api-doc.md does not need to be changed. 
karussell: This is awesome & cleaner - thanks!
karussell: Cool, thanks!

Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/template/RoundTripRoutingTemplate.java b/core/src/main/java/com/graphhopper/routing/template/RoundTripRoutingTemplate.java
index d77806931..76ad659e2 100644
--- a/core/src/main/java/com/graphhopper/routing/template/RoundTripRoutingTemplate.java
+++ b/core/src/main/java/com/graphhopper/routing/template/RoundTripRoutingTemplate.java
@@ -67,13 +67,13 @@ public class RoundTripRoutingTemplate extends AbstractRoutingTemplate implements
 
     @Override
     public List<QueryResult> lookup(List<GHPoint> points, FlagEncoder encoder) {
-        if (points.isEmpty())
-            throw new IllegalStateException("For round trip calculation one point is required");
+        if (points.size() != 1 || ghRequest.getPoints().size() != 1)
+            throw new IllegalStateException("For round trip calculation exactly one point is required");
         final double distanceInMeter = ghRequest.getHints().getDouble(RoundTrip.DISTANCE, 10000);
         final long seed = ghRequest.getHints().getLong(RoundTrip.SEED, 0L);
-        final double initialHeading = ghRequest.getHints().getDouble(RoundTrip.HEADING, Double.NaN);
-        final int roundTripPointCount = Math.min(20, ghRequest.getHints().getInt(Algorithms.ROUND_TRIP + ".points", 2 + (int) (distanceInMeter / 50000)));
-        final GHPoint start = ghRequest.getPoints().get(0);
+        double initialHeading = ghRequest.getFavoredHeading(0);
+        final int roundTripPointCount = Math.min(20, ghRequest.getHints().getInt(RoundTrip.POINTS, 2 + (int) (distanceInMeter / 50000)));
+        final GHPoint start = points.get(0);
 
         TourStrategy strategy = new MultiPointTour(new Random(seed), distanceInMeter, roundTripPointCount, initialHeading);
         queryResults = new ArrayList<>(2 + strategy.getNumberOfGeneratedPoints());
@@ -84,7 +84,7 @@ public class RoundTripRoutingTemplate extends AbstractRoutingTemplate implements
 
         queryResults.add(startQR);
 
-        GHPoint last = points.get(0);
+        GHPoint last = start;
         for (int i = 0; i < strategy.getNumberOfGeneratedPoints(); i++) {
             double heading = strategy.getHeadingForIteration(i);
             QueryResult result = generateValidPoint(last, strategy.getDistanceForIteration(i), heading, edgeFilter);
diff --git a/core/src/main/java/com/graphhopper/util/Parameters.java b/core/src/main/java/com/graphhopper/util/Parameters.java
index 59b95e7c6..bf112ad42 100644
--- a/core/src/main/java/com/graphhopper/util/Parameters.java
+++ b/core/src/main/java/com/graphhopper/util/Parameters.java
@@ -82,7 +82,7 @@ public class Parameters {
         public static final class RoundTrip {
             public static final String DISTANCE = ROUND_TRIP + ".distance";
             public static final String SEED = ROUND_TRIP + ".seed";
-            public static final String HEADING = "heading";
+            public static final String POINTS = ROUND_TRIP + ".points";
             public static final String INIT_MAX_RETRIES = ROUTING_INIT_PREFIX + ROUND_TRIP + ".max_retries";
         }
     }
diff --git a/docs/web/api-doc.md b/docs/web/api-doc.md
index 4b3aec4ae..54246904c 100644
--- a/docs/web/api-doc.md
+++ b/docs/web/api-doc.md
@@ -58,7 +58,7 @@ weighting        | `fastest`  | Which kind of 'best' route calculation you need.
 edge_traversal   |`false`     | Use `true` if you want to consider turn restrictions for bike and motor vehicles. Keep in mind that the response time is roughly 2 times slower.
 algorithm        |`astarbi`   | The algorithm to calculate the route. Other options are `dijkstra`, `astar`, `astarbi`, `alternative_route` and `round_trip`
 block_area       | -          | Block road access via a point with the format `latitude,longitude` or an area defined by a circle `lat,lon,radius` or a rectangle `lat1,lon1,lat2,lon2`. Separate multiple areas with a semicolon `;`.
-heading          | NaN        | Favour a heading direction for a certain point. Specify either one heading for the start point or as many as there are points. In this case headings are associated by their order to the specific points. Headings are given as north based clockwise angle between 0 and 360 degree. This parameter also influences the tour generated with `algorithm=round_trip` and force the initial direction.
+heading          | NaN        | Favour a heading direction for a certain point. Specify either one heading for the start point or as many as there are points. In this case headings are associated by their order to the specific points. Headings are given as north based clockwise angle between 0 and 360 degree. This parameter also influences the tour generated with `algorithm=round_trip` and forces the initial direction.
 heading_penalty  | 120        | Penalty for omitting a specified heading. The penalty corresponds to the accepted time delay in seconds in comparison to the route without a heading.
 pass_through     | `false`    | If `true` u-turns are avoided at via-points with regard to the `heading_penalty`.
 round_trip.distance                 | 10000 | If `algorithm=round_trip` this parameter configures approximative length of the resulting round trip


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/template/RoundTripRoutingTemplateTest.java b/core/src/test/java/com/graphhopper/routing/template/RoundTripRoutingTemplateTest.java
index 602d6374f..1935fde6e 100644
--- a/core/src/test/java/com/graphhopper/routing/template/RoundTripRoutingTemplateTest.java
+++ b/core/src/test/java/com/graphhopper/routing/template/RoundTripRoutingTemplateTest.java
@@ -23,17 +23,20 @@ import com.graphhopper.routing.*;
 import com.graphhopper.routing.util.*;
 import com.graphhopper.routing.weighting.FastestWeighting;
 import com.graphhopper.routing.weighting.Weighting;
-import com.graphhopper.storage.Graph;
-import com.graphhopper.storage.RAMDirectory;
+import com.graphhopper.storage.*;
 import com.graphhopper.storage.index.LocationIndex;
 import com.graphhopper.storage.index.LocationIndexTree;
 import com.graphhopper.storage.index.QueryResult;
 import com.graphhopper.util.Helper;
+import com.graphhopper.util.Parameters;
+import com.graphhopper.util.shapes.GHPoint;
 import org.junit.Test;
 
 import java.util.Arrays;
+import java.util.Collections;
 import java.util.List;
 
+import static com.graphhopper.routing.AbstractRoutingAlgorithmTester.updateDistancesFor;
 import static com.graphhopper.util.Parameters.Algorithms.DIJKSTRA_BI;
 import static org.junit.Assert.assertEquals;
 
@@ -45,13 +48,63 @@ public class RoundTripRoutingTemplateTest {
     private final EncodingManager em = new EncodingManager(carFE);
     // TODO private final TraversalMode tMode = TraversalMode.EDGE_BASED_2DIR;
     private final TraversalMode tMode = TraversalMode.NODE_BASED;
+    private final GHPoint ghPoint1 = new GHPoint(0, 0);
+    private final GHPoint ghPoint2 = new GHPoint(1, 1);
+
+    @Test(expected = IllegalStateException.class)
+    public void lookup_throwsIfNumberOfGivenPointsNotOne() {
+        RoundTripRoutingTemplate routingTemplate = new RoundTripRoutingTemplate(
+                new GHRequest(Collections.singletonList(ghPoint1)), new GHResponse(), null, 1);
+        routingTemplate.lookup(Arrays.asList(ghPoint1, ghPoint2), carFE);
+    }
+
+    @Test(expected = IllegalStateException.class)
+    public void lookup_throwsIfNumberOfPointsInRequestNotOne() {
+        RoundTripRoutingTemplate routingTemplate = new RoundTripRoutingTemplate(
+                new GHRequest(Arrays.asList(ghPoint1, ghPoint2)), new GHResponse(), null, 1);
+        routingTemplate.lookup(Collections.singletonList(ghPoint1), carFE);
+    }
+
+    @Test
+    public void testLookupAndCalcPaths_simpleSquareGraph() {
+        Graph g = createSquareGraph();
+        // start at node 0 and head south, make sure the round trip is long enough to reach most southern node 6
+        GHPoint start = new GHPoint(1, -1);
+        double heading = 180.0;
+        int numPoints = 2;
+        double roundTripDistance = 670000;
+
+        GHRequest ghRequest =
+                new GHRequest(Collections.singletonList(start), Collections.singletonList(heading));
+        ghRequest.getHints().put(Parameters.Algorithms.RoundTrip.POINTS, numPoints);
+        ghRequest.getHints().put(Parameters.Algorithms.RoundTrip.DISTANCE, roundTripDistance);
+        LocationIndex locationIndex = new LocationIndexTree(g, new RAMDirectory()).prepareIndex();
+        RoundTripRoutingTemplate routingTemplate =
+                new RoundTripRoutingTemplate(ghRequest, new GHResponse(), locationIndex, 1);
+        List<QueryResult> stagePoints = routingTemplate.lookup(ghRequest.getPoints(), carFE);
+        assertEquals(3, stagePoints.size());
+        assertEquals(0, stagePoints.get(0).getClosestNode());
+        assertEquals(6, stagePoints.get(1).getClosestNode());
+        assertEquals(0, stagePoints.get(2).getClosestNode());
+
+        QueryGraph queryGraph = new QueryGraph(g);
+        queryGraph.lookup(stagePoints);
+        Weighting weighting = new FastestWeighting(carFE);
+        List<Path> paths = routingTemplate.calcPaths(
+                queryGraph, new RoutingAlgorithmFactorySimple(), new AlgorithmOptions(DIJKSTRA_BI, weighting, tMode));
+        // make sure the resulting paths are connected and form a round trip starting and ending at the start node 0
+        assertEquals(2, paths.size());
+        assertEquals(Helper.createTList(0, 7, 6, 5), paths.get(0).calcNodes());
+        assertEquals(Helper.createTList(5, 4, 3, 2, 1, 0), paths.get(1).calcNodes());
+    }
 
     @Test
     public void testCalcRoundTrip() throws Exception {
         Weighting weighting = new FastestWeighting(carFE);
         Graph g = createTestGraph(true);
 
-        RoundTripRoutingTemplate rTripRouting = new RoundTripRoutingTemplate(new GHRequest(), new GHResponse(), null, 1);
+        RoundTripRoutingTemplate rTripRouting =
+                new RoundTripRoutingTemplate(new GHRequest(), new GHResponse(), null, 1);
 
         LocationIndex locationIndex = new LocationIndexTree(g, new RAMDirectory()).prepareIndex();
         QueryResult qr4 = locationIndex.findClosest(0.05, 0.25, EdgeFilter.ALL_EDGES);
@@ -64,7 +117,8 @@ public class RoundTripRoutingTemplateTest {
         QueryGraph qGraph = new QueryGraph(g);
         qGraph.lookup(qr4, qr5);
         rTripRouting.setQueryResults(Arrays.asList(qr5, qr4, qr5));
-        List<Path> paths = rTripRouting.calcPaths(qGraph, new RoutingAlgorithmFactorySimple(), new AlgorithmOptions(DIJKSTRA_BI, weighting, tMode));
+        List<Path> paths = rTripRouting.calcPaths(qGraph, new RoutingAlgorithmFactorySimple(),
+                new AlgorithmOptions(DIJKSTRA_BI, weighting, tMode));
         assertEquals(2, paths.size());
         assertEquals(Helper.createTList(5, 6, 3, 4), paths.get(0).calcNodes());
         assertEquals(Helper.createTList(4, 8, 7, 6, 5), paths.get(1).calcNodes());
@@ -72,7 +126,8 @@ public class RoundTripRoutingTemplateTest {
         qGraph = new QueryGraph(g);
         qGraph.lookup(qr4, qr6);
         rTripRouting.setQueryResults(Arrays.asList(qr6, qr4, qr6));
-        paths = rTripRouting.calcPaths(qGraph, new RoutingAlgorithmFactorySimple(), new AlgorithmOptions(DIJKSTRA_BI, weighting, tMode));
+        paths = rTripRouting.calcPaths(qGraph, new RoutingAlgorithmFactorySimple(),
+                new AlgorithmOptions(DIJKSTRA_BI, weighting, tMode));
         assertEquals(2, paths.size());
         assertEquals(Helper.createTList(6, 3, 4), paths.get(0).calcNodes());
         assertEquals(Helper.createTList(4, 8, 7, 6), paths.get(1).calcNodes());
@@ -81,4 +136,28 @@ public class RoundTripRoutingTemplateTest {
     private Graph createTestGraph(boolean fullGraph) {
         return new AlternativeRouteTest(tMode).createTestGraph(fullGraph, em);
     }
+
+    private Graph createSquareGraph() {
+        // simple square
+        //  1 | 0 1 2      
+        //  0 | 7   3
+        // -1 | 6 5 4 
+        // ---|------
+        //    |-1 0 1
+        GraphHopperStorage graph =
+                new GraphHopperStorage(new RAMDirectory(), em, false, new GraphExtension.NoOpExtension());
+        graph.create(1000);
+        for (int i = 0; i < 8; ++i) {
+            graph.edge(i, (i + 1) % 8, 1, true);
+        }
+        updateDistancesFor(graph, 0, 1, -1);
+        updateDistancesFor(graph, 1, 1, 0);
+        updateDistancesFor(graph, 2, 1, 1);
+        updateDistancesFor(graph, 3, 0, 1);
+        updateDistancesFor(graph, 4, -1, 1);
+        updateDistancesFor(graph, 5, -1, 0);
+        updateDistancesFor(graph, 6, -1, -1);
+        updateDistancesFor(graph, 7, 0, -1);
+        return graph;
+    }
 }
diff --git a/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java b/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java
index 0b6b0282a..1979b3a3c 100644
--- a/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java
+++ b/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java
@@ -806,10 +806,9 @@ public class GraphHopperIT {
     @Test
     public void testRoundTour() {
         GHRequest rq = new GHRequest().
-                addPoint(new GHPoint(43.741069, 7.426854)).
+                addPoint(new GHPoint(43.741069, 7.426854), 50).
                 setVehicle(vehicle).setWeighting("fastest").
                 setAlgorithm(ROUND_TRIP);
-        rq.getHints().put(RoundTrip.HEADING, 50);
         rq.getHints().put(RoundTrip.DISTANCE, 1000);
         rq.getHints().put(RoundTrip.SEED, 0);