Repository: graphhopper/graphhopper
Pull request #1603 (2019-04-27 07:08:43)

Extracts new ShortcutUnpacker from Path4CH.
Partly in preparation to include turn cost times with edge-based CH (#1585) and easier testing shortcut unpacking is moved from Path4CH to a separate class.

easbar: Looks like travis has a problem downloading jdk11:
```
curl: (51) SSL: no alternative certificate subject name matches target host name 'download.java.net'
```
karussell: Thanks!

> Looks like travis has a problem downloading jdk11:

Yes, will see how fast they fix the cert issue and apply the workaround if not fast enough :) https://github.com/sormuras/bach/issues/51#issuecomment-487380743
karussell: Thanks for this refactoring and the bug fix + tests!

Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java b/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java
index ce6135e1a..cbefc3d8d 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java
@@ -172,6 +172,7 @@ class NodeBasedNodeContractor extends AbstractNodeContractor {
                 continue;
 
             final double incomingEdgeWeight = prepareWeighting.calcWeight(incomingEdges, true, EdgeIterator.NO_EDGE);
+            // this check is important to prevent calling calcMillis on inaccessible edges and also allows early exit
             if (Double.isInfinite(incomingEdgeWeight)) {
                 continue;
             }
@@ -360,7 +361,7 @@ class NodeBasedNodeContractor extends AbstractNodeContractor {
             else
                 str = from + "->";
 
-            return str + to + ", weight:" + weight + " (" + skippedEdge1 + "," + skippedEdge2 + ")";
+            return str + to + ", weight:" + weight + " (" + skippedEdge1 + "," + skippedEdge2 + "), dist: " + dist;
         }
     }
 
diff --git a/core/src/main/java/com/graphhopper/routing/ch/Path4CH.java b/core/src/main/java/com/graphhopper/routing/ch/Path4CH.java
index f47a6ea92..d2d38ab9c 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/Path4CH.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/Path4CH.java
@@ -20,81 +20,29 @@ package com.graphhopper.routing.ch;
 import com.graphhopper.routing.PathBidirRef;
 import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.Graph;
-import com.graphhopper.util.CHEdgeIteratorState;
+import com.graphhopper.storage.ShortcutUnpacker;
 import com.graphhopper.util.EdgeIterator;
+import com.graphhopper.util.EdgeIteratorState;
 
-import java.util.Locale;
-
-/**
- * Recursively unpack shortcuts.
- * <p>
- *
- * @author Peter Karich
- * @see PrepareContractionHierarchies
- */
 public class Path4CH extends PathBidirRef {
-    private final Graph routingGraph;
+    private final ShortcutUnpacker shortcutUnpacker;
 
-    public Path4CH(Graph routingGraph, Graph baseGraph, Weighting weighting) {
+    public Path4CH(Graph routingGraph, Graph baseGraph, final Weighting weighting) {
         super(baseGraph, weighting);
-        this.routingGraph = routingGraph;
+        this.shortcutUnpacker = new ShortcutUnpacker(routingGraph, new ShortcutUnpacker.Visitor() {
+            @Override
+            public void visit(EdgeIteratorState edge, boolean reverse, int prevOrNextEdgeId) {
+                distance += edge.getDistance();
+                time += weighting.calcMillis(edge, reverse, EdgeIterator.NO_EDGE);
+                addEdge(edge.getEdge());
+            }
+        });
     }
 
     @Override
     protected final void processEdge(int edgeId, int endNode, int prevEdgeId) {
         // Shortcuts do only contain valid weight so first expand before adding
         // to distance and time
-        expandEdge(getEdge(edgeId, endNode), false);
-    }
-
-    private void expandEdge(CHEdgeIteratorState edge, boolean reverse) {
-        if (!edge.isShortcut()) {
-            distance += edge.getDistance();
-            time += weighting.calcMillis(edge, reverse, EdgeIterator.NO_EDGE);
-            addEdge(edge.getEdge());
-            return;
-        }
-        expandSkippedEdges(edge.getSkippedEdge1(), edge.getSkippedEdge2(), edge.getBaseNode(), edge.getAdjNode(), reverse);
-    }
-
-    private void expandSkippedEdges(int skippedEdge1, int skippedEdge2, int from, int to, boolean reverse) {
-        // for edge-based CH we need to take special care for loop shortcuts
-        if (from != to) {
-            // get properties like speed of the edge in the correct direction
-            if (reverseOrder == reverse) {
-                int tmp = from;
-                from = to;
-                to = tmp;
-            }
-            CHEdgeIteratorState sk2to = getEdge(skippedEdge2, to);
-            if (sk2to != null) {
-                expandEdge(sk2to, !reverseOrder);
-                expandEdge(getEdge(skippedEdge1, from), reverseOrder);
-            } else {
-                expandEdge(getEdge(skippedEdge1, to), !reverseOrder);
-                expandEdge(getEdge(skippedEdge2, from), reverseOrder);
-            }
-        } else {
-            CHEdgeIteratorState sk1 = getEdge(skippedEdge1, from);
-            CHEdgeIteratorState sk2 = getEdge(skippedEdge2, from);
-            if (sk1.getAdjNode() == sk1.getBaseNode() || sk2.getAdjNode() == sk2.getBaseNode()) {
-                // this is a loop where both skipped edges are loops. but this should never happen.
-                throw new IllegalStateException(String.format(Locale.ROOT,
-                        "error: detected edge where both skipped edges are loops. from: %d, to: %d, " +
-                                "skip-edge1: %d, skip-edge2: %d, reverse: %b", from, to, skippedEdge1, skippedEdge2, reverse));
-            }
-
-            if (!reverseOrder) {
-                expandEdge(sk1, !reverse);
-                expandEdge(sk2, reverse);
-            } else {
-                expandEdge(sk2, reverse);
-                expandEdge(sk1, !reverse);
-            }
-        }
-    }
-
-    private CHEdgeIteratorState getEdge(int edgeId, int adjNode) {
-        return (CHEdgeIteratorState) routingGraph.getEdgeIteratorState(edgeId, adjNode);
+        shortcutUnpacker.visitOriginalEdges(edgeId, endNode, reverseOrder);
     }
 }
diff --git a/core/src/main/java/com/graphhopper/routing/weighting/AbstractWeighting.java b/core/src/main/java/com/graphhopper/routing/weighting/AbstractWeighting.java
index 7bcdda0fd..92366a779 100644
--- a/core/src/main/java/com/graphhopper/routing/weighting/AbstractWeighting.java
+++ b/core/src/main/java/com/graphhopper/routing/weighting/AbstractWeighting.java
@@ -49,8 +49,8 @@ public abstract class AbstractWeighting implements Weighting {
         if (reverse && !edgeState.getReverse(accessEnc) || !reverse && !edgeState.get(accessEnc))
             throw new IllegalStateException("Calculating time should not require to read speed from edge in wrong direction. " +
                     "(" + edgeState.getBaseNode() + " - " + edgeState.getAdjNode() + ") "
-                            + edgeState.fetchWayGeometry(3) + " " + edgeState.getDistance() + " "
-                            + "Reverse:" + reverse + ", fwd:" + edgeState.get(accessEnc) + ", bwd:" + edgeState.getReverse(accessEnc));
+                    + edgeState.fetchWayGeometry(3) + ", dist: " + edgeState.getDistance() + " "
+                    + "Reverse:" + reverse + ", fwd:" + edgeState.get(accessEnc) + ", bwd:" + edgeState.getReverse(accessEnc) + ", fwd-speed: " + edgeState.get(avSpeedEnc) + ", bwd-speed: " + edgeState.getReverse(avSpeedEnc));
 
         double speed = reverse ? edgeState.getReverse(avSpeedEnc) : edgeState.get(avSpeedEnc);
         if (Double.isInfinite(speed) || Double.isNaN(speed) || speed < 0)
diff --git a/core/src/main/java/com/graphhopper/storage/ShortcutUnpacker.java b/core/src/main/java/com/graphhopper/storage/ShortcutUnpacker.java
new file mode 100644
index 000000000..cf94ba55b
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/storage/ShortcutUnpacker.java
@@ -0,0 +1,97 @@
+package com.graphhopper.storage;
+
+import com.graphhopper.routing.ch.PrepareContractionHierarchies;
+import com.graphhopper.util.CHEdgeIteratorState;
+import com.graphhopper.util.EdgeIterator;
+import com.graphhopper.util.EdgeIteratorState;
+
+import java.util.Locale;
+
+/**
+ * Recursively unpack shortcuts.
+ * <p>
+ *
+ * @author Peter Karich
+ * @author easbar
+ * @see PrepareContractionHierarchies
+ */
+public class ShortcutUnpacker {
+    private final Graph graph;
+    private final Visitor visitor;
+    private boolean reverseOrder;
+
+    public ShortcutUnpacker(Graph graph, Visitor visitor) {
+        this.graph = graph;
+        this.visitor = visitor;
+    }
+
+    /**
+     * Finds an edge/shortcut with the given id and adjNode and calls the visitor for each original edge that is
+     * packed inside this shortcut (or if an original edge is given simply calls the visitor on it).
+     *
+     * @param reverseOrder if true the original edges will be traversed in reverse order
+     */
+    public void visitOriginalEdges(int edgeId, int adjNode, boolean reverseOrder) {
+        this.reverseOrder = reverseOrder;
+        CHEdgeIteratorState edge = getEdge(edgeId, adjNode);
+        if (edge == null) {
+            throw new IllegalArgumentException("Edge with id: " + edgeId + " does not exist or does not touch node " + adjNode);
+        }
+        expandEdge(edge, false);
+    }
+
+    private void expandEdge(CHEdgeIteratorState edge, boolean reverse) {
+        if (!edge.isShortcut()) {
+            // todo: should properly pass previous edge here. for example this is important for turn cost time evaluation
+            // with edge-based CH, #1585
+            visitor.visit(edge, reverse, EdgeIterator.NO_EDGE);
+            return;
+        }
+        expandSkippedEdges(edge.getSkippedEdge1(), edge.getSkippedEdge2(), edge.getBaseNode(), edge.getAdjNode(), reverse);
+    }
+
+    private void expandSkippedEdges(int skippedEdge1, int skippedEdge2, int from, int to, boolean reverse) {
+        // for edge-based CH we need to take special care for loop shortcuts
+        if (from == to) {
+            CHEdgeIteratorState sk1 = getEdge(skippedEdge1, from);
+            CHEdgeIteratorState sk2 = getEdge(skippedEdge2, from);
+            if (sk1.getAdjNode() == sk1.getBaseNode() || sk2.getAdjNode() == sk2.getBaseNode()) {
+                // this is a loop where both skipped edges are loops. but this should never happen.
+                throw new IllegalStateException(String.format(Locale.ROOT,
+                        "error: detected edge where both skipped edges are loops. from: %d, to: %d, " +
+                                "skip-edge1: %d, skip-edge2: %d, reverse: %b", from, to, skippedEdge1, skippedEdge2, reverse));
+            }
+
+            if (reverseOrder == reverse) {
+                expandEdge(sk1, !reverseOrder);
+                expandEdge(sk2, reverseOrder);
+            } else {
+                expandEdge(sk2, !reverseOrder);
+                expandEdge(sk1, reverseOrder);
+            }
+        } else {
+            // get properties like speed of the edge in the correct direction
+            if (reverseOrder != reverse) {
+                int tmp = from;
+                from = to;
+                to = tmp;
+            }
+            CHEdgeIteratorState sk2to = getEdge(skippedEdge2, to);
+            if (sk2to != null) {
+                expandEdge(getEdge(skippedEdge1, from), !reverseOrder);
+                expandEdge(sk2to, reverseOrder);
+            } else {
+                expandEdge(getEdge(skippedEdge2, from), !reverseOrder);
+                expandEdge(getEdge(skippedEdge1, to), reverseOrder);
+            }
+        }
+    }
+
+    private CHEdgeIteratorState getEdge(int edgeId, int adjNode) {
+        return (CHEdgeIteratorState) graph.getEdgeIteratorState(edgeId, adjNode);
+    }
+
+    public interface Visitor {
+        void visit(EdgeIteratorState edge, boolean reverse, int prevOrNextEdgeId);
+    }
+}


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/CHQueryWithTurnCostsTest.java b/core/src/test/java/com/graphhopper/routing/CHQueryWithTurnCostsTest.java
index 289ae68b1..d0b3452fe 100644
--- a/core/src/test/java/com/graphhopper/routing/CHQueryWithTurnCostsTest.java
+++ b/core/src/test/java/com/graphhopper/routing/CHQueryWithTurnCostsTest.java
@@ -27,10 +27,7 @@ import com.graphhopper.routing.util.LevelEdgeFilter;
 import com.graphhopper.routing.weighting.ShortestWeighting;
 import com.graphhopper.routing.weighting.TurnWeighting;
 import com.graphhopper.routing.weighting.Weighting;
-import com.graphhopper.storage.CHGraph;
-import com.graphhopper.storage.GraphBuilder;
-import com.graphhopper.storage.GraphHopperStorage;
-import com.graphhopper.storage.TurnCostExtension;
+import com.graphhopper.storage.*;
 import com.graphhopper.util.CHEdgeIteratorState;
 import com.graphhopper.util.EdgeIteratorState;
 import com.graphhopper.util.GHUtility;
@@ -111,6 +108,7 @@ public class CHQueryWithTurnCostsTest {
         // contraction yields no shortcuts
         setLevelEqualToNodeIdForAllNodes();
 
+        // note that we are using the shortest weighting but turn cost times are included whatsoever, see #1590
         testPathCalculation(0, 1, 40, IntArrayList.from(0, 2, 4, 6, 5, 3, 1));
         testPathCalculation(1, 0, 28, IntArrayList.from(1, 3, 5, 6, 4, 2, 0));
         testPathCalculation(4, 3, 23, IntArrayList.from(4, 6, 5, 3));
@@ -118,6 +116,79 @@ public class CHQueryWithTurnCostsTest {
         testPathCalculation(4, 4, 0, IntArrayList.from(4));
     }
 
+    @Test
+    public void testFindPathWithTurnCosts_loopShortcutBwdSearch() {
+        // the loop shortcut 4-4 will be encountered during the bwd search
+        //             3
+        //            / \
+        //           1   2
+        //            \ /
+        // 0 - 7 - 8 - 4 - 6 - 5
+        graph.edge(0, 7, 1, false);
+        graph.edge(7, 8, 1, false);
+        graph.edge(8, 4, 1, false);
+        graph.edge(4, 1, 1, false);
+        graph.edge(1, 3, 1, false);
+        graph.edge(3, 2, 1, false);
+        graph.edge(2, 4, 1, false);
+        graph.edge(4, 6, 1, false);
+        graph.edge(6, 5, 1, false);
+        addRestriction(8, 4, 6);
+        addRestriction(8, 4, 2);
+        addRestriction(1, 4, 6);
+
+        graph.freeze();
+
+        // from contracting node 1
+        addShortcut(4, 3, 3, 4, 3, 4, 2);
+        // from contracting node 2
+        addShortcut(3, 4, 5, 6, 5, 6, 2);
+        // from contracting node 3
+        addShortcut(4, 4, 3, 6, 9, 10, 4);
+        // from contracting node 4
+        addShortcut(8, 4, 2, 6, 2, 11, 5);
+        addShortcut(8, 6, 2, 7, 12, 7, 6);
+        setLevelEqualToNodeIdForAllNodes();
+
+        testPathCalculation(0, 5, 9, IntArrayList.from(0, 7, 8, 4, 1, 3, 2, 4, 6, 5));
+    }
+
+    @Test
+    public void testFindPathWithTurnCosts_loopShortcutFwdSearch() {
+        // the loop shortcut 4-4 will be encountered during the fwd search
+        //         3
+        //        / \
+        //       1   2
+        //        \ /
+        // 5 - 6 - 4 - 7 - 8 - 0
+        graph.edge(5, 6, 1, false);
+        graph.edge(6, 4, 1, false);
+        graph.edge(4, 1, 1, false);
+        graph.edge(1, 3, 1, false);
+        graph.edge(3, 2, 1, false);
+        graph.edge(2, 4, 1, false);
+        graph.edge(4, 7, 1, false);
+        graph.edge(7, 8, 1, false);
+        graph.edge(8, 0, 1, false);
+        addRestriction(6, 4, 7);
+        addRestriction(6, 4, 2);
+        addRestriction(1, 4, 7);
+        graph.freeze();
+
+        // from contracting node 1
+        addShortcut(4, 3, 2, 3, 2, 3, 2);
+        // from contracting node 2
+        addShortcut(3, 4, 4, 5, 4, 5, 2);
+        // from contracting node 3
+        addShortcut(4, 4, 2, 5, 9, 10, 4);
+        // from contracting node 4
+        addShortcut(6, 4, 1, 5, 1, 11, 5);
+        addShortcut(6, 7, 1, 6, 12, 6, 6);
+        setLevelEqualToNodeIdForAllNodes();
+
+        testPathCalculation(5, 0, 9, IntArrayList.from(5, 6, 4, 1, 3, 2, 4, 7, 8, 0));
+    }
+
     @Test
     public void testFindPathWithTurnCosts_directed_single_shortcut() {
         //    2     3
diff --git a/core/src/test/java/com/graphhopper/routing/ch/CHTurnCostTest.java b/core/src/test/java/com/graphhopper/routing/ch/CHTurnCostTest.java
index c4cda875c..9b0c1f9d9 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/CHTurnCostTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ch/CHTurnCostTest.java
@@ -607,6 +607,29 @@ public class CHTurnCostTest {
         compareCHWithDijkstra(1000, contractionOrder);
     }
 
+    @Test
+    public void testFindPath_loop() {
+        //             3
+        //            / \
+        //           1   2
+        //            \ /
+        // 0 - 7 - 8 - 4 - 6 - 5
+        graph.edge(0, 7, 1, false);
+        graph.edge(7, 8, 1, false);
+        graph.edge(8, 4, 1, false);
+        graph.edge(4, 1, 1, false);
+        graph.edge(1, 3, 1, false);
+        graph.edge(3, 2, 1, false);
+        graph.edge(2, 4, 1, false);
+        graph.edge(4, 6, 1, false);
+        graph.edge(6, 5, 1, false);
+        addRestriction(8, 4, 6);
+        graph.freeze();
+
+        RoutingAlgorithmFactory factory = prepareCH(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8));
+        compareCHQueryWithDijkstra(factory, 0, 5);
+    }
+
     @Test
     public void testFindPath_loopsMustAlwaysBeAccepted() {
         //     ---
diff --git a/core/src/test/java/com/graphhopper/storage/ShortcutUnpackerTest.java b/core/src/test/java/com/graphhopper/storage/ShortcutUnpackerTest.java
new file mode 100644
index 000000000..cf7700f1f
--- /dev/null
+++ b/core/src/test/java/com/graphhopper/storage/ShortcutUnpackerTest.java
@@ -0,0 +1,189 @@
+package com.graphhopper.storage;
+
+import com.carrotsearch.hppc.DoubleArrayList;
+import com.carrotsearch.hppc.IntArrayList;
+import com.graphhopper.routing.ch.PrepareEncoder;
+import com.graphhopper.routing.profiles.DecimalEncodedValue;
+import com.graphhopper.routing.util.EncodingManager;
+import com.graphhopper.routing.util.FlagEncoder;
+import com.graphhopper.routing.util.MotorcycleFlagEncoder;
+import com.graphhopper.routing.weighting.FastestWeighting;
+import com.graphhopper.routing.weighting.Weighting;
+import com.graphhopper.util.EdgeIteratorState;
+import org.junit.Before;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class ShortcutUnpackerTest {
+
+    private FlagEncoder encoder;
+    private Weighting weighting;
+    private GraphHopperStorage graph;
+    private CHGraph chGraph;
+
+    @Before
+    public void init() {
+        // use motorcycle to be able to set different fwd/bwd speeds
+        encoder = new MotorcycleFlagEncoder(5, 5, 10);
+        EncodingManager encodingManager = EncodingManager.create(encoder);
+        weighting = new FastestWeighting(encoder);
+        graph = new GraphBuilder(encodingManager).setCHGraph(weighting).setEdgeBasedCH(true).create();
+        chGraph = graph.getGraph(CHGraph.class, weighting);
+    }
+
+    @Test
+    public void testUnpacking() {
+        // 0-1-2-3-4-5-6
+        DecimalEncodedValue speedEnc = encoder.getAverageSpeedEnc();
+        double fwdSpeed = 60;
+        double bwdSpeed = 30;
+        graph.edge(0, 1, 1, true).set(speedEnc, fwdSpeed).setReverse(speedEnc, bwdSpeed);
+        graph.edge(1, 2, 1, true).set(speedEnc, fwdSpeed).setReverse(speedEnc, bwdSpeed);
+        graph.edge(2, 3, 1, true).set(speedEnc, fwdSpeed).setReverse(speedEnc, bwdSpeed);
+        graph.edge(3, 4, 1, true).set(speedEnc, fwdSpeed).setReverse(speedEnc, bwdSpeed);
+        graph.edge(4, 5, 1, true).set(speedEnc, fwdSpeed).setReverse(speedEnc, bwdSpeed);
+        graph.edge(5, 6, 1, true).set(speedEnc, fwdSpeed).setReverse(speedEnc, bwdSpeed);
+        graph.freeze();
+        chGraph.shortcut(0, 2, PrepareEncoder.getScFwdDir(), 2, 2, 0, 1);
+        chGraph.shortcut(2, 4, PrepareEncoder.getScFwdDir(), 2, 2, 2, 3);
+        chGraph.shortcut(4, 6, PrepareEncoder.getScFwdDir(), 2, 2, 4, 5);
+        chGraph.shortcut(2, 6, PrepareEncoder.getScFwdDir(), 2, 2, 7, 8);
+        chGraph.shortcut(0, 6, PrepareEncoder.getScFwdDir(), 2, 2, 6, 9);
+
+        {
+            // unpack the shortcut 0-6, traverse original edges in 'forward' order (from node 0 to 6)
+            TestVisitor visitor = new TestVisitor();
+            new ShortcutUnpacker(chGraph, visitor).visitOriginalEdges(10, 6, false);
+            assertEquals(IntArrayList.from(0, 1, 2, 3, 4, 5), visitor.edgeIds);
+            assertEquals(IntArrayList.from(1, 2, 3, 4, 5, 6), visitor.adjNodes);
+            assertEquals(DoubleArrayList.from(0.06, 0.06, 0.06, 0.06, 0.06, 0.06), visitor.weights);
+            assertEquals(DoubleArrayList.from(1, 1, 1, 1, 1, 1), visitor.distances);
+            assertEquals(DoubleArrayList.from(60, 60, 60, 60, 60, 60), visitor.times);
+        }
+
+        {
+            // unpack the shortcut 0-6, traverse original edges in 'backward' order (from node 6 to 0)
+            // note that traversing in backward order does not mean the original edges are read in reverse (e.g. fwd speed still applies)
+            // -> only the order of the original edges is reversed
+            TestVisitor visitor = new TestVisitor();
+            new ShortcutUnpacker(chGraph, visitor).visitOriginalEdges(10, 6, true);
+            assertEquals(IntArrayList.from(5, 4, 3, 2, 1, 0), visitor.edgeIds);
+            assertEquals(IntArrayList.from(6, 5, 4, 3, 2, 1), visitor.adjNodes);
+            assertEquals(DoubleArrayList.from(0.06, 0.06, 0.06, 0.06, 0.06, 0.06), visitor.weights);
+            assertEquals(DoubleArrayList.from(1, 1, 1, 1, 1, 1), visitor.distances);
+            assertEquals(DoubleArrayList.from(60, 60, 60, 60, 60, 60), visitor.times);
+        }
+
+        {
+            // unpack the shortcut 6-0, traverse original edges in 'forward' order (from node 6 to 0)
+            TestVisitor visitor = new TestVisitor();
+            new ShortcutUnpacker(chGraph, visitor).visitOriginalEdges(10, 0, false);
+            assertEquals(IntArrayList.from(5, 4, 3, 2, 1, 0), visitor.edgeIds);
+            assertEquals(IntArrayList.from(5, 4, 3, 2, 1, 0), visitor.adjNodes);
+            assertEquals(DoubleArrayList.from(0.12, 0.12, 0.12, 0.12, 0.12, 0.12), visitor.weights);
+            assertEquals(DoubleArrayList.from(1, 1, 1, 1, 1, 1), visitor.distances);
+            assertEquals(DoubleArrayList.from(120, 120, 120, 120, 120, 120), visitor.times);
+        }
+
+        {
+            // unpack the shortcut 6-0, traverse original edges in 'backward' order (from node 0 to 6)
+            TestVisitor visitor = new TestVisitor();
+            new ShortcutUnpacker(chGraph, visitor).visitOriginalEdges(10, 0, true);
+            assertEquals(IntArrayList.from(0, 1, 2, 3, 4, 5), visitor.edgeIds);
+            assertEquals(IntArrayList.from(0, 1, 2, 3, 4, 5), visitor.adjNodes);
+            assertEquals(DoubleArrayList.from(0.12, 0.12, 0.12, 0.12, 0.12, 0.12), visitor.weights);
+            assertEquals(DoubleArrayList.from(1, 1, 1, 1, 1, 1), visitor.distances);
+            assertEquals(DoubleArrayList.from(120, 120, 120, 120, 120, 120), visitor.times);
+        }
+    }
+
+    @Test
+    public void loopShortcut() {
+        //     3
+        //    / \
+        //   2   4
+        //    \ /
+        // 0 - 1 - 5
+        DecimalEncodedValue speedEnc = encoder.getAverageSpeedEnc();
+        double fwdSpeed = 60;
+        double bwdSpeed = 30;
+        graph.edge(0, 1, 1, true).set(speedEnc, fwdSpeed).setReverse(speedEnc, bwdSpeed);
+        graph.edge(1, 2, 1, true).set(speedEnc, fwdSpeed).setReverse(speedEnc, bwdSpeed);
+        graph.edge(2, 3, 1, true).set(speedEnc, fwdSpeed).setReverse(speedEnc, bwdSpeed);
+        graph.edge(3, 4, 1, true).set(speedEnc, fwdSpeed).setReverse(speedEnc, bwdSpeed);
+        graph.edge(4, 1, 1, true).set(speedEnc, fwdSpeed).setReverse(speedEnc, bwdSpeed);
+        graph.edge(1, 5, 1, true).set(speedEnc, fwdSpeed).setReverse(speedEnc, bwdSpeed);
+        graph.freeze();
+        shortcut(1, 3, 2, 2, 1, 2, 1, 2);
+        shortcut(3, 1, 2, 2, 3, 4, 3, 4);
+        shortcut(1, 1, 4, 4, 6, 7, 1, 4);
+        shortcut(0, 1, 5, 5, 0, 8, 0, 4);
+        shortcut(0, 5, 6, 6, 9, 5, 0, 5);
+
+        {
+            // unpack the shortcut 0->5, traverse original edges in 'forward' order (from node 0 to 5)
+            TestVisitor visitor = new TestVisitor();
+            new ShortcutUnpacker(chGraph, visitor).visitOriginalEdges(10, 5, false);
+            assertEquals(IntArrayList.from(0, 1, 2, 3, 4, 5), visitor.edgeIds);
+            assertEquals(IntArrayList.from(1, 2, 3, 4, 1, 5), visitor.adjNodes);
+            assertEquals(DoubleArrayList.from(0.06, 0.06, 0.06, 0.06, 0.06, 0.06), visitor.weights);
+            assertEquals(DoubleArrayList.from(1, 1, 1, 1, 1, 1), visitor.distances);
+            assertEquals(DoubleArrayList.from(60, 60, 60, 60, 60, 60), visitor.times);
+        }
+
+        {
+            // unpack the shortcut 0->5, traverse original edges in 'backward' order (from node 5 to 0)
+            TestVisitor visitor = new TestVisitor();
+            new ShortcutUnpacker(chGraph, visitor).visitOriginalEdges(10, 5, true);
+            assertEquals(IntArrayList.from(5, 4, 3, 2, 1, 0), visitor.edgeIds);
+            assertEquals(IntArrayList.from(5, 1, 4, 3, 2, 1), visitor.adjNodes);
+            assertEquals(DoubleArrayList.from(0.06, 0.06, 0.06, 0.06, 0.06, 0.06), visitor.weights);
+            assertEquals(DoubleArrayList.from(1, 1, 1, 1, 1, 1), visitor.distances);
+            assertEquals(DoubleArrayList.from(60, 60, 60, 60, 60, 60), visitor.times);
+        }
+
+        {
+            // unpack the shortcut 5<-0, traverse original edges in 'forward' order (from node 5 to 0)
+            TestVisitor visitor = new TestVisitor();
+            new ShortcutUnpacker(chGraph, visitor).visitOriginalEdges(10, 0, false);
+            assertEquals(IntArrayList.from(5, 4, 3, 2, 1, 0), visitor.edgeIds);
+            assertEquals(IntArrayList.from(1, 4, 3, 2, 1, 0), visitor.adjNodes);
+            assertEquals(DoubleArrayList.from(0.12, 0.12, 0.12, 0.12, 0.12, 0.12), visitor.weights);
+            assertEquals(DoubleArrayList.from(1, 1, 1, 1, 1, 1), visitor.distances);
+            assertEquals(DoubleArrayList.from(120, 120, 120, 120, 120, 120), visitor.times);
+        }
+
+        {
+            // unpack the shortcut 5<-0, traverse original edges in 'backward' order (from node 0 to 5)
+            TestVisitor visitor = new TestVisitor();
+            new ShortcutUnpacker(chGraph, visitor).visitOriginalEdges(10, 0, true);
+            assertEquals(IntArrayList.from(0, 1, 2, 3, 4, 5), visitor.edgeIds);
+            assertEquals(IntArrayList.from(0, 1, 2, 3, 4, 1), visitor.adjNodes);
+            assertEquals(DoubleArrayList.from(0.12, 0.12, 0.12, 0.12, 0.12, 0.12), visitor.weights);
+            assertEquals(DoubleArrayList.from(1, 1, 1, 1, 1, 1), visitor.distances);
+            assertEquals(DoubleArrayList.from(120, 120, 120, 120, 120, 120), visitor.times);
+        }
+    }
+
+    private void shortcut(int baseNode, int adjNode, double weight, double distance, int skip1, int skip2, int origFirst, int origLast) {
+        chGraph.shortcutEdgeBased(baseNode, adjNode, PrepareEncoder.getScFwdDir(), weight, distance, skip1, skip2, origFirst, origLast);
+    }
+
+    private class TestVisitor implements ShortcutUnpacker.Visitor {
+        private final IntArrayList edgeIds = new IntArrayList();
+        private final IntArrayList adjNodes = new IntArrayList();
+        private final DoubleArrayList weights = new DoubleArrayList();
+        private final DoubleArrayList distances = new DoubleArrayList();
+        private final DoubleArrayList times = new DoubleArrayList();
+
+        @Override
+        public void visit(EdgeIteratorState edge, boolean reverse, int prevOrNextEdgeId) {
+            edgeIds.add(edge.getEdge());
+            adjNodes.add(reverse ? edge.getBaseNode() : edge.getAdjNode());
+            weights.add(weighting.calcWeight(edge, reverse, prevOrNextEdgeId));
+            distances.add(edge.getDistance());
+            times.add(weighting.calcMillis(edge, reverse, prevOrNextEdgeId));
+        }
+    }
+}
\ No newline at end of file