Repository: graphhopper/graphhopper
Pull request #909 (2016-12-13 08:37:17)

Refactor unfavoring of virtual edges (#885)
This addresses issue #885.

Also needed for graphhopper/map-matching#70

stefanholder: >Can we reduce this to `List<EdgeIteratorState>`?

Done.

>Would you mind adding a Testcase that shows the issue described in #885 and that it is solved by your PR?

Done.
karussell: @boldtrn please confirm & merge (as here just one author it is safe to 'squash and merge')
@kodonnell can we close #885 then?
stefanholder: >@boldtrn please confirm & merge (as here just one author it is safe to 'squash and merge')

If both commits are squashed then the test case showing the issue described in #885 is lost.
karussell: Hmmh, why isn't it added to the latest commit?
stefanholder: >Hmmh, why isn't it added to the latest commit?

Simply speaking, because adding something and deleting the same in a single commit results in no change. The test case in the first commit tests `enforceHeadingByEdgeId` as it is described in the original javadoc of this method and hence reveals the problems with this method. The second commit changes the contract of the method and the unit tests to match its behavior.
karussell: Ok, then you mean 'lost' in the sense for historical reasons. Makes sense. @boldtrn 
kodonnell: > @kodonnell can we close #885 then?

Sure. Happy for you to close it when merged, or I can.
boldtrn: @stefanholder Thanks for adding a test.

> If both commits are squashed then the test case showing the issue described in #885 is lost.

The reason why I asked you to add a test was to document the issue and make sure that we don't add a similar issue by mistake in the future. See my [comment](https://github.com/graphhopper/graphhopper/pull/909/files/ac385b6918b9001f9ce313f5270ea72ea86506f1#diff-b023b2a2f1f8a34fc135e3905e7b86d3). But maybe I am overthinking this issue? I will approve my review, that's probably somethin @karussell has to decide.


stefanholder: >as here just one author it is safe to 'squash and merge'

@karussell, squashing a PR via the github UI always changes the author to the person that does the squash merging. I just verified this with a test squash. The reason behind this is that github uses the `git merge --squash` to create the squashed changes and then commits them under the maintainer's name. (See also graphhopper/map-matching#83 for the previous discussion on this topic.)

Note that it's possible to [disable squash merging](https://github.com/blog/2141-squash-your-commits) in the github repository options. Squashing without changing authorship can be done manually using `git rebase -i`.

Patch:
diff --git a/CONTRIBUTORS.md b/CONTRIBUTORS.md
index 66462ef7f..317909fbd 100644
--- a/CONTRIBUTORS.md
+++ b/CONTRIBUTORS.md
@@ -42,7 +42,8 @@ Most of the contributors are mentioned at Github as [Members](https://github.com
  * rajanski, script to do routing via PostGIS
  * rodneyodonnell, improved dead end removal and fords
  * rodo, more descriptions
- * seeebiii, motorcycle improvements 
+ * seeebiii, motorcycle improvements
+ * stefanholder, Stefan Holder, BMW AG, refactored unfavoring of virtual edges #885
  * Svantulden, improved documentation and nearest API
  * thehereward, code cleanups like #620
  * vvikas, ideas for many to many improvements and #616
diff --git a/core/src/main/java/com/graphhopper/routing/QueryGraph.java b/core/src/main/java/com/graphhopper/routing/QueryGraph.java
index 99f5337a2..8c98e8e62 100644
--- a/core/src/main/java/com/graphhopper/routing/QueryGraph.java
+++ b/core/src/main/java/com/graphhopper/routing/QueryGraph.java
@@ -141,7 +141,10 @@ public class QueryGraph implements Graph {
             return getElevation(nodeId);
         }
     };
-    private List<VirtualEdgeIteratorState> modifiedEdges = new ArrayList<VirtualEdgeIteratorState>(5);
+
+    // Use LinkedHashSet for predictable iteration order.
+    private final Set<VirtualEdgeIteratorState> unfavoredEdges = new LinkedHashSet<>(5);
+
     private boolean useEdgeExplorerCache = false;
 
     public QueryGraph(Graph graph) {
@@ -407,7 +410,7 @@ public class QueryGraph implements Graph {
 
     /**
      * Set those edges at the virtual node (nodeId) to 'unfavored' that require at least a turn of
-     * 100° from favoredHeading
+     * 100° from favoredHeading.
      * <p>
      *
      * @param nodeId         VirtualNode at which edges get unfavored
@@ -451,11 +454,11 @@ public class QueryGraph implements Graph {
             if (Math.abs(delta) > 1.74) // penalize if a turn of more than 100°
             {
                 edge.setUnfavored(true);
-                modifiedEdges.add(edge);
+                unfavoredEdges.add(edge);
                 //also apply to opposite edge for reverse routing
                 VirtualEdgeIteratorState reverseEdge = virtualEdges.get(virtNodeIDintern * 4 + getPosOfReverseEdge(edgePos));
                 reverseEdge.setUnfavored(true);
-                modifiedEdges.add(reverseEdge);
+                unfavoredEdges.add(reverseEdge);
                 enforcementOccurred = true;
             }
 
@@ -464,35 +467,49 @@ public class QueryGraph implements Graph {
     }
 
     /**
-     * Set one specific edge at the virtual node with nodeId to 'unfavored' to enforce routing along
-     * other edges
+     * Sets the virtual edge with virtualEdgeId and its reverse edge to 'unfavored', which
+     * effectively penalizes both virtual edges towards an adjacent node of virtualNodeId.
+     * This makes it more likely (but does not guarantee) that the router chooses a route towards
+     * the other adjacent node of virtualNodeId.
      * <p>
      *
-     * @param nodeId   VirtualNode at which edges get unfavored
-     * @param edgeId   edge to become unfavored
-     * @param incoming if true, incoming edge is unfavored, else outgoing edge
-     * @return boolean indicating if enforcement took place
+     * @param virtualNodeId  virtual node at which edges get unfavored
+     * @param virtualEdgeId  this edge and the reverse virtual edge become unfavored
      */
-    public boolean enforceHeadingByEdgeId(int nodeId, int edgeId, boolean incoming) {
-        if (!isVirtualNode(nodeId))
-            return false;
+    public void unfavorVirtualEdgePair(int virtualNodeId, int virtualEdgeId) {
+        if (!isVirtualNode(virtualNodeId)) {
+            throw new IllegalArgumentException("Node id " + virtualNodeId
+                    + " must be a virtual node.");
+        }
 
-        VirtualEdgeIteratorState incomingEdge = (VirtualEdgeIteratorState) getEdgeIteratorState(edgeId, nodeId);
-        VirtualEdgeIteratorState reverseEdge = (VirtualEdgeIteratorState) getEdgeIteratorState(edgeId, incomingEdge.getBaseNode());
+        VirtualEdgeIteratorState incomingEdge =
+                (VirtualEdgeIteratorState) getEdgeIteratorState(virtualEdgeId, virtualNodeId);
+        VirtualEdgeIteratorState reverseEdge = (VirtualEdgeIteratorState) getEdgeIteratorState(
+                virtualEdgeId, incomingEdge.getBaseNode());
         incomingEdge.setUnfavored(true);
-        modifiedEdges.add(incomingEdge);
+        unfavoredEdges.add(incomingEdge);
         reverseEdge.setUnfavored(true);
-        modifiedEdges.add(reverseEdge);
-        return true;
+        unfavoredEdges.add(reverseEdge);
+    }
+
+    /**
+     * Returns all virtual edges that have been unfavored via
+     * {@link #enforceHeading(int, double, boolean)} or {@link #unfavorVirtualEdgePair(int, int)}.
+     */
+    public Set<EdgeIteratorState> getUnfavoredVirtualEdges() {
+        // Need to create a new set to convert Set<VirtualEdgeIteratorState> to
+        // Set<EdgeIteratorState>.
+        return new LinkedHashSet<EdgeIteratorState>(unfavoredEdges);
     }
 
     /**
      * Removes the 'unfavored' status of all virtual edges.
      */
     public void clearUnfavoredStatus() {
-        for (VirtualEdgeIteratorState edge : modifiedEdges) {
+        for (VirtualEdgeIteratorState edge : unfavoredEdges) {
             edge.setUnfavored(false);
         }
+        unfavoredEdges.clear();
     }
 
     @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 5cb6d25d9..cfa22fb93 100644
--- a/core/src/main/java/com/graphhopper/routing/template/ViaRoutingTemplate.java
+++ b/core/src/main/java/com/graphhopper/routing/template/ViaRoutingTemplate.java
@@ -98,7 +98,7 @@ public class ViaRoutingTemplate extends AbstractRoutingTemplate implements Routi
                 Path prevRoute = pathList.get(placeIndex - 2);
                 if (prevRoute.getEdgeCount() > 0) {
                     EdgeIteratorState incomingVirtualEdge = prevRoute.getFinalEdge();
-                    queryGraph.enforceHeadingByEdgeId(fromQResult.getClosestNode(), incomingVirtualEdge.getEdge(), false);
+                    queryGraph.unfavorVirtualEdgePair(fromQResult.getClosestNode(), incomingVirtualEdge.getEdge());
                 }
             }
 


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/QueryGraphTest.java b/core/src/test/java/com/graphhopper/routing/QueryGraphTest.java
index 2ee744b0b..4e6164fdf 100644
--- a/core/src/test/java/com/graphhopper/routing/QueryGraphTest.java
+++ b/core/src/test/java/com/graphhopper/routing/QueryGraphTest.java
@@ -30,6 +30,8 @@ import org.junit.Before;
 import org.junit.Test;
 
 import java.util.Arrays;
+import java.util.HashSet;
+import java.util.LinkedHashSet;
 
 import static com.graphhopper.storage.index.QueryResult.Position.*;
 import static org.junit.Assert.*;
@@ -602,7 +604,7 @@ public class QueryGraphTest {
     }
 
     @Test
-    public void testEnforceHeadingByEdgeId() {
+    public void testunfavorVirtualEdgePair() {
 
         initHorseshoeGraph(g);
         EdgeIteratorState edge = GHUtility.getEdge(g, 0, 1);
@@ -613,22 +615,21 @@ public class QueryGraphTest {
         queryGraph.lookup(Arrays.asList(qr));
 
         // enforce coming in north
-        queryGraph.enforceHeadingByEdgeId(2, 1, false);
+        queryGraph.unfavorVirtualEdgePair(2, 1);
         // test penalized south
-        boolean expect = true;
         VirtualEdgeIteratorState incomingEdge = (VirtualEdgeIteratorState) queryGraph.getEdgeIteratorState(1, 2);
-
         VirtualEdgeIteratorState incomingEdgeReverse = (VirtualEdgeIteratorState) queryGraph.getEdgeIteratorState(1, incomingEdge.getBaseNode());
-        // expect incoming edge in reverse direction to be avoided
+        boolean expect = true;  // expect incoming and reverse incoming edge to be avoided
         assertEquals(expect, incomingEdge.getBool(EdgeIteratorState.K_UNFAVORED_EDGE, !expect));
-        // expect reverse incoming edge to be avoided
         assertEquals(expect, incomingEdgeReverse.getBool(EdgeIteratorState.K_UNFAVORED_EDGE, !expect));
+        assertEquals(new LinkedHashSet<>(Arrays.asList(incomingEdge, incomingEdgeReverse)),
+                queryGraph.getUnfavoredVirtualEdges());
 
         queryGraph.clearUnfavoredStatus();
-        expect = false;
+        expect = false; // expect incoming and reverse incoming edge not to be avoided
         assertEquals(expect, incomingEdge.getBool(EdgeIteratorState.K_UNFAVORED_EDGE, !expect));
-        // expect reverse incoming edge to be unfavored
         assertEquals(expect, incomingEdgeReverse.getBool(EdgeIteratorState.K_UNFAVORED_EDGE, !expect));
+        assertEquals(new LinkedHashSet<>(), queryGraph.getUnfavoredVirtualEdges());
     }
 
     @Test