Repository: tinkerpop Updated Branches: refs/heads/TINKERPOP-1990 0324c820b -> 6b52a8c0e (forced update)
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/6b52a8c0/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/6b52a8c0/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/6b52a8c0/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/6b52a8c0/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/6b52a8c0/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/6b52a8c0/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/6b52a8c0/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/6b52a8c0/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/6b52a8c0/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/6b52a8c0/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/6b52a8c0/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 --> http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/6b52a8c0/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/SparkHadoopGraphProvider.java ---------------------------------------------------------------------- diff --git a/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/SparkHadoopGraphProvider.java b/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/SparkHadoopGraphProvider.java index 2f727c8..2eebac1 100644 --- a/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/SparkHadoopGraphProvider.java +++ b/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/SparkHadoopGraphProvider.java @@ -43,6 +43,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.map.ConnectedComponen import org.apache.tinkerpop.gremlin.process.traversal.step.map.PageRankTest; import org.apache.tinkerpop.gremlin.process.traversal.step.map.PeerPressureTest; import org.apache.tinkerpop.gremlin.process.traversal.step.map.ProgramTest; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.ShortestPathTest; import org.apache.tinkerpop.gremlin.spark.structure.Spark; import org.apache.tinkerpop.gremlin.spark.structure.io.PersistedOutputRDD; import org.apache.tinkerpop.gremlin.spark.structure.io.SparkContextStorageCheck; @@ -117,6 +118,7 @@ public class SparkHadoopGraphProvider extends AbstractFileGraphProvider { !test.equals(ProgramTest.Traversals.class) && !test.equals(PageRankTest.Traversals.class) && !test.equals(ConnectedComponentTest.Traversals.class) && + !test.equals(ShortestPathTest.Traversals.class) && !test.equals(PeerPressureTest.Traversals.class) && !test.equals(FileSystemStorageCheck.class) && !testMethodName.equals("shouldSupportJobChaining") && // GraphComputerTest.shouldSupportJobChaining
