Repository: graphhopper/graphhopper
Pull request #1722 (2019-09-10 15:45:50)

Alternative routes with node-based CH
So this is my attempt. Goal was to start with few moving parts, and finish with fewer. :-)

Note that this doesn't even use the existing `AlternativeRoutes`. This is really all the code there is.

Actually, the most hairy code in this class is stuff for walking backwards and forwards on `Path` because we don't have that as a utility.

The algorithm seems to be pretty "self-regulating" -- thanks to CH, candidates are already filtered down. So we don't have to check so many candidates. The share-factor is a very good filter criterion, so we don't even seem to really need a maximum number of paths here. 

![Screen Shot 2019-09-10 at 17 46 26](https://user-images.githubusercontent.com/520916/64629191-096a8400-d3f3-11e9-9479-aaf9e8cb253a.png)


easbar: Cool! I def. agree that the `Path` class needs some thought. Especially because it is half algorithm (path extraction) and half a data/result type. I'll open an issue for this (started typing it earlier, but not finished yet). 

The method used here is one that (in literature) predates the one used in #1524 ? What are the advantages/disadvantages of the two methods ?
easbar: For the path issues I opened https://github.com/graphhopper/graphhopper/issues/1727
karussell: I was going to merge master but the newly introduced [tests fail](https://travis-ci.org/graphhopper/graphhopper/jobs/612660686#L1019):

```
[ERROR] Tests run: 3, Failures: 2, Errors: 0, Skipped: 0, Time elapsed: 0.021 s <<< FAILURE! - in com.graphhopper.routing.AlternativeRouteCHTest

[ERROR] testCalcAlternatives2(com.graphhopper.routing.AlternativeRouteCHTest)  Time elapsed: 0.011 s  <<< FAILURE!
java.lang.AssertionError: expected:<3> but was:<1>
	at com.graphhopper.routing.AlternativeRouteCHTest.testCalcAlternatives2(AlternativeRouteCHTest.java:128)

[ERROR] testCalcAlternatives(com.graphhopper.routing.AlternativeRouteCHTest)  Time elapsed: 0.005 s  <<< FAILURE!
java.lang.AssertionError: expected:<2> but was:<1>
	at com.graphhopper.routing.AlternativeRouteCHTest.testCalcAlternatives(AlternativeRouteCHTest.java:98)
```

Is this a work in progress?
michaz: > Is this a work in progress?

Ah. Yes. I don't even know what I was trying to do there. I don't have a proper test case yet. Coming up.
michaz: I would cautiously call this finished. Merge?

Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/AlternativeRouteCH.java b/core/src/main/java/com/graphhopper/routing/AlternativeRouteCH.java
new file mode 100644
index 000000000..9329a2601
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/AlternativeRouteCH.java
@@ -0,0 +1,240 @@
+/*
+ *  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;
+
+import com.carrotsearch.hppc.IntIndexedContainer;
+import com.carrotsearch.hppc.predicates.IntObjectPredicate;
+import com.graphhopper.routing.ch.CHWeighting;
+import com.graphhopper.routing.weighting.Weighting;
+import com.graphhopper.storage.Graph;
+import com.graphhopper.storage.SPTEntry;
+import com.graphhopper.util.EdgeIteratorState;
+
+import java.util.*;
+
+/**
+ *
+ * Minimum number-of-moving-parts implementation of alternative route search with
+ * contraction hierarchies.
+ *
+ * "Alternative Routes in Road Networks" (Abraham et al.)
+ *
+ * @author michaz
+ */
+public class AlternativeRouteCH extends DijkstraBidirectionCHNoSOD {
+
+    private double maxWeightFactor = 1.4;
+    private double maxShareFactor = 0.6;
+    public static final double T = 10000.0;
+
+    public AlternativeRouteCH(Graph graph, Weighting weighting) {
+        super(graph, weighting);
+    }
+
+    List<AlternativeInfo> calcAlternatives(final int s, final int t) {
+        // First, do a regular bidirectional route search
+        checkAlreadyRun();
+        init(s, 0, t, 0);
+        runAlgo();
+        final Path bestPath = extractPath();
+        if (!bestPath.isFound()) {
+            return Collections.emptyList();
+        }
+
+        final List<AlternativeInfo> alternatives = new ArrayList<>();
+        alternatives.add(new AlternativeInfo(bestPath, 0));
+        final double maxWeight = maxWeightFactor * bestPath.getWeight();
+
+        bestWeightMapFrom.forEach(new IntObjectPredicate<SPTEntry>() {
+            @Override
+            public boolean apply(final int v, final SPTEntry fromSPTEntry) {
+                SPTEntry toSPTEntry = bestWeightMapTo.get(v);
+                if (toSPTEntry == null)
+                    return true;
+
+                // Filter alternatives that are too long
+                if (fromSPTEntry.getWeightOfVisitedPath() + toSPTEntry.getWeightOfVisitedPath() > maxWeight)
+                    return true;
+
+                // This gives us a path s -> v -> t, but since we are using contraction hierarchies,
+                // s -> v and v -> t need not be shortest paths. In fact, they can sometimes be pretty strange.
+                // We still use this preliminary path to filter for shared path length with other alternatives,
+                // so we don't have to work so much.
+                Path preliminaryRoute = createPathExtractor(graph, weighting).extract(fromSPTEntry, toSPTEntry, fromSPTEntry.getWeightOfVisitedPath() + toSPTEntry.getWeightOfVisitedPath());
+                double preliminaryShare = calculateShare(preliminaryRoute);
+                if (preliminaryShare > maxShareFactor) {
+                    return true;
+                }
+
+                // Okay, now we want the s -> v -> t shortest via-path, so we route s -> v and v -> t
+                // and glue them together.
+                DijkstraBidirectionCHNoSOD svRouter = new DijkstraBidirectionCHNoSOD(graph, weighting);
+                svRouter.setEdgeFilter(additionalEdgeFilter);
+                final Path svPath = svRouter.calcPath(s, v);
+                final IntIndexedContainer svNodes = svPath.calcNodes();
+                DijkstraBidirectionCHNoSOD vtRouter = new DijkstraBidirectionCHNoSOD(graph, weighting);
+                vtRouter.setEdgeFilter(additionalEdgeFilter);
+                final Path vtPath = vtRouter.calcPath(v, t);
+                final IntIndexedContainer vtNodes = vtPath.calcNodes();
+                Path path = new Path(graph.getBaseGraph()) {
+                    Path extract() {
+                        setFromNode(svNodes.get(0));
+                        for (EdgeIteratorState edge : svPath.calcEdges()) {
+                            addEdge(edge.getEdge());
+                        }
+                        for (EdgeIteratorState edge : vtPath.calcEdges()) {
+                            addEdge(edge.getEdge());
+                        }
+                        setEndNode(vtNodes.get(vtNodes.size() - 1));
+                        setFound(true);
+                        setWeight(svPath.getWeight() + vtPath.getWeight());
+                        setDistance(svPath.getDistance() + vtPath.getDistance());
+                        time = svPath.time + vtPath.time;
+                        return this;
+                    }
+                }.extract();
+
+                // And calculate the share again, because this can be totally different.
+                // The first filter is a good heuristic, but we still need this one.
+                double share = calculateShare(path);
+                if (share > maxShareFactor) {
+                    return true;
+                }
+
+                // This is the final test we need: Discard paths that are not "locally shortest" around v.
+                // So move a couple of nodes to the left and right from v on our path,
+                // route, and check if v is on the shortest path.
+                int vIndex = svNodes.size() - 1;
+                if (!tTest(path, vIndex))
+                    return true;
+
+                alternatives.add(new AlternativeInfo(path, share));
+                return true;
+            }
+
+            private double calculateShare(final Path path) {
+                double sharedDistance = 0.0;
+                List<EdgeIteratorState> edges = path.calcEdges();
+                for (EdgeIteratorState edge : edges) {
+                    if (nodesInCurrentAlternativeSetContains(edge.getBaseNode()) && nodesInCurrentAlternativeSetContains(edge.getAdjNode())) {
+                        sharedDistance += edge.getDistance();
+                    }
+                }
+                return sharedDistance / path.getDistance();
+            }
+
+            private boolean nodesInCurrentAlternativeSetContains(int v) {
+                for (AlternativeInfo alternative : alternatives) {
+                    if (alternative.nodes.contains(v)) {
+                        return true;
+                    }
+                }
+                return false;
+            }
+
+            private boolean tTest(Path path, int vIndex) {
+                if (path.getEdgeCount() == 0) return true;
+                int fromNode = getPreviousNodeTMetersAway(path, vIndex);
+                int toNode = getNextNodeTMetersAway(path, vIndex);
+                DijkstraBidirectionCHNoSOD tRouter = new DijkstraBidirectionCHNoSOD(graph, new CHWeighting(weighting));
+                tRouter.setEdgeFilter(additionalEdgeFilter);
+                Path tPath = tRouter.calcPath(fromNode, toNode);
+                IntIndexedContainer tNodes = tPath.calcNodes();
+                return tNodes.contains(path.calcNodes().get(vIndex));
+            }
+
+            private int getPreviousNodeTMetersAway(Path path, int vIndex) {
+                List<EdgeIteratorState> edges = path.calcEdges();
+                double distance = 0.0;
+                int i = vIndex;
+                while (i > 0 && distance < T) {
+                    distance += edges.get(i-1).getDistance();
+                    i--;
+                }
+                return edges.get(i).getBaseNode();
+            }
+
+            private int getNextNodeTMetersAway(Path path, int vIndex) {
+                List<EdgeIteratorState> edges = path.calcEdges();
+                double distance = 0.0;
+                int i = vIndex;
+                while (i < edges.size() - 1 && distance < T) {
+                    distance += edges.get(i).getDistance();
+                    i++;
+                }
+                return edges.get(i-1).getAdjNode();
+            }
+
+        });
+        Collections.sort(alternatives, new Comparator<AlternativeInfo>() {
+            @Override
+            public int compare(AlternativeInfo o1, AlternativeInfo o2) {
+                return Double.compare(o1.path.getWeight(), o2.path.getWeight());
+            }
+        });
+        return alternatives;
+    }
+
+    @Override
+    public List<Path> calcPaths(int from, int to) {
+        List<AlternativeInfo> alts = calcAlternatives(from, to);
+        if (alts.isEmpty()) {
+            return Collections.singletonList(createEmptyPath());
+        }
+        List<Path> paths = new ArrayList<>(alts.size());
+        for (AlternativeInfo a : alts) {
+            paths.add(a.path);
+        }
+        return paths;
+    }
+
+    public void setMaxWeightFactor(double maxWeightFactor) {
+        this.maxWeightFactor = maxWeightFactor;
+    }
+
+    public void setMaxShareFactor(double maxShareFactor) {
+        this.maxShareFactor = maxShareFactor;
+    }
+
+    public static class AlternativeInfo {
+        final Path path;
+        final double shareWeight;
+        final IntIndexedContainer nodes;
+
+        AlternativeInfo(Path path, double shareWeight) {
+            this.path = path;
+            this.shareWeight = shareWeight;
+            this.nodes = path.calcNodes();
+        }
+
+        public Path getPath() {
+            return path;
+        }
+
+        @Override
+        public String toString() {
+            return "AlternativeInfo{" +
+                    "path=" + path +
+                    ", shareWeight=" + shareWeight +
+                    ", nodes=" + nodes +
+                    '}';
+        }
+    }
+
+}
diff --git a/core/src/main/java/com/graphhopper/routing/ch/CHRoutingAlgorithmFactory.java b/core/src/main/java/com/graphhopper/routing/ch/CHRoutingAlgorithmFactory.java
index e521b37b3..23372e451 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/CHRoutingAlgorithmFactory.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/CHRoutingAlgorithmFactory.java
@@ -27,8 +27,9 @@ import com.graphhopper.storage.CHProfile;
 import com.graphhopper.storage.Graph;
 import com.graphhopper.storage.TurnCostStorage;
 
-import static com.graphhopper.util.Parameters.Algorithms.ASTAR_BI;
-import static com.graphhopper.util.Parameters.Algorithms.DIJKSTRA_BI;
+import static com.graphhopper.util.Parameters.Algorithms.*;
+import static com.graphhopper.util.Parameters.Algorithms.AltRoute.MAX_SHARE;
+import static com.graphhopper.util.Parameters.Algorithms.AltRoute.MAX_WEIGHT;
 
 public class CHRoutingAlgorithmFactory implements RoutingAlgorithmFactory {
     private final CHGraph chGraph;
@@ -81,6 +82,11 @@ public class CHRoutingAlgorithmFactory implements RoutingAlgorithmFactory {
             } else {
                 return new DijkstraBidirectionCHNoSOD(graph, chWeighting);
             }
+        } else if (ALT_ROUTE.equalsIgnoreCase(opts.getAlgorithm())) {
+            AlternativeRouteCH altRouteAlgo = new AlternativeRouteCH(graph, chWeighting);
+            altRouteAlgo.setMaxWeightFactor(opts.getHints().getDouble(MAX_WEIGHT, 1.4));
+            altRouteAlgo.setMaxShareFactor(opts.getHints().getDouble(MAX_SHARE, 0.6));
+            return altRouteAlgo;
         } else {
             throw new IllegalArgumentException("Algorithm " + opts.getAlgorithm() + " not supported for node-based Contraction Hierarchies. Try with ch.disable=true");
         }


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/AlternativeRouteCHTest.java b/core/src/test/java/com/graphhopper/routing/AlternativeRouteCHTest.java
new file mode 100644
index 000000000..6c5ad681a
--- /dev/null
+++ b/core/src/test/java/com/graphhopper/routing/AlternativeRouteCHTest.java
@@ -0,0 +1,105 @@
+/*
+ *  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;
+
+import com.graphhopper.routing.ch.CHWeighting;
+import com.graphhopper.routing.ch.NodeOrderingProvider;
+import com.graphhopper.routing.ch.PrepareContractionHierarchies;
+import com.graphhopper.routing.util.*;
+import com.graphhopper.routing.weighting.FastestWeighting;
+import com.graphhopper.routing.weighting.Weighting;
+import com.graphhopper.storage.*;
+import org.junit.Test;
+
+import java.util.Arrays;
+import java.util.List;
+
+import static org.junit.Assert.*;
+
+public class AlternativeRouteCHTest {
+    private final FlagEncoder carFE = new CarFlagEncoder();
+    private final EncodingManager em = EncodingManager.create(carFE);
+    private final Weighting weighting = new FastestWeighting(carFE);
+
+    public GraphHopperStorage createTestGraph(EncodingManager tmpEM) {
+        final GraphHopperStorage graph = new GraphHopperStorage(new RAMDirectory(), tmpEM, false);
+        CHProfile chProfile = CHProfile.nodeBased(new FastestWeighting(carFE));
+        graph.addCHGraph(chProfile);
+        graph.create(1000);
+
+        /*
+
+           9
+          /\
+         1  2-3-4-10
+         \   /   \
+         5--6-7---8
+        
+         */
+
+        // Make all edges the length of T, the distance around v than an s->v->t path
+        // has to be locally-shortest to be considered.
+        // So we get all three alternatives.
+
+        graph.edge(5, 6, AlternativeRouteCH.T, true);
+        graph.edge(6, 3, AlternativeRouteCH.T, true);
+        graph.edge(3, 4, AlternativeRouteCH.T, true);
+        graph.edge(4, 10, AlternativeRouteCH.T, true);
+
+        graph.edge(6, 7, AlternativeRouteCH.T, true);
+        graph.edge(7, 8, AlternativeRouteCH.T, true);
+        graph.edge(8, 4, AlternativeRouteCH.T, true);
+
+        graph.edge(5, 1, AlternativeRouteCH.T, true);
+        graph.edge(1, 9, AlternativeRouteCH.T, true);
+        graph.edge(9, 2, AlternativeRouteCH.T, true);
+        graph.edge(2, 3, AlternativeRouteCH.T, true);
+
+        graph.freeze();
+
+        // Carefully construct the CH so that the forward tree and the backward tree
+        // meet on all three possible paths from 5 to 10
+        final List<Integer> nodeOrdering = Arrays.asList(0, 10, 4, 3, 2, 5, 1, 6, 7, 8, 9);
+        PrepareContractionHierarchies contractionHierarchies = PrepareContractionHierarchies.fromGraphHopperStorage(graph, chProfile);
+        contractionHierarchies.useFixedNodeOrdering(new NodeOrderingProvider() {
+            @Override
+            public int getNodeIdForLevel(int level) {
+                return nodeOrdering.get(level);
+            }
+
+            @Override
+            public int getNumNodes() {
+                return nodeOrdering.size();
+            }
+        });
+        contractionHierarchies.doWork();
+        return graph;
+    }
+
+    @Test
+    public void testCalcAlternatives() {
+        GraphHopperStorage g = createTestGraph(em);
+        AlternativeRouteCH altDijkstra = new AlternativeRouteCH(g.getCHGraph(), new CHWeighting(weighting));
+        altDijkstra.setEdgeFilter(new LevelEdgeFilter(g.getCHGraph()));
+        altDijkstra.setMaxShareFactor(0.9);
+        altDijkstra.setMaxWeightFactor(10);
+        List<AlternativeRouteCH.AlternativeInfo> pathInfos = altDijkstra.calcAlternatives(5, 10);
+        assertEquals(3, pathInfos.size());
+    }
+
+}