You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by dk...@apache.org on 2018/08/01 19:30:09 UTC
[45/50] [abbrv] tinkerpop git commit: TINKERPOP-1990 Implemented
`ShortestPathVertexProgram` and `ShortestPathVertexProgramStep`.
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/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 eab562d..857b3f0 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;
@@ -71,6 +72,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;
@@ -166,6 +168,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,
@@ -194,6 +197,7 @@ public class ProcessComputerSuite extends AbstractGremlinSuite {
// algorithms
PageRankVertexProgramTest.class,
PeerPressureVertexProgramTest.class,
+ ShortestPathVertexProgramTest.class,
BulkLoaderVertexProgramTest.class,
BulkDumperVertexProgramTest.class,
CloneVertexProgramTest.class,
@@ -258,6 +262,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/e1ba81b4/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/e1ba81b4/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/e1ba81b4/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/e1ba81b4/pom.xml
----------------------------------------------------------------------
diff --git a/pom.xml b/pom.xml
index 4badaa1..9c9e27e 100644
--- a/pom.xml
+++ b/pom.xml
@@ -1268,6 +1268,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 -->