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/05/30 14:37:36 UTC
[3/4] 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/0ccedb67
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/0ccedb67
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/0ccedb67
Branch: refs/heads/shortest-path-wip
Commit: 0ccedb676b251954605ba5307b171c94cc07264a
Parents: c374dbe
Author: Daniel Kuppitz <da...@hotmail.com>
Authored: Tue May 22 07:59:32 2018 -0700
Committer: Daniel Kuppitz <da...@hotmail.com>
Committed: Fri May 25 13:41:45 2018 -0700
----------------------------------------------------------------------
.../tinkerpop/gremlin/jsr223/CoreImports.java | 4 +
.../search/path/ShortestPathVertexProgram.java | 562 +++++++++++++++++++
.../step/map/ShortestPathVertexProgramStep.java | 243 ++++++++
.../gremlin/process/remote/RemoteGraph.java | 8 +
.../traversal/dsl/graph/GraphTraversal.java | 40 +-
.../traversal/dsl/graph/GraphTraversalTest.java | 2 +-
.../tinkerpop/gremlin/AbstractGremlinTest.java | 4 +
.../gremlin/process/ProcessComputerSuite.java | 5 +
.../search/path/ShortestPathTestHelper.java | 72 +++
.../path/ShortestPathVertexProgramTest.java | 264 +++++++++
.../traversal/step/map/ShortestPathTest.java | 309 ++++++++++
pom.xml | 3 +
.../structure/TinkerGraphPlayTest.java | 118 +++-
13 files changed, 1599 insertions(+), 35 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0ccedb67/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/0ccedb67/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..acf6ed4
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java
@@ -0,0 +1,562 @@
+/*
+ * 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) {
+ final Traversal.Admin<Edge, Number> traversal = this.distanceTraversal.getPure();
+ traversal.addStart(traversal.getTraverserGenerator().generate(edge, traversal.getStartStep(), 1));
+ return traversal.tryNext().orElse(0L);
+ }
+
+ private boolean exceedsMaxDistance(final Number distance) {
+ 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/0ccedb67/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..ac2991f
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPathVertexProgramStep.java
@@ -0,0 +1,243 @@
+/*
+ * 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.lambda.ElementValueTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.step.*;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.DefaultStepConfiguration;
+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 {
+
+ 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);
+ }
+
+ @SuppressWarnings("unused") // mainly used by reflection code in StepConfiguration
+ public void setTargetVertexFilter(final Traversal<Vertex, ?> filterTraversal) {
+ if (null == filterTraversal) throw Graph.Exceptions.argumentCanNotBeNull("filterTraversal");
+ this.targetVertexFilter = new PureTraversal<>(this.integrateChild(filterTraversal.asAdmin()));
+ }
+
+ @SuppressWarnings("unused") // mainly used by reflection code in StepConfiguration
+ public void setEdgeTraversal(final Traversal<Vertex, Edge> edgeTraversal) {
+ if (null == edgeTraversal) throw Graph.Exceptions.argumentCanNotBeNull("edgeTraversal");
+ this.edgeTraversal = new PureTraversal<>(this.integrateChild(edgeTraversal.asAdmin()));
+ }
+
+ @SuppressWarnings("unused") // mainly used by reflection code in StepConfiguration
+ public void setDistanceTraversal(final Traversal<Edge, Number> distanceTraversal) {
+ if (null == distanceTraversal) throw Graph.Exceptions.argumentCanNotBeNull("distanceTraversal");
+ this.distanceTraversal = new PureTraversal<>(this.integrateChild(distanceTraversal.asAdmin()));
+ }
+
+ @SuppressWarnings("unused") // mainly used by reflection code in StepConfiguration
+ public void setMaxDistance(final Number maxDistance) {
+ this.maxDistance = maxDistance;
+ }
+
+ @SuppressWarnings("unused") // mainly used by reflection code in StepConfiguration
+ public void setIncludeEdges(final boolean includeEdges) {
+ this.includeEdges = includeEdges;
+ }
+
+ @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();
+ }
+
+ /**
+ * Gremlin expressions that can be used to produce {@link StepConfiguration} options for use with
+ * {@link GraphTraversal#shortestPath()}.
+ *
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+ @SuppressWarnings("WeakerAccess")
+ public static class ShortestPath {
+
+ /**
+ * The traversal to use to filter the target vertices for all shortest paths.
+ */
+ public static StepConfiguration<Step> target(final Traversal<Vertex, ?> filterTraversal) {
+ return new DefaultStepConfiguration(ShortestPathVertexProgramStep.class, "setTargetVertexFilter", filterTraversal.asAdmin());
+ }
+
+ /**
+ * The edge traversal direction to use during the shortest path search phase.
+ * @see ShortestPath#edges(Traversal)
+ */
+ public static StepConfiguration<Step> direction(final Direction direction) {
+ return edges(__.toE(direction).asAdmin());
+ }
+
+ /**
+ * The traversal to use to filter the edges traversed during the shortest path search phase.
+ */
+ public static StepConfiguration<Step> edges(final Traversal<Vertex, Edge> edgeTraversal) {
+ return new DefaultStepConfiguration(ShortestPathVertexProgramStep.class, "setEdgeTraversal", edgeTraversal.asAdmin());
+ }
+
+ /**
+ * The edge property to use for shortest path distance calculations.
+ * @see ShortestPath#distance(Traversal)
+ */
+ public static StepConfiguration<Step> distance(final String property) {
+ //noinspection unchecked
+ return distance((Traversal.Admin) new ElementValueTraversal<>(property));
+ }
+
+ /**
+ * The traversal to use to get the distance of an edge during the shortest path search phase.
+ */
+ public static StepConfiguration<Step> distance(final Traversal<Edge, Number> distanceTraversal) {
+ return new DefaultStepConfiguration(ShortestPathVertexProgramStep.class, "setDistanceTraversal", distanceTraversal);
+ }
+
+ /**
+ * Limits the maximum distance for all shortest paths. Any path with a distance greater than the specified value
+ * will not be returned.
+ */
+ public static StepConfiguration<Step> maxDistance(final Number maxDistance) {
+ return new DefaultStepConfiguration(ShortestPathVertexProgramStep.class, "setMaxDistance", maxDistance);
+ }
+
+ /**
+ * Include edges in the shortest path computation result.
+ * @see ShortestPath#includeEdges(boolean)
+ */
+ public static StepConfiguration<Step> edgesIncluded() {
+ return includeEdges(true);
+ }
+
+ /**
+ * Whether to include edges in the shortest path computation result.
+ */
+ public static StepConfiguration<Step> includeEdges(final boolean includeEdges) {
+ return new DefaultStepConfiguration(ShortestPathVertexProgramStep.class, "setIncludeEdges", includeEdges);
+ }
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0ccedb67/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/0ccedb67/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 5747df2..850b680 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
@@ -19,9 +19,7 @@
package org.apache.tinkerpop.gremlin.process.traversal.dsl.graph;
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.*;
import org.apache.tinkerpop.gremlin.process.traversal.Order;
import org.apache.tinkerpop.gremlin.process.traversal.P;
import org.apache.tinkerpop.gremlin.process.traversal.Path;
@@ -157,10 +155,7 @@ import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Optional;
-import java.util.function.BiFunction;
-import java.util.function.Consumer;
-import java.util.function.Function;
-import java.util.function.Predicate;
+import java.util.function.*;
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
@@ -307,9 +302,9 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> {
}
/**
- * Map the {@link Vertex} to its adjacent vertices given a direction and edge labels.
+ * Map the {@link Vertex} to its adjacent vertices given a edgeTraversal and edge labels.
*
- * @param direction the direction to traverse from the current vertex
+ * @param direction the edgeTraversal to traverse from the current vertex
* @param edgeLabels the edge labels to traverse
* @return the traversal with an appended {@link VertexStep}.
* @see <a href="http://tinkerpop.apache.org/docs/${project.version}/reference/#vertex-steps" target="_blank">Reference Documentation - Vertex Step</a>
@@ -360,9 +355,9 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> {
}
/**
- * Map the {@link Vertex} to its incident edges given the direction and edge labels.
+ * Map the {@link Vertex} to its incident edges given the edgeTraversal and edge labels.
*
- * @param direction the direction to traverse from the current vertex
+ * @param direction the edgeTraversal to traverse from the current vertex
* @param edgeLabels the edge labels to traverse
* @return the traversal with an appended {@link VertexStep}.
* @see <a href="http://tinkerpop.apache.org/docs/${project.version}/reference/#vertex-steps" target="_blank">Reference Documentation - Vertex Step</a>
@@ -413,9 +408,9 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> {
}
/**
- * Map the {@link Edge} to its incident vertices given the direction.
+ * Map the {@link Edge} to its incident vertices given the edgeTraversal.
*
- * @param direction the direction to traverser from the current edge
+ * @param direction the edgeTraversal to traverser from the current edge
* @return the traversal with an appended {@link EdgeVertexStep}.
* @see <a href="http://tinkerpop.apache.org/docs/${project.version}/reference/#vertex-steps" target="_blank">Reference Documentation - Vertex Step</a>
* @since 3.0.0-incubating
@@ -2422,6 +2417,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}
@@ -2815,6 +2828,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/0ccedb67/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/0ccedb67/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/0ccedb67/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/0ccedb67/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/0ccedb67/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
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0ccedb67/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..ed1aed7
--- /dev/null
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ShortestPathTest.java
@@ -0,0 +1,309 @@
+/*
+ * 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 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.ShortestPathVertexProgramStep.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();
+
+ @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);
+ }
+
+ 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(edgesIncluded());
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath_directionXINX() {
+ return g.V().shortestPath().with(direction(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(edgesIncluded()).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"));
+ }
+ }
+}
\ No newline at end of file