You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by dk...@apache.org on 2018/08/10 00:02:43 UTC
[13/14] tinkerpop git commit: TINKERPOP-1990 Implemented
`ShortestPathVertexProgram` and `ShortestPathVertexProgramStep`.
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js
----------------------------------------------------------------------
diff --git a/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js b/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js
index a0ae7ca..0cdcd21 100644
--- a/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js
+++ b/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js
@@ -80,6 +80,21 @@ const ignoredScenarios = {
'g_V_peerPressure_byXclusterX_byXoutEXknowsXX_pageRankX1X_byXrankX_byXoutEXknowsXX_timesX2X_group_byXclusterX_byXrank_sumX_limitX100X': new IgnoreError(ignoreReason.computerNotSupported),
'g_V_hasXname_rippleX_inXcreatedX_peerPressure_byXoutEX_byXclusterX_repeatXunionXidentity__bothX_timesX2X_dedup_valueMapXname_clusterX': new IgnoreError(ignoreReason.computerNotSupported),
'g_V_hasXname_rippleX_inXcreatedX_peerPressure_withXEDGES_outEX_withXPROPERTY_NAME_clusterX_repeatXunionXidentity__bothX_timesX2X_dedup_valueMapXname_clusterX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_both_dedup_shortestPath': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath_edgesIncluded': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath_directionXINX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath_edgesXoutEX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath_edgesIncluded_edgesXoutEX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXname_markoX_shortestPath': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath_targetXhasXname_markoXX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath_targetXvaluesXnameX_isXmarkoXX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXname_markoX_shortestPath_targetXhasLabelXsoftwareXX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXname_markoX_shortestPath_targetXhasXname_joshXX_distanceXweightX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXname_danielX_shortestPath_targetXhasXname_stephenXX_edgesXbothEXusesXX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXsong_name_MIGHT_AS_WELLX_shortestPath_targetXhasXsong_name_MAYBE_YOU_KNOW_HOW_I_FEELXX_edgesXoutEXfollowedByXX_distanceXweightX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXname_markoX_shortestPath_maxDistanceX1X': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXname_vadasX_shortestPath_distanceXweightX_maxDistanceX1_3X': new IgnoreError(ignoreReason.computerNotSupported),
};
defineSupportCode(function(methods) {
@@ -352,4 +367,4 @@ function IgnoreError(reason) {
Error.captureStackTrace(this, IgnoreError);
}
-util.inherits(IgnoreError, Error);
\ No newline at end of file
+util.inherits(IgnoreError, Error);
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/gremlin-python/src/main/jython/gremlin_python/process/graph_traversal.py
----------------------------------------------------------------------
diff --git a/gremlin-python/src/main/jython/gremlin_python/process/graph_traversal.py b/gremlin-python/src/main/jython/gremlin_python/process/graph_traversal.py
index b073aa8..a54853b 100644
--- a/gremlin-python/src/main/jython/gremlin_python/process/graph_traversal.py
+++ b/gremlin-python/src/main/jython/gremlin_python/process/graph_traversal.py
@@ -438,6 +438,10 @@ class GraphTraversal(Traversal):
self.bytecode.add_step("select", *args)
return self
+ def shortestPath(self, *args):
+ self.bytecode.add_step("shortestPath", *args)
+ return self
+
def sideEffect(self, *args):
self.bytecode.add_step("sideEffect", *args)
return self
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/gremlin-test/features/map/Path.feature
----------------------------------------------------------------------
diff --git a/gremlin-test/features/map/Path.feature b/gremlin-test/features/map/Path.feature
index b0cb9dd..0bb7573 100644
--- a/gremlin-test/features/map/Path.feature
+++ b/gremlin-test/features/map/Path.feature
@@ -15,7 +15,7 @@
# specific language governing permissions and limitations
# under the License.
-Feature: Step - count()
+Feature: Step - path()
Scenario: g_VX1X_name_path
Given the modern graph
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/gremlin-test/features/map/ShortestPath.feature
----------------------------------------------------------------------
diff --git a/gremlin-test/features/map/ShortestPath.feature b/gremlin-test/features/map/ShortestPath.feature
new file mode 100644
index 0000000..eff743f
--- /dev/null
+++ b/gremlin-test/features/map/ShortestPath.feature
@@ -0,0 +1,361 @@
+# 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.
+
+Feature: Step - shortestPath()
+
+ Scenario: g_V_shortestPath
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath()
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],v[lop],v[peter]] |
+ | p[v[josh],v[lop]] |
+ | p[v[josh],v[marko],v[vadas]] |
+ | p[v[josh],v[marko]] |
+ | p[v[josh],v[ripple]] |
+ | p[v[josh]] |
+ | p[v[lop],v[josh],v[ripple]] |
+ | p[v[lop],v[josh]] |
+ | p[v[lop],v[marko],v[vadas]] |
+ | p[v[lop],v[marko]] |
+ | p[v[lop],v[peter]] |
+ | p[v[lop]] |
+ | p[v[marko],v[josh],v[ripple]] |
+ | p[v[marko],v[josh]] |
+ | p[v[marko],v[lop],v[peter]] |
+ | p[v[marko],v[lop]] |
+ | p[v[marko],v[vadas]] |
+ | p[v[marko]] |
+ | p[v[peter],v[lop],v[josh],v[ripple]] |
+ | p[v[peter],v[lop],v[josh]] |
+ | p[v[peter],v[lop],v[marko],v[vadas]] |
+ | p[v[peter],v[lop],v[marko]] |
+ | p[v[peter],v[lop]] |
+ | p[v[peter]] |
+ | p[v[ripple],v[josh],v[lop],v[peter]] |
+ | p[v[ripple],v[josh],v[lop]] |
+ | p[v[ripple],v[josh],v[marko],v[vadas]] |
+ | p[v[ripple],v[josh],v[marko]] |
+ | p[v[ripple],v[josh]] |
+ | p[v[ripple]] |
+ | p[v[vadas],v[marko],v[josh],v[ripple]] |
+ | p[v[vadas],v[marko],v[josh]] |
+ | p[v[vadas],v[marko],v[lop],v[peter]] |
+ | p[v[vadas],v[marko],v[lop]] |
+ | p[v[vadas],v[marko]] |
+ | p[v[vadas]] |
+
+ Scenario: g_V_both_dedup_shortestPath
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().both().dedup().shortestPath()
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],v[lop],v[peter]] |
+ | p[v[josh],v[lop]] |
+ | p[v[josh],v[marko],v[vadas]] |
+ | p[v[josh],v[marko]] |
+ | p[v[josh],v[ripple]] |
+ | p[v[josh]] |
+ | p[v[lop],v[josh],v[ripple]] |
+ | p[v[lop],v[josh]] |
+ | p[v[lop],v[marko],v[vadas]] |
+ | p[v[lop],v[marko]] |
+ | p[v[lop],v[peter]] |
+ | p[v[lop]] |
+ | p[v[marko],v[josh],v[ripple]] |
+ | p[v[marko],v[josh]] |
+ | p[v[marko],v[lop],v[peter]] |
+ | p[v[marko],v[lop]] |
+ | p[v[marko],v[vadas]] |
+ | p[v[marko]] |
+ | p[v[peter],v[lop],v[josh],v[ripple]] |
+ | p[v[peter],v[lop],v[josh]] |
+ | p[v[peter],v[lop],v[marko],v[vadas]] |
+ | p[v[peter],v[lop],v[marko]] |
+ | p[v[peter],v[lop]] |
+ | p[v[peter]] |
+ | p[v[ripple],v[josh],v[lop],v[peter]] |
+ | p[v[ripple],v[josh],v[lop]] |
+ | p[v[ripple],v[josh],v[marko],v[vadas]] |
+ | p[v[ripple],v[josh],v[marko]] |
+ | p[v[ripple],v[josh]] |
+ | p[v[ripple]] |
+ | p[v[vadas],v[marko],v[josh],v[ripple]] |
+ | p[v[vadas],v[marko],v[josh]] |
+ | p[v[vadas],v[marko],v[lop],v[peter]] |
+ | p[v[vadas],v[marko],v[lop]] |
+ | p[v[vadas],v[marko]] |
+ | p[v[vadas]] |
+
+ Scenario: g_V_shortestPath_edgesIncluded
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath().with("~tinkerpop.shortestPath.includeEdges", true)
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],e[josh-created->lop],v[lop],e[peter-created->lop],v[peter]] |
+ | p[v[josh],e[josh-created->lop],v[lop]] |
+ | p[v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[josh],e[marko-knows->josh],v[marko],e[marko-knows->vadas],v[vadas]] |
+ | p[v[josh],e[marko-knows->josh],v[marko]] |
+ | p[v[josh]] |
+ | p[v[lop],e[josh-created->lop],v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[lop],e[josh-created->lop],v[josh]] |
+ | p[v[lop],e[marko-created->lop],v[marko],e[marko-knows->vadas],v[vadas]] |
+ | p[v[lop],e[marko-created->lop],v[marko]] |
+ | p[v[lop],e[peter-created->lop],v[peter]] |
+ | p[v[lop]] |
+ | p[v[marko],e[marko-created->lop],v[lop],e[peter-created->lop],v[peter]] |
+ | p[v[marko],e[marko-created->lop],v[lop]] |
+ | p[v[marko],e[marko-knows->josh],v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[marko],e[marko-knows->josh],v[josh]] |
+ | p[v[marko],e[marko-knows->vadas],v[vadas]] |
+ | p[v[marko]] |
+ | p[v[peter],e[peter-created->lop],v[lop],e[josh-created->lop],v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[peter],e[peter-created->lop],v[lop],e[josh-created->lop],v[josh]] |
+ | p[v[peter],e[peter-created->lop],v[lop],e[marko-created->lop],v[marko],e[marko-knows->vadas],v[vadas]] |
+ | p[v[peter],e[peter-created->lop],v[lop],e[marko-created->lop],v[marko]] |
+ | p[v[peter],e[peter-created->lop],v[lop]] |
+ | p[v[peter]] |
+ | p[v[ripple],e[josh-created->ripple],v[josh],e[josh-created->lop],v[lop],e[peter-created->lop],v[peter]] |
+ | p[v[ripple],e[josh-created->ripple],v[josh],e[josh-created->lop],v[lop]] |
+ | p[v[ripple],e[josh-created->ripple],v[josh],e[marko-knows->josh],v[marko],e[marko-knows->vadas],v[vadas]] |
+ | p[v[ripple],e[josh-created->ripple],v[josh],e[marko-knows->josh],v[marko]] |
+ | p[v[ripple],e[josh-created->ripple],v[josh]] |
+ | p[v[ripple]] |
+ | p[v[vadas],e[marko-knows->vadas],v[marko],e[marko-created->lop],v[lop],e[peter-created->lop],v[peter]] |
+ | p[v[vadas],e[marko-knows->vadas],v[marko],e[marko-created->lop],v[lop]] |
+ | p[v[vadas],e[marko-knows->vadas],v[marko],e[marko-knows->josh],v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[vadas],e[marko-knows->vadas],v[marko],e[marko-knows->josh],v[josh]] |
+ | p[v[vadas],e[marko-knows->vadas],v[marko]] |
+ | p[v[vadas]] |
+
+ Scenario: g_V_shortestPath_directionXINX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath().with("~tinkerpop.shortestPath.edges", Direction.IN)
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],v[marko]] |
+ | p[v[josh]] |
+ | p[v[lop],v[josh]] |
+ | p[v[lop],v[marko]] |
+ | p[v[lop],v[peter]] |
+ | p[v[lop]] |
+ | p[v[marko]] |
+ | p[v[peter]] |
+ | p[v[ripple],v[josh],v[marko]] |
+ | p[v[ripple],v[josh]] |
+ | p[v[ripple]] |
+ | p[v[vadas],v[marko]] |
+ | p[v[vadas]] |
+
+ Scenario: g_V_shortestPath_edgesXoutEX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath().with("~tinkerpop.shortestPath.edges", __.outE())
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],v[lop]] |
+ | p[v[josh],v[ripple]] |
+ | p[v[josh]] |
+ | p[v[lop]] |
+ | p[v[marko],v[josh],v[ripple]] |
+ | p[v[marko],v[josh]] |
+ | p[v[marko],v[lop]] |
+ | p[v[marko],v[vadas]] |
+ | p[v[marko]] |
+ | p[v[peter],v[lop]] |
+ | p[v[peter]] |
+ | p[v[ripple]] |
+ | p[v[vadas]] |
+
+ Scenario: g_V_shortestPath_edgesIncluded_edgesXoutEX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath().
+ with("~tinkerpop.shortestPath.includeEdges", true).
+ with("~tinkerpop.shortestPath.edges", __.outE())
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],e[josh-created->lop],v[lop]] |
+ | p[v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[josh]] |
+ | p[v[lop]] |
+ | p[v[marko],e[marko-created->lop],v[lop]] |
+ | p[v[marko],e[marko-knows->josh],v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[marko],e[marko-knows->josh],v[josh]] |
+ | p[v[marko],e[marko-knows->vadas],v[vadas]] |
+ | p[v[marko]] |
+ | p[v[peter],e[peter-created->lop],v[lop]] |
+ | p[v[peter]] |
+ | p[v[ripple]] |
+ | p[v[vadas]] |
+
+ Scenario: g_V_hasXname_markoX_shortestPath
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().has("name","marko").shortestPath()
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[marko],v[josh],v[ripple]] |
+ | p[v[marko],v[josh]] |
+ | p[v[marko],v[lop],v[peter]] |
+ | p[v[marko],v[lop]] |
+ | p[v[marko],v[vadas]] |
+ | p[v[marko]] |
+
+ Scenario: g_V_shortestPath_targetXhasXname_markoXX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath().with("~tinkerpop.shortestPath.target", __.has("name","marko"))
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],v[marko]] |
+ | p[v[lop],v[marko]] |
+ | p[v[marko]] |
+ | p[v[peter],v[lop],v[marko]] |
+ | p[v[ripple],v[josh],v[marko]] |
+ | p[v[vadas],v[marko]] |
+
+ Scenario: g_V_shortestPath_targetXvaluesXnameX_isXmarkoXX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath().with("~tinkerpop.shortestPath.target", __.values("name").is("marko"))
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],v[marko]] |
+ | p[v[lop],v[marko]] |
+ | p[v[marko]] |
+ | p[v[peter],v[lop],v[marko]] |
+ | p[v[ripple],v[josh],v[marko]] |
+ | p[v[vadas],v[marko]] |
+
+ Scenario: g_V_hasXname_markoX_shortestPath_targetXhasLabelXsoftwareXX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().has("name","marko").shortestPath().with("~tinkerpop.shortestPath.target", __.hasLabel("software"))
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[marko],v[josh],v[ripple]] |
+ | p[v[marko],v[lop]] |
+
+ Scenario: g_V_hasXname_markoX_shortestPath_targetXhasXname_joshXX_distanceXweightX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().has("name","marko").shortestPath().
+ with("~tinkerpop.shortestPath.target", __.has("name","josh")).
+ with("~tinkerpop.shortestPath.distance", "weight")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[marko],v[lop],v[josh]] |
+
+ Scenario: g_V_hasXname_danielX_shortestPath_targetXhasXname_stephenXX_edgesXbothEXusesXX
+ Given the crew graph
+ And the traversal of
+ """
+ g.withComputer().V().has("name","daniel").shortestPath().
+ with("~tinkerpop.shortestPath.target", __.has("name","stephen")).
+ with("~tinkerpop.shortestPath.edges", __.bothE("uses"))
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[daniel],v[gremlin],v[stephen]] |
+ | p[v[daniel],v[tinkergraph],v[stephen]] |
+
+ Scenario: g_V_hasXsong_name_MIGHT_AS_WELLX_shortestPath_targetXhasXsong_name_MAYBE_YOU_KNOW_HOW_I_FEELXX_edgesXoutEXfollowedByXX_distanceXweightX
+ Given the grateful graph
+ And the traversal of
+ """
+ g.withComputer().V().has("song","name","MIGHT AS WELL").
+ shortestPath().
+ with("~tinkerpop.shortestPath.target", __.has("song","name","MAYBE YOU KNOW HOW I FEEL")).
+ with("~tinkerpop.shortestPath.edges", __.outE("followedBy")).
+ with("~tinkerpop.shortestPath.distance", "weight")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[MIGHT AS WELL],v[DRUMS],v[MAYBE YOU KNOW HOW I FEEL]] |
+ | p[v[MIGHT AS WELL],v[SHIP OF FOOLS],v[MAYBE YOU KNOW HOW I FEEL]] |
+
+ Scenario: g_V_hasXname_markoX_shortestPath_maxDistanceX1X
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().has("name","marko").shortestPath().with("~tinkerpop.shortestPath.maxDistance", 1)
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[marko],v[josh]] |
+ | p[v[marko],v[lop]] |
+ | p[v[marko],v[vadas]] |
+ | p[v[marko]] |
+
+ Scenario: g_V_hasXname_vadasX_shortestPath_distanceXweightX_maxDistanceX1_3X
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().has("name","vadas").shortestPath().
+ with("~tinkerpop.shortestPath.distance", "weight").
+ with("~tinkerpop.shortestPath.maxDistance", 1.3)
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[vadas],v[marko],v[lop],v[josh]] |
+ | p[v[vadas],v[marko],v[lop],v[peter]] |
+ | p[v[vadas],v[marko],v[lop]] |
+ | p[v[vadas],v[marko]] |
+ | p[v[vadas]] |
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/AbstractGremlinTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/AbstractGremlinTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/AbstractGremlinTest.java
index 7ca44ba..6a2b700 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/AbstractGremlinTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/AbstractGremlinTest.java
@@ -180,6 +180,10 @@ public abstract class AbstractGremlinTest {
return convertToVertex(graph, vertexName).id();
}
+ public Vertex convertToVertex(final String vertexName) {
+ return convertToVertex(graph, vertexName);
+ }
+
public Vertex convertToVertex(final Graph graph, final String vertexName) {
// all test graphs have "name" as a unique id which makes it easy to hardcode this...works for now
return graph.traversal().V().has("name", vertexName).next();
@@ -249,7 +253,7 @@ public abstract class AbstractGremlinTest {
public void printTraversalForm(final Traversal traversal) {
logger.info(String.format("Testing: %s", name.getMethodName()));
logger.info(" pre-strategy:" + traversal);
- traversal.hasNext();
+ if (!traversal.asAdmin().isLocked()) traversal.asAdmin().applyStrategies();
logger.info(" post-strategy:" + traversal);
verifyUniqueStepIds(traversal.asAdmin());
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java
index 4749e93..0a2a405 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java
@@ -127,7 +127,7 @@ public abstract class AbstractGremlinProcessTest extends AbstractGremlinTest {
public static <T> void checkResults(final List<T> expectedResults, final Traversal<?, T> traversal) {
final List<T> results = traversal.toList();
- assertFalse(traversal.hasNext());
+ assertThat(traversal.hasNext(), is(false));
if (expectedResults.size() != results.size()) {
logger.error("Expected results: " + expectedResults);
logger.error("Actual results: " + results);
@@ -145,11 +145,10 @@ public abstract class AbstractGremlinProcessTest extends AbstractGremlinTest {
}
final Map<T, Long> expectedResultsCount = new HashMap<>();
final Map<T, Long> resultsCount = new HashMap<>();
+ expectedResults.forEach(t -> MapHelper.incr(expectedResultsCount, t, 1L));
+ results.forEach(t -> MapHelper.incr(resultsCount, t, 1L));
assertEquals("Checking indexing is equivalent", expectedResultsCount.size(), resultsCount.size());
- expectedResults.forEach(t -> MapHelper.incr(expectedResultsCount, t, 1l));
- results.forEach(t -> MapHelper.incr(resultsCount, t, 1l));
expectedResultsCount.forEach((k, v) -> assertEquals("Checking result group counts", v, resultsCount.get(k)));
- assertThat(traversal.hasNext(), is(false));
}
public static <T> void checkResults(final Map<T, Long> expectedResults, final Traversal<?, T> traversal) {
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessComputerSuite.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessComputerSuite.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessComputerSuite.java
index 6466ae8..5a39908 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessComputerSuite.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessComputerSuite.java
@@ -26,6 +26,7 @@ import org.apache.tinkerpop.gremlin.process.computer.bulkloading.BulkLoaderVerte
import org.apache.tinkerpop.gremlin.process.computer.clone.CloneVertexProgramTest;
import org.apache.tinkerpop.gremlin.process.computer.clustering.peerpressure.PeerPressureVertexProgramTest;
import org.apache.tinkerpop.gremlin.process.computer.ranking.pagerank.PageRankVertexProgramTest;
+import org.apache.tinkerpop.gremlin.process.computer.search.path.ShortestPathVertexProgramTest;
import org.apache.tinkerpop.gremlin.process.traversal.TraversalEngine;
import org.apache.tinkerpop.gremlin.process.traversal.TraversalInterruptionComputerTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.ComplexTest;
@@ -72,6 +73,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.map.ProgramTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.ProjectTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.PropertiesTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.ReadTest;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.ShortestPathTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.SelectTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.SumTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.UnfoldTest;
@@ -168,6 +170,7 @@ public class ProcessComputerSuite extends AbstractGremlinSuite {
ProgramTest.Traversals.class,
PropertiesTest.Traversals.class,
ReadTest.Traversals.class,
+ ShortestPathTest.Traversals.class,
SelectTest.Traversals.class,
UnfoldTest.Traversals.class,
ValueMapTest.Traversals.class,
@@ -196,6 +199,7 @@ public class ProcessComputerSuite extends AbstractGremlinSuite {
// algorithms
PageRankVertexProgramTest.class,
PeerPressureVertexProgramTest.class,
+ ShortestPathVertexProgramTest.class,
BulkLoaderVertexProgramTest.class,
BulkDumperVertexProgramTest.class,
CloneVertexProgramTest.class,
@@ -260,6 +264,7 @@ public class ProcessComputerSuite extends AbstractGremlinSuite {
ProjectTest.class,
ProgramTest.class,
PropertiesTest.class,
+ ShortestPathTest.class,
SelectTest.class,
UnfoldTest.class,
ValueMapTest.class,
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathTestHelper.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathTestHelper.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathTestHelper.java
new file mode 100644
index 0000000..7f3aa63
--- /dev/null
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathTestHelper.java
@@ -0,0 +1,100 @@
+/*
+ * 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.tinkerpop.gremlin.process.AbstractGremlinProcessTest;
+import org.apache.tinkerpop.gremlin.process.traversal.P;
+import org.apache.tinkerpop.gremlin.process.traversal.Path;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource;
+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.step.util.MapHelper;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.MutablePath;
+import org.apache.tinkerpop.gremlin.structure.Edge;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.hamcrest.Matchers;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import static org.hamcrest.Matchers.equalTo;
+import static org.hamcrest.Matchers.is;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertThat;
+
+/**
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+public class ShortestPathTestHelper {
+
+ private final AbstractGremlinProcessTest test;
+ private final GraphTraversalSource g;
+ private final Map<String, Vertex> vertexCache;
+ private final Map<Object, Map<Object, Edge>> edgeCache;
+
+ public ShortestPathTestHelper(final AbstractGremlinProcessTest test, final GraphTraversalSource g) {
+ this.test = test;
+ this.g = g;
+ this.vertexCache = new HashMap<>();
+ this.edgeCache = new HashMap<>();
+ }
+
+ public void checkResults(final List<Path> expected, final List<Path> actual) {
+ AbstractGremlinProcessTest.checkResults(expected, __.inject(actual.toArray(new Path[actual.size()])));
+ }
+
+ public Path makePath(final String... names) {
+ return makePath(false, names);
+ }
+
+ public Path makePath(final boolean includeEdges, final String... names) {
+ Path path = ImmutablePath.make();
+ boolean first = true;
+ for (final String name : names) {
+ final Vertex vertex = vertexCache.computeIfAbsent(name, test::convertToVertex);
+ if (!first) {
+ if (includeEdges) {
+ final Object id1 = ((Vertex) path.get(path.size() - 1)).id();
+ final Object id2 = vertex.id();
+ final Edge edge;
+ if (edgeCache.containsKey(id1)) {
+ edge = edgeCache.get(id1).computeIfAbsent(id2, id -> getEdge(id1, id));
+ } else if (edgeCache.containsKey(id2)) {
+ edge = edgeCache.get(id2).computeIfAbsent(id1, id -> getEdge(id, id2));
+ } else {
+ edgeCache.put(id1, new HashMap<>());
+ edgeCache.get(id1).put(id2, edge = getEdge(id1, id2));
+ }
+ path = path.extend(edge, Collections.emptySet());
+ }
+ }
+ path = path.extend(vertex, Collections.emptySet());
+ first = false;
+ }
+ return path;
+ }
+
+ private Edge getEdge(final Object id1, final Object id2) {
+ return g.V(id1)
+ .bothE().filter(__.otherV().hasId(id2))
+ .next();
+ }
+}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgramTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgramTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgramTest.java
new file mode 100644
index 0000000..303299d
--- /dev/null
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgramTest.java
@@ -0,0 +1,297 @@
+/*
+ * 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.tinkerpop.gremlin.LoadGraphWith;
+import org.apache.tinkerpop.gremlin.process.AbstractGremlinProcessTest;
+import org.apache.tinkerpop.gremlin.process.computer.ComputerResult;
+import org.apache.tinkerpop.gremlin.process.traversal.Path;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.structure.Direction;
+import org.junit.Before;
+import org.junit.Test;
+
+import java.util.*;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.CREW;
+import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.GRATEFUL;
+import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.MODERN;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+/**
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+public class ShortestPathVertexProgramTest extends AbstractGremlinProcessTest {
+
+ private ShortestPathTestHelper helper;
+
+ @Before
+ public void initializeHelper() throws Exception {
+ this.helper = new ShortestPathTestHelper(this, g);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void shouldFindAllShortestPathsWithDefaultParameters() throws Exception {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(ShortestPathVertexProgram.build().create(graph)).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS).map(helper::makePath).collect(Collectors.toList());
+ helper.checkResults(expected, shortestPaths);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void shouldFindAllShortestPathsWithEdgesIncluded() throws Exception {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(ShortestPathVertexProgram.build().includeEdges(true).create(graph)).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS).map(p -> helper.makePath(true, p))
+ .collect(Collectors.toList());
+ helper.checkResults(expected, shortestPaths);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void shouldFindOutDirectedShortestPaths() throws Exception {
+ final List<ShortestPathVertexProgram> programs = Arrays.asList(
+ ShortestPathVertexProgram.build().edgeTraversal(__.outE()).create(graph),
+ ShortestPathVertexProgram.build().edgeDirection(Direction.OUT).create(graph));
+ for (final ShortestPathVertexProgram program : programs) {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(program).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> (p[0].equals("marko") && !p[p.length - 1].equals("peter"))
+ || (p[0].equals("vadas") && p.length == 1)
+ || (p[0].equals("lop") && p.length == 1)
+ || (p[0].equals("josh") && Arrays.asList("lop", "josh", "ripple").contains(p[p.length - 1]))
+ || (p[0].equals("ripple") && p.length == 1)
+ || (p[0].equals("peter") && Arrays.asList("lop", "peter").contains(p[p.length - 1])))
+ .map(helper::makePath).collect(Collectors.toList());
+ helper.checkResults(expected, shortestPaths);
+ }
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void shouldFindInDirectedShortestPaths() throws Exception {
+ final List<ShortestPathVertexProgram> programs = Arrays.asList(
+ ShortestPathVertexProgram.build().edgeTraversal(__.inE()).create(graph),
+ ShortestPathVertexProgram.build().edgeDirection(Direction.IN).create(graph));
+ for (final ShortestPathVertexProgram program : programs) {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(program).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> (p[0].equals("marko") && p.length == 1)
+ || (p[0].equals("vadas") && Arrays.asList("marko", "vadas").contains(p[p.length - 1]))
+ || (p[0].equals("lop") && Arrays.asList("marko", "lop", "josh", "peter").contains(p[p.length - 1]))
+ || (p[0].equals("josh") && Arrays.asList("marko", "josh").contains(p[p.length - 1]))
+ || (p[0].equals("ripple") && Arrays.asList("marko", "josh", "ripple").contains(p[p.length - 1]))
+ || (p[0].equals("peter") && p.length == 1))
+ .map(helper::makePath).collect(Collectors.toList());
+ helper.checkResults(expected, shortestPaths);
+ }
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void shouldFindDirectedShortestPathsWithEdgesIncluded() throws Exception {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(ShortestPathVertexProgram.build().edgeTraversal(__.outE()).includeEdges(true).create(graph)).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> (p[0].equals("marko") && !p[p.length - 1].equals("peter"))
+ || (p[0].equals("vadas") && p.length == 1)
+ || (p[0].equals("lop") && p.length == 1)
+ || (p[0].equals("josh") && Arrays.asList("lop", "josh", "ripple").contains(p[p.length - 1]))
+ || (p[0].equals("ripple") && p.length == 1)
+ || (p[0].equals("peter") && Arrays.asList("lop", "peter").contains(p[p.length - 1])))
+ .map(p -> helper.makePath(true, p)).collect(Collectors.toList());
+ helper.checkResults(expected, shortestPaths);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void shouldFindShortestPathsWithStartVertexFilter() throws Exception {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(ShortestPathVertexProgram.build().source(__.has("name", "marko")).create(graph)).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[0].equals("marko")).map(helper::makePath).collect(Collectors.toList());
+ helper.checkResults(expected, shortestPaths);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void shouldFindShortestPathsWithEndVertexFilter() throws Exception {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(ShortestPathVertexProgram.build().target(__.has("name", "marko")).create(graph)).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[p.length - 1].equals("marko")).map(helper::makePath).collect(Collectors.toList());
+ helper.checkResults(expected, shortestPaths);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void shouldFindShortestPathsWithStartEndVertexFilter() throws Exception {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(ShortestPathVertexProgram.build()
+ .source(__.has("name", "marko"))
+ .target(__.hasLabel("software")).create(graph)).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p ->
+ p[0].equals("marko") && Arrays.asList("lop", "ripple").contains(p[p.length - 1]))
+ .map(helper::makePath).collect(Collectors.toList());
+ helper.checkResults(expected, shortestPaths);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void shouldUseCustomDistanceProperty() throws Exception {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(ShortestPathVertexProgram.build()
+ .source(__.has("name", "marko"))
+ .target(__.has("name", "josh"))
+ .distanceProperty("weight").create(graph)).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ assertEquals(1, shortestPaths.size());
+ assertEquals(helper.makePath("marko", "lop", "josh"), shortestPaths.get(0));
+ }
+
+ @Test
+ @LoadGraphWith(CREW)
+ public void shouldFindEqualLengthPaths() throws Exception {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(ShortestPathVertexProgram.build()
+ .edgeTraversal(__.bothE("uses"))
+ .source(__.has("name", "daniel"))
+ .target(__.has("name", "stephen")).create(graph)).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Arrays.asList(
+ helper.makePath("daniel", "gremlin", "stephen"),
+ helper.makePath("daniel", "tinkergraph", "stephen"));
+ helper.checkResults(expected, shortestPaths);
+ }
+
+ @Test
+ @LoadGraphWith(GRATEFUL)
+ public void shouldFindEqualLengthPathsUsingDistanceProperty() throws Exception {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(ShortestPathVertexProgram.build()
+ .edgeTraversal(__.outE("followedBy"))
+ .source(__.has("song", "name", "MIGHT AS WELL"))
+ .target(__.has("song", "name", "MAYBE YOU KNOW HOW I FEEL"))
+ .distanceProperty("weight")
+ .create(graph)).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Arrays.asList(
+ helper.makePath("MIGHT AS WELL", "DRUMS", "MAYBE YOU KNOW HOW I FEEL"),
+ helper.makePath("MIGHT AS WELL", "SHIP OF FOOLS", "MAYBE YOU KNOW HOW I FEEL"));
+ helper.checkResults(expected, shortestPaths);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void shouldRespectMaxDistance() throws Exception {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(ShortestPathVertexProgram.build()
+ .source(__.has("name", "marko"))
+ .maxDistance(1).create(graph)).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[0].equals("marko") && p.length <= 2).map(helper::makePath).collect(Collectors.toList());
+ helper.checkResults(expected, shortestPaths);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void shouldRespectMaxCustomDistance() throws Exception {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(ShortestPathVertexProgram.build()
+ .source(__.has("name", "vadas"))
+ .distanceProperty("weight").maxDistance(1.3).create(graph)).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Stream.concat(Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[0].equals("vadas") &&
+ Arrays.asList("vadas", "marko", "lop", "peter").contains(p[p.length - 1]))
+ .map(helper::makePath),
+ Stream.of(helper.makePath("vadas", "marko", "lop", "josh")))
+ .collect(Collectors.toList());
+ helper.checkResults(expected, shortestPaths);
+ }
+
+ public static String[][] ALL_SHORTEST_PATHS = new String[][]{
+ new String[]{"marko"},
+ new String[]{"marko", "vadas"},
+ new String[]{"marko", "lop"},
+ new String[]{"marko", "lop", "peter"},
+ new String[]{"marko", "josh"},
+ new String[]{"marko", "josh", "ripple"},
+ new String[]{"vadas"},
+ new String[]{"vadas", "marko"},
+ new String[]{"vadas", "marko", "lop"},
+ new String[]{"vadas", "marko", "lop", "peter"},
+ new String[]{"vadas", "marko", "josh", "ripple"},
+ new String[]{"vadas", "marko", "josh"},
+ new String[]{"lop"},
+ new String[]{"lop", "marko"},
+ new String[]{"lop", "marko", "vadas"},
+ new String[]{"lop", "josh"},
+ new String[]{"lop", "josh", "ripple"},
+ new String[]{"lop", "peter"},
+ new String[]{"josh"},
+ new String[]{"josh", "marko"},
+ new String[]{"josh", "marko", "vadas"},
+ new String[]{"josh", "lop"},
+ new String[]{"josh", "lop", "peter"},
+ new String[]{"josh", "ripple"},
+ new String[]{"ripple"},
+ new String[]{"ripple", "josh"},
+ new String[]{"ripple", "josh", "marko"},
+ new String[]{"ripple", "josh", "marko", "vadas"},
+ new String[]{"ripple", "josh", "lop"},
+ new String[]{"ripple", "josh", "lop", "peter"},
+ new String[]{"peter"},
+ new String[]{"peter", "lop"},
+ new String[]{"peter", "lop", "marko"},
+ new String[]{"peter", "lop", "marko", "vadas"},
+ new String[]{"peter", "lop", "josh"},
+ new String[]{"peter", "lop", "josh", "ripple"}
+ };
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ShortestPathTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ShortestPathTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ShortestPathTest.java
new file mode 100644
index 0000000..a55215b
--- /dev/null
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ShortestPathTest.java
@@ -0,0 +1,353 @@
+/*
+ * 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.traversal.step.map;
+
+import org.apache.tinkerpop.gremlin.LoadGraphWith;
+import org.apache.tinkerpop.gremlin.process.AbstractGremlinProcessTest;
+import org.apache.tinkerpop.gremlin.process.GremlinProcessRunner;
+import org.apache.tinkerpop.gremlin.process.computer.search.path.ShortestPathTestHelper;
+import org.apache.tinkerpop.gremlin.process.traversal.Path;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.structure.Direction;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+import java.util.Arrays;
+import java.util.List;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.CREW;
+import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.GRATEFUL;
+import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.MODERN;
+import static org.apache.tinkerpop.gremlin.process.computer.search.path.ShortestPathVertexProgramTest.ALL_SHORTEST_PATHS;
+import static org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ShortestPath.*;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+/**
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+@RunWith(GremlinProcessRunner.class)
+public abstract class ShortestPathTest extends AbstractGremlinProcessTest {
+
+ private ShortestPathTestHelper helper;
+
+ @Before
+ public void initializeHelper() throws Exception {
+ this.helper = new ShortestPathTestHelper(this, g);
+ }
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath();
+
+ public abstract Traversal<Vertex, Path> get_g_V_both_dedup_shortestPath();
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath_edgesIncluded();
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath_directionXINX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath_edgesXoutEX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath_edgesIncluded_edgesXoutEX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath();
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath_targetXhasXname_markoXX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath_targetXvaluesXnameX_isXmarkoXX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath_targetXhasLabelXsoftwareXX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath_targetXhasXname_joshXX_distanceXweightX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXname_danielX_shortestPath_targetXhasXname_stephenXX_edgesXbothEXusesXX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXsong_name_MIGHT_AS_WELLX_shortestPath_targetXhasXsong_name_MAYBE_YOU_KNOW_HOW_I_FEELXX_edgesXoutEXfollowedByXX_distanceXweightX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath_maxDistanceX1X();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXname_vadasX_shortestPath_distanceXweightX_maxDistanceX1_3X();
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS).map(helper::makePath)
+ .collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_both_dedup_shortestPath() {
+ final Traversal<Vertex, Path> traversal = get_g_V_both_dedup_shortestPath();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS).map(helper::makePath)
+ .collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath_edgesIncluded() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath_edgesIncluded();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS).map(p -> helper.makePath(true, p))
+ .collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath_directionXINX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath_directionXINX();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> (p[0].equals("marko") && p.length == 1)
+ || (p[0].equals("vadas") && Arrays.asList("marko", "vadas").contains(p[p.length - 1]))
+ || (p[0].equals("lop") && Arrays.asList("marko", "lop", "josh", "peter").contains(p[p.length - 1]))
+ || (p[0].equals("josh") && Arrays.asList("marko", "josh").contains(p[p.length - 1]))
+ || (p[0].equals("ripple") && Arrays.asList("marko", "josh", "ripple").contains(p[p.length - 1]))
+ || (p[0].equals("peter") && p.length == 1))
+ .map(helper::makePath).collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath_edgesXoutEX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath_edgesXoutEX();
+ printTraversalForm(traversal);
+ checkOutDirectedPaths(false, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath_edgesIncluded_edgesXoutEX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath_edgesIncluded_edgesXoutEX();
+ printTraversalForm(traversal);
+ checkOutDirectedPaths(true, traversal);
+ }
+
+ private void checkOutDirectedPaths(final boolean includeEdges, final Traversal<Vertex, Path> traversal) {
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> (p[0].equals("marko") && !p[p.length - 1].equals("peter"))
+ || (p[0].equals("vadas") && p.length == 1)
+ || (p[0].equals("lop") && p.length == 1)
+ || (p[0].equals("josh") && Arrays.asList("lop", "josh", "ripple").contains(p[p.length - 1]))
+ || (p[0].equals("ripple") && p.length == 1)
+ || (p[0].equals("peter") && Arrays.asList("lop", "peter").contains(p[p.length - 1])))
+ .map(names -> helper.makePath(includeEdges, names)).collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_hasXname_markoX_shortestPath() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXname_markoX_shortestPath();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[0].equals("marko")).map(helper::makePath).collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath_targetXhasXname_markoXX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath_targetXhasXname_markoXX();
+ printTraversalForm(traversal);
+ checkPathsToMarko(traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath_targetXvaluesXnameX_isXmarkoXX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath_targetXvaluesXnameX_isXmarkoXX();
+ printTraversalForm(traversal);
+ checkPathsToMarko(traversal);
+ }
+
+ private void checkPathsToMarko(final Traversal<Vertex, Path> traversal) {
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[p.length - 1].equals("marko")).map(helper::makePath).collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_hasXname_markoX_shortestPath_targetXhasLabelXsoftwareXX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXname_markoX_shortestPath_targetXhasLabelXsoftwareXX();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p ->
+ p[0].equals("marko") && Arrays.asList("lop", "ripple").contains(p[p.length - 1]))
+ .map(helper::makePath).collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_hasXname_markoX_shortestPath_targetXhasXname_joshXX_distanceXweightX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXname_markoX_shortestPath_targetXhasXname_joshXX_distanceXweightX();
+ printTraversalForm(traversal);
+ assertTrue(traversal.hasNext());
+ assertEquals(helper.makePath("marko", "lop", "josh"), traversal.next());
+ assertFalse(traversal.hasNext());
+ }
+
+ @Test
+ @LoadGraphWith(CREW)
+ public void g_V_hasXname_danielX_shortestPath_targetXhasXname_stephenXX_edgesXbothEXusesXX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXname_danielX_shortestPath_targetXhasXname_stephenXX_edgesXbothEXusesXX();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.asList(
+ helper.makePath("daniel", "gremlin", "stephen"),
+ helper.makePath("daniel", "tinkergraph", "stephen"));
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(GRATEFUL)
+ public void g_V_hasXsong_name_MIGHT_AS_WELLX_shortestPath_targetXhasXsong_name_MAYBE_YOU_KNOW_HOW_I_FEELXX_edgesXoutEXfollowedByXX_distanceXweightX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXsong_name_MIGHT_AS_WELLX_shortestPath_targetXhasXsong_name_MAYBE_YOU_KNOW_HOW_I_FEELXX_edgesXoutEXfollowedByXX_distanceXweightX();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.asList(
+ helper.makePath("MIGHT AS WELL", "DRUMS", "MAYBE YOU KNOW HOW I FEEL"),
+ helper.makePath("MIGHT AS WELL", "SHIP OF FOOLS", "MAYBE YOU KNOW HOW I FEEL"));
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_hasXname_markoX_shortestPath_maxDistanceX1X() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXname_markoX_shortestPath_maxDistanceX1X();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[0].equals("marko") && p.length <= 2).map(helper::makePath).collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_hasXname_vadasX_shortestPath_distanceXweightX_maxDistanceX1_3X() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXname_vadasX_shortestPath_distanceXweightX_maxDistanceX1_3X();
+ printTraversalForm(traversal);
+ final List<Path> expected = Stream.concat(Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[0].equals("vadas") &&
+ Arrays.asList("vadas", "marko", "lop", "peter").contains(p[p.length - 1]))
+ .map(helper::makePath),
+ Stream.of(helper.makePath("vadas", "marko", "lop", "josh")))
+ .collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ public static class Traversals extends ShortestPathTest {
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath() {
+ return g.V().shortestPath();
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_both_dedup_shortestPath() {
+ return g.V().both().dedup().shortestPath();
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath_edgesIncluded() {
+ return g.V().shortestPath().with(includeEdges, true);
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath_directionXINX() {
+ return g.V().shortestPath().with(edges, Direction.IN);
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath_edgesXoutEX() {
+ return g.V().shortestPath().with(edges, __.outE());
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath_edgesIncluded_edgesXoutEX() {
+ return g.V().shortestPath().with(includeEdges, true).with(edges, __.outE());
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath() {
+ return g.V().has("name", "marko").shortestPath();
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath_targetXhasXname_markoXX() {
+ return g.V().shortestPath().with(target, __.has("name", "marko"));
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath_targetXvaluesXnameX_isXmarkoXX() {
+ return g.V().shortestPath().with(target, __.<Vertex, String>values("name").is("marko"));
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath_targetXhasLabelXsoftwareXX() {
+ return g.V().has("name", "marko").shortestPath().with(target, __.hasLabel("software"));
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath_targetXhasXname_joshXX_distanceXweightX() {
+ return g.V().has("name", "marko").shortestPath()
+ .with(target, __.has("name","josh"))
+ .with(distance, "weight");
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXname_danielX_shortestPath_targetXhasXname_stephenXX_edgesXbothEXusesXX() {
+ return g.V().has("name", "daniel").shortestPath()
+ .with(target, __.has("name","stephen"))
+ .with(edges, __.bothE("uses"));
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXsong_name_MIGHT_AS_WELLX_shortestPath_targetXhasXsong_name_MAYBE_YOU_KNOW_HOW_I_FEELXX_edgesXoutEXfollowedByXX_distanceXweightX() {
+ return g.V().has("song", "name", "MIGHT AS WELL")
+ .shortestPath().
+ with(target, __.has("song", "name", "MAYBE YOU KNOW HOW I FEEL")).
+ with(edges, __.outE("followedBy")).
+ with(distance, "weight");
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath_maxDistanceX1X() {
+ return g.V().has("name", "marko").shortestPath()
+ .with(maxDistance, 1);
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXname_vadasX_shortestPath_distanceXweightX_maxDistanceX1_3X() {
+ return g.V().has("name", "vadas").shortestPath()
+ .with(distance, "weight")
+ .with(maxDistance, 1.3);
+ }
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/pom.xml
----------------------------------------------------------------------
diff --git a/pom.xml b/pom.xml
index ea42197..a3496f3 100644
--- a/pom.xml
+++ b/pom.xml
@@ -1271,6 +1271,9 @@ limitations under the License.
org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
</include>
<include>
+ org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java
+ </include>
+ <include>
org/apache/tinkerpop/gremlin/process/computer/traversal/TraversalVertexProgram.java
</include>
<!-- traversal -->