http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/823e9354/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/823e9354/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/823e9354/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/823e9354/pom.xml ---------------------------------------------------------------------- diff --git a/pom.xml b/pom.xml index 13dd988..7f2aa87 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 -->