[27/28] tinkerpop git commit: Implemented `ShortestPathVertexProgram` and `ShortestPathVertexProgramStep`.

[dk...@apache.org]

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/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..71f4469
--- /dev/null
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ShortestPathTest.java
@@ -0,0 +1,310 @@
+/*
+ * 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 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.ShortestPathVertexProgramStep.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();
+
+    @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);
+    }
+
+    public static class Traversals extends ShortestPathTest {
+
+        @Override
+        public Traversal<Vertex, Path> get_g_V_shortestPath() {
+            return g.V().shortestPath().dedup();
+        }
+
+        @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(INCLUDE_EDGES, 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(INCLUDE_EDGES, 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");
+        }
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/pom.xml
----------------------------------------------------------------------
diff --git a/pom.xml b/pom.xml
index 199a4ba..e5efd7f 100644
--- a/pom.xml
+++ b/pom.xml
@@ -1222,6 +1222,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 -->