tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dkupp...@apache.org
Subject [49/50] [abbrv] tinkerpop git commit: TINKERPOP-1990 Implemented `ShortestPathVertexProgram` and `ShortestPathVertexProgramStep`.
Date Sun, 29 Jul 2018 17:22:34 GMT
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b003528c/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 b224c8b..57b05bd 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;
@@ -70,6 +71,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.map.ProfileTest;
 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.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;
@@ -163,6 +165,7 @@ public class ProcessComputerSuite extends AbstractGremlinSuite {
             ProjectTest.Traversals.class,
             ProgramTest.Traversals.class,
             PropertiesTest.Traversals.class,
+            ShortestPathTest.Traversals.class,
             SelectTest.Traversals.class,
             UnfoldTest.Traversals.class,
             ValueMapTest.Traversals.class,
@@ -190,6 +193,7 @@ public class ProcessComputerSuite extends AbstractGremlinSuite {
             // algorithms
             PageRankVertexProgramTest.class,
             PeerPressureVertexProgramTest.class,
+            ShortestPathVertexProgramTest.class,
             BulkLoaderVertexProgramTest.class,
             BulkDumperVertexProgramTest.class,
             CloneVertexProgramTest.class,
@@ -254,6 +258,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/b003528c/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/b003528c/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/b003528c/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..bf4a5b7
--- /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().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(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/b003528c/pom.xml
----------------------------------------------------------------------
diff --git a/pom.xml b/pom.xml
index c279851..6d48391 100644
--- a/pom.xml
+++ b/pom.xml
@@ -1282,6 +1282,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 -->


Mime
View raw message