Repository: graphhopper/graphhopper (java)

Issue:
Edge-based bidirectional algorithms do not agree with Dijkstra when there is a loop and turn restrictions.
Here is a graph involving a loop and some turn restrictions for which the edge-based bidirectional algorithms do not agree with Dijkstra / do not find the optimal path:

https://github.com/graphhopper/graphhopper/blob/fe8df1d7e56ac6052571eaf2bfc675ba1cd6415e/core/src/test/java/com/graphhopper/routing/EdgeBasedRoutingAlgorithmTest.java#L162-L185

Pull request:
Fixes missing best path update for bidir algos when there is a loop at the meeting point (#1592)
- Fixes #1592.
- removes no longer needed `TraversalMode.EDGE_BASED_1DIR` (see #1520)


Patch:
diff --git a/core/files/changelog.txt b/core/files/changelog.txt
index 659e0cdfc..4ac9737fc 100644
--- a/core/files/changelog.txt
+++ b/core/files/changelog.txt
@@ -1,3 +1,5 @@
+0.13
+    removed TraversalMode.EDGE_BASED_1DIR
 0.12
     renamed VirtualEdgeIteratorState.getOriginalEdgeKey to more precise getOriginalEdgeKey #1549
     access refactoring #1436 that moves AccessValue into SpatialRule.Access
diff --git a/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java b/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
index 05edba060..c0445d30e 100644
--- a/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
+++ b/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
@@ -73,8 +73,8 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
     protected abstract SPTEntry createStartEntry(int node, double weight, boolean reverse);
 
     /**
-     * Creates a new entry of the shortest path tree (a {@link SPTEntry} or one of its subclasses) during a
-     * dijkstra expansion.
+     * Creates a new entry of the shortest path tree (a {@link SPTEntry} or one of its subclasses) during a dijkstra
+     * expansion.
      *
      * @param edge    the edge that is currently processed for the expansion
      * @param incEdge the id of the edge that is incoming to the node the edge is pointed at. usually this is the same as
@@ -248,13 +248,9 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
             if (getIncomingEdge(entryOther) != getIncomingEdge(entry))
                 throw new IllegalStateException("cannot happen for edge based execution of " + getName());
 
-            if (entryOther.adjNode != entry.adjNode) {
-                // prevents the path to contain the edge at the meeting point twice and subtracts the weight (excluding turn weight => no previous edge)
-                entry = entry.getParent();
-                weight -= weighting.calcWeight(edgeState, reverse, EdgeIterator.NO_EDGE);
-            } else if (!traversalMode.hasUTurnSupport())
-                // we detected a u-turn at meeting point, skip if not supported
-                return;
+            // prevents the path to contain the edge at the meeting point twice and subtracts the weight (excluding turn weight => no previous edge)
+            entry = entry.getParent();
+            weight -= weighting.calcWeight(edgeState, reverse, EdgeIterator.NO_EDGE);
         }
 
         if (weight < bestPath.getWeight()) {
diff --git a/core/src/main/java/com/graphhopper/routing/util/TraversalMode.java b/core/src/main/java/com/graphhopper/routing/util/TraversalMode.java
index ca6aaceb4..eac312554 100644
--- a/core/src/main/java/com/graphhopper/routing/util/TraversalMode.java
+++ b/core/src/main/java/com/graphhopper/routing/util/TraversalMode.java
@@ -37,37 +37,25 @@ public enum TraversalMode {
     /**
      * The simplest traversal mode but without turn restrictions or cost support.
      */
-    NODE_BASED(false, 1, false),
-    /**
-     * Strictly not recommended as it could lead to 'route not found' for bidirectional algorithms.
-     * An edged-based traversal mode with basic turn restriction and cost support, including the
-     * most scenarios. But without certain turn restrictions and without u-turns. As fast as node
-     * based.
-     */
-    EDGE_BASED_1DIR(true, 1, false),
+    NODE_BASED(false, false),
     /**
      * The bidirectional edged-based traversal mode with turn restriction and cost support. Without
      * u-turn support. 2 times slower than node based.
      */
-    EDGE_BASED_2DIR(true, 2, false),
+    EDGE_BASED_2DIR(true, false),
     /**
      * Not recommended as it leads to strange routes that outsmart the turn costs. The most feature
-     * rich edged-based traversal mode with turn restriction and cost support, including u-turns. 4
+     * rich edge-based traversal mode with turn restriction and cost support, including u-turns. 4
      * times slower than node based.
      */
-    EDGE_BASED_2DIR_UTURN(true, 2, true);
+    EDGE_BASED_2DIR_UTURN(true, true);
 
     private final boolean edgeBased;
-    private final int noOfStates;
     private final boolean uTurnSupport;
 
-    TraversalMode(boolean edgeBased, int noOfStates, boolean uTurnSupport) {
+    TraversalMode(boolean edgeBased, boolean uTurnSupport) {
         this.edgeBased = edgeBased;
-        this.noOfStates = noOfStates;
         this.uTurnSupport = uTurnSupport;
-
-        if (noOfStates != 1 && noOfStates != 2)
-            throw new IllegalArgumentException("Currently only 1 or 2 states allowed");
     }
 
     public static TraversalMode fromString(String name) {
@@ -91,14 +79,7 @@ public enum TraversalMode {
      * @return the identifier to access the shortest path tree
      */
     public final int createTraversalId(EdgeIteratorState iterState, boolean reverse) {
-        if (edgeBased) {
-            if (noOfStates == 1)
-                return iterState.getEdge();
-
-            return GHUtility.createEdgeKey(iterState.getBaseNode(), iterState.getAdjNode(), iterState.getEdge(), reverse);
-        }
-
-        return iterState.getAdjNode();
+        return createTraversalId(iterState.getBaseNode(), iterState.getAdjNode(), iterState.getEdge(), reverse);
     }
 
     /**
@@ -106,25 +87,17 @@ public enum TraversalMode {
      */
     public final int createTraversalId(int baseNode, int adjNode, int edgeId, boolean reverse) {
         if (edgeBased) {
-            if (noOfStates == 1)
-                return edgeId;
-
             return GHUtility.createEdgeKey(baseNode, adjNode, edgeId, reverse);
         }
-
         return adjNode;
     }
 
     public int reverseEdgeKey(int edgeKey) {
-        if (edgeBased && noOfStates > 1)
+        if (edgeBased)
             return GHUtility.reverseEdgeKey(edgeKey);
         return edgeKey;
     }
 
-    public int getNoOfStates() {
-        return noOfStates;
-    }
-
     public boolean isEdgeBased() {
         return edgeBased;
     }
diff --git a/core/src/main/java/com/graphhopper/util/GHUtility.java b/core/src/main/java/com/graphhopper/util/GHUtility.java
index 5f4c1543c..dd054f33f 100644
--- a/core/src/main/java/com/graphhopper/util/GHUtility.java
+++ b/core/src/main/java/com/graphhopper/util/GHUtility.java
@@ -465,7 +465,7 @@ public class GHUtility {
     public static int createEdgeKey(int nodeA, int nodeB, int edgeId, boolean reverse) {
         edgeId = edgeId << 1;
         if (reverse)
-            return (nodeA > nodeB) ? edgeId : edgeId + 1;
+            return (nodeA >= nodeB) ? edgeId : edgeId + 1;
         return (nodeA > nodeB) ? edgeId + 1 : edgeId;
     }
 
diff --git a/reader-gtfs/pom.xml b/reader-gtfs/pom.xml
index 7341c2d14..af501bbcd 100644
--- a/reader-gtfs/pom.xml
+++ b/reader-gtfs/pom.xml
@@ -71,6 +71,12 @@
             <artifactId>dropwizard-client</artifactId>
             <version>${dropwizard.version}</version>
         </dependency>
+        <!-- see #1606 -->
+        <dependency>
+            <groupId>javax.activation</groupId>
+            <artifactId>activation</artifactId>
+            <version>1.1.1</version>
+        </dependency>
 
         <dependency>
             <groupId>com.graphhopper</groupId>


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java b/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java
index 60b70c23d..bc07cd7e4 100644
--- a/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java
+++ b/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java
@@ -51,7 +51,6 @@ public class AStarBidirectionTest extends AbstractRoutingAlgorithmTester {
     public static Collection<Object[]> configs() {
         return Arrays.asList(new Object[][]{
                 {TraversalMode.NODE_BASED},
-                {TraversalMode.EDGE_BASED_1DIR},
                 {TraversalMode.EDGE_BASED_2DIR},
                 {TraversalMode.EDGE_BASED_2DIR_UTURN}
         });
diff --git a/core/src/test/java/com/graphhopper/routing/AStarTest.java b/core/src/test/java/com/graphhopper/routing/AStarTest.java
index 56f12bd46..5f35819a0 100644
--- a/core/src/test/java/com/graphhopper/routing/AStarTest.java
+++ b/core/src/test/java/com/graphhopper/routing/AStarTest.java
@@ -46,7 +46,6 @@ public class AStarTest extends AbstractRoutingAlgorithmTester {
     public static Collection<Object[]> configs() {
         return Arrays.asList(new Object[][]{
                 {TraversalMode.NODE_BASED},
-                {TraversalMode.EDGE_BASED_1DIR},
                 {TraversalMode.EDGE_BASED_2DIR},
                 {TraversalMode.EDGE_BASED_2DIR_UTURN}
         });
diff --git a/core/src/test/java/com/graphhopper/routing/DijkstraBidirectionRefTest.java b/core/src/test/java/com/graphhopper/routing/DijkstraBidirectionRefTest.java
index 9667bd361..617ddc249 100644
--- a/core/src/test/java/com/graphhopper/routing/DijkstraBidirectionRefTest.java
+++ b/core/src/test/java/com/graphhopper/routing/DijkstraBidirectionRefTest.java
@@ -45,7 +45,6 @@ public class DijkstraBidirectionRefTest extends AbstractRoutingAlgorithmTester {
     public static Collection<Object[]> configs() {
         return Arrays.asList(new Object[][]{
                 {TraversalMode.NODE_BASED},
-                {TraversalMode.EDGE_BASED_1DIR},
                 {TraversalMode.EDGE_BASED_2DIR},
                 {TraversalMode.EDGE_BASED_2DIR_UTURN}
         });
diff --git a/core/src/test/java/com/graphhopper/routing/DijkstraTest.java b/core/src/test/java/com/graphhopper/routing/DijkstraTest.java
index 29fec9201..2ba58ff0e 100644
--- a/core/src/test/java/com/graphhopper/routing/DijkstraTest.java
+++ b/core/src/test/java/com/graphhopper/routing/DijkstraTest.java
@@ -45,7 +45,6 @@ public class DijkstraTest extends AbstractRoutingAlgorithmTester {
     public static Collection<Object[]> configs() {
         return Arrays.asList(new Object[][]{
                 {TraversalMode.NODE_BASED},
-                {TraversalMode.EDGE_BASED_1DIR},
                 {TraversalMode.EDGE_BASED_2DIR},
                 {TraversalMode.EDGE_BASED_2DIR_UTURN}
         });
diff --git a/core/src/test/java/com/graphhopper/routing/EdgeBasedRoutingAlgorithmTest.java b/core/src/test/java/com/graphhopper/routing/EdgeBasedRoutingAlgorithmTest.java
index e9e39e371..6ed16ab82 100644
--- a/core/src/test/java/com/graphhopper/routing/EdgeBasedRoutingAlgorithmTest.java
+++ b/core/src/test/java/com/graphhopper/routing/EdgeBasedRoutingAlgorithmTest.java
@@ -31,7 +31,6 @@ import com.graphhopper.storage.GraphBuilder;
 import com.graphhopper.storage.GraphHopperStorage;
 import com.graphhopper.storage.TurnCostExtension;
 import com.graphhopper.util.EdgeIteratorState;
-import org.junit.Assume;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -149,17 +148,42 @@ public class EdgeBasedRoutingAlgorithmTest {
         // test 7-6-5 and reverse
         p = createAlgo(g, AlgorithmOptions.start().
                 weighting(createWeighting(carEncoder, tcs, 40)).
-                traversalMode(TraversalMode.EDGE_BASED_1DIR).build()).
+                traversalMode(TraversalMode.EDGE_BASED_2DIR).build()).
                 calcPath(5, 7);
         assertEquals(IntArrayList.from(5, 6, 7), p.calcNodes());
 
         p = createAlgo(g, AlgorithmOptions.start().
                 weighting(createWeighting(carEncoder, tcs, 40)).
-                traversalMode(TraversalMode.EDGE_BASED_1DIR).build()).
+                traversalMode(TraversalMode.EDGE_BASED_2DIR).build()).
                 calcPath(7, 5);
         assertEquals(IntArrayList.from(7, 6, 3, 2, 5), p.calcNodes());
     }
 
+    @Test
+    public void testLoop_issue1592() {
+        GraphHopperStorage g = createStorage(createEncodingManager(true));
+        // 0-6
+        //  \ \
+        //   4-3
+        //   |
+        //   1o
+        g.edge(0, 6, 10, true);
+        g.edge(6, 3, 10, true);
+        g.edge(0, 4, 1, true);
+        g.edge(4, 1, 1, true);
+        g.edge(4, 3, 1, true);
+        g.edge(1, 1, 10, true);
+        TurnCostExtension tcs = (TurnCostExtension) g.getExtension();
+        addTurnRestriction(g, tcs, 0, 4, 3);
+
+        Path p = createAlgo(g, AlgorithmOptions.start().
+                weighting(createWeighting(carEncoder, tcs, 40)).
+                traversalMode(TraversalMode.EDGE_BASED_2DIR).build()).
+                calcPath(0, 3);
+        assertEquals(14, p.getDistance(), 1.e-3);
+        assertEquals(IntArrayList.from(0, 4, 1, 1, 4, 3), p.calcNodes());
+    }
+
     @Test
     public void testTurnCosts_timeCalculation() {
         // 0 - 1 - 2 - 3 - 4
@@ -276,7 +300,7 @@ public class EdgeBasedRoutingAlgorithmTest {
         TurnCostExtension tcs = (TurnCostExtension) g.getExtension();
         Path p = createAlgo(g, AlgorithmOptions.start().
                 weighting(createWeighting(carEncoder, tcs, 40)).
-                traversalMode(TraversalMode.EDGE_BASED_1DIR).build()).
+                traversalMode(TraversalMode.EDGE_BASED_2DIR).build()).
                 calcPath(5, 1);
 
         // no restriction and costs
@@ -288,7 +312,7 @@ public class EdgeBasedRoutingAlgorithmTest {
 
         p = createAlgo(g, AlgorithmOptions.start().
                 weighting(createWeighting(carEncoder, tcs, 40)).
-                traversalMode(TraversalMode.EDGE_BASED_1DIR).build()).
+                traversalMode(TraversalMode.EDGE_BASED_2DIR).build()).
                 calcPath(5, 1);
         assertEquals(IntArrayList.from(5, 6, 3, 1), p.calcNodes());
     }
diff --git a/core/src/test/java/com/graphhopper/util/GHUtilityTest.java b/core/src/test/java/com/graphhopper/util/GHUtilityTest.java
index bd98a5afa..1b423322c 100644
--- a/core/src/test/java/com/graphhopper/util/GHUtilityTest.java
+++ b/core/src/test/java/com/graphhopper/util/GHUtilityTest.java
@@ -170,6 +170,9 @@ public class GHUtilityTest {
         assertEquals(8, GHUtility.createEdgeKey(1, 2, 4, false));
         assertEquals(9, GHUtility.createEdgeKey(2, 1, 4, false));
 
+        assertEquals(6, GHUtility.createEdgeKey(1, 1, 3, false));
+        assertEquals(6, GHUtility.createEdgeKey(1, 1, 3, true));
+
         assertTrue(GHUtility.isSameEdgeKeys(GHUtility.createEdgeKey(1, 2, 4, false), GHUtility.createEdgeKey(1, 2, 4, false)));
         assertTrue(GHUtility.isSameEdgeKeys(GHUtility.createEdgeKey(2, 1, 4, false), GHUtility.createEdgeKey(1, 2, 4, false)));
         assertFalse(GHUtility.isSameEdgeKeys(GHUtility.createEdgeKey(1, 2, 4, false), GHUtility.createEdgeKey(1, 2, 5, false)));