TINKERPOP-1990 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/e1ba81b4 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/e1ba81b4 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/e1ba81b4 Branch: refs/heads/TINKERPOP-1990 Commit: e1ba81b4b25c562050fae10b52ab67c5dec96232 Parents: 69b6f96 Author: Daniel Kuppitz <daniel_kupp...@hotmail.com> Authored: Wed May 23 08:46:34 2018 -0400 Committer: Daniel Kuppitz <daniel_kupp...@hotmail.com> Committed: Wed Aug 1 12:26:30 2018 -0700 ---------------------------------------------------------------------- CHANGELOG.asciidoc | 1 + docs/src/reference/the-graphcomputer.asciidoc | 51 ++ docs/src/reference/the-traversal.asciidoc | 56 ++ .../tinkerpop/gremlin/jsr223/CoreImports.java | 4 + .../search/path/ShortestPathVertexProgram.java | 581 +++++++++++++++++++ .../traversal/step/map/ShortestPath.java | 108 ++++ .../step/map/ShortestPathVertexProgramStep.java | 174 ++++++ .../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 +- .../gremlin/structure/io/gryo/GryoVersion.java | 12 +- .../structure/io/gryo/UtilSerializers.java | 15 + .../gremlin/structure/util/Attachable.java | 3 +- .../traversal/dsl/graph/GraphTraversalTest.java | 2 +- .../Process/Traversal/GraphTraversal.cs | 11 +- .../lib/process/graph-traversal.js | 10 + .../gremlin_python/process/graph_traversal.py | 4 + .../tinkerpop/gremlin/AbstractGremlinTest.java | 6 +- .../process/AbstractGremlinProcessTest.java | 11 +- .../gremlin/process/ProcessComputerSuite.java | 5 + .../search/path/ShortestPathTestHelper.java | 100 ++++ .../path/ShortestPathVertexProgramTest.java | 297 ++++++++++ .../traversal/step/map/ShortestPathTest.java | 353 +++++++++++ pom.xml | 3 + 32 files changed, 1880 insertions(+), 26 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/CHANGELOG.asciidoc ---------------------------------------------------------------------- diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc index 430f52d..4ffc6b7 100644 --- a/CHANGELOG.asciidoc +++ b/CHANGELOG.asciidoc @@ -25,6 +25,7 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima This release also includes changes from <<release-3-3-3, 3.3.3>>. +* Implemented `ShortestPathVertexProgram` and the `shortestPath()` step. * `AbstractGraphProvider` uses `g.io()` for loading test data. * Added the `io()` start step and `read()` and `write()` termination steps to the Gremlin language. * Added `GraphFeatures.supportsIoRead()` and `GraphFeatures.supportsIoWrite()`. http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/docs/src/reference/the-graphcomputer.asciidoc ---------------------------------------------------------------------- diff --git a/docs/src/reference/the-graphcomputer.asciidoc b/docs/src/reference/the-graphcomputer.asciidoc index 1d7586c..3d7ec00 100644 --- a/docs/src/reference/the-graphcomputer.asciidoc +++ b/docs/src/reference/the-graphcomputer.asciidoc @@ -403,6 +403,57 @@ g.V().peerPressure().by('cluster').valueMap() g.V().peerPressure().by(outE('knows')).by('cluster').valueMap() ---- +[[shortestpathvertexprogram]] +=== ShortestPathVertexProgram + +The `ShortestPathVertexProram` provides an easy way to find shortest non-cyclic paths in the graph. It provides several options to configure +the output format, the start- and end-vertices, the direction, a custom distance function, as well as a distance limitation. By default it just +finds all undirected, shortest paths in the graph. + +[gremlin-groovy,modern] +---- +spvp = ShortestPathVertexProgram.build().create() <1> +result = graph.compute().program(spvp).submit().get() <2> +result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS) <3> +---- + +<1> Create a `ShortestPathVertexProgram` with its default configuration. +<2> Execute the `ShortestPathVertexProgram`. +<3> Get all shortest paths from the results memory. + +[gremlin-groovy,modern] +---- +spvp = ShortestPathVertexProgram.build().includeEdges(true).create() <1> +result = graph.compute().program(spvp).submit().get() <2> +result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS) <3> +---- + +<1> Create a `ShortestPathVertexProgram` as before, but configure it to include edges in the result. +<2> Execute the `ShortestPathVertexProgram`. +<3> Get all shortest paths from the results memory. + +The `ShortestPathVertexProgram.Builder` provides the following configuration methods: + +[width="100%",cols="3,15,5",options="header"] +|========================================================= +| Method | Description | Default +| `source(Traversal)` | Sets a filter traversal for the start vertices (e.g. `__.has('name','marko')`). | all vertices (`__.identity()`) +| `target(Traversal)` | Sets a filter traversal for the end vertices. | all vertices +| `edgeDirection(Direction)` | Sets the direction to traverse during the shortest path discovery. | `Direction.BOTH` +| `edgeTraversal(Traversal)` | Sets a traversal that emits the edges to traverse from the current vertex. | `__.bothE()` +| `distanceProperty(String)` | Sets the edge property to use for the distance calculations. | none +| `distanceTraversal(Traversal)` | Sets the traversal that calculates the distance for the current edge. | `__.constant(1)` +| `maxDistance(Traversal)` | Limits the shortest path distance. | none +| `includeEdges(Boolean)` | Whether to include edges in shortest paths or not. | `false` +|========================================================= + +IMPORTANT: If a maximum distance is provided, the discovery process will only stop to follow a path at this distance if there was no +custom distance property or traversal provided. Custom distances can be negative, hence exceeding the maximum distance doesn't mean that there +can't be any more valid paths. However, paths will be filtered at the end, when no more non-cyclic paths can be found. The bottom line is that +custom distance properties or traversals can lead to much longer runtimes and a much higher memory consumption. + +Note that `GraphTraversal` provides a <<shortestpath-step,`shortestPath()`>>-step. + [[bulkdumpervertexprogram]] [[clonevertexprogram]] === CloneVertexProgram http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/docs/src/reference/the-traversal.asciidoc ---------------------------------------------------------------------- diff --git a/docs/src/reference/the-traversal.asciidoc b/docs/src/reference/the-traversal.asciidoc index 7d385c8..f4a60fb 100644 --- a/docs/src/reference/the-traversal.asciidoc +++ b/docs/src/reference/the-traversal.asciidoc @@ -2663,6 +2663,62 @@ link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/grem link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/structure/Column.html++[`Column`], link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/process/traversal/Pop.html++[`Pop`] +[[shortestpath-step]] +=== ShortestPath step + +The `shortestPath()`-step provides an easy way to find shortest non-cyclic paths in a graph. It is configurable +using the `with()`-modulator with the options given below. + +[width="100%",cols="3,3,15,5",options="header"] +|========================================================= +| Key | Type | Description | Default +| `target` | `Traversal` | Sets a filter traversal for the end vertices (e.g. `__.has('name','marko')`). | all vertices (`__.identity()`) +| `edges` | `Traversal` or `Direction` | Sets a `Traversal` that emits the edges to traverse from the current vertex or the `Direction` to traverse during the shortest path discovery. | `Direction.BOTH` +| `distance` | `Traversal` or `String` | Sets the `Traversal` that calculates the distance for the current edge or the name of an edge property to use for the distance calculations. | `__.constant(1)` +| `maxDistance` | `Number` | Sets the distance limit for all shortest paths. | none +| `includeEdges` | `Boolean` | Whether to include edges in the result or not. | `false` +|========================================================= + +[gremlin-groovy,modern] +---- +a = g.withComputer() +a.V().shortestPath() <1> +a.V().has('person','name','marko').shortestPath() <2> +a.V().shortestPath().with(ShortestPath.target, __.has('name','peter')) <3> +a.V().shortestPath(). + with(ShortestPath.edges, Direction.IN). + with(ShortestPath.target, __.has('name','josh')) <4> +a.V().has('person','name','marko'). + shortestPath(). + with(ShortestPath.target, __.has('name','josh')) <5> +a.V().has('person','name','marko'). + shortestPath(). + with(ShortestPath.target, __.has('name','josh')). + with(ShortestPath.distance, 'weight') <6> +a.V().has('person','name','marko'). + shortestPath(). + with(ShortestPath.target, __.has('name','josh')). + with(ShortestPath.includeEdges, true) <7> +g.inject(a.V().shortestPath(). + with(ShortestPath.distance, 'weight'). + with(ShortestPath.includeEdges, true). + with(ShortestPath.maxDistance, 1).toList().toArray()). + map(unfold().values('name','weight').fold()) <8> +---- + +<1> Find all shortest paths. +<2> Find all shortest paths from `marko`. +<3> Find all shortest paths to `peter`. +<4> Find all in-directed paths to `josh`. +<5> Find all shortest paths from `marko` to `josh`. +<6> Find all shortest paths from `marko` to `josh` using a custom distance property. +<7> Find all shortest paths from `marko` to `josh` and include edges in the result. +<8> Find all shortest paths using a custom distance property and limit the distance to 1. Inject the result into a OLTP GraphTraversal in order to be able to select properties from all elements in all paths. + +*Additional References* + +link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.html#shortestPath--++[`shortestPath()`] + [[simplepath-step]] === SimplePath Step http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/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 72ad47a..9830cdd 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 @@ -47,10 +47,12 @@ 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.PageRank; import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.PeerPressure; +import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ShortestPath; 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; @@ -268,6 +270,8 @@ public final class CoreImports { CLASS_IMPORTS.add(PageRank.class); CLASS_IMPORTS.add(PageRankMapReduce.class); CLASS_IMPORTS.add(PageRankVertexProgram.class); + CLASS_IMPORTS.add(ShortestPath.class); + CLASS_IMPORTS.add(ShortestPathVertexProgram.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/e1ba81b4/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..549dff9 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java @@ -0,0 +1,581 @@ +/* + * 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.GraphComputer; +import org.apache.tinkerpop.gremlin.process.computer.Memory; +import org.apache.tinkerpop.gremlin.process.computer.MemoryComputeKey; +import org.apache.tinkerpop.gremlin.process.computer.MessageScope; +import org.apache.tinkerpop.gremlin.process.computer.Messenger; +import org.apache.tinkerpop.gremlin.process.computer.VertexComputeKey; +import org.apache.tinkerpop.gremlin.process.computer.VertexProgram; +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.Operator; +import org.apache.tinkerpop.gremlin.process.traversal.Path; +import org.apache.tinkerpop.gremlin.process.traversal.Step; +import org.apache.tinkerpop.gremlin.process.traversal.Traversal; +import org.apache.tinkerpop.gremlin.process.traversal.Traverser; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.ImmutablePath; +import org.apache.tinkerpop.gremlin.process.traversal.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.Direction; +import org.apache.tinkerpop.gremlin.structure.Edge; +import org.apache.tinkerpop.gremlin.structure.Element; +import org.apache.tinkerpop.gremlin.structure.Graph; +import org.apache.tinkerpop.gremlin.structure.Vertex; +import org.apache.tinkerpop.gremlin.structure.VertexProperty; +import org.apache.tinkerpop.gremlin.structure.util.StringFactory; +import org.apache.tinkerpop.gremlin.structure.util.reference.ReferenceFactory; +import org.apache.tinkerpop.gremlin.util.NumberHelper; +import org.javatuples.Pair; +import org.javatuples.Triplet; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.function.Function; + +/** + * @author Daniel Kuppitz (http://gremlin.guru) + */ +public class ShortestPathVertexProgram implements VertexProgram<Triplet<Path, Edge, Number>> { + + @SuppressWarnings("WeakerAccess") + 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"; + + private static final int SEARCH = 0; + private static final int COLLECT_PATHS = 1; + private static final int UPDATE_HALTED_TRAVERSERS = 2; + + public static final PureTraversal<Vertex, ?> DEFAULT_VERTEX_FILTER_TRAVERSAL = new PureTraversal<>( + __.<Vertex> identity().asAdmin()); // todo: 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<>( + __.<Edge> start().<Number> constant(1).asAdmin()); // todo: 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.haltedTraversersIndex = new IndexedTraverserSet<>(v -> v); + for (final Traverser.Admin<Vertex> traverser : this.haltedTraversers) { + this.haltedTraversersIndex.add(traverser.split()); + } + 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()); + } + TraversalVertexProgram.storeHaltedTraversers(configuration, this.haltedTraversers); + } + + @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) { + memory.set(VOTE_TO_HALT, true); + memory.set(STATE, SEARCH); + } + + @Override + public void execute(final Vertex vertex, final Messenger<Triplet<Path, Edge, Number>> messenger, final Memory memory) { + + switch (memory.<Integer>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 int state = memory.get(STATE); + if (state == COLLECT_PATHS) { + if (this.standalone) return true; + memory.set(STATE, UPDATE_HALTED_TRAVERSERS); + return false; + } + if (state == UPDATE_HALTED_TRAVERSERS) return true; + else memory.set(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(ReferenceFactory.detach(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(); + } + return vertex.property(TraversalVertexProgram.HALTED_TRAVERSERS).isPresent(); + } + + private boolean isEndVertex(final Vertex vertex) { + final Traversal.Admin<Vertex, ?> filterTraversal = this.targetVertexFilterTraversal.getPure(); + //noinspection unchecked + final Step<Vertex, Vertex> startStep = (Step<Vertex, Vertex>) filterTraversal.getStartStep(); + filterTraversal.addStart(filterTraversal.getTraverserGenerator().generate(vertex, startStep, 1)); + 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(vertex)) { + if (this.distanceEqualsNumberOfHops || + this.maxDistance == null || + NumberHelper.compare(pair.getValue0(), this.maxDistance) <= 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(__.values(distance)) // todo: (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) { + 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; + } + }; + } +} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPath.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPath.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPath.java new file mode 100644 index 0000000..b0d7815 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPath.java @@ -0,0 +1,108 @@ +/* + * 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.traversal.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.structure.Direction; +import org.apache.tinkerpop.gremlin.structure.Graph; + +/** + * Configuration options to be passed to the {@link GraphTraversal#with(String, Object)} step. + */ +public 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 maxDistance = Graph.Hidden.hide("tinkerpop.shortestPath.maxDistance"); + + /** + * Configures the inclusion of edges in the shortest path computation result. + */ + public static final String includeEdges = Graph.Hidden.hide("tinkerpop.shortestPath.includeEdges"); + + 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 (maxDistance.equals(key)) { + if (value instanceof Number) { + step.setMaxDistance((Number) value); + return true; + } + else throw new IllegalArgumentException("ShortestPath.maxDistance requires a Number as its argument"); + } + else if (includeEdges.equals(key)) { + if (value instanceof Boolean) { + step.setIncludeEdges((Boolean) value); + return true; + } + else throw new IllegalArgumentException("ShortestPath.includeEdges requires a Boolean as its argument"); + } + return false; + } +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/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..692cb6a --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPathVertexProgramStep.java @@ -0,0 +1,174 @@ +/* + * 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.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.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); + } + + void setTargetVertexFilter(final Traversal filterTraversal) { + this.targetVertexFilter = new PureTraversal<>(this.integrateChild(filterTraversal.asAdmin())); + } + + void setEdgeTraversal(final Traversal edgeTraversal) { + this.edgeTraversal = new PureTraversal<>(this.integrateChild(edgeTraversal.asAdmin())); + } + + void setDistanceTraversal(final Traversal distanceTraversal) { + this.distanceTraversal = new PureTraversal<>(this.integrateChild(distanceTraversal.asAdmin())); + } + + void setMaxDistance(final Number maxDistance) { + this.maxDistance = maxDistance; + } + + 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(); + } + +} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/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 2df5ecf..200645e 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 = "https://issues.apache.org/jira/browse/TINKERPOP-1976";) @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/e1ba81b4/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/e1ba81b4/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 a675ad1..593323c 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; @@ -2452,6 +2453,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} @@ -2882,6 +2901,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/e1ba81b4/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/e1ba81b4/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/e1ba81b4/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/e1ba81b4/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/e1ba81b4/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/e1ba81b4/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/e1ba81b4/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/e1ba81b4/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/e1ba81b4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java index e7dfd93..6d55704 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java @@ -114,10 +114,10 @@ import org.apache.tinkerpop.gremlin.util.function.MultiComparator; import org.apache.tinkerpop.shaded.kryo.ClassResolver; import org.apache.tinkerpop.shaded.kryo.KryoSerializable; import org.apache.tinkerpop.shaded.kryo.serializers.JavaSerializer; -import org.javatuples.Pair; import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.LabelledCounter; import org.apache.commons.collections.map.ReferenceMap; -import java.util.Stack; +import org.javatuples.Pair; +import org.javatuples.Triplet; import java.math.BigDecimal; import java.math.BigInteger; @@ -154,6 +154,7 @@ import java.util.LinkedList; import java.util.List; import java.util.Locale; import java.util.Optional; +import java.util.Stack; import java.util.TimeZone; import java.util.TreeMap; import java.util.TreeSet; @@ -356,6 +357,7 @@ public enum GryoVersion { add(GryoTypeReg.of(MapReduce.NullObject.class, 74)); add(GryoTypeReg.of(AtomicLong.class, 79)); add(GryoTypeReg.of(Pair.class, 88, new UtilSerializers.PairSerializer())); + add(GryoTypeReg.of(Triplet.class, 183, new UtilSerializers.TripletSerializer())); // ***LAST ID*** add(GryoTypeReg.of(TraversalExplanation.class, 106, new JavaSerializer())); add(GryoTypeReg.of(Duration.class, 93, new JavaTimeSerializers.DurationSerializer())); @@ -393,8 +395,7 @@ public enum GryoVersion { add(GryoTypeReg.of(LP_NL_O_OB_P_S_SE_SL_Traverser.class, 179)); add(GryoTypeReg.of(LabelledCounter.class, 180)); add(GryoTypeReg.of(Stack.class, 181)); - add(GryoTypeReg.of(ReferenceMap.class, 182)); // ***LAST ID*** - + add(GryoTypeReg.of(ReferenceMap.class, 182)); // placeholder serializers for classes that don't live here in core. this will allow them to be used if // present or ignored if the class isn't available. either way the registration numbers are held as @@ -520,6 +521,7 @@ public enum GryoVersion { add(GryoTypeReg.of(MapReduce.NullObject.class, 74)); add(GryoTypeReg.of(AtomicLong.class, 79)); add(GryoTypeReg.of(Pair.class, 88, new UtilSerializers.PairSerializer())); + add(GryoTypeReg.of(Triplet.class, 183, new UtilSerializers.TripletSerializer())); // ***LAST ID*** add(GryoTypeReg.of(TraversalExplanation.class, 106, new JavaSerializer())); add(GryoTypeReg.of(Duration.class, 93, new JavaTimeSerializers.DurationSerializer())); @@ -583,7 +585,7 @@ public enum GryoVersion { add(GryoTypeReg.of(LP_NL_O_OB_P_S_SE_SL_Traverser.class, 179)); add(GryoTypeReg.of(LabelledCounter.class, 180)); add(GryoTypeReg.of(Stack.class, 181)); - add(GryoTypeReg.of(ReferenceMap.class, 182)); // ***LAST ID*** + add(GryoTypeReg.of(ReferenceMap.class, 182)); }}; } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/UtilSerializers.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/UtilSerializers.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/UtilSerializers.java index 5182e6c..aff6059 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/UtilSerializers.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/UtilSerializers.java @@ -28,6 +28,7 @@ import org.apache.tinkerpop.shaded.kryo.Serializer; import org.apache.tinkerpop.shaded.kryo.io.Input; import org.apache.tinkerpop.shaded.kryo.io.Output; import org.javatuples.Pair; +import org.javatuples.Triplet; import java.net.InetAddress; import java.net.URI; @@ -216,6 +217,20 @@ final class UtilSerializers { } } + static final class TripletSerializer implements SerializerShim<Triplet> { + @Override + public <O extends OutputShim> void write(final KryoShim<?, O> kryo, final O output, final Triplet triplet) { + kryo.writeClassAndObject(output, triplet.getValue0()); + kryo.writeClassAndObject(output, triplet.getValue1()); + kryo.writeClassAndObject(output, triplet.getValue2()); + } + + @Override + public <I extends InputShim> Triplet read(final KryoShim<I, ?> kryo, final I input, final Class<Triplet> tripletClass) { + return Triplet.with(kryo.readClassAndObject(input), kryo.readClassAndObject(input), kryo.readClassAndObject(input)); + } + } + static final class EntrySerializer extends Serializer<Map.Entry> { @Override public void write(final Kryo kryo, final Output output, final Map.Entry entry) { http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Attachable.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Attachable.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Attachable.java index fa999aa..3cd76f2 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Attachable.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Attachable.java @@ -26,6 +26,7 @@ import org.apache.tinkerpop.gremlin.structure.Property; import org.apache.tinkerpop.gremlin.structure.T; import org.apache.tinkerpop.gremlin.structure.Vertex; import org.apache.tinkerpop.gremlin.structure.VertexProperty; +import org.apache.tinkerpop.gremlin.structure.util.empty.EmptyGraph; import java.util.Iterator; import java.util.Optional; @@ -70,7 +71,7 @@ public interface Attachable<V> { */ public static class Method { public static <V> Function<Attachable<V>, V> get(final Host hostVertexOrGraph) { - return (Attachable<V> attachable) -> { + return hostVertexOrGraph instanceof EmptyGraph ? Attachable::get : (Attachable<V> attachable) -> { final Object base = attachable.get(); if (base instanceof Vertex) { final Optional<Vertex> optional = hostVertexOrGraph instanceof Graph ? http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/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 3d9a549..d1da36d 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 @@ -43,7 +43,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", "read", "write", "with", "option", "iterate", "to", "from", "profile", "pageRank", "peerPressure", "program", "none")); + private static Set<String> NO_GRAPH = new HashSet<>(Arrays.asList("asAdmin", "by", "read", "write", "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", "read", "write", "iterate", "mapValues", "mapKeys")); http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/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 361b246..aba8a7f 100644 --- a/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs +++ b/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs @@ -1386,6 +1386,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) @@ -1722,4 +1731,4 @@ namespace Gremlin.Net.Process.Traversal } } -} \ No newline at end of file +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/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 4f39fa5..6479515 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 @@ -953,6 +953,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/e1ba81b4/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 6d56c5c..cffb5eb 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 @@ -434,6 +434,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/e1ba81b4/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 7ca44ba..6a2b700 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 @@ -180,6 +180,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(); @@ -249,7 +253,7 @@ public abstract class AbstractGremlinTest { public void printTraversalForm(final Traversal traversal) { logger.info(String.format("Testing: %s", name.getMethodName())); logger.info(" pre-strategy:" + traversal); - traversal.hasNext(); + if (!traversal.asAdmin().isLocked()) traversal.asAdmin().applyStrategies(); logger.info(" post-strategy:" + traversal); verifyUniqueStepIds(traversal.asAdmin()); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e1ba81b4/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java ---------------------------------------------------------------------- diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java index 2861724..e15fff8 100644 --- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java +++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java @@ -119,7 +119,7 @@ public abstract class AbstractGremlinProcessTest extends AbstractGremlinTest { public static <T> void checkResults(final List<T> expectedResults, final Traversal<?, T> traversal) { final List<T> results = traversal.toList(); - assertFalse(traversal.hasNext()); + assertThat(traversal.hasNext(), is(false)); if (expectedResults.size() != results.size()) { logger.error("Expected results: " + expectedResults); logger.error("Actual results: " + results); @@ -128,20 +128,19 @@ public abstract class AbstractGremlinProcessTest extends AbstractGremlinTest { for (T t : results) { if (t instanceof Map) { - assertThat("Checking map result existence: " + t, expectedResults.stream().filter(e -> e instanceof Map).filter(e -> internalCheckMap((Map) e, (Map) t)).findAny().isPresent(), is(true)); + assertThat("Checking map result existence: " + t, expectedResults.stream().anyMatch(e -> e instanceof Map && internalCheckMap((Map) e, (Map) t)), is(true)); } else if (t instanceof List) { - assertThat("Checking list result existence: " + t, expectedResults.stream().filter(e -> e instanceof List).filter(e -> internalCheckList((List) e, (List) t)).findAny().isPresent(), is(true)); + assertThat("Checking list result existence: " + t, expectedResults.stream().anyMatch(e -> e instanceof List && internalCheckList((List) e, (List) t)), is(true)); } else { assertThat("Checking result existence: " + t, expectedResults.contains(t), is(true)); } } final Map<T, Long> expectedResultsCount = new HashMap<>(); final Map<T, Long> resultsCount = new HashMap<>(); + expectedResults.forEach(t -> MapHelper.incr(expectedResultsCount, t, 1L)); + results.forEach(t -> MapHelper.incr(resultsCount, t, 1L)); assertEquals("Checking indexing is equivalent", expectedResultsCount.size(), resultsCount.size()); - expectedResults.forEach(t -> MapHelper.incr(expectedResultsCount, t, 1l)); - results.forEach(t -> MapHelper.incr(resultsCount, t, 1l)); expectedResultsCount.forEach((k, v) -> assertEquals("Checking result group counts", v, resultsCount.get(k))); - assertThat(traversal.hasNext(), is(false)); } public static <T> void checkResults(final Map<T, Long> expectedResults, final Traversal<?, T> traversal) {
