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/06/01 17:42:34 UTC
[28/28] tinkerpop git commit: Implemented `ShortestPathVertexProgram`
and `ShortestPathVertexProgramStep`.
Implemented `ShortestPathVertexProgram` and `ShortestPathVertexProgramStep`.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/a373c8b2
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/a373c8b2
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/a373c8b2
Branch: refs/heads/shortest-path-wip
Commit: a373c8b2d621e4ccd6fc0534f7b306e38949e71f
Parents: fc0b2dc
Author: Daniel Kuppitz <da...@hotmail.com>
Authored: Wed May 23 08:46:34 2018 -0400
Committer: Daniel Kuppitz <da...@hotmail.com>
Committed: Fri Jun 1 10:41:20 2018 -0700
----------------------------------------------------------------------
.../tinkerpop/gremlin/jsr223/CoreImports.java | 4 +
.../search/path/ShortestPathVertexProgram.java | 566 +++++++++++++++++++
.../step/map/ShortestPathVertexProgramStep.java | 259 +++++++++
.../gremlin/process/remote/RemoteGraph.java | 8 +
.../gremlin/process/traversal/Traversal.java | 16 +-
.../traversal/dsl/graph/GraphTraversal.java | 20 +
.../traversal/lambda/ColumnTraversal.java | 8 +
.../traversal/lambda/ConstantTraversal.java | 9 +-
.../traversal/lambda/ElementValueTraversal.java | 10 +-
.../traversal/lambda/IdentityTraversal.java | 7 +-
.../process/traversal/lambda/LoopTraversal.java | 6 +
.../traversal/lambda/TokenTraversal.java | 8 +
.../process/traversal/lambda/TrueTraversal.java | 5 +
.../structure/io/graphson/GraphSONModule.java | 2 +-
.../traversal/dsl/graph/GraphTraversalTest.java | 2 +-
.../Process/Traversal/GraphTraversal.cs | 9 +
.../lib/process/graph-traversal.js | 10 +
.../gremlin_python/process/graph_traversal.py | 4 +
.../tinkerpop/gremlin/AbstractGremlinTest.java | 4 +
.../gremlin/process/ProcessComputerSuite.java | 5 +
.../search/path/ShortestPathTestHelper.java | 72 +++
.../path/ShortestPathVertexProgramTest.java | 264 +++++++++
.../traversal/step/map/ShortestPathTest.java | 310 ++++++++++
pom.xml | 3 +
24 files changed, 1599 insertions(+), 12 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java
index 368b92d..d853b8f 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java
@@ -46,9 +46,11 @@ import org.apache.tinkerpop.gremlin.process.computer.clustering.peerpressure.Clu
import org.apache.tinkerpop.gremlin.process.computer.clustering.peerpressure.PeerPressureVertexProgram;
import org.apache.tinkerpop.gremlin.process.computer.ranking.pagerank.PageRankMapReduce;
import org.apache.tinkerpop.gremlin.process.computer.ranking.pagerank.PageRankVertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.search.path.ShortestPathVertexProgram;
import org.apache.tinkerpop.gremlin.process.computer.traversal.MemoryTraversalSideEffects;
import org.apache.tinkerpop.gremlin.process.computer.traversal.TraversalVertexProgram;
import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.PageRankVertexProgramStep;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ShortestPathVertexProgramStep;
import org.apache.tinkerpop.gremlin.process.computer.traversal.strategy.decoration.VertexProgramStrategy;
import org.apache.tinkerpop.gremlin.process.computer.traversal.strategy.optimization.GraphFilterStrategy;
import org.apache.tinkerpop.gremlin.process.remote.RemoteConnection;
@@ -262,6 +264,8 @@ public final class CoreImports {
CLASS_IMPORTS.add(PageRankMapReduce.class);
CLASS_IMPORTS.add(PageRankVertexProgram.class);
CLASS_IMPORTS.add(PageRankVertexProgramStep.PageRank.class);
+ CLASS_IMPORTS.add(ShortestPathVertexProgram.class);
+ CLASS_IMPORTS.add(ShortestPathVertexProgramStep.ShortestPath.class);
CLASS_IMPORTS.add(GraphFilterStrategy.class);
CLASS_IMPORTS.add(TraversalVertexProgram.class);
CLASS_IMPORTS.add(VertexProgramStrategy.class);
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/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
new file mode 100644
index 0000000..37d647e
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java
@@ -0,0 +1,566 @@
+/*
+ * 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.commons.configuration.Configuration;
+import org.apache.tinkerpop.gremlin.process.computer.*;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.TraversalVertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ProgramVertexProgramStep;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.VertexProgramStep;
+import org.apache.tinkerpop.gremlin.process.computer.util.AbstractVertexProgramBuilder;
+import org.apache.tinkerpop.gremlin.process.traversal.*;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.lambda.ConstantTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.lambda.ElementValueTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.lambda.IdentityTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.ImmutablePath;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.IndexedTraverserSet;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
+import org.apache.tinkerpop.gremlin.process.traversal.util.PureTraversal;
+import org.apache.tinkerpop.gremlin.structure.*;
+import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
+import org.apache.tinkerpop.gremlin.util.NumberHelper;
+import org.javatuples.Pair;
+import org.javatuples.Triplet;
+
+import java.util.*;
+import java.util.function.Function;
+
+/**
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+public class ShortestPathVertexProgram implements VertexProgram<Triplet<Path, Edge, Number>> {
+
+ public static final String SHORTEST_PATHS = "gremlin.shortestPathVertexProgram.shortestPaths";
+
+ private static final String SOURCE_VERTEX_FILTER = "gremlin.shortestPathVertexProgram.sourceVertexFilter";
+ private static final String TARGET_VERTEX_FILTER = "gremlin.shortestPathVertexProgram.targetVertexFilter";
+ private static final String EDGE_TRAVERSAL = "gremlin.shortestPathVertexProgram.edgeTraversal";
+ private static final String DISTANCE_TRAVERSAL = "gremlin.shortestPathVertexProgram.distanceTraversal";
+ private static final String MAX_DISTANCE = "gremlin.shortestPathVertexProgram.maxDistance";
+ private static final String INCLUDE_EDGES = "gremlin.shortestPathVertexProgram.includeEdges";
+
+ private static final String STATE = "gremlin.shortestPathVertexProgram.state";
+ private static final String PATHS = "gremlin.shortestPathVertexProgram.paths";
+ private static final String VOTE_TO_HALT = "gremlin.shortestPathVertexProgram.voteToHalt";
+
+ public static final PureTraversal<Vertex, ?> DEFAULT_VERTEX_FILTER_TRAVERSAL = new PureTraversal<>(new IdentityTraversal<>());
+ public static final PureTraversal<Vertex, Edge> DEFAULT_EDGE_TRAVERSAL = new PureTraversal<>(__.bothE().asAdmin());
+ public static final PureTraversal<Edge, Number> DEFAULT_DISTANCE_TRAVERSAL = new PureTraversal<>(new ConstantTraversal<>(1));
+
+ private TraverserSet<Vertex> haltedTraversers;
+ private IndexedTraverserSet<Vertex, Vertex> haltedTraversersIndex;
+ private PureTraversal<?, ?> traversal;
+ private PureTraversal<Vertex, ?> sourceVertexFilterTraversal = DEFAULT_VERTEX_FILTER_TRAVERSAL.clone();
+ private PureTraversal<Vertex, ?> targetVertexFilterTraversal = DEFAULT_VERTEX_FILTER_TRAVERSAL.clone();
+ private PureTraversal<Vertex, Edge> edgeTraversal = DEFAULT_EDGE_TRAVERSAL.clone();
+ private PureTraversal<Edge, Number> distanceTraversal = DEFAULT_DISTANCE_TRAVERSAL.clone();
+ private Step<Vertex, Path> programStep;
+ private Number maxDistance;
+ private boolean distanceEqualsNumberOfHops;
+ private boolean includeEdges;
+ private boolean standalone;
+
+ private static final Set<VertexComputeKey> VERTEX_COMPUTE_KEYS = new HashSet<>(Arrays.asList(
+ VertexComputeKey.of(PATHS, true),
+ VertexComputeKey.of(TraversalVertexProgram.HALTED_TRAVERSERS, false)));
+
+ private final Set<MemoryComputeKey> memoryComputeKeys = new HashSet<>(Arrays.asList(
+ MemoryComputeKey.of(VOTE_TO_HALT, Operator.and, false, true),
+ MemoryComputeKey.of(STATE, Operator.assign, true, true)));
+
+ private ShortestPathVertexProgram() {
+
+ }
+
+ @Override
+ public void loadState(final Graph graph, final Configuration configuration) {
+
+ if (configuration.containsKey(SOURCE_VERTEX_FILTER))
+ this.sourceVertexFilterTraversal = PureTraversal.loadState(configuration, SOURCE_VERTEX_FILTER, graph);
+
+ if (configuration.containsKey(TARGET_VERTEX_FILTER))
+ this.targetVertexFilterTraversal = PureTraversal.loadState(configuration, TARGET_VERTEX_FILTER, graph);
+
+ if (configuration.containsKey(EDGE_TRAVERSAL))
+ this.edgeTraversal = PureTraversal.loadState(configuration, EDGE_TRAVERSAL, graph);
+
+ if (configuration.containsKey(DISTANCE_TRAVERSAL))
+ this.distanceTraversal = PureTraversal.loadState(configuration, DISTANCE_TRAVERSAL, graph);
+
+ if (configuration.containsKey(MAX_DISTANCE))
+ this.maxDistance = (Number) configuration.getProperty(MAX_DISTANCE);
+
+ this.distanceEqualsNumberOfHops = this.distanceTraversal.equals(DEFAULT_DISTANCE_TRAVERSAL);
+ this.includeEdges = configuration.getBoolean(INCLUDE_EDGES, false);
+ this.standalone = !configuration.containsKey(VertexProgramStep.ROOT_TRAVERSAL);
+
+ if (!this.standalone) {
+ this.traversal = PureTraversal.loadState(configuration, VertexProgramStep.ROOT_TRAVERSAL, graph);
+ final String programStepId = configuration.getString(ProgramVertexProgramStep.STEP_ID);
+ for (final Step step : this.traversal.get().getSteps()) {
+ if (step.getId().equals(programStepId)) {
+ //noinspection unchecked
+ this.programStep = step;
+ break;
+ }
+ }
+ }
+
+ this.haltedTraversers = TraversalVertexProgram.loadHaltedTraversers(configuration);
+ this.memoryComputeKeys.add(MemoryComputeKey.of(SHORTEST_PATHS, Operator.addAll, true, !standalone));
+ }
+
+ @Override
+ public void storeState(final Configuration configuration) {
+ VertexProgram.super.storeState(configuration);
+ this.sourceVertexFilterTraversal.storeState(configuration, SOURCE_VERTEX_FILTER);
+ this.targetVertexFilterTraversal.storeState(configuration, TARGET_VERTEX_FILTER);
+ this.edgeTraversal.storeState(configuration, EDGE_TRAVERSAL);
+ this.distanceTraversal.storeState(configuration, DISTANCE_TRAVERSAL);
+ configuration.setProperty(INCLUDE_EDGES, this.includeEdges);
+ if (this.maxDistance != null)
+ configuration.setProperty(MAX_DISTANCE, maxDistance);
+ if (this.traversal != null) {
+ this.traversal.storeState(configuration, ProgramVertexProgramStep.ROOT_TRAVERSAL);
+ configuration.setProperty(ProgramVertexProgramStep.STEP_ID, this.programStep.getId());
+ }
+ }
+
+ @Override
+ public Set<VertexComputeKey> getVertexComputeKeys() {
+ return VERTEX_COMPUTE_KEYS;
+ }
+
+ @Override
+ public Set<MemoryComputeKey> getMemoryComputeKeys() {
+ return memoryComputeKeys;
+ }
+
+ @Override
+ public Set<MessageScope> getMessageScopes(final Memory memory) {
+ return Collections.emptySet();
+ }
+
+ @Override
+ public VertexProgram<Triplet<Path, Edge, Number>> clone() {
+ try {
+ final ShortestPathVertexProgram clone = (ShortestPathVertexProgram) super.clone();
+ if (null != this.edgeTraversal)
+ clone.edgeTraversal = this.edgeTraversal.clone();
+ if (null != this.sourceVertexFilterTraversal)
+ clone.sourceVertexFilterTraversal = this.sourceVertexFilterTraversal.clone();
+ if (null != this.targetVertexFilterTraversal)
+ clone.targetVertexFilterTraversal = this.targetVertexFilterTraversal.clone();
+ if (null != this.distanceTraversal)
+ clone.distanceTraversal = this.distanceTraversal.clone();
+ if (null != this.traversal) {
+ clone.traversal = this.traversal.clone();
+ for (final Step step : clone.traversal.get().getSteps()) {
+ if (step.getId().equals(this.programStep.getId())) {
+ //noinspection unchecked
+ clone.programStep = step;
+ break;
+ }
+ }
+ }
+ return clone;
+ } catch (final CloneNotSupportedException e) {
+ throw new IllegalStateException(e.getMessage(), e);
+ }
+ }
+
+ @Override
+ public GraphComputer.ResultGraph getPreferredResultGraph() {
+ return GraphComputer.ResultGraph.ORIGINAL;
+ }
+
+ @Override
+ public GraphComputer.Persist getPreferredPersist() {
+ return GraphComputer.Persist.NOTHING;
+ }
+
+ @Override
+ public void setup(final Memory memory) {
+
+ this.haltedTraversersIndex = new IndexedTraverserSet<>(v -> v);
+ for (final Traverser.Admin<Vertex> traverser : this.haltedTraversers) {
+ this.haltedTraversersIndex.add(traverser.split());
+ }
+ this.haltedTraversers.clear();
+
+ memory.set(VOTE_TO_HALT, true);
+ memory.set(STATE, State.SEARCH);
+ }
+
+ @Override
+ public void execute(final Vertex vertex, final Messenger<Triplet<Path, Edge, Number>> messenger, final Memory memory) {
+
+ switch (memory.<State>get(STATE)) {
+
+ case COLLECT_PATHS:
+ collectShortestPaths(vertex, memory);
+ return;
+
+ case UPDATE_HALTED_TRAVERSERS:
+ updateHaltedTraversers(vertex, memory);
+ return;
+ }
+
+ boolean voteToHalt = true;
+
+ if (memory.isInitialIteration()) {
+
+ copyHaltedTraversersFromMemory(vertex);
+
+ if (!isStartVertex(vertex)) return;
+
+ final Map<Vertex, Pair<Number, Set<Path>>> paths = new HashMap<>();
+ final Path path;
+ final Set<Path> pathSet = new HashSet<>();
+
+ pathSet.add(path = makePath(vertex));
+ paths.put(vertex, Pair.with(0, pathSet));
+
+ vertex.property(VertexProperty.Cardinality.single, PATHS, paths);
+
+ processEdges(vertex, path, 0, messenger);
+
+ voteToHalt = false;
+
+ } else {
+
+ final Map<Vertex, Pair<Number, Set<Path>>> paths =
+ vertex.<Map<Vertex, Pair<Number, Set<Path>>>>property(PATHS).orElseGet(HashMap::new);
+ final Iterator<Triplet<Path, Edge, Number>> iterator = messenger.receiveMessages();
+
+ while (iterator.hasNext()) {
+
+ final Triplet<Path, Edge, Number> triplet = iterator.next();
+ final Path sourcePath = triplet.getValue0();
+ final Number distance = triplet.getValue2();
+ final Vertex sourceVertex = sourcePath.get(0);
+
+ Path newPath = null;
+
+ if (paths.containsKey(sourceVertex)) {
+
+ final Number currentShortestDistance = paths.get(sourceVertex).getValue0();
+ final int cmp = NumberHelper.compare(distance, currentShortestDistance);
+
+ if (cmp <= 0) {
+ newPath = extendPath(sourcePath, triplet.getValue1(), vertex);
+ if (cmp < 0) {
+ final Set<Path> pathSet = new HashSet<>();
+ pathSet.add(newPath);
+ paths.put(sourceVertex, Pair.with(distance, pathSet));
+ } else {
+ paths.get(sourceVertex).getValue1().add(newPath);
+ }
+ }
+ } else if (!exceedsMaxDistance(distance)) {
+ final Set<Path> pathSet = new HashSet<>();
+ pathSet.add(newPath = extendPath(sourcePath, triplet.getValue1(), vertex));
+ paths.put(sourceVertex, Pair.with(distance, pathSet));
+ }
+
+ if (newPath != null) {
+ vertex.property(VertexProperty.Cardinality.single, PATHS, paths);
+ processEdges(vertex, newPath, distance, messenger);
+ voteToHalt = false;
+ }
+ }
+ }
+
+ memory.add(VOTE_TO_HALT, voteToHalt);
+ }
+
+ @Override
+ public boolean terminate(final Memory memory) {
+ if (memory.isInitialIteration() && this.haltedTraversersIndex != null) {
+ this.haltedTraversersIndex.clear();
+ }
+ final boolean voteToHalt = memory.get(VOTE_TO_HALT);
+ if (voteToHalt) {
+ final State state = memory.get(STATE);
+ if (state.equals(State.COLLECT_PATHS)) {
+ if (this.standalone) return true;
+ memory.set(STATE, State.UPDATE_HALTED_TRAVERSERS);
+ return false;
+ }
+ if (state.equals(State.UPDATE_HALTED_TRAVERSERS)) return true;
+ if (state.equals(State.COLLECT_PATHS)) memory.set(STATE, State.UPDATE_HALTED_TRAVERSERS);
+ else memory.set(STATE, State.COLLECT_PATHS);
+ return false;
+ } else {
+ memory.set(VOTE_TO_HALT, true);
+ return false;
+ }
+ }
+
+ @Override
+ public String toString() {
+
+ final List<String> options = new ArrayList<>();
+ final Function<String, String> shortName = name -> name.substring(name.lastIndexOf(".") + 1);
+
+ if (!this.sourceVertexFilterTraversal.equals(DEFAULT_VERTEX_FILTER_TRAVERSAL)) {
+ options.add(shortName.apply(SOURCE_VERTEX_FILTER) + "=" + this.sourceVertexFilterTraversal.get());
+ }
+
+ if (!this.targetVertexFilterTraversal.equals(DEFAULT_VERTEX_FILTER_TRAVERSAL)) {
+ options.add(shortName.apply(TARGET_VERTEX_FILTER) + "=" + this.targetVertexFilterTraversal.get());
+ }
+
+ if (!this.edgeTraversal.equals(DEFAULT_EDGE_TRAVERSAL)) {
+ options.add(shortName.apply(EDGE_TRAVERSAL) + "=" + this.edgeTraversal.get());
+ }
+
+ if (!this.distanceTraversal.equals(DEFAULT_DISTANCE_TRAVERSAL)) {
+ options.add(shortName.apply(DISTANCE_TRAVERSAL) + "=" + this.distanceTraversal.get());
+ }
+
+ options.add(shortName.apply(INCLUDE_EDGES) + "=" + this.includeEdges);
+
+ return StringFactory.vertexProgramString(this, String.join(", ", options));
+ }
+
+ //////////////////////////////
+
+ private void copyHaltedTraversersFromMemory(final Vertex vertex) {
+ final Collection<Traverser.Admin<Vertex>> traversers = this.haltedTraversersIndex.get(vertex);
+ if (traversers != null) {
+ final TraverserSet<Vertex> newHaltedTraversers = new TraverserSet<>();
+ newHaltedTraversers.addAll(traversers);
+ vertex.property(VertexProperty.Cardinality.single, TraversalVertexProgram.HALTED_TRAVERSERS, newHaltedTraversers);
+ }
+ }
+
+
+ private static Path makePath(final Vertex newVertex) {
+ return extendPath(null, newVertex);
+ }
+
+ private static Path extendPath(final Path currentPath, final Element... elements) {
+ Path result = ImmutablePath.make();
+ if (currentPath != null) {
+ for (final Object o : currentPath.objects()) {
+ result = result.extend(o, Collections.emptySet());
+ }
+ }
+ for (final Element element : elements) {
+ if (element != null) result = result.extend(element, Collections.emptySet());
+ }
+ return result;
+ }
+
+ private boolean isStartVertex(final Vertex vertex) {
+ if (this.standalone) {
+ final Traversal.Admin<Vertex, ?> filterTraversal = this.sourceVertexFilterTraversal.getPure();
+ filterTraversal.addStart(filterTraversal.getTraverserGenerator().generate(vertex, filterTraversal.getStartStep(), 1));
+ return filterTraversal.hasNext();
+ }
+ if (vertex.property(TraversalVertexProgram.HALTED_TRAVERSERS).isPresent()) return true;
+ for (final Traverser<?> traverser : this.haltedTraversers) {
+ if (vertex.equals(traverser.get())) return true;
+ }
+ return false;
+ }
+
+ private boolean isEndVertex(final Vertex vertex, final Vertex startVertex) {
+ final Traversal.Admin<Vertex, ?> filterTraversal = this.targetVertexFilterTraversal.getPure();
+ //noinspection unchecked
+ final Step<Vertex, Vertex> startStep = (Step<Vertex, Vertex>) filterTraversal.getStartStep();
+ if (this.standalone) {
+ filterTraversal.addStart(filterTraversal.getTraverserGenerator().generate(vertex, startStep, 1));
+ } else {
+ final Property<TraverserSet<Vertex>> haltedTraversers = startVertex.property(TraversalVertexProgram.HALTED_TRAVERSERS);
+ if (haltedTraversers.isPresent()) {
+ for (final Traverser.Admin<Vertex> traverser : haltedTraversers.value()) {
+ filterTraversal.addStart(traverser.split(vertex, startStep));
+ }
+ }
+ }
+ return filterTraversal.hasNext();
+ }
+
+ private void processEdges(final Vertex vertex, final Path currentPath, final Number currentDistance,
+ final Messenger<Triplet<Path, Edge, Number>> messenger) {
+
+ final Traversal.Admin<Vertex, Edge> edgeTraversal = this.edgeTraversal.getPure();
+ edgeTraversal.addStart(edgeTraversal.getTraverserGenerator().generate(vertex, edgeTraversal.getStartStep(), 1));
+
+ while (edgeTraversal.hasNext()) {
+ final Edge edge = edgeTraversal.next();
+ final Number distance = getDistance(edge);
+
+ Vertex otherV = edge.inVertex();
+ if (otherV.equals(vertex))
+ otherV = edge.outVertex();
+
+ if (!currentPath.objects().contains(otherV)) {
+ messenger.sendMessage(MessageScope.Global.of(otherV),
+ Triplet.with(currentPath, this.includeEdges ? edge : null,
+ NumberHelper.add(currentDistance, distance)));
+ }
+ }
+ }
+
+ private void updateHaltedTraversers(final Vertex vertex, final Memory memory) {
+ if (isStartVertex(vertex)) {
+ final List<Path> paths = memory.get(SHORTEST_PATHS);
+ if (vertex.property(TraversalVertexProgram.HALTED_TRAVERSERS).isPresent()) {
+ final TraverserSet<Vertex> haltedTraversers = vertex.value(TraversalVertexProgram.HALTED_TRAVERSERS);
+ final TraverserSet<Path> newHaltedTraversers = new TraverserSet<>();
+ for (final Traverser.Admin<Vertex> traverser : haltedTraversers) {
+ final Vertex v = traverser.get();
+ for (final Path path : paths) {
+ if (path.get(0).equals(v)) {
+ newHaltedTraversers.add(traverser.split(path, this.programStep));
+ }
+ }
+ }
+ vertex.property(VertexProperty.Cardinality.single, TraversalVertexProgram.HALTED_TRAVERSERS, newHaltedTraversers);
+ }
+ }
+ }
+
+ private Number getDistance(final Edge edge) {
+ if (this.distanceEqualsNumberOfHops) return 1;
+ final Traversal.Admin<Edge, Number> traversal = this.distanceTraversal.getPure();
+ traversal.addStart(traversal.getTraverserGenerator().generate(edge, traversal.getStartStep(), 1));
+ return traversal.tryNext().orElse(0);
+ }
+
+ private boolean exceedsMaxDistance(final Number distance) {
+ // This method is used to stop the message sending for paths that exceed the specified maximum distance. Since
+ // custom distances can be negative, this method should only return true if the distance is calculated based on
+ // the number of hops.
+ return this.distanceEqualsNumberOfHops && this.maxDistance != null
+ && NumberHelper.compare(distance, this.maxDistance) > 0;
+ }
+
+ private void collectShortestPaths(final Vertex vertex, final Memory memory) {
+
+ final VertexProperty<Map<Vertex, Pair<Number, Set<Path>>>> pathProperty = vertex.property(PATHS);
+
+ if (pathProperty.isPresent()) {
+
+ final Map<Vertex, Pair<Number, Set<Path>>> paths = pathProperty.value();
+ final List<Path> result = new ArrayList<>();
+
+ for (final Pair<Number, Set<Path>> pair : paths.values()) {
+ for (final Path path : pair.getValue1()) {
+ if (isEndVertex(path.get(path.size() - 1), path.get(0))) {
+ result.add(path);
+ }
+ }
+ }
+
+ pathProperty.remove();
+
+ memory.add(SHORTEST_PATHS, result);
+ }
+ }
+
+ //////////////////////////////
+
+ public static Builder build() {
+ return new Builder();
+ }
+
+ @SuppressWarnings("WeakerAccess")
+ public static final class Builder extends AbstractVertexProgramBuilder<Builder> {
+
+
+ private Builder() {
+ super(ShortestPathVertexProgram.class);
+ }
+
+ public Builder source(final Traversal<Vertex, ?> sourceVertexFilter) {
+ if (null == sourceVertexFilter) throw Graph.Exceptions.argumentCanNotBeNull("sourceVertexFilter");
+ PureTraversal.storeState(this.configuration, SOURCE_VERTEX_FILTER, sourceVertexFilter.asAdmin());
+ return this;
+ }
+
+ public Builder target(final Traversal<Vertex, ?> targetVertexFilter) {
+ if (null == targetVertexFilter) throw Graph.Exceptions.argumentCanNotBeNull("targetVertexFilter");
+ PureTraversal.storeState(this.configuration, TARGET_VERTEX_FILTER, targetVertexFilter.asAdmin());
+ return this;
+ }
+
+ public Builder edgeDirection(final Direction direction) {
+ if (null == direction) throw Graph.Exceptions.argumentCanNotBeNull("direction");
+ return edgeTraversal(__.toE(direction));
+ }
+
+ public Builder edgeTraversal(final Traversal<Vertex, Edge> edgeTraversal) {
+ if (null == edgeTraversal) throw Graph.Exceptions.argumentCanNotBeNull("edgeTraversal");
+ PureTraversal.storeState(this.configuration, EDGE_TRAVERSAL, edgeTraversal.asAdmin());
+ return this;
+ }
+
+ public Builder distanceProperty(final String distance) {
+ //noinspection unchecked
+ return distance != null
+ ? distanceTraversal((Traversal) new ElementValueTraversal<>(distance))
+ : distanceTraversal(DEFAULT_DISTANCE_TRAVERSAL.getPure());
+ }
+
+ public Builder distanceTraversal(final Traversal<Edge, Number> distanceTraversal) {
+ if (null == distanceTraversal) throw Graph.Exceptions.argumentCanNotBeNull("distanceTraversal");
+ PureTraversal.storeState(this.configuration, DISTANCE_TRAVERSAL, distanceTraversal.asAdmin());
+ return this;
+ }
+
+ public Builder maxDistance(final Number distance) { // todo: implement test
+ if (null != distance)
+ this.configuration.setProperty(MAX_DISTANCE, distance);
+ else
+ this.configuration.clearProperty(MAX_DISTANCE);
+ return this;
+ }
+
+ public Builder includeEdges(final boolean include) {
+ this.configuration.setProperty(INCLUDE_EDGES, include);
+ return this;
+ }
+ }
+
+ ////////////////////////////
+
+ @Override
+ public Features getFeatures() {
+ return new Features() {
+ @Override
+ public boolean requiresGlobalMessageScopes() {
+ return true;
+ }
+
+ @Override
+ public boolean requiresVertexPropertyAddition() {
+ return true;
+ }
+ };
+ }
+
+ private enum State {
+ SEARCH, COLLECT_PATHS, UPDATE_HALTED_TRAVERSERS
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPathVertexProgramStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPathVertexProgramStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPathVertexProgramStep.java
new file mode 100644
index 0000000..d4b165f
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPathVertexProgramStep.java
@@ -0,0 +1,259 @@
+/*
+ * 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.traversal.step.map;
+
+import org.apache.tinkerpop.gremlin.process.computer.*;
+import org.apache.tinkerpop.gremlin.process.computer.search.path.ShortestPathVertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.TraversalVertexProgram;
+import org.apache.tinkerpop.gremlin.process.traversal.*;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.*;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.Parameters;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
+import org.apache.tinkerpop.gremlin.process.traversal.util.PureTraversal;
+import org.apache.tinkerpop.gremlin.structure.Direction;
+import org.apache.tinkerpop.gremlin.structure.Edge;
+import org.apache.tinkerpop.gremlin.structure.Graph;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
+import org.apache.tinkerpop.gremlin.util.Serializer;
+
+import java.io.IOException;
+import java.util.*;
+
+/**
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+public final class ShortestPathVertexProgramStep extends VertexProgramStep implements TraversalParent, Configuring {
+
+ private Parameters parameters = new Parameters();
+ private PureTraversal<Vertex, ?> targetVertexFilter = ShortestPathVertexProgram.DEFAULT_VERTEX_FILTER_TRAVERSAL.clone();
+ private PureTraversal<Vertex, Edge> edgeTraversal = ShortestPathVertexProgram.DEFAULT_EDGE_TRAVERSAL.clone();
+ private PureTraversal<Edge, Number> distanceTraversal = ShortestPathVertexProgram.DEFAULT_DISTANCE_TRAVERSAL.clone();
+ private Number maxDistance;
+ private boolean includeEdges;
+
+ public ShortestPathVertexProgramStep(final Traversal.Admin<?, ?> traversal) {
+ super(traversal);
+ }
+
+ private void setTargetVertexFilter(final Traversal filterTraversal) {
+ this.targetVertexFilter = new PureTraversal<>(this.integrateChild(filterTraversal.asAdmin()));
+ }
+
+ private void setEdgeTraversal(final Traversal edgeTraversal) {
+ this.edgeTraversal = new PureTraversal<>(this.integrateChild(edgeTraversal.asAdmin()));
+ }
+
+ private void setDistanceTraversal(final Traversal distanceTraversal) {
+ this.distanceTraversal = new PureTraversal<>(this.integrateChild(distanceTraversal.asAdmin()));
+ }
+
+ private void setMaxDistance(final Number maxDistance) {
+ this.maxDistance = maxDistance;
+ }
+
+ private void setIncludeEdges(final boolean includeEdges) {
+ this.includeEdges = includeEdges;
+ }
+
+ @Override
+ public void configure(final Object... keyValues) {
+ if (!ShortestPath.configure(this, (String) keyValues[0], keyValues[1])) {
+ this.parameters.set(this, keyValues);
+ }
+ }
+
+ @Override
+ public Parameters getParameters() {
+ return parameters;
+ }
+
+ @Override
+ protected Traverser.Admin<ComputerResult> processNextStart() throws NoSuchElementException {
+ return super.processNextStart();
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public List<Traversal.Admin<?, ?>> getLocalChildren() {
+ return Arrays.asList(
+ this.targetVertexFilter.get(),
+ this.edgeTraversal.get(),
+ this.distanceTraversal.get());
+ }
+
+ @Override
+ public String toString() {
+ return StringFactory.stepString(this, this.targetVertexFilter.get(), this.edgeTraversal.get(),
+ this.distanceTraversal.get(), this.maxDistance, this.includeEdges, new GraphFilter(this.computer));
+ }
+
+ @Override
+ public ShortestPathVertexProgram generateProgram(final Graph graph, final Memory memory) {
+
+ final ShortestPathVertexProgram.Builder builder = ShortestPathVertexProgram.build()
+ .target(this.targetVertexFilter.getPure())
+ .edgeTraversal(this.edgeTraversal.getPure())
+ .distanceTraversal(this.distanceTraversal.getPure())
+ .maxDistance(this.maxDistance)
+ .includeEdges(this.includeEdges);
+
+ //noinspection unchecked
+ final PureTraversal pureRootTraversal = new PureTraversal<>(this.traversal);
+ Object rootTraversalValue;
+ try {
+ rootTraversalValue = Base64.getEncoder().encodeToString(Serializer.serializeObject(pureRootTraversal));
+ } catch (final IOException ignored) {
+ rootTraversalValue = pureRootTraversal;
+ }
+
+ builder.configure(
+ ProgramVertexProgramStep.ROOT_TRAVERSAL, rootTraversalValue,
+ ProgramVertexProgramStep.STEP_ID, this.id);
+
+ if (memory.exists(TraversalVertexProgram.HALTED_TRAVERSERS)) {
+ final TraverserSet<?> haltedTraversers = memory.get(TraversalVertexProgram.HALTED_TRAVERSERS);
+ if (!haltedTraversers.isEmpty()) {
+ Object haltedTraversersValue;
+ try {
+ haltedTraversersValue = Base64.getEncoder().encodeToString(Serializer.serializeObject(haltedTraversers));
+ } catch (final IOException ignored) {
+ haltedTraversersValue = haltedTraversers;
+ }
+ builder.configure(TraversalVertexProgram.HALTED_TRAVERSERS, haltedTraversersValue);
+ }
+ }
+
+ return builder.create(graph);
+ }
+
+ @Override
+ public Set<TraverserRequirement> getRequirements() {
+ return TraversalParent.super.getSelfAndChildRequirements();
+ }
+
+ @Override
+ public ShortestPathVertexProgramStep clone() {
+ final ShortestPathVertexProgramStep clone = (ShortestPathVertexProgramStep) super.clone();
+ clone.targetVertexFilter = this.targetVertexFilter.clone();
+ clone.edgeTraversal = this.edgeTraversal.clone();
+ clone.distanceTraversal = this.distanceTraversal.clone();
+ return clone;
+ }
+
+ @Override
+ public void setTraversal(final Traversal.Admin<?, ?> parentTraversal) {
+ super.setTraversal(parentTraversal);
+ this.integrateChild(this.targetVertexFilter.get());
+ this.integrateChild(this.edgeTraversal.get());
+ this.integrateChild(this.distanceTraversal.get());
+ }
+
+ @Override
+ public int hashCode() {
+ return super.hashCode();
+ }
+
+ /**
+ * Configuration options to be passed to the {@link GraphTraversal#with(String, Object)} step.
+ */
+ public static class ShortestPath {
+
+ /**
+ * Configures the traversal to use to filter the target vertices for all shortest paths.
+ */
+ public static final String TARGET = Graph.Hidden.hide("tinkerpop.shortestPath.target");
+
+ /**
+ * Configures the direction or traversal to use to filter the edges traversed during the shortest path search phase.
+ */
+ public static final String EDGES = Graph.Hidden.hide("tinkerpop.shortestPath.edges");
+
+ /**
+ * Configures the edge property or traversal to use for shortest path distance calculations.
+ */
+ public static final String DISTANCE = Graph.Hidden.hide("tinkerpop.shortestPath.distance");
+
+ /**
+ * Configures the maximum distance for all shortest paths. Any path with a distance greater than the specified
+ * value will not be returned.
+ */
+ public static final String MAX_DISTANCE = Graph.Hidden.hide("tinkerpop.shortestPath.maxDistance");
+
+ /**
+ * Configures the inclusion of edges in the shortest path computation result.
+ */
+ public static final String INCLUDE_EDGES = Graph.Hidden.hide("tinkerpop.shortestPath.includeEdges");
+
+ private static boolean configure(final ShortestPathVertexProgramStep step, final String key, final Object value) {
+
+ if (TARGET.equals(key)) {
+ if (value instanceof Traversal) {
+ step.setTargetVertexFilter((Traversal) value);
+ return true;
+ }
+ else throw new IllegalArgumentException("ShortestPath.TARGET requires a Traversal as its argument");
+ }
+ else if (EDGES.equals(key)) {
+ if (value instanceof Traversal) {
+ step.setEdgeTraversal((Traversal) value);
+ return true;
+ }
+ else if (value instanceof Direction) {
+ step.setEdgeTraversal(__.toE((Direction) value));
+ return true;
+ }
+ else throw new IllegalArgumentException(
+ "ShortestPath.EDGES requires a Traversal or a Direction as its argument");
+ }
+ else if (DISTANCE.equals(key)) {
+ if (value instanceof Traversal) {
+ step.setDistanceTraversal((Traversal) value);
+ return true;
+ }
+ else if (value instanceof String) {
+ // todo: new ElementValueTraversal((String) value)
+ step.setDistanceTraversal(__.values((String) value));
+ return true;
+ }
+ else throw new IllegalArgumentException(
+ "ShortestPath.DISTANCE requires a Traversal or a property name as its argument");
+ }
+ else if (MAX_DISTANCE.equals(key)) {
+ if (value instanceof Number) {
+ step.setMaxDistance((Number) value);
+ return true;
+ }
+ else throw new IllegalArgumentException("ShortestPath.MAX_DISTANCE requires a Number as its argument");
+ }
+ else if (INCLUDE_EDGES.equals(key)) {
+ if (value instanceof Boolean) {
+ step.setIncludeEdges((Boolean) value);
+ return true;
+ }
+ else throw new IllegalArgumentException("ShortestPath.INCLUDE_EDGES requires a Boolean as its argument");
+ }
+ return false;
+ }
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java
index da12114..8874f09 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java
@@ -61,6 +61,10 @@ import java.util.Iterator;
method = "*",
reason = "hmmmm")
@Graph.OptOut(
+ test = "org.apache.tinkerpop.gremlin.process.traversal.step.map.ShortestPathTest",
+ method = "*",
+ reason = "hmmmm")
+@Graph.OptOut(
test = "org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.TranslationStrategyProcessTest",
method = "*",
reason = "hmmmm")
@@ -89,6 +93,10 @@ import java.util.Iterator;
method = "*",
reason = "RemoteGraph does not support direct Graph.compute() access")
@Graph.OptOut(
+ test = "org.apache.tinkerpop.gremlin.process.computer.search.path.ShortestPathVertexProgramTest",
+ method = "*",
+ reason = "RemoteGraph does not support direct Graph.compute() access")
+@Graph.OptOut(
test = "org.apache.tinkerpop.gremlin.process.computer.bulkloading.BulkLoaderVertexProgramTest",
method = "*",
reason = "RemoteGraph does not support direct Graph.compute() access")
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java
index 220c995..30435ab 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java
@@ -496,15 +496,17 @@ public interface Traversal<S, E> extends Iterator<E>, Serializable, Cloneable, A
public void setGraph(final Graph graph);
public default boolean equals(final Traversal.Admin<S, E> other) {
- final List<Step> steps = this.getSteps();
- final List<Step> otherSteps = other.getSteps();
- if (steps.size() == otherSteps.size()) {
- for (int i = 0; i < steps.size(); i++) {
- if (!steps.get(i).equals(otherSteps.get(i))) {
- return false;
+ if (this.getClass().equals(other.getClass())) {
+ final List<Step> steps = this.getSteps();
+ final List<Step> otherSteps = other.getSteps();
+ if (steps.size() == otherSteps.size()) {
+ for (int i = 0; i < steps.size(); i++) {
+ if (!steps.get(i).equals(otherSteps.get(i))) {
+ return false;
+ }
}
+ return true;
}
- return true;
}
return false;
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
index 7d1e7e4..28798ee 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
@@ -22,6 +22,7 @@ import org.apache.tinkerpop.gremlin.process.computer.VertexProgram;
import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.PageRankVertexProgramStep;
import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.PeerPressureVertexProgramStep;
import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ProgramVertexProgramStep;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ShortestPathVertexProgramStep;
import org.apache.tinkerpop.gremlin.process.traversal.Order;
import org.apache.tinkerpop.gremlin.process.traversal.P;
import org.apache.tinkerpop.gremlin.process.traversal.Path;
@@ -2422,6 +2423,24 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> {
}
/**
+ * Executes a Shortest Path algorithm over the graph.
+ *
+ * @return the traversal with the appended {@link ShortestPathVertexProgramStep}
+ * @see <a href="http://tinkerpop.apache.org/docs/${project.version}/reference/#shortestpath-step" target="_blank">Reference Documentation - ShortestPath Step</a>
+ */
+ public default GraphTraversal<S, Path> shortestPath() {
+ if (this.asAdmin().getEndStep() instanceof GraphStep) {
+ // This is very unfortunate, but I couldn't find another way to make it work. Without the additional
+ // IdentityStep, TraversalVertexProgram doesn't handle halted traversers as expected (it ignores both:
+ // HALTED_TRAVERSER stored in memory and stored as vertex properties); instead it just emits all vertices.
+ this.identity();
+ }
+ this.asAdmin().getBytecode().addStep(Symbols.shortestPath);
+ return (GraphTraversal<S, Path>) ((Traversal.Admin) this.asAdmin())
+ .addStep(new ShortestPathVertexProgramStep(this.asAdmin()));
+ }
+
+ /**
* Executes an arbitrary {@link VertexProgram} over the graph.
*
* @return the traversal with the appended {@link ProgramVertexProgramStep}
@@ -2817,6 +2836,7 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> {
public static final String pageRank = "pageRank";
public static final String peerPressure = "peerPressure";
+ public static final String shortestPath = "shortestPath";
public static final String program = "program";
public static final String by = "by";
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ColumnTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ColumnTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ColumnTraversal.java
index 5023805..9e2f31c 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ColumnTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ColumnTraversal.java
@@ -22,6 +22,8 @@ package org.apache.tinkerpop.gremlin.process.traversal.lambda;
import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.structure.Column;
+import java.util.Objects;
+
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
*/
@@ -57,4 +59,10 @@ public final class ColumnTraversal extends AbstractLambdaTraversal {
public int hashCode() {
return this.getClass().hashCode() ^ this.column.hashCode();
}
+
+ @Override
+ public boolean equals(final Object other) {
+ return other instanceof ColumnTraversal
+ && Objects.equals(((ColumnTraversal) other).column, this.column);
+ }
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ConstantTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ConstantTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ConstantTraversal.java
index 91973b9..bcf82d4 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ConstantTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ConstantTraversal.java
@@ -18,6 +18,8 @@
*/
package org.apache.tinkerpop.gremlin.process.traversal.lambda;
+import java.util.Objects;
+
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
*/
@@ -43,5 +45,10 @@ public final class ConstantTraversal<S, E> extends AbstractLambdaTraversal<S, E>
public int hashCode() {
return this.getClass().hashCode() ^ this.end.hashCode();
}
-}
+ @Override
+ public boolean equals(final Object other) {
+ return other instanceof ConstantTraversal
+ && Objects.equals(((ConstantTraversal) other).end, this.end);
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ElementValueTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ElementValueTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ElementValueTraversal.java
index 2e9b26c..fbfff62 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ElementValueTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/ElementValueTraversal.java
@@ -22,6 +22,8 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalUtil;
import org.apache.tinkerpop.gremlin.structure.Element;
+import java.util.Objects;
+
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
*/
@@ -62,4 +64,10 @@ public final class ElementValueTraversal<V> extends AbstractLambdaTraversal<Elem
public int hashCode() {
return super.hashCode() ^ this.propertyKey.hashCode();
}
-}
+
+ @Override
+ public boolean equals(final Object other) {
+ return other instanceof ElementValueTraversal
+ && Objects.equals(((ElementValueTraversal) other).propertyKey, this.propertyKey);
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/IdentityTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/IdentityTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/IdentityTraversal.java
index 98f85c0..1ed5749 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/IdentityTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/IdentityTraversal.java
@@ -41,4 +41,9 @@ public final class IdentityTraversal<S> extends AbstractLambdaTraversal<S, S> {
public String toString() {
return "identity";
}
-}
+
+ @Override
+ public boolean equals(final Object other) {
+ return other instanceof IdentityTraversal;
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/LoopTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/LoopTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/LoopTraversal.java
index ae03c94..68b6b18 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/LoopTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/LoopTraversal.java
@@ -55,4 +55,10 @@ public final class LoopTraversal<S> extends AbstractLambdaTraversal<S, S> {
public int hashCode() {
return this.getClass().hashCode() ^ Long.hashCode(this.maxLoops);
}
+
+ @Override
+ public boolean equals(final Object other) {
+ return other instanceof LoopTraversal
+ && ((LoopTraversal) other).maxLoops == this.maxLoops;
+ }
}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TokenTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TokenTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TokenTraversal.java
index 4f98a54..d41c402 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TokenTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TokenTraversal.java
@@ -22,6 +22,8 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.structure.Element;
import org.apache.tinkerpop.gremlin.structure.T;
+import java.util.Objects;
+
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
*/
@@ -57,4 +59,10 @@ public final class TokenTraversal<S extends Element, E> extends AbstractLambdaTr
public int hashCode() {
return this.getClass().hashCode() ^ this.t.hashCode();
}
+
+ @Override
+ public boolean equals(final Object other) {
+ return other instanceof TokenTraversal
+ && Objects.equals(((TokenTraversal) other).t, this.t);
+ }
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TrueTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TrueTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TrueTraversal.java
index 84c0db6..71580ce 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TrueTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/TrueTraversal.java
@@ -43,4 +43,9 @@ public final class TrueTraversal<S> extends AbstractLambdaTraversal<S, S> {
public TrueTraversal<S> clone() {
return INSTANCE;
}
+
+ @Override
+ public boolean equals(final Object other) {
+ return other instanceof TrueTraversal;
+ }
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java
index 2e795a5..1bccd7c 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java
@@ -129,7 +129,7 @@ abstract class GraphSONModule extends TinkerPopJacksonModule {
put(List.class, "List");
put(Set.class, "Set");
- // Tinkerpop Graph objects
+ // TinkerPop Graph objects
put(Lambda.class, "Lambda");
put(Vertex.class, "Vertex");
put(Edge.class, "Edge");
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalTest.java
index 9009d0b..d621755 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalTest.java
@@ -42,7 +42,7 @@ import static org.junit.Assert.assertEquals;
public class GraphTraversalTest {
private static final Logger logger = LoggerFactory.getLogger(GraphTraversalTest.class);
- private static Set<String> NO_GRAPH = new HashSet<>(Arrays.asList("asAdmin", "by", "with", "option", "iterate", "to", "from", "profile", "pageRank", "peerPressure", "program", "none"));
+ private static Set<String> NO_GRAPH = new HashSet<>(Arrays.asList("asAdmin", "by", "with", "option", "iterate", "to", "from", "profile", "pageRank", "peerPressure", "shortestPath", "program", "none"));
private static Set<String> NO_ANONYMOUS = new HashSet<>(Arrays.asList("start", "__"));
private static Set<String> IGNORES_BYTECODE = new HashSet<>(Arrays.asList("asAdmin", "iterate", "mapValues", "mapKeys"));
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs
----------------------------------------------------------------------
diff --git a/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs b/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs
index 537cdbe..45eecfa 100644
--- a/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs
+++ b/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs
@@ -1359,6 +1359,15 @@ namespace Gremlin.Net.Process.Traversal
}
/// <summary>
+ /// Adds the shortestPath step to this <see cref="GraphTraversal{SType, EType}" />.
+ /// </summary>
+ public GraphTraversal<S, Path> ShortestPath ()
+ {
+ Bytecode.AddStep("shortestPath");
+ return Wrap<S, Path>(this);
+ }
+
+ /// <summary>
/// Adds the sideEffect step to this <see cref="GraphTraversal{SType, EType}" />.
/// </summary>
public GraphTraversal<S, E> SideEffect (IConsumer consumer)
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-javascript/src/main/javascript/gremlin-javascript/lib/process/graph-traversal.js
----------------------------------------------------------------------
diff --git a/gremlin-javascript/src/main/javascript/gremlin-javascript/lib/process/graph-traversal.js b/gremlin-javascript/src/main/javascript/gremlin-javascript/lib/process/graph-traversal.js
index f143542..b139c9f 100644
--- a/gremlin-javascript/src/main/javascript/gremlin-javascript/lib/process/graph-traversal.js
+++ b/gremlin-javascript/src/main/javascript/gremlin-javascript/lib/process/graph-traversal.js
@@ -933,6 +933,16 @@ class GraphTraversal extends Traversal {
}
/**
+ * Graph traversal shortestPath method.
+ * @param {...Object} args
+ * @returns {GraphTraversal}
+ */
+ shortestPath(...args) {
+ this.bytecode.addStep('shortestPath', args);
+ return this;
+ }
+
+ /**
* Graph traversal sideEffect method.
* @param {...Object} args
* @returns {GraphTraversal}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-python/src/main/jython/gremlin_python/process/graph_traversal.py
----------------------------------------------------------------------
diff --git a/gremlin-python/src/main/jython/gremlin_python/process/graph_traversal.py b/gremlin-python/src/main/jython/gremlin_python/process/graph_traversal.py
index bb81d87..518ef13 100644
--- a/gremlin-python/src/main/jython/gremlin_python/process/graph_traversal.py
+++ b/gremlin-python/src/main/jython/gremlin_python/process/graph_traversal.py
@@ -425,6 +425,10 @@ class GraphTraversal(Traversal):
self.bytecode.add_step("select", *args)
return self
+ def shortestPath(self, *args):
+ self.bytecode.add_step("shortestPath", *args)
+ return self
+
def sideEffect(self, *args):
self.bytecode.add_step("sideEffect", *args)
return self
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/AbstractGremlinTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/AbstractGremlinTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/AbstractGremlinTest.java
index 25d7a55..fde1b8d 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/AbstractGremlinTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/AbstractGremlinTest.java
@@ -170,6 +170,10 @@ public abstract class AbstractGremlinTest {
return convertToVertex(graph, vertexName).id();
}
+ public Vertex convertToVertex(final String vertexName) {
+ return convertToVertex(graph, vertexName);
+ }
+
public Vertex convertToVertex(final Graph graph, final String vertexName) {
// all test graphs have "name" as a unique id which makes it easy to hardcode this...works for now
return graph.traversal().V().has("name", vertexName).next();
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/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 3d51a94..520ec6e 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
@@ -25,6 +25,7 @@ import org.apache.tinkerpop.gremlin.process.computer.bulkdumping.BulkDumperVerte
import org.apache.tinkerpop.gremlin.process.computer.bulkloading.BulkLoaderVertexProgramTest;
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;
@@ -69,6 +70,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;
@@ -162,6 +164,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,
@@ -189,6 +192,7 @@ public class ProcessComputerSuite extends AbstractGremlinSuite {
// algorithms
PageRankVertexProgramTest.class,
PeerPressureVertexProgramTest.class,
+ ShortestPathVertexProgramTest.class,
BulkLoaderVertexProgramTest.class,
BulkDumperVertexProgramTest.class,
@@ -252,6 +256,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/a373c8b2/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..cf17578
--- /dev/null
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathTestHelper.java
@@ -0,0 +1,72 @@
+/*
+ * 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.structure.Edge;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+public class ShortestPathTestHelper {
+
+ private final AbstractGremlinProcessTest test;
+ private final GraphTraversalSource g;
+
+ public ShortestPathTestHelper(final AbstractGremlinProcessTest test, final GraphTraversalSource g) {
+ this.test = test;
+ this.g = g;
+ }
+
+ 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 = test.convertToVertex(name);
+ if (!first) {
+ if (includeEdges) {
+ final Edge edge = g.V(((Vertex) path.get(path.size() - 1)).id())
+ .bothE().filter(__.otherV().is(P.eq(vertex)))
+ .next();
+ path = path.extend(edge, Collections.emptySet());
+ }
+ }
+ path = path.extend(vertex, Collections.emptySet());
+ first = false;
+ }
+ return path;
+ }
+}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a373c8b2/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..b53d6ae
--- /dev/null
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgramTest.java
@@ -0,0 +1,264 @@
+/*
+ * 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 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);
+ }
+
+ 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