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/f1776cc2 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/f1776cc2 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/f1776cc2 Branch: refs/heads/shortest-path-wip Commit: f1776cc20acf0582cbf85555331caeecbc95e59f Parents: 12b84a1 Author: Stephen Mallette <sp...@genoprime.com> Authored: Wed May 23 08:46:34 2018 -0400 Committer: Daniel Kuppitz <daniel_kupp...@hotmail.com> Committed: Thu May 31 14:42:02 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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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/f1776cc2/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