Repository: tinkerpop Updated Branches: refs/heads/shortest-path-wip 0f6cdcd91 -> 82f51e493
added max distance tests Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/82f51e49 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/82f51e49 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/82f51e49 Branch: refs/heads/shortest-path-wip Commit: 82f51e4933d9c7238b084cdae7e9c340591c2393 Parents: 0f6cdcd Author: Daniel Kuppitz <[email protected]> Authored: Tue Jun 19 12:16:02 2018 -0700 Committer: Daniel Kuppitz <[email protected]> Committed: Tue Jun 19 12:16:02 2018 -0700 ---------------------------------------------------------------------- .../search/path/ShortestPathVertexProgram.java | 6 ++- .../path/ShortestPathVertexProgramTest.java | 33 +++++++++++++++ .../traversal/step/map/ShortestPathTest.java | 42 ++++++++++++++++++++ 3 files changed, 80 insertions(+), 1 deletion(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/82f51e49/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java index f3a3293..45b221d 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java @@ -459,7 +459,11 @@ public class ShortestPathVertexProgram implements VertexProgram<Triplet<Path, Ed for (final Pair<Number, Set<Path>> pair : paths.values()) { for (final Path path : pair.getValue1()) { if (isEndVertex(vertex)) { - result.add(path); + if (this.distanceEqualsNumberOfHops || + this.maxDistance == null || + NumberHelper.compare(pair.getValue0(), this.maxDistance) <= 0) { + result.add(path); + } } } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/82f51e49/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 index b53d6ae..303299d 100644 --- 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 @@ -29,6 +29,7 @@ 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; @@ -223,6 +224,38 @@ public class ShortestPathVertexProgramTest extends AbstractGremlinProcessTest { 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"}, http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/82f51e49/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 index a9d5ccb..176f201 100644 --- 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 @@ -34,6 +34,7 @@ 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; @@ -83,6 +84,10 @@ public abstract class ShortestPathTest extends AbstractGremlinProcessTest { 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() { @@ -233,6 +238,30 @@ public abstract class ShortestPathTest extends AbstractGremlinProcessTest { 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 @@ -307,5 +336,18 @@ public abstract class ShortestPathTest extends AbstractGremlinProcessTest { 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(MAX_DISTANCE, 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(MAX_DISTANCE, 1.3); + } } } \ No newline at end of file
