tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dkupp...@apache.org
Subject [2/2] tinkerpop git commit: TINKERPOP-1990 Implemented `ShortestPathVertexProgram` and `ShortestPathVertexProgramStep`.
Date Thu, 09 Aug 2018 20:03:33 GMT
TINKERPOP-1990 Implemented `ShortestPathVertexProgram` and `ShortestPathVertexProgramStep`.


Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/b0d8e78c
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/b0d8e78c
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/b0d8e78c

Branch: refs/heads/TINKERPOP-1990
Commit: b0d8e78cb03a90271503c820cfeadd1ec6eef3ec
Parents: f88ace1
Author: Daniel Kuppitz <daniel_kuppitz@hotmail.com>
Authored: Wed May 23 08:46:34 2018 -0400
Committer: Daniel Kuppitz <daniel_kuppitz@hotmail.com>
Committed: Thu Aug 9 13:03:16 2018 -0700

----------------------------------------------------------------------
 CHANGELOG.asciidoc                              |   1 +
 docs/src/recipes/shortest-path.asciidoc         |  62 ++
 docs/src/reference/the-graphcomputer.asciidoc   |  51 ++
 docs/src/reference/the-traversal.asciidoc       |  61 ++
 .../tinkerpop/gremlin/jsr223/CoreImports.java   |   4 +
 .../search/path/ShortestPathVertexProgram.java  | 611 +++++++++++++++++++
 .../traversal/step/map/ShortestPath.java        | 108 ++++
 .../step/map/ShortestPathVertexProgramStep.java | 185 ++++++
 .../gremlin/process/remote/RemoteGraph.java     |   4 +
 .../gremlin/process/traversal/Traversal.java    |  16 +-
 .../traversal/dsl/graph/GraphTraversal.java     |  20 +
 .../traversal/lambda/ColumnTraversal.java       |   8 +
 .../traversal/lambda/ConstantTraversal.java     |   9 +-
 .../traversal/lambda/ElementValueTraversal.java |  10 +-
 .../traversal/lambda/IdentityTraversal.java     |   7 +-
 .../process/traversal/lambda/LoopTraversal.java |   6 +
 .../traversal/lambda/TokenTraversal.java        |   8 +
 .../process/traversal/lambda/TrueTraversal.java |   5 +
 .../structure/io/graphson/GraphSONModule.java   |   2 +-
 .../gremlin/structure/io/gryo/GryoVersion.java  |  12 +-
 .../structure/io/gryo/UtilSerializers.java      |  15 +
 .../gremlin/structure/util/Attachable.java      |   3 +-
 .../traversal/dsl/graph/GraphTraversalTest.java |   2 +-
 .../Process/Traversal/GraphTraversal.cs         |   9 +
 .../lib/process/graph-traversal.js              |  10 +
 .../test/cucumber/feature-steps.js              |  17 +-
 .../gremlin_python/process/graph_traversal.py   |   4 +
 gremlin-test/features/map/Path.feature          |   2 +-
 gremlin-test/features/map/ShortestPath.feature  | 353 +++++++++++
 .../tinkerpop/gremlin/AbstractGremlinTest.java  |   6 +-
 .../process/AbstractGremlinProcessTest.java     |   7 +-
 .../gremlin/process/ProcessComputerSuite.java   |   5 +
 .../search/path/ShortestPathTestHelper.java     | 100 +++
 .../path/ShortestPathVertexProgramTest.java     | 297 +++++++++
 .../traversal/step/map/ShortestPathTest.java    | 353 +++++++++++
 pom.xml                                         |   3 +
 36 files changed, 2351 insertions(+), 25 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 303d963..f82727a 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -25,6 +25,7 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima
 
 This release also includes changes from <<release-3-3-3, 3.3.3>>.
 
+* Implemented `ShortestPathVertexProgram` and the `shortestPath()` step.
 * `AbstractGraphProvider` uses `g.io()` for loading test data.
 * Added the `io()` start step and `read()` and `write()` termination steps to the Gremlin language.
 * Added `GraphFeatures.supportsIoRead()` and `GraphFeatures.supportsIoWrite()`.

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/docs/src/recipes/shortest-path.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/recipes/shortest-path.asciidoc b/docs/src/recipes/shortest-path.asciidoc
index 2e33055..04c542d 100644
--- a/docs/src/recipes/shortest-path.asciidoc
+++ b/docs/src/recipes/shortest-path.asciidoc
@@ -49,6 +49,16 @@ length three), but this example is not considering that.
 <2> It might be interesting to know the path lengths for all paths between vertex "1" and "5".
 <3> Alternatively, one might wish to do a path length distribution over all the paths.
 
+The following code block demonstrates how the shortest path from `v[1]` to `v[5]` can be queried in OLAP, using the `shortestPath()` step.
+
+[gremlin-groovy,existing]
+----
+g = g.withComputer()
+g.V(1).shortestPath().
+  with(ShortestPath.edges, Direction.OUT).
+  with(ShortestPath.target, hasId(5))
+----
+
 The previous example defines the length of the path by the number of vertices in the path, but the "path" might also
 be measured by data within the graph itself. The following example use the same graph structure as the previous example,
 but includes a "weight" on the edges, that will be used to help determine the "cost" of a particular path:
@@ -95,6 +105,17 @@ calculated cost. With some slight modifications given the use of `select` it bec
 the output. Note that the path with the lowest "cost" actually has a longer path length as determined by the graph
 structure.
 
+The next code block demonstrates how the `shortestPath()` step can be used in OLAP to determine the shortest weighted path.
+
+[gremlin-groovy,existing]
+----
+g = g.withComputer()
+g.V(1).shortestPath().
+  with(ShortestPath.edges, Direction.OUT).
+  with(ShortestPath.distance, 'weight').
+  with(ShortestPath.target, hasId(5))
+----
+
 The following query illustrates how `select(<traversal>)` can be used to find all shortest weighted undirected paths
 in the modern toy graph.
 
@@ -136,3 +157,44 @@ g.withSack(0.0).V().as("from").       <1>
 <7> Order the output by the start vertex id and then the end vertex id (for better readability).
 <8> Deduplicate vertex pairs (the shortest path from `v[1]` to `v[6]` is the same as the path from `v[6]` to `v[1]`).
 
+Again, this can be translated into an OLAP query using the `shortestPath()` step.
+
+[gremlin-groovy,existing]
+----
+result = g.withComputer().V().
+  shortestPath().
+    with(ShortestPath.distance, 'weight').
+    with(ShortestPath.includeEdges, true).
+  filter(count(local).is(gt(1))).
+  group().
+    by(project('from','to').
+         by(limit(local, 1)).
+         by(tail(local, 1))).
+  unfold().
+  order().
+    by(select(keys).select('from').id()).
+    by(select(keys).select('to').id()).toList()
+----
+
+The obvious difference in the result is the absence of property values in the OLAP result. Since OLAP traversers are not
+allowed to leave the local star graph, it's not possible to have the exact same result in an OLAP query. However, the determined
+shortest paths can be passed back into the OLTP `GraphTraversalSource`, which can then be used to query the values.
+
+[gremlin-groovy,existing]
+----
+g.withSideEffect('v', []).                            <1>
+  inject(result.toArray()).as('kv').select(values).
+  unfold().
+  map(unfold().as('v_or_e').
+      coalesce(V().where(eq('v_or_e')).store('v'),
+               select('v').tail(local, 1).bothE().where(eq('v_or_e'))).
+      values('name','weight').
+      fold()).
+  group().
+    by(select('kv').select(keys)).unfold().
+  order().
+    by(select(keys).select('from').id()).
+    by(select(keys).select('to').id()).toList()
+----
+
+<1> The side-effect `v` is used to keep track of the last processed vertex, hence it needs to be an order-preserving list. Without this explicit definition `v` would become a `BulkSet` which doesn't preserve the insert order.

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/docs/src/reference/the-graphcomputer.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/reference/the-graphcomputer.asciidoc b/docs/src/reference/the-graphcomputer.asciidoc
index 1d7586c..3d7ec00 100644
--- a/docs/src/reference/the-graphcomputer.asciidoc
+++ b/docs/src/reference/the-graphcomputer.asciidoc
@@ -403,6 +403,57 @@ g.V().peerPressure().by('cluster').valueMap()
 g.V().peerPressure().by(outE('knows')).by('cluster').valueMap()
 ----
 
+[[shortestpathvertexprogram]]
+=== ShortestPathVertexProgram
+
+The `ShortestPathVertexProram` provides an easy way to find shortest non-cyclic paths in the graph. It provides several options to configure
+the output format, the start- and end-vertices, the direction, a custom distance function, as well as a distance limitation. By default it just
+finds all undirected, shortest paths in the graph.
+
+[gremlin-groovy,modern]
+----
+spvp = ShortestPathVertexProgram.build().create() <1>
+result = graph.compute().program(spvp).submit().get() <2>
+result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS) <3>
+----
+
+<1> Create a `ShortestPathVertexProgram` with its default configuration.
+<2> Execute the `ShortestPathVertexProgram`.
+<3> Get all shortest paths from the results memory.
+
+[gremlin-groovy,modern]
+----
+spvp = ShortestPathVertexProgram.build().includeEdges(true).create() <1>
+result = graph.compute().program(spvp).submit().get() <2>
+result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS) <3>
+----
+
+<1> Create a `ShortestPathVertexProgram` as before, but configure it to include edges in the result.
+<2> Execute the `ShortestPathVertexProgram`.
+<3> Get all shortest paths from the results memory.
+
+The `ShortestPathVertexProgram.Builder` provides the following configuration methods:
+
+[width="100%",cols="3,15,5",options="header"]
+|=========================================================
+| Method | Description | Default
+| `source(Traversal)` | Sets a filter traversal for the start vertices (e.g. `__.has('name','marko')`). | all vertices (`__.identity()`)
+| `target(Traversal)` | Sets a filter traversal for the end vertices. | all vertices
+| `edgeDirection(Direction)` | Sets the direction to traverse during the shortest path discovery. | `Direction.BOTH`
+| `edgeTraversal(Traversal)` | Sets a traversal that emits the edges to traverse from the current vertex. | `__.bothE()`
+| `distanceProperty(String)` | Sets the edge property to use for the distance calculations. | none
+| `distanceTraversal(Traversal)` | Sets the traversal that calculates the distance for the current edge. | `__.constant(1)`
+| `maxDistance(Traversal)` | Limits the shortest path distance. | none
+| `includeEdges(Boolean)` | Whether to include edges in shortest paths or not. | `false`
+|=========================================================
+
+IMPORTANT: If a maximum distance is provided, the discovery process will only stop to follow a path at this distance if there was no
+custom distance property or traversal provided. Custom distances can be negative, hence exceeding the maximum distance doesn't mean that there
+can't be any more valid paths. However, paths will be filtered at the end, when no more non-cyclic paths can be found. The bottom line is that
+custom distance properties or traversals can lead to much longer runtimes and a much higher memory consumption.
+
+Note that `GraphTraversal` provides a <<shortestpath-step,`shortestPath()`>>-step.
+
 [[bulkdumpervertexprogram]]
 [[clonevertexprogram]]
 === CloneVertexProgram

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/docs/src/reference/the-traversal.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/reference/the-traversal.asciidoc b/docs/src/reference/the-traversal.asciidoc
index 7d385c8..edc0645 100644
--- a/docs/src/reference/the-traversal.asciidoc
+++ b/docs/src/reference/the-traversal.asciidoc
@@ -2663,6 +2663,67 @@ link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/grem
 link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/structure/Column.html++[`Column`],
 link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/process/traversal/Pop.html++[`Pop`]
 
+[[shortestpath-step]]
+=== ShortestPath step
+
+The `shortestPath()`-step provides an easy way to find shortest non-cyclic paths in a graph. It is configurable
+using the `with()`-modulator with the options given below.
+
+[width="100%",cols="3,3,15,5",options="header"]
+|=========================================================
+| Key | Type | Description | Default
+| `target` | `Traversal` | Sets a filter traversal for the end vertices (e.g. `__.has('name','marko')`). | all vertices (`__.identity()`)
+| `edges` | `Traversal` or `Direction` | Sets a `Traversal` that emits the edges to traverse from the current vertex or the `Direction` to traverse during the shortest path discovery. | `Direction.BOTH`
+| `distance` | `Traversal` or `String` | Sets the `Traversal` that calculates the distance for the current edge or the name of an edge property to use for the distance calculations. | `__.constant(1)`
+| `maxDistance` | `Number` | Sets the distance limit for all shortest paths. | none
+| `includeEdges` | `Boolean` | Whether to include edges in the result or not. | `false`
+|=========================================================
+
+[gremlin-groovy,modern]
+----
+g = g.withComputer()
+g.V().shortestPath() <1>
+g.V().has('person','name','marko').shortestPath() <2>
+g.V().shortestPath().with(ShortestPath.target, __.has('name','peter')) <3>
+g.V().shortestPath().
+        with(ShortestPath.edges, Direction.IN).
+        with(ShortestPath.target, __.has('name','josh')) <4>
+g.V().has('person','name','marko').
+      shortestPath().
+        with(ShortestPath.target, __.has('name','josh')) <5>
+g.V().has('person','name','marko').
+      shortestPath().
+        with(ShortestPath.target, __.has('name','josh')).
+        with(ShortestPath.distance, 'weight') <6>
+g.V().has('person','name','marko').
+      shortestPath().
+        with(ShortestPath.target, __.has('name','josh')).
+        with(ShortestPath.includeEdges, true) <7>
+----
+
+<1> Find all shortest paths.
+<2> Find all shortest paths from `marko`.
+<3> Find all shortest paths to `peter`.
+<4> Find all in-directed paths to `josh`.
+<5> Find all shortest paths from `marko` to `josh`.
+<6> Find all shortest paths from `marko` to `josh` using a custom distance property.
+<7> Find all shortest paths from `marko` to `josh` and include edges in the result.
+
+[gremlin-groovy,modern]
+----
+g.inject(g.withComputer().V().shortestPath().
+           with(ShortestPath.distance, 'weight').
+           with(ShortestPath.includeEdges, true).
+           with(ShortestPath.maxDistance, 1).toList().toArray()).
+  map(unfold().values('name','weight').fold()) <1>
+----
+
+<1> Find all shortest paths using a custom distance property and limit the distance to 1. Inject the result into a OLTP `GraphTraversal` in order to be able to select properties from all elements in all paths.
+
+*Additional References*
+
+link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.html#shortestPath--++[`shortestPath()`]
+
 [[simplepath-step]]
 === SimplePath Step
 

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java
index 72ad47a..9830cdd 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java
@@ -47,10 +47,12 @@ import org.apache.tinkerpop.gremlin.process.computer.clustering.peerpressure.Clu
 import org.apache.tinkerpop.gremlin.process.computer.clustering.peerpressure.PeerPressureVertexProgram;
 import org.apache.tinkerpop.gremlin.process.computer.ranking.pagerank.PageRankMapReduce;
 import org.apache.tinkerpop.gremlin.process.computer.ranking.pagerank.PageRankVertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.search.path.ShortestPathVertexProgram;
 import org.apache.tinkerpop.gremlin.process.computer.traversal.MemoryTraversalSideEffects;
 import org.apache.tinkerpop.gremlin.process.computer.traversal.TraversalVertexProgram;
 import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.PageRank;
 import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.PeerPressure;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ShortestPath;
 import org.apache.tinkerpop.gremlin.process.computer.traversal.strategy.decoration.VertexProgramStrategy;
 import org.apache.tinkerpop.gremlin.process.computer.traversal.strategy.optimization.GraphFilterStrategy;
 import org.apache.tinkerpop.gremlin.process.remote.RemoteConnection;
@@ -268,6 +270,8 @@ public final class CoreImports {
         CLASS_IMPORTS.add(PageRank.class);
         CLASS_IMPORTS.add(PageRankMapReduce.class);
         CLASS_IMPORTS.add(PageRankVertexProgram.class);
+        CLASS_IMPORTS.add(ShortestPath.class);
+        CLASS_IMPORTS.add(ShortestPathVertexProgram.class);
         CLASS_IMPORTS.add(GraphFilterStrategy.class);
         CLASS_IMPORTS.add(TraversalVertexProgram.class);
         CLASS_IMPORTS.add(VertexProgramStrategy.class);

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java
new file mode 100644
index 0000000..1949c53
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java
@@ -0,0 +1,611 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF 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 org.apache.tinkerpop.gremlin.process.computer.search.path;
+
+import org.apache.commons.configuration.Configuration;
+import org.apache.tinkerpop.gremlin.process.computer.GraphComputer;
+import org.apache.tinkerpop.gremlin.process.computer.Memory;
+import org.apache.tinkerpop.gremlin.process.computer.MemoryComputeKey;
+import org.apache.tinkerpop.gremlin.process.computer.MessageScope;
+import org.apache.tinkerpop.gremlin.process.computer.Messenger;
+import org.apache.tinkerpop.gremlin.process.computer.VertexComputeKey;
+import org.apache.tinkerpop.gremlin.process.computer.VertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.TraversalVertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ProgramVertexProgramStep;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.VertexProgramStep;
+import org.apache.tinkerpop.gremlin.process.computer.util.AbstractVertexProgramBuilder;
+import org.apache.tinkerpop.gremlin.process.traversal.Operator;
+import org.apache.tinkerpop.gremlin.process.traversal.Path;
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.ImmutablePath;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.IndexedTraverserSet;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
+import org.apache.tinkerpop.gremlin.process.traversal.util.PureTraversal;
+import org.apache.tinkerpop.gremlin.structure.Direction;
+import org.apache.tinkerpop.gremlin.structure.Edge;
+import org.apache.tinkerpop.gremlin.structure.Element;
+import org.apache.tinkerpop.gremlin.structure.Graph;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.apache.tinkerpop.gremlin.structure.VertexProperty;
+import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
+import org.apache.tinkerpop.gremlin.structure.util.reference.ReferenceFactory;
+import org.apache.tinkerpop.gremlin.util.NumberHelper;
+import org.javatuples.Pair;
+import org.javatuples.Triplet;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Function;
+
+/**
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+public class ShortestPathVertexProgram implements VertexProgram<Triplet<Path, Edge, Number>> {
+
+    @SuppressWarnings("WeakerAccess")
+    public static final String SHORTEST_PATHS = "gremlin.shortestPathVertexProgram.shortestPaths";
+
+    private static final String SOURCE_VERTEX_FILTER = "gremlin.shortestPathVertexProgram.sourceVertexFilter";
+    private static final String TARGET_VERTEX_FILTER = "gremlin.shortestPathVertexProgram.targetVertexFilter";
+    private static final String EDGE_TRAVERSAL = "gremlin.shortestPathVertexProgram.edgeTraversal";
+    private static final String DISTANCE_TRAVERSAL = "gremlin.shortestPathVertexProgram.distanceTraversal";
+    private static final String MAX_DISTANCE = "gremlin.shortestPathVertexProgram.maxDistance";
+    private static final String INCLUDE_EDGES = "gremlin.shortestPathVertexProgram.includeEdges";
+
+    private static final String STATE = "gremlin.shortestPathVertexProgram.state";
+    private static final String PATHS = "gremlin.shortestPathVertexProgram.paths";
+    private static final String VOTE_TO_HALT = "gremlin.shortestPathVertexProgram.voteToHalt";
+
+    private static final int SEARCH = 0;
+    private static final int COLLECT_PATHS = 1;
+    private static final int UPDATE_HALTED_TRAVERSERS = 2;
+
+    public static final PureTraversal<Vertex, ?> DEFAULT_VERTEX_FILTER_TRAVERSAL = new PureTraversal<>(
+            __.<Vertex> identity().asAdmin()); // todo: new IdentityTraversal<>()
+    public static final PureTraversal<Vertex, Edge> DEFAULT_EDGE_TRAVERSAL = new PureTraversal<>(__.bothE().asAdmin());
+    public static final PureTraversal<Edge, Number> DEFAULT_DISTANCE_TRAVERSAL = new PureTraversal<>(
+            __.<Edge> start().<Number> constant(1).asAdmin()); // todo: new ConstantTraversal<>(1)
+
+    private TraverserSet<Vertex> haltedTraversers;
+    private IndexedTraverserSet<Vertex, Vertex> haltedTraversersIndex;
+    private PureTraversal<?, ?> traversal;
+    private PureTraversal<Vertex, ?> sourceVertexFilterTraversal = DEFAULT_VERTEX_FILTER_TRAVERSAL.clone();
+    private PureTraversal<Vertex, ?> targetVertexFilterTraversal = DEFAULT_VERTEX_FILTER_TRAVERSAL.clone();
+    private PureTraversal<Vertex, Edge> edgeTraversal = DEFAULT_EDGE_TRAVERSAL.clone();
+    private PureTraversal<Edge, Number> distanceTraversal = DEFAULT_DISTANCE_TRAVERSAL.clone();
+    private Step<Vertex, Path> programStep;
+    private Number maxDistance;
+    private boolean distanceEqualsNumberOfHops;
+    private boolean includeEdges;
+    private boolean standalone;
+
+    private static final Set<VertexComputeKey> VERTEX_COMPUTE_KEYS = new HashSet<>(Arrays.asList(
+            VertexComputeKey.of(PATHS, true),
+            VertexComputeKey.of(TraversalVertexProgram.HALTED_TRAVERSERS, false)));
+
+    private final Set<MemoryComputeKey> memoryComputeKeys = new HashSet<>(Arrays.asList(
+            MemoryComputeKey.of(VOTE_TO_HALT, Operator.and, false, true),
+            MemoryComputeKey.of(STATE, Operator.assign, true, true)));
+
+    private ShortestPathVertexProgram() {
+
+    }
+
+    @Override
+    public void loadState(final Graph graph, final Configuration configuration) {
+
+        if (configuration.containsKey(SOURCE_VERTEX_FILTER))
+            this.sourceVertexFilterTraversal = PureTraversal.loadState(configuration, SOURCE_VERTEX_FILTER, graph);
+
+        if (configuration.containsKey(TARGET_VERTEX_FILTER))
+            this.targetVertexFilterTraversal = PureTraversal.loadState(configuration, TARGET_VERTEX_FILTER, graph);
+
+        if (configuration.containsKey(EDGE_TRAVERSAL))
+            this.edgeTraversal = PureTraversal.loadState(configuration, EDGE_TRAVERSAL, graph);
+
+        if (configuration.containsKey(DISTANCE_TRAVERSAL))
+            this.distanceTraversal = PureTraversal.loadState(configuration, DISTANCE_TRAVERSAL, graph);
+
+        if (configuration.containsKey(MAX_DISTANCE))
+            this.maxDistance = (Number) configuration.getProperty(MAX_DISTANCE);
+
+        this.distanceEqualsNumberOfHops = this.distanceTraversal.equals(DEFAULT_DISTANCE_TRAVERSAL);
+        this.includeEdges = configuration.getBoolean(INCLUDE_EDGES, false);
+        this.standalone = !configuration.containsKey(VertexProgramStep.ROOT_TRAVERSAL);
+
+        if (!this.standalone) {
+            this.traversal = PureTraversal.loadState(configuration, VertexProgramStep.ROOT_TRAVERSAL, graph);
+            final String programStepId = configuration.getString(ProgramVertexProgramStep.STEP_ID);
+            for (final Step step : this.traversal.get().getSteps()) {
+                if (step.getId().equals(programStepId)) {
+                    //noinspection unchecked
+                    this.programStep = step;
+                    break;
+                }
+            }
+        }
+
+        // restore halted traversers from the configuration and build an index for direct access
+        this.haltedTraversers = TraversalVertexProgram.loadHaltedTraversers(configuration);
+        this.haltedTraversersIndex = new IndexedTraverserSet<>(v -> v);
+        for (final Traverser.Admin<Vertex> traverser : this.haltedTraversers) {
+            this.haltedTraversersIndex.add(traverser.split());
+        }
+        this.memoryComputeKeys.add(MemoryComputeKey.of(SHORTEST_PATHS, Operator.addAll, true, !standalone));
+    }
+
+    @Override
+    public void storeState(final Configuration configuration) {
+        VertexProgram.super.storeState(configuration);
+        this.sourceVertexFilterTraversal.storeState(configuration, SOURCE_VERTEX_FILTER);
+        this.targetVertexFilterTraversal.storeState(configuration, TARGET_VERTEX_FILTER);
+        this.edgeTraversal.storeState(configuration, EDGE_TRAVERSAL);
+        this.distanceTraversal.storeState(configuration, DISTANCE_TRAVERSAL);
+        configuration.setProperty(INCLUDE_EDGES, this.includeEdges);
+        if (this.maxDistance != null)
+            configuration.setProperty(MAX_DISTANCE, maxDistance);
+        if (this.traversal != null) {
+            this.traversal.storeState(configuration, ProgramVertexProgramStep.ROOT_TRAVERSAL);
+            configuration.setProperty(ProgramVertexProgramStep.STEP_ID, this.programStep.getId());
+        }
+        TraversalVertexProgram.storeHaltedTraversers(configuration, this.haltedTraversers);
+    }
+
+    @Override
+    public Set<VertexComputeKey> getVertexComputeKeys() {
+        return VERTEX_COMPUTE_KEYS;
+    }
+
+    @Override
+    public Set<MemoryComputeKey> getMemoryComputeKeys() {
+        return memoryComputeKeys;
+    }
+
+    @Override
+    public Set<MessageScope> getMessageScopes(final Memory memory) {
+        return Collections.emptySet();
+    }
+
+    @Override
+    public VertexProgram<Triplet<Path, Edge, Number>> clone() {
+        try {
+            final ShortestPathVertexProgram clone = (ShortestPathVertexProgram) super.clone();
+            if (null != this.edgeTraversal)
+                clone.edgeTraversal = this.edgeTraversal.clone();
+            if (null != this.sourceVertexFilterTraversal)
+                clone.sourceVertexFilterTraversal = this.sourceVertexFilterTraversal.clone();
+            if (null != this.targetVertexFilterTraversal)
+                clone.targetVertexFilterTraversal = this.targetVertexFilterTraversal.clone();
+            if (null != this.distanceTraversal)
+                clone.distanceTraversal = this.distanceTraversal.clone();
+            if (null != this.traversal) {
+                clone.traversal = this.traversal.clone();
+                for (final Step step : clone.traversal.get().getSteps()) {
+                    if (step.getId().equals(this.programStep.getId())) {
+                        //noinspection unchecked
+                        clone.programStep = step;
+                        break;
+                    }
+                }
+            }
+            return clone;
+        } catch (final CloneNotSupportedException e) {
+            throw new IllegalStateException(e.getMessage(), e);
+        }
+    }
+
+    @Override
+    public GraphComputer.ResultGraph getPreferredResultGraph() {
+        return GraphComputer.ResultGraph.ORIGINAL;
+    }
+
+    @Override
+    public GraphComputer.Persist getPreferredPersist() {
+        return GraphComputer.Persist.NOTHING;
+    }
+
+    @Override
+    public void setup(final Memory memory) {
+        memory.set(VOTE_TO_HALT, true);
+        memory.set(STATE, SEARCH);
+    }
+
+    @Override
+    public void execute(final Vertex vertex, final Messenger<Triplet<Path, Edge, Number>> messenger, final Memory memory) {
+
+        switch (memory.<Integer>get(STATE)) {
+
+            case COLLECT_PATHS:
+                collectShortestPaths(vertex, memory);
+                return;
+
+            case UPDATE_HALTED_TRAVERSERS:
+                updateHaltedTraversers(vertex, memory);
+                return;
+        }
+
+        boolean voteToHalt = true;
+
+        if (memory.isInitialIteration()) {
+
+            // Use the first iteration to copy halted traversers from the halted traverser index to the respective
+            // vertices. This way the rest of the code can be simplified and always expect the HALTED_TRAVERSERS
+            // property to be available (if halted traversers exist for this vertex).
+            copyHaltedTraversersFromMemory(vertex);
+
+            // ignore vertices that don't pass the start-vertex filter
+            if (!isStartVertex(vertex)) return;
+
+            // start to track paths for all valid start-vertices
+            final Map<Vertex, Pair<Number, Set<Path>>> paths = new HashMap<>();
+            final Path path;
+            final Set<Path> pathSet = new HashSet<>();
+
+            pathSet.add(path = makePath(vertex));
+            paths.put(vertex, Pair.with(0, pathSet));
+
+            vertex.property(VertexProperty.Cardinality.single, PATHS, paths);
+
+            // send messages to valid adjacent vertices
+            processEdges(vertex, path, 0, messenger);
+
+            voteToHalt = false;
+
+        } else {
+
+            // load existing paths to this vertex and extend them based on messages received from adjacent vertices
+            final Map<Vertex, Pair<Number, Set<Path>>> paths =
+                    vertex.<Map<Vertex, Pair<Number, Set<Path>>>>property(PATHS).orElseGet(HashMap::new);
+            final Iterator<Triplet<Path, Edge, Number>> iterator = messenger.receiveMessages();
+
+            while (iterator.hasNext()) {
+
+                final Triplet<Path, Edge, Number> triplet = iterator.next();
+                final Path sourcePath = triplet.getValue0();
+                final Number distance = triplet.getValue2();
+                final Vertex sourceVertex = sourcePath.get(0);
+
+                Path newPath = null;
+
+                // already know a path coming from this source vertex?
+                if (paths.containsKey(sourceVertex)) {
+
+                    final Number currentShortestDistance = paths.get(sourceVertex).getValue0();
+                    final int cmp = NumberHelper.compare(distance, currentShortestDistance);
+
+                    if (cmp <= 0) {
+                        newPath = extendPath(sourcePath, triplet.getValue1(), vertex);
+                        if (cmp < 0) {
+                            // if the path length is smaller than the current shortest path's length, replace the
+                            // current set of shortest paths
+                            final Set<Path> pathSet = new HashSet<>();
+                            pathSet.add(newPath);
+                            paths.put(sourceVertex, Pair.with(distance, pathSet));
+                        } else {
+                            // if the path length is equal to the current shortest path's length, add the new path
+                            // to the set of shortest paths
+                            paths.get(sourceVertex).getValue1().add(newPath);
+                        }
+                    }
+                } else if (!exceedsMaxDistance(distance)) {
+                    // store the new path as the shortest path from the source vertex to the current vertex
+                    final Set<Path> pathSet = new HashSet<>();
+                    pathSet.add(newPath = extendPath(sourcePath, triplet.getValue1(), vertex));
+                    paths.put(sourceVertex, Pair.with(distance, pathSet));
+                }
+
+                // if a new path was found, send messages to adjacent vertices, otherwise do nothing as there's no
+                // chance to find any new paths going forward
+                if (newPath != null) {
+                    vertex.property(VertexProperty.Cardinality.single, PATHS, paths);
+                    processEdges(vertex, newPath, distance, messenger);
+                    voteToHalt = false;
+                }
+            }
+        }
+
+        // VOTE_TO_HALT will be set to true if an iteration hasn't found any new paths
+        memory.add(VOTE_TO_HALT, voteToHalt);
+    }
+
+    @Override
+    public boolean terminate(final Memory memory) {
+        if (memory.isInitialIteration() && this.haltedTraversersIndex != null) {
+            this.haltedTraversersIndex.clear();
+        }
+        final boolean voteToHalt = memory.get(VOTE_TO_HALT);
+        if (voteToHalt) {
+            final int state = memory.get(STATE);
+            if (state == COLLECT_PATHS) {
+                // After paths were collected,
+                // a) the VP is done in standalone mode (paths will be in memory) or
+                // b) the halted traversers will be updated in order to have the paths available in the traversal
+                if (this.standalone) return true;
+                memory.set(STATE, UPDATE_HALTED_TRAVERSERS);
+                return false;
+            }
+            if (state == UPDATE_HALTED_TRAVERSERS) return true;
+            else memory.set(STATE, COLLECT_PATHS); // collect paths if no new paths were found
+            return false;
+        } else {
+            memory.set(VOTE_TO_HALT, true);
+            return false;
+        }
+    }
+
+    @Override
+    public String toString() {
+
+        final List<String> options = new ArrayList<>();
+        final Function<String, String> shortName = name -> name.substring(name.lastIndexOf(".") + 1);
+
+        if (!this.sourceVertexFilterTraversal.equals(DEFAULT_VERTEX_FILTER_TRAVERSAL)) {
+            options.add(shortName.apply(SOURCE_VERTEX_FILTER) + "=" + this.sourceVertexFilterTraversal.get());
+        }
+
+        if (!this.targetVertexFilterTraversal.equals(DEFAULT_VERTEX_FILTER_TRAVERSAL)) {
+            options.add(shortName.apply(TARGET_VERTEX_FILTER) + "=" + this.targetVertexFilterTraversal.get());
+        }
+
+        if (!this.edgeTraversal.equals(DEFAULT_EDGE_TRAVERSAL)) {
+            options.add(shortName.apply(EDGE_TRAVERSAL) + "=" + this.edgeTraversal.get());
+        }
+
+        if (!this.distanceTraversal.equals(DEFAULT_DISTANCE_TRAVERSAL)) {
+            options.add(shortName.apply(DISTANCE_TRAVERSAL) + "=" + this.distanceTraversal.get());
+        }
+
+        options.add(shortName.apply(INCLUDE_EDGES) + "=" + this.includeEdges);
+
+        return StringFactory.vertexProgramString(this, String.join(", ", options));
+    }
+
+    //////////////////////////////
+
+    private void copyHaltedTraversersFromMemory(final Vertex vertex) {
+        final Collection<Traverser.Admin<Vertex>> traversers = this.haltedTraversersIndex.get(vertex);
+        if (traversers != null) {
+            final TraverserSet<Vertex> newHaltedTraversers = new TraverserSet<>();
+            newHaltedTraversers.addAll(traversers);
+            vertex.property(VertexProperty.Cardinality.single, TraversalVertexProgram.HALTED_TRAVERSERS, newHaltedTraversers);
+        }
+    }
+
+
+    private static Path makePath(final Vertex newVertex) {
+        return extendPath(null, newVertex);
+    }
+
+    private static Path extendPath(final Path currentPath, final Element... elements) {
+        Path result = ImmutablePath.make();
+        if (currentPath != null) {
+            for (final Object o : currentPath.objects()) {
+                result = result.extend(o, Collections.emptySet());
+            }
+        }
+        for (final Element element : elements) {
+            if (element != null) {
+                result = result.extend(ReferenceFactory.detach(element), Collections.emptySet());
+            }
+        }
+        return result;
+    }
+
+    private boolean isStartVertex(final Vertex vertex) {
+        // use the sourceVertexFilterTraversal if the VP is running in standalone mode (not part of a traversal)
+        if (this.standalone) {
+            final Traversal.Admin<Vertex, ?> filterTraversal = this.sourceVertexFilterTraversal.getPure();
+            filterTraversal.addStart(filterTraversal.getTraverserGenerator().generate(vertex, filterTraversal.getStartStep(), 1));
+            return filterTraversal.hasNext();
+        }
+        // ...otherwise use halted traversers to determine whether this is a start vertex
+        return vertex.property(TraversalVertexProgram.HALTED_TRAVERSERS).isPresent();
+    }
+
+    private boolean isEndVertex(final Vertex vertex) {
+        final Traversal.Admin<Vertex, ?> filterTraversal = this.targetVertexFilterTraversal.getPure();
+        //noinspection unchecked
+        final Step<Vertex, Vertex> startStep = (Step<Vertex, Vertex>) filterTraversal.getStartStep();
+        filterTraversal.addStart(filterTraversal.getTraverserGenerator().generate(vertex, startStep, 1));
+        return filterTraversal.hasNext();
+    }
+
+    private void processEdges(final Vertex vertex, final Path currentPath, final Number currentDistance,
+                              final Messenger<Triplet<Path, Edge, Number>> messenger) {
+
+        final Traversal.Admin<Vertex, Edge> edgeTraversal = this.edgeTraversal.getPure();
+        edgeTraversal.addStart(edgeTraversal.getTraverserGenerator().generate(vertex, edgeTraversal.getStartStep(), 1));
+
+        while (edgeTraversal.hasNext()) {
+            final Edge edge = edgeTraversal.next();
+            final Number distance = getDistance(edge);
+
+            Vertex otherV = edge.inVertex();
+            if (otherV.equals(vertex))
+                otherV = edge.outVertex();
+
+            // only send message if the adjacent vertex is not yet part of the current path
+            if (!currentPath.objects().contains(otherV)) {
+                messenger.sendMessage(MessageScope.Global.of(otherV),
+                        Triplet.with(currentPath, this.includeEdges ? edge : null,
+                                NumberHelper.add(currentDistance, distance)));
+            }
+        }
+    }
+
+    private void updateHaltedTraversers(final Vertex vertex, final Memory memory) {
+        if (isStartVertex(vertex)) {
+            final List<Path> paths = memory.get(SHORTEST_PATHS);
+            if (vertex.property(TraversalVertexProgram.HALTED_TRAVERSERS).isPresent()) {
+                // replace the current set of halted traversers with new new traversers that hold the shortest paths
+                // found for this vertex
+                final TraverserSet<Vertex> haltedTraversers = vertex.value(TraversalVertexProgram.HALTED_TRAVERSERS);
+                final TraverserSet<Path> newHaltedTraversers = new TraverserSet<>();
+                for (final Traverser.Admin<Vertex> traverser : haltedTraversers) {
+                    final Vertex v = traverser.get();
+                    for (final Path path : paths) {
+                        if (path.get(0).equals(v)) {
+                            newHaltedTraversers.add(traverser.split(path, this.programStep));
+                        }
+                    }
+                }
+                vertex.property(VertexProperty.Cardinality.single, TraversalVertexProgram.HALTED_TRAVERSERS, newHaltedTraversers);
+            }
+        }
+    }
+
+    private Number getDistance(final Edge edge) {
+        if (this.distanceEqualsNumberOfHops) return 1;
+        final Traversal.Admin<Edge, Number> traversal = this.distanceTraversal.getPure();
+        traversal.addStart(traversal.getTraverserGenerator().generate(edge, traversal.getStartStep(), 1));
+        return traversal.tryNext().orElse(0);
+    }
+
+    private boolean exceedsMaxDistance(final Number distance) {
+        // This method is used to stop the message sending for paths that exceed the specified maximum distance. Since
+        // custom distances can be negative, this method should only return true if the distance is calculated based on
+        // the number of hops.
+        return this.distanceEqualsNumberOfHops && this.maxDistance != null
+                && NumberHelper.compare(distance, this.maxDistance) > 0;
+    }
+
+    /**
+     * Move any valid path into the VP's memory.
+     * @param vertex The current vertex.
+     * @param memory The VertexProgram's memory.
+     */
+    private void collectShortestPaths(final Vertex vertex, final Memory memory) {
+
+        final VertexProperty<Map<Vertex, Pair<Number, Set<Path>>>> pathProperty = vertex.property(PATHS);
+
+        if (pathProperty.isPresent()) {
+
+            final Map<Vertex, Pair<Number, Set<Path>>> paths = pathProperty.value();
+            final List<Path> result = new ArrayList<>();
+
+            for (final Pair<Number, Set<Path>> pair : paths.values()) {
+                for (final Path path : pair.getValue1()) {
+                    if (isEndVertex(vertex)) {
+                        if (this.distanceEqualsNumberOfHops ||
+                                this.maxDistance == null ||
+                                NumberHelper.compare(pair.getValue0(), this.maxDistance) <= 0) {
+                            result.add(path);
+                        }
+                    }
+                }
+            }
+
+            pathProperty.remove();
+
+            memory.add(SHORTEST_PATHS, result);
+        }
+    }
+
+    //////////////////////////////
+
+    public static Builder build() {
+        return new Builder();
+    }
+
+    @SuppressWarnings("WeakerAccess")
+    public static final class Builder extends AbstractVertexProgramBuilder<Builder> {
+
+
+        private Builder() {
+            super(ShortestPathVertexProgram.class);
+        }
+
+        public Builder source(final Traversal<Vertex, ?> sourceVertexFilter) {
+            if (null == sourceVertexFilter) throw Graph.Exceptions.argumentCanNotBeNull("sourceVertexFilter");
+            PureTraversal.storeState(this.configuration, SOURCE_VERTEX_FILTER, sourceVertexFilter.asAdmin());
+            return this;
+        }
+
+        public Builder target(final Traversal<Vertex, ?> targetVertexFilter) {
+            if (null == targetVertexFilter) throw Graph.Exceptions.argumentCanNotBeNull("targetVertexFilter");
+            PureTraversal.storeState(this.configuration, TARGET_VERTEX_FILTER, targetVertexFilter.asAdmin());
+            return this;
+        }
+
+        public Builder edgeDirection(final Direction direction) {
+            if (null == direction) throw Graph.Exceptions.argumentCanNotBeNull("direction");
+            return edgeTraversal(__.toE(direction));
+        }
+
+        public Builder edgeTraversal(final Traversal<Vertex, Edge> edgeTraversal) {
+            if (null == edgeTraversal) throw Graph.Exceptions.argumentCanNotBeNull("edgeTraversal");
+            PureTraversal.storeState(this.configuration, EDGE_TRAVERSAL, edgeTraversal.asAdmin());
+            return this;
+        }
+
+        public Builder distanceProperty(final String distance) {
+            //noinspection unchecked
+            return distance != null
+                    ? distanceTraversal(__.values(distance)) // todo: (Traversal) new ElementValueTraversal<>(distance)
+                    : distanceTraversal(DEFAULT_DISTANCE_TRAVERSAL.getPure());
+        }
+
+        public Builder distanceTraversal(final Traversal<Edge, Number> distanceTraversal) {
+            if (null == distanceTraversal) throw Graph.Exceptions.argumentCanNotBeNull("distanceTraversal");
+            PureTraversal.storeState(this.configuration, DISTANCE_TRAVERSAL, distanceTraversal.asAdmin());
+            return this;
+        }
+
+        public Builder maxDistance(final Number distance) {
+            if (null != distance)
+                this.configuration.setProperty(MAX_DISTANCE, distance);
+            else
+                this.configuration.clearProperty(MAX_DISTANCE);
+            return this;
+        }
+
+        public Builder includeEdges(final boolean include) {
+            this.configuration.setProperty(INCLUDE_EDGES, include);
+            return this;
+        }
+    }
+
+    ////////////////////////////
+
+    @Override
+    public Features getFeatures() {
+        return new Features() {
+            @Override
+            public boolean requiresGlobalMessageScopes() {
+                return true;
+            }
+
+            @Override
+            public boolean requiresVertexPropertyAddition() {
+                return true;
+            }
+        };
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPath.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPath.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPath.java
new file mode 100644
index 0000000..b0d7815
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPath.java
@@ -0,0 +1,108 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF 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 org.apache.tinkerpop.gremlin.process.computer.traversal.step.map;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.structure.Direction;
+import org.apache.tinkerpop.gremlin.structure.Graph;
+
+/**
+ * Configuration options to be passed to the {@link GraphTraversal#with(String, Object)} step.
+ */
+public class ShortestPath {
+
+    /**
+     * Configures the traversal to use to filter the target vertices for all shortest paths.
+     */
+    public static final String target = Graph.Hidden.hide("tinkerpop.shortestPath.target");
+
+    /**
+     * Configures the direction or traversal to use to filter the edges traversed during the shortest path search phase.
+     */
+    public static final String edges = Graph.Hidden.hide("tinkerpop.shortestPath.edges");
+
+    /**
+     * Configures the edge property or traversal to use for shortest path distance calculations.
+     */
+    public static final String distance = Graph.Hidden.hide("tinkerpop.shortestPath.distance");
+
+    /**
+     * Configures the maximum distance for all shortest paths. Any path with a distance greater than the specified
+     * value will not be returned.
+     */
+    public static final String maxDistance = Graph.Hidden.hide("tinkerpop.shortestPath.maxDistance");
+
+    /**
+     * Configures the inclusion of edges in the shortest path computation result.
+     */
+    public static final String includeEdges = Graph.Hidden.hide("tinkerpop.shortestPath.includeEdges");
+
+    static boolean configure(final ShortestPathVertexProgramStep step, final String key, final Object value) {
+
+        if (target.equals(key)) {
+            if (value instanceof Traversal) {
+                step.setTargetVertexFilter((Traversal) value);
+                return true;
+            }
+            else throw new IllegalArgumentException("ShortestPath.target requires a Traversal as its argument");
+        }
+        else if (edges.equals(key)) {
+            if (value instanceof Traversal) {
+                step.setEdgeTraversal((Traversal) value);
+                return true;
+            }
+            else if (value instanceof Direction) {
+                step.setEdgeTraversal(__.toE((Direction) value));
+                return true;
+            }
+            else throw new IllegalArgumentException(
+                    "ShortestPath.edges requires a Traversal or a Direction as its argument");
+        }
+        else if (distance.equals(key)) {
+            if (value instanceof Traversal) {
+                step.setDistanceTraversal((Traversal) value);
+                return true;
+            }
+            else if (value instanceof String) {
+                // todo: new ElementValueTraversal((String) value)
+                step.setDistanceTraversal(__.values((String) value));
+                return true;
+            }
+            else throw new IllegalArgumentException(
+                    "ShortestPath.distance requires a Traversal or a property name as its argument");
+        }
+        else if (maxDistance.equals(key)) {
+            if (value instanceof Number) {
+                step.setMaxDistance((Number) value);
+                return true;
+            }
+            else throw new IllegalArgumentException("ShortestPath.maxDistance requires a Number as its argument");
+        }
+        else if (includeEdges.equals(key)) {
+            if (value instanceof Boolean) {
+                step.setIncludeEdges((Boolean) value);
+                return true;
+            }
+            else throw new IllegalArgumentException("ShortestPath.includeEdges requires a Boolean as its argument");
+        }
+        return false;
+    }
+}

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPathVertexProgramStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPathVertexProgramStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPathVertexProgramStep.java
new file mode 100644
index 0000000..e9a09e2
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPathVertexProgramStep.java
@@ -0,0 +1,185 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF 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 org.apache.tinkerpop.gremlin.process.computer.traversal.step.map;
+
+import org.apache.tinkerpop.gremlin.process.computer.ComputerResult;
+import org.apache.tinkerpop.gremlin.process.computer.GraphFilter;
+import org.apache.tinkerpop.gremlin.process.computer.Memory;
+import org.apache.tinkerpop.gremlin.process.computer.search.path.ShortestPathVertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.TraversalVertexProgram;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.step.Configuring;
+import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.Parameters;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
+import org.apache.tinkerpop.gremlin.process.traversal.util.PureTraversal;
+import org.apache.tinkerpop.gremlin.structure.Edge;
+import org.apache.tinkerpop.gremlin.structure.Graph;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
+import org.apache.tinkerpop.gremlin.util.Serializer;
+
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.Base64;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+public final class ShortestPathVertexProgramStep extends VertexProgramStep implements TraversalParent, Configuring {
+
+    private Parameters parameters = new Parameters();
+    private PureTraversal<Vertex, ?> targetVertexFilter = ShortestPathVertexProgram.DEFAULT_VERTEX_FILTER_TRAVERSAL.clone();
+    private PureTraversal<Vertex, Edge> edgeTraversal = ShortestPathVertexProgram.DEFAULT_EDGE_TRAVERSAL.clone();
+    private PureTraversal<Edge, Number> distanceTraversal = ShortestPathVertexProgram.DEFAULT_DISTANCE_TRAVERSAL.clone();
+    private Number maxDistance;
+    private boolean includeEdges;
+
+    public ShortestPathVertexProgramStep(final Traversal.Admin<?, ?> traversal) {
+        super(traversal);
+    }
+
+    void setTargetVertexFilter(final Traversal filterTraversal) {
+        this.targetVertexFilter = new PureTraversal<>(this.integrateChild(filterTraversal.asAdmin()));
+    }
+
+    void setEdgeTraversal(final Traversal edgeTraversal) {
+        this.edgeTraversal = new PureTraversal<>(this.integrateChild(edgeTraversal.asAdmin()));
+    }
+
+    void setDistanceTraversal(final Traversal distanceTraversal) {
+        this.distanceTraversal = new PureTraversal<>(this.integrateChild(distanceTraversal.asAdmin()));
+    }
+
+    void setMaxDistance(final Number maxDistance) {
+        this.maxDistance = maxDistance;
+    }
+
+    void setIncludeEdges(final boolean includeEdges) {
+        this.includeEdges = includeEdges;
+    }
+
+    @Override
+    public void configure(final Object... keyValues) {
+        if (!ShortestPath.configure(this, (String) keyValues[0], keyValues[1])) {
+            this.parameters.set(this, keyValues);
+        }
+    }
+
+    @Override
+    public Parameters getParameters() {
+        return parameters;
+    }
+
+    @Override
+    protected Traverser.Admin<ComputerResult> processNextStart() throws NoSuchElementException {
+        return super.processNextStart();
+    }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public List<Traversal.Admin<?, ?>> getLocalChildren() {
+        return Arrays.asList(
+                this.targetVertexFilter.get(),
+                this.edgeTraversal.get(),
+                this.distanceTraversal.get());
+    }
+
+    @Override
+    public String toString() {
+        return StringFactory.stepString(this, this.targetVertexFilter.get(), this.edgeTraversal.get(),
+                this.distanceTraversal.get(), this.maxDistance, this.includeEdges, new GraphFilter(this.computer));
+    }
+
+    @Override
+    public ShortestPathVertexProgram generateProgram(final Graph graph, final Memory memory) {
+
+        final ShortestPathVertexProgram.Builder builder = ShortestPathVertexProgram.build()
+                .target(this.targetVertexFilter.getPure())
+                .edgeTraversal(this.edgeTraversal.getPure())
+                .distanceTraversal(this.distanceTraversal.getPure())
+                .maxDistance(this.maxDistance)
+                .includeEdges(this.includeEdges);
+
+        //noinspection unchecked
+        final PureTraversal pureRootTraversal = new PureTraversal<>(this.traversal);
+        Object rootTraversalValue;
+        try {
+            rootTraversalValue = Base64.getEncoder().encodeToString(Serializer.serializeObject(pureRootTraversal));
+        } catch (final IOException ignored) {
+            rootTraversalValue = pureRootTraversal;
+        }
+
+        builder.configure(
+                ProgramVertexProgramStep.ROOT_TRAVERSAL, rootTraversalValue,
+                ProgramVertexProgramStep.STEP_ID, this.id);
+
+        // There are two locations in which halted traversers can be stored: in memory or as vertex properties. In the
+        // former case they need to be copied to this VertexProgram's configuration as the VP won't have access to the
+        // previous VP's memory.
+        if (memory.exists(TraversalVertexProgram.HALTED_TRAVERSERS)) {
+            final TraverserSet<?> haltedTraversers = memory.get(TraversalVertexProgram.HALTED_TRAVERSERS);
+            if (!haltedTraversers.isEmpty()) {
+                Object haltedTraversersValue;
+                try {
+                    haltedTraversersValue = Base64.getEncoder().encodeToString(Serializer.serializeObject(haltedTraversers));
+                } catch (final IOException ignored) {
+                    haltedTraversersValue = haltedTraversers;
+                }
+                builder.configure(TraversalVertexProgram.HALTED_TRAVERSERS, haltedTraversersValue);
+            }
+        }
+
+        return builder.create(graph);
+    }
+
+    @Override
+    public Set<TraverserRequirement> getRequirements() {
+        return TraversalParent.super.getSelfAndChildRequirements();
+    }
+
+    @Override
+    public ShortestPathVertexProgramStep clone() {
+        final ShortestPathVertexProgramStep clone = (ShortestPathVertexProgramStep) super.clone();
+        clone.targetVertexFilter = this.targetVertexFilter.clone();
+        clone.edgeTraversal = this.edgeTraversal.clone();
+        clone.distanceTraversal = this.distanceTraversal.clone();
+        return clone;
+    }
+
+    @Override
+    public void setTraversal(final Traversal.Admin<?, ?> parentTraversal) {
+        super.setTraversal(parentTraversal);
+        this.integrateChild(this.targetVertexFilter.get());
+        this.integrateChild(this.edgeTraversal.get());
+        this.integrateChild(this.distanceTraversal.get());
+    }
+
+    @Override
+    public int hashCode() {
+        return super.hashCode();
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java
index f19d5fa..eaced7a 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java
@@ -72,6 +72,10 @@ import java.util.Iterator;
         method = "*",
         reason = "RemoteGraph does not support direct Graph.compute() access")
 @Graph.OptOut(
+        test = "org.apache.tinkerpop.gremlin.process.computer.search.path.ShortestPathVertexProgramTest",
+        method = "*",
+        reason = "RemoteGraph does not support direct Graph.compute() access")
+@Graph.OptOut(
         test = "org.apache.tinkerpop.gremlin.process.computer.bulkloading.BulkLoaderVertexProgramTest",
         method = "*",
         reason = "RemoteGraph does not support direct Graph.compute() access")

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java
index 220c995..30435ab 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java
@@ -496,15 +496,17 @@ public interface Traversal<S, E> extends Iterator<E>, Serializable, Cloneable, A
         public void setGraph(final Graph graph);
 
         public default boolean equals(final Traversal.Admin<S, E> other) {
-            final List<Step> steps = this.getSteps();
-            final List<Step> otherSteps = other.getSteps();
-            if (steps.size() == otherSteps.size()) {
-                for (int i = 0; i < steps.size(); i++) {
-                    if (!steps.get(i).equals(otherSteps.get(i))) {
-                        return false;
+            if (this.getClass().equals(other.getClass())) {
+                final List<Step> steps = this.getSteps();
+                final List<Step> otherSteps = other.getSteps();
+                if (steps.size() == otherSteps.size()) {
+                    for (int i = 0; i < steps.size(); i++) {
+                        if (!steps.get(i).equals(otherSteps.get(i))) {
+                            return false;
+                        }
                     }
+                    return true;
                 }
-                return true;
             }
             return false;
         }

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
index a675ad1..593323c 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
@@ -22,6 +22,7 @@ import org.apache.tinkerpop.gremlin.process.computer.VertexProgram;
 import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.PageRankVertexProgramStep;
 import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.PeerPressureVertexProgramStep;
 import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ProgramVertexProgramStep;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ShortestPathVertexProgramStep;
 import org.apache.tinkerpop.gremlin.process.traversal.Order;
 import org.apache.tinkerpop.gremlin.process.traversal.P;
 import org.apache.tinkerpop.gremlin.process.traversal.Path;
@@ -2452,6 +2453,24 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> {
     }
 
     /**
+     * Executes a Shortest Path algorithm over the graph.
+     *
+     * @return the traversal with the appended {@link ShortestPathVertexProgramStep}
+     * @see <a href="http://tinkerpop.apache.org/docs/${project.version}/reference/#shortestpath-step" target="_blank">Reference Documentation - ShortestPath Step</a>
+     */
+    public default GraphTraversal<S, Path> shortestPath() {
+        if (this.asAdmin().getEndStep() instanceof GraphStep) {
+            // This is very unfortunate, but I couldn't find another way to make it work. Without the additional
+            // IdentityStep, TraversalVertexProgram doesn't handle halted traversers as expected (it ignores both:
+            // HALTED_TRAVERSER stored in memory and stored as vertex properties); instead it just emits all vertices.
+            this.identity();
+        }
+        this.asAdmin().getBytecode().addStep(Symbols.shortestPath);
+        return (GraphTraversal<S, Path>) ((Traversal.Admin) this.asAdmin())
+                .addStep(new ShortestPathVertexProgramStep(this.asAdmin()));
+    }
+
+    /**
      * Executes an arbitrary {@link VertexProgram} over the graph.
      *
      * @return the traversal with the appended {@link ProgramVertexProgramStep}
@@ -2882,6 +2901,7 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> {
 
         public static final String pageRank = "pageRank";
         public static final String peerPressure = "peerPressure";
+        public static final String shortestPath = "shortestPath";
         public static final String program = "program";
 
         public static final String by = "by";

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ColumnTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ColumnTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ColumnTraversal.java
index 5023805..9e2f31c 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ColumnTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ColumnTraversal.java
@@ -22,6 +22,8 @@ package org.apache.tinkerpop.gremlin.process.traversal.lambda;
 import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
 import org.apache.tinkerpop.gremlin.structure.Column;
 
+import java.util.Objects;
+
 /**
  * @author Marko A. Rodriguez (http://markorodriguez.com)
  */
@@ -57,4 +59,10 @@ public final class ColumnTraversal extends AbstractLambdaTraversal {
     public int hashCode() {
         return this.getClass().hashCode() ^ this.column.hashCode();
     }
+
+    @Override
+    public boolean equals(final Object other) {
+        return other instanceof ColumnTraversal
+                && Objects.equals(((ColumnTraversal) other).column, this.column);
+    }
 }

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ConstantTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ConstantTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ConstantTraversal.java
index 91973b9..bcf82d4 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ConstantTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ConstantTraversal.java
@@ -18,6 +18,8 @@
  */
 package org.apache.tinkerpop.gremlin.process.traversal.lambda;
 
+import java.util.Objects;
+
 /**
  * @author Marko A. Rodriguez (http://markorodriguez.com)
  */
@@ -43,5 +45,10 @@ public final class ConstantTraversal<S, E> extends AbstractLambdaTraversal<S, E>
     public int hashCode() {
         return this.getClass().hashCode() ^ this.end.hashCode();
     }
-}
 
+    @Override
+    public boolean equals(final Object other) {
+        return other instanceof ConstantTraversal
+                && Objects.equals(((ConstantTraversal) other).end, this.end);
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ElementValueTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ElementValueTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ElementValueTraversal.java
index 2e9b26c..fbfff62 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ElementValueTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ElementValueTraversal.java
@@ -22,6 +22,8 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
 import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalUtil;
 import org.apache.tinkerpop.gremlin.structure.Element;
 
+import java.util.Objects;
+
 /**
  * @author Marko A. Rodriguez (http://markorodriguez.com)
  */
@@ -62,4 +64,10 @@ public final class ElementValueTraversal<V> extends AbstractLambdaTraversal<Elem
     public int hashCode() {
         return super.hashCode() ^ this.propertyKey.hashCode();
     }
-}
+
+    @Override
+    public boolean equals(final Object other) {
+        return other instanceof ElementValueTraversal
+                && Objects.equals(((ElementValueTraversal) other).propertyKey, this.propertyKey);
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/IdentityTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/IdentityTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/IdentityTraversal.java
index 98f85c0..1ed5749 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/IdentityTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/IdentityTraversal.java
@@ -41,4 +41,9 @@ public final class IdentityTraversal<S> extends AbstractLambdaTraversal<S, S> {
     public String toString() {
         return "identity";
     }
-}
+
+    @Override
+    public boolean equals(final Object other) {
+        return other instanceof IdentityTraversal;
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/LoopTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/LoopTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/LoopTraversal.java
index ae03c94..68b6b18 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/LoopTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/LoopTraversal.java
@@ -55,4 +55,10 @@ public final class LoopTraversal<S> extends AbstractLambdaTraversal<S, S> {
     public int hashCode() {
         return this.getClass().hashCode() ^ Long.hashCode(this.maxLoops);
     }
+
+    @Override
+    public boolean equals(final Object other) {
+        return other instanceof LoopTraversal
+                && ((LoopTraversal) other).maxLoops == this.maxLoops;
+    }
 }
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TokenTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TokenTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TokenTraversal.java
index 4f98a54..d41c402 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TokenTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TokenTraversal.java
@@ -22,6 +22,8 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
 import org.apache.tinkerpop.gremlin.structure.Element;
 import org.apache.tinkerpop.gremlin.structure.T;
 
+import java.util.Objects;
+
 /**
  * @author Marko A. Rodriguez (http://markorodriguez.com)
  */
@@ -57,4 +59,10 @@ public final class TokenTraversal<S extends Element, E> extends AbstractLambdaTr
     public int hashCode() {
         return this.getClass().hashCode() ^ this.t.hashCode();
     }
+
+    @Override
+    public boolean equals(final Object other) {
+        return other instanceof TokenTraversal
+                && Objects.equals(((TokenTraversal) other).t, this.t);
+    }
 }

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TrueTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TrueTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TrueTraversal.java
index 84c0db6..71580ce 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TrueTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TrueTraversal.java
@@ -43,4 +43,9 @@ public final class TrueTraversal<S> extends AbstractLambdaTraversal<S, S> {
     public TrueTraversal<S> clone() {
         return INSTANCE;
     }
+
+    @Override
+    public boolean equals(final Object other) {
+        return other instanceof TrueTraversal;
+    }
 }

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java
index 2e795a5..1bccd7c 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java
@@ -129,7 +129,7 @@ abstract class GraphSONModule extends TinkerPopJacksonModule {
                     put(List.class, "List");
                     put(Set.class, "Set");
 
-                    // Tinkerpop Graph objects
+                    // TinkerPop Graph objects
                     put(Lambda.class, "Lambda");
                     put(Vertex.class, "Vertex");
                     put(Edge.class, "Edge");

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java
index e7dfd93..6d55704 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java
@@ -114,10 +114,10 @@ import org.apache.tinkerpop.gremlin.util.function.MultiComparator;
 import org.apache.tinkerpop.shaded.kryo.ClassResolver;
 import org.apache.tinkerpop.shaded.kryo.KryoSerializable;
 import org.apache.tinkerpop.shaded.kryo.serializers.JavaSerializer;
-import org.javatuples.Pair;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.LabelledCounter;
 import org.apache.commons.collections.map.ReferenceMap;
-import java.util.Stack;
+import org.javatuples.Pair;
+import org.javatuples.Triplet;
 
 import java.math.BigDecimal;
 import java.math.BigInteger;
@@ -154,6 +154,7 @@ import java.util.LinkedList;
 import java.util.List;
 import java.util.Locale;
 import java.util.Optional;
+import java.util.Stack;
 import java.util.TimeZone;
 import java.util.TreeMap;
 import java.util.TreeSet;
@@ -356,6 +357,7 @@ public enum GryoVersion {
             add(GryoTypeReg.of(MapReduce.NullObject.class, 74));
             add(GryoTypeReg.of(AtomicLong.class, 79));
             add(GryoTypeReg.of(Pair.class, 88, new UtilSerializers.PairSerializer()));
+            add(GryoTypeReg.of(Triplet.class, 183, new UtilSerializers.TripletSerializer()));                 // ***LAST ID***
             add(GryoTypeReg.of(TraversalExplanation.class, 106, new JavaSerializer()));
 
             add(GryoTypeReg.of(Duration.class, 93, new JavaTimeSerializers.DurationSerializer()));
@@ -393,8 +395,7 @@ public enum GryoVersion {
             add(GryoTypeReg.of(LP_NL_O_OB_P_S_SE_SL_Traverser.class, 179));
             add(GryoTypeReg.of(LabelledCounter.class, 180));
             add(GryoTypeReg.of(Stack.class, 181));
-            add(GryoTypeReg.of(ReferenceMap.class, 182));                        // ***LAST ID***
-
+            add(GryoTypeReg.of(ReferenceMap.class, 182));
 
             // placeholder serializers for classes that don't live here in core. this will allow them to be used if
             // present  or ignored if the class isn't available. either way the registration numbers are held as
@@ -520,6 +521,7 @@ public enum GryoVersion {
             add(GryoTypeReg.of(MapReduce.NullObject.class, 74));
             add(GryoTypeReg.of(AtomicLong.class, 79));
             add(GryoTypeReg.of(Pair.class, 88, new UtilSerializers.PairSerializer()));
+            add(GryoTypeReg.of(Triplet.class, 183, new UtilSerializers.TripletSerializer()));                 // ***LAST ID***
             add(GryoTypeReg.of(TraversalExplanation.class, 106, new JavaSerializer()));
 
             add(GryoTypeReg.of(Duration.class, 93, new JavaTimeSerializers.DurationSerializer()));
@@ -583,7 +585,7 @@ public enum GryoVersion {
             add(GryoTypeReg.of(LP_NL_O_OB_P_S_SE_SL_Traverser.class, 179));
             add(GryoTypeReg.of(LabelledCounter.class, 180));
             add(GryoTypeReg.of(Stack.class, 181));
-            add(GryoTypeReg.of(ReferenceMap.class, 182));                        // ***LAST ID***
+            add(GryoTypeReg.of(ReferenceMap.class, 182));
         }};
     }
 

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/UtilSerializers.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/UtilSerializers.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/UtilSerializers.java
index 5182e6c..aff6059 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/UtilSerializers.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/UtilSerializers.java
@@ -28,6 +28,7 @@ import org.apache.tinkerpop.shaded.kryo.Serializer;
 import org.apache.tinkerpop.shaded.kryo.io.Input;
 import org.apache.tinkerpop.shaded.kryo.io.Output;
 import org.javatuples.Pair;
+import org.javatuples.Triplet;
 
 import java.net.InetAddress;
 import java.net.URI;
@@ -216,6 +217,20 @@ final class UtilSerializers {
         }
     }
 
+    static final class TripletSerializer implements SerializerShim<Triplet> {
+        @Override
+        public <O extends OutputShim> void write(final KryoShim<?, O> kryo, final O output, final Triplet triplet) {
+            kryo.writeClassAndObject(output, triplet.getValue0());
+            kryo.writeClassAndObject(output, triplet.getValue1());
+            kryo.writeClassAndObject(output, triplet.getValue2());
+        }
+
+        @Override
+        public <I extends InputShim> Triplet read(final KryoShim<I, ?> kryo, final I input, final Class<Triplet> tripletClass) {
+            return Triplet.with(kryo.readClassAndObject(input), kryo.readClassAndObject(input), kryo.readClassAndObject(input));
+        }
+    }
+
     static final class EntrySerializer extends Serializer<Map.Entry> {
         @Override
         public void write(final Kryo kryo, final Output output, final Map.Entry entry) {

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Attachable.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Attachable.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Attachable.java
index fa999aa..3cd76f2 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Attachable.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Attachable.java
@@ -26,6 +26,7 @@ import org.apache.tinkerpop.gremlin.structure.Property;
 import org.apache.tinkerpop.gremlin.structure.T;
 import org.apache.tinkerpop.gremlin.structure.Vertex;
 import org.apache.tinkerpop.gremlin.structure.VertexProperty;
+import org.apache.tinkerpop.gremlin.structure.util.empty.EmptyGraph;
 
 import java.util.Iterator;
 import java.util.Optional;
@@ -70,7 +71,7 @@ public interface Attachable<V> {
      */
     public static class Method {
         public static <V> Function<Attachable<V>, V> get(final Host hostVertexOrGraph) {
-            return (Attachable<V> attachable) -> {
+            return hostVertexOrGraph instanceof EmptyGraph ? Attachable::get : (Attachable<V> attachable) -> {
                 final Object base = attachable.get();
                 if (base instanceof Vertex) {
                     final Optional<Vertex> optional = hostVertexOrGraph instanceof Graph ?

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalTest.java
index 3d9a549..d1da36d 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalTest.java
@@ -43,7 +43,7 @@ import static org.junit.Assert.assertEquals;
 public class GraphTraversalTest {
     private static final Logger logger = LoggerFactory.getLogger(GraphTraversalTest.class);
 
-    private static Set<String> NO_GRAPH = new HashSet<>(Arrays.asList("asAdmin", "by", "read", "write", "with", "option", "iterate", "to", "from", "profile", "pageRank", "peerPressure", "program", "none"));
+    private static Set<String> NO_GRAPH = new HashSet<>(Arrays.asList("asAdmin", "by", "read", "write", "with", "option", "iterate", "to", "from", "profile", "pageRank", "peerPressure", "shortestPath", "program", "none"));
     private static Set<String> NO_ANONYMOUS = new HashSet<>(Arrays.asList("start", "__"));
     private static Set<String> IGNORES_BYTECODE = new HashSet<>(Arrays.asList("asAdmin", "read", "write", "iterate", "mapValues", "mapKeys"));
 

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs
----------------------------------------------------------------------
diff --git a/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs b/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs
index 361b246..af78f20 100644
--- a/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs
+++ b/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs
@@ -1386,6 +1386,15 @@ namespace Gremlin.Net.Process.Traversal
         }
 
         /// <summary>
+        ///     Adds the shortestPath step to this <see cref="GraphTraversal{SType, EType}" />.
+        /// </summary>
+        public GraphTraversal<S, Path> ShortestPath ()
+        {
+            Bytecode.AddStep("shortestPath");
+            return Wrap<S, Path>(this);
+        }
+
+        /// <summary>
         ///     Adds the sideEffect step to this <see cref="GraphTraversal{SType, EType}" />.
         /// </summary>
         public GraphTraversal<S, E> SideEffect (IConsumer consumer)

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b0d8e78c/gremlin-javascript/src/main/javascript/gremlin-javascript/lib/process/graph-traversal.js
----------------------------------------------------------------------
diff --git a/gremlin-javascript/src/main/javascript/gremlin-javascript/lib/process/graph-traversal.js b/gremlin-javascript/src/main/javascript/gremlin-javascript/lib/process/graph-traversal.js
index 4f39fa5..6479515 100644
--- a/gremlin-javascript/src/main/javascript/gremlin-javascript/lib/process/graph-traversal.js
+++ b/gremlin-javascript/src/main/javascript/gremlin-javascript/lib/process/graph-traversal.js
@@ -953,6 +953,16 @@ class GraphTraversal extends Traversal {
   }
   
   /**
+   * Graph traversal shortestPath method.
+   * @param {...Object} args
+   * @returns {GraphTraversal}
+   */
+  shortestPath(...args) {
+    this.bytecode.addStep('shortestPath', args);
+    return this;
+  }
+  
+  /**
    * Graph traversal sideEffect method.
    * @param {...Object} args
    * @returns {GraphTraversal}


Mime
View raw message