You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by dk...@apache.org on 2018/08/10 00:02:31 UTC
[01/14] tinkerpop git commit: TINKERPOP-1967 Added
connectedComponent() step [Forced Update!]
Repository: tinkerpop
Updated Branches:
refs/heads/TINKERPOP-1990 b0d8e78cb -> 0324c820b (forced update)
TINKERPOP-1967 Added connectedComponent() step
Deprecated the recipe for "Connected Components" but left the old content present as I felt it had educational value.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/0acceb90
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/0acceb90
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/0acceb90
Branch: refs/heads/TINKERPOP-1990
Commit: 0acceb90efc6516df20586d756765f94efc6cbf2
Parents: f88ace1
Author: Stephen Mallette <sp...@genoprime.com>
Authored: Thu May 17 14:44:01 2018 -0400
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Thu Aug 9 10:54:40 2018 -0400
----------------------------------------------------------------------
CHANGELOG.asciidoc | 1 +
docs/src/recipes/connected-components.asciidoc | 8 +-
docs/src/reference/the-graphcomputer.asciidoc | 6 +
docs/src/reference/the-traversal.asciidoc | 35 +++
docs/src/upgrade/release-3.4.x.asciidoc | 32 +++
.../tinkerpop/gremlin/jsr223/CoreImports.java | 4 +
.../ConnectedComponentVertexProgram.java | 234 +++++++++++++++++++
.../traversal/step/map/ConnectedComponent.java | 38 +++
.../ConnectedComponentVertexProgramStep.java | 98 ++++++++
.../gremlin/process/remote/RemoteGraph.java | 4 +
.../traversal/dsl/graph/GraphTraversal.java | 15 ++
.../traversal/dsl/graph/GraphTraversalTest.java | 2 +-
.../Process/Traversal/GraphTraversal.cs | 9 +
.../lib/process/graph-traversal.js | 10 +
.../gremlin_python/process/graph_traversal.py | 4 +
.../gremlin/process/ProcessComputerSuite.java | 2 +
.../step/map/ConnectedComponentTest.java | 117 ++++++++++
.../computer/SparkHadoopGraphProvider.java | 2 +
18 files changed, 619 insertions(+), 2 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 303d963..481a7d3 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -35,6 +35,7 @@ This release also includes changes from <<release-3-3-3, 3.3.3>>.
* Replaced `Parameterizing.addPropertyMutations()` with `Configuring.configure()`.
* Changed interface hierarchy for `Parameterizing` and `Mutating` interfaces as they are tightly related.
* Introduced the `with()` step modulator which can supply configuration options to `Configuring` steps.
+* Added `connectedComponent()` step and related `VertexProgram`.
* Added `supportsUpsert()` option to `VertexFeatures` and `EdgeFeatures`.
* `min()` and `max()` now support all types implementing `Comparable`.
* Change the `toString()` of `Path` to be standardized as other graph elements are.
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/docs/src/recipes/connected-components.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/recipes/connected-components.asciidoc b/docs/src/recipes/connected-components.asciidoc
index 46d61eb..70abdbd 100644
--- a/docs/src/recipes/connected-components.asciidoc
+++ b/docs/src/recipes/connected-components.asciidoc
@@ -18,7 +18,13 @@ limitations under the License.
== Connected Components
Gremlin can be used to find link:https://en.wikipedia.org/wiki/Connected_component_(graph_theory)[connected components]
-in a graph. Consider the following graph which has three connected components:
+in a graph. As of TinkerPop 3.4.0, the process has been simplified to the `connectedComponent()`-step which is
+described in more detail in the link:
+link:http://tinkerpop.apache.org/docs/x.y.z/reference/#connectedcomponent-step[Reference Documentation].
+
+The `connectedComponent()`-step replaces the original recipe described below from earlier versions of TinkerPop,
+however the algorithm from that old recipe remains interesting for educational purposes and has thus not been removed.
+The original recipe considers the following graph which has three connected components:
image:connected-components.png[width=600]
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/docs/src/reference/the-graphcomputer.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/reference/the-graphcomputer.asciidoc b/docs/src/reference/the-graphcomputer.asciidoc
index 1d7586c..9cd1c76 100644
--- a/docs/src/reference/the-graphcomputer.asciidoc
+++ b/docs/src/reference/the-graphcomputer.asciidoc
@@ -403,6 +403,12 @@ g.V().peerPressure().by('cluster').valueMap()
g.V().peerPressure().by(outE('knows')).by('cluster').valueMap()
----
+[[connectedcomponentvertexprogram]]
+=== ConnectedComponentVertexProgram
+
+The `ConnectedComponentVertexProgram` identifies link:https://en.wikipedia.org/wiki/Connected_component_(graph_theory)[Connected Component]
+instances in a graph. See <<connectedcomponent-step,`connectedComponent()`>>-step for more information.
+
[[bulkdumpervertexprogram]]
[[clonevertexprogram]]
=== CloneVertexProgram
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/docs/src/reference/the-traversal.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/reference/the-traversal.asciidoc b/docs/src/reference/the-traversal.asciidoc
index 7d385c8..4d5b48a 100644
--- a/docs/src/reference/the-traversal.asciidoc
+++ b/docs/src/reference/the-traversal.asciidoc
@@ -625,6 +625,41 @@ g.V().coin(1.0)
link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.html#coin-double-++[`coin(double)`]
+[[connectedcomponent-step]]
+=== ConnectedComponent Step
+
+The `connectedComponent()` step performs a computation to identify link:https://en.wikipedia.org/wiki/Connected_component_(graph_theory)[Connected Component]
+instances in a graph. When this step completes, the vertices will be labelled with a component identifier to denote
+the component to which they are associated.
+
+IMPORTANT: The `connectedComponent()`-step is a `VertexComputing`-step and as such, can only be used against a graph
+that supports `GraphComputer` (OLAP).
+
+[gremlin-groovy,modern]
+----
+g = graph.traversal().withComputer()
+g.V().
+ connectedComponent().
+ with(ConnectedComponent.propertyName, 'component').
+ project('name','component').
+ by('name').
+ by('component')
+g.V().hasLabel('person').
+ connectedComponent().
+ with(ConnectedComponent.propertyName, 'component').
+ with(ConnectedComponent.edges, outE('knows')).
+ project('name','component').
+ by('name').
+ by('component')
+----
+
+Note the use of the `with()` modulating step which provides configuration options to the algorithm. It takes
+configuration keys from the `ConnectedComponent` class and is automatically imported to the Gremlin Console.
+
+*Additional References*
+
+link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.html#connectedComponent--++[`connectedComponent()`]
+
[[constant-step]]
=== Constant Step
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/docs/src/upgrade/release-3.4.x.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/upgrade/release-3.4.x.asciidoc b/docs/src/upgrade/release-3.4.x.asciidoc
index 587e761..00f2635 100644
--- a/docs/src/upgrade/release-3.4.x.asciidoc
+++ b/docs/src/upgrade/release-3.4.x.asciidoc
@@ -65,6 +65,38 @@ release where breaking changes are allowed.
See: link:https://issues.apache.org/jira/browse/TINKERPOP-1975[TINKERPOP-1975],
link:http://tinkerpop.apache.org/docs/3.4.0/reference/#with-step[Reference Documentation]
+==== connectedComponent() Step
+
+In prior version of TinkerPop, it was recommended that the identification of
+link:https://en.wikipedia.org/wiki/Connected_component_(graph_theory)[Connected Component] instances in a graph be
+computed by way of a reasonably complex bit of Gremlin that looked something like this:
+
+[source,groovy]
+----
+g.V().emit(cyclicPath().or().not(both())).repeat(both()).until(cyclicPath()).
+ path().aggregate("p").
+ unfold().dedup().
+ map(__.as("v").select("p").unfold().
+ filter(unfold().where(eq("v"))).
+ unfold().dedup().order().by(id).fold()).
+ dedup()
+----
+
+The above approach had a number of drawbacks that included a large execution cost as well as incompatibilities in OLAP.
+To simplify usage of this commonly use graph algorithm, TinkerPop 3.4.0 introduces the `connectedComponent()` step
+which reduces the above operation to:
+
+[source,groovy]
+----
+g.withComputer().V().connectedComponent()
+----
+
+It is important to note that this step does require the use of a `GraphComputer` to work, as it utilizes a
+`VertexProgram` behind the scenes.
+
+See: link:https://issues.apache.org/jira/browse/TINKERPOP-1967[TINKERPOP-1967],
+link:http://tinkerpop.apache.org/docs/x.y.z/reference/#connectedcomponent-step[Reference Documentation]
+
==== io() Step
There have been some important changes to IO operations for reading and writing graph data. The use of `Graph.io()`
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/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..eb3b831 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
@@ -42,6 +42,7 @@ import org.apache.tinkerpop.gremlin.process.computer.bulkloading.BulkLoaderVerte
import org.apache.tinkerpop.gremlin.process.computer.bulkloading.IncrementalBulkLoader;
import org.apache.tinkerpop.gremlin.process.computer.bulkloading.OneTimeBulkLoader;
import org.apache.tinkerpop.gremlin.process.computer.clone.CloneVertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.clustering.connected.ConnectedComponentVertexProgram;
import org.apache.tinkerpop.gremlin.process.computer.clustering.peerpressure.ClusterCountMapReduce;
import org.apache.tinkerpop.gremlin.process.computer.clustering.peerpressure.ClusterPopulationMapReduce;
import org.apache.tinkerpop.gremlin.process.computer.clustering.peerpressure.PeerPressureVertexProgram;
@@ -49,6 +50,7 @@ import org.apache.tinkerpop.gremlin.process.computer.ranking.pagerank.PageRankMa
import org.apache.tinkerpop.gremlin.process.computer.ranking.pagerank.PageRankVertexProgram;
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.ConnectedComponent;
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.strategy.decoration.VertexProgramStrategy;
@@ -251,6 +253,8 @@ public final class CoreImports {
// graph computer
CLASS_IMPORTS.add(Computer.class);
CLASS_IMPORTS.add(ComputerResult.class);
+ CLASS_IMPORTS.add(ConnectedComponent.class);
+ CLASS_IMPORTS.add(ConnectedComponentVertexProgram.class);
CLASS_IMPORTS.add(GraphComputer.class);
CLASS_IMPORTS.add(Memory.class);
CLASS_IMPORTS.add(VertexProgram.class);
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java
new file mode 100644
index 0000000..de718f1
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java
@@ -0,0 +1,234 @@
+/*
+ * 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.clustering.connected;
+
+import org.apache.commons.configuration.BaseConfiguration;
+import org.apache.commons.configuration.Configuration;
+import org.apache.commons.configuration.ConfigurationUtils;
+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.util.AbstractVertexProgramBuilder;
+import org.apache.tinkerpop.gremlin.process.traversal.Operator;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+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.VertexProperty;
+
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+
+/**
+ * Identifies "Connected Component" instances in a graph by assigning a component identifier (the lexicographically
+ * least string value of the vertex in the component) to each vertex.
+ *
+ * @author Stephen Mallette (http://stephen.genoprime.com)
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+public class ConnectedComponentVertexProgram implements VertexProgram<String> {
+
+ public static final String COMPONENT = "gremlin.connectedComponentVertexProgram.component";
+ private static final String PROPERTY = "gremlin.connectedComponentVertexProgram.property";
+ private static final String EDGE_TRAVERSAL = "gremlin.pageRankVertexProgram.edgeTraversal";
+ private static final String HAS_HALTED = "gremlin.connectedComponentVertexProgram.hasHalted";
+ private static final String VOTE_TO_HALT = "gremlin.connectedComponentVertexProgram.voteToHalt";
+
+ private static final Set<MemoryComputeKey> MEMORY_COMPUTE_KEYS = Collections.singleton(MemoryComputeKey.of(VOTE_TO_HALT, Operator.and, false, true));
+ private MessageScope.Local<?> scope = MessageScope.Local.of(__::bothE);
+ private Set<MessageScope> scopes;
+ private String property = COMPONENT;
+ private boolean hasHalted = false;
+ private PureTraversal<Vertex, Edge> edgeTraversal = null;
+ private Configuration configuration;
+
+ private ConnectedComponentVertexProgram() {}
+
+ @Override
+ public void loadState(final Graph graph, final Configuration config) {
+ configuration = new BaseConfiguration();
+ if (config != null) {
+ ConfigurationUtils.copy(config, configuration);
+ }
+
+ if (configuration.containsKey(EDGE_TRAVERSAL)) {
+ this.edgeTraversal = PureTraversal.loadState(configuration, EDGE_TRAVERSAL, graph);
+ this.scope = MessageScope.Local.of(() -> this.edgeTraversal.get().clone());
+ }
+
+ scopes = new HashSet<>(Collections.singletonList(scope));
+
+ this.property = configuration.getString(PROPERTY, COMPONENT);
+ this.hasHalted = configuration.getBoolean(HAS_HALTED, false);
+ }
+
+ @Override
+ public void storeState(final Configuration config) {
+ VertexProgram.super.storeState(config);
+ if (configuration != null) {
+ ConfigurationUtils.copy(configuration, config);
+ }
+ }
+
+ @Override
+ public void setup(final Memory memory) {
+ memory.set(VOTE_TO_HALT, true);
+ }
+
+ @Override
+ public void execute(final Vertex vertex, final Messenger<String> messenger, final Memory memory) {
+ if (memory.isInitialIteration()) {
+ // on the first pass, just initialize the component to its own id then pass it to all adjacent vertices
+ // for evaluation
+ vertex.property(VertexProperty.Cardinality.single, property, vertex.id().toString());
+
+ // no need to send messages from traversers that were filtered - happens for stuff like
+ // g.V().hasLabel('software').connectedComponent() (i.e. when there is a TraversalVertexProgram in the mix
+ // halting traversers. only want to send messages from traversers that are still hanging about after
+ // the filter. the unfiltered vertices can only react to messages sent to them. of course, this can
+ // lead to weirdness in results.
+ if (vertex.edges(Direction.BOTH).hasNext() && !(hasHalted && !vertex.property(TraversalVertexProgram.HALTED_TRAVERSERS).isPresent())) {
+ // since there was message passing we don't want to halt on the first round. this should only trigger
+ // a single pass finish if the graph is completely disconnected (technically, it won't even really
+ // work in cases where halted traversers come into play
+ messenger.sendMessage(scope, vertex.id().toString());
+ memory.add(VOTE_TO_HALT, false);
+ }
+ } else {
+ // by the second iteration all vertices that matter should have a component assigned
+ String currentComponent = vertex.value(property);
+ boolean different = false;
+
+ // iterate through messages received and determine if there is a component that has a lesser value than
+ // the currently assigned one
+ final Iterator<String> componentIterator = messenger.receiveMessages();
+ while(componentIterator.hasNext()) {
+ final String candidateComponent = componentIterator.next();
+ if (candidateComponent.compareTo(currentComponent) < 0) {
+ currentComponent = candidateComponent;
+ different = true;
+ }
+ }
+
+ // if there is a better component then assign it and notify adjacent vertices. triggering the message
+ // passing should not halt future executions
+ if (different) {
+ vertex.property(VertexProperty.Cardinality.single, property, currentComponent);
+ messenger.sendMessage(scope, currentComponent);
+ memory.add(VOTE_TO_HALT, false);
+ }
+ }
+ }
+
+ @Override
+ public Set<VertexComputeKey> getVertexComputeKeys() {
+ return new HashSet<>(Collections.singletonList(VertexComputeKey.of(property, false)));
+ }
+
+ @Override
+ public Set<MemoryComputeKey> getMemoryComputeKeys() {
+ return MEMORY_COMPUTE_KEYS;
+ }
+
+ @Override
+ public boolean terminate(final Memory memory) {
+ final boolean voteToHalt = memory.<Boolean>get(VOTE_TO_HALT);
+ if (voteToHalt) {
+ return true;
+ } else {
+ // it is basically always assumed that the program will want to halt, but if message passing occurs, the
+ // program will want to continue, thus reset false values to true for future iterations
+ memory.set(VOTE_TO_HALT, true);
+ return false;
+ }
+ }
+
+ @Override
+ public Set<MessageScope> getMessageScopes(final Memory memory) {
+ return scopes;
+ }
+
+ @Override
+ public GraphComputer.ResultGraph getPreferredResultGraph() {
+ return GraphComputer.ResultGraph.NEW;
+ }
+
+ @Override
+ public GraphComputer.Persist getPreferredPersist() {
+ return GraphComputer.Persist.VERTEX_PROPERTIES;
+ }
+
+
+ @Override
+ @SuppressWarnings("CloneDoesntCallSuperClone,CloneDoesntDeclareCloneNotSupportedException")
+ public ConnectedComponentVertexProgram clone() {
+ return this;
+ }
+
+ @Override
+ public Features getFeatures() {
+ return new Features() {
+ @Override
+ public boolean requiresLocalMessageScopes() {
+ return true;
+ }
+
+ @Override
+ public boolean requiresVertexPropertyAddition() {
+ return true;
+ }
+ };
+ }
+
+ public static ConnectedComponentVertexProgram.Builder build() {
+ return new ConnectedComponentVertexProgram.Builder();
+ }
+
+ public static final class Builder extends AbstractVertexProgramBuilder<ConnectedComponentVertexProgram.Builder> {
+
+ private Builder() {
+ super(ConnectedComponentVertexProgram.class);
+ }
+
+ public ConnectedComponentVertexProgram.Builder hasHalted(final boolean hasHalted) {
+ this.configuration.setProperty(HAS_HALTED, hasHalted);
+ return this;
+ }
+
+ public ConnectedComponentVertexProgram.Builder edges(final Traversal.Admin<Vertex, Edge> edgeTraversal) {
+ PureTraversal.storeState(this.configuration, EDGE_TRAVERSAL, edgeTraversal);
+ return this;
+ }
+
+ public ConnectedComponentVertexProgram.Builder property(final String key) {
+ this.configuration.setProperty(PROPERTY, key);
+ return this;
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponent.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponent.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponent.java
new file mode 100644
index 0000000..85558bc
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponent.java
@@ -0,0 +1,38 @@
+/*
+ * 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.dsl.graph.GraphTraversal;
+import org.apache.tinkerpop.gremlin.structure.Graph;
+
+/**
+ * Configuration options to be passed to the {@link GraphTraversal#with(String, Object)} step on
+ * {@link GraphTraversal#connectedComponent()} ()}.
+ */
+public class ConnectedComponent {
+ /**
+ * Configures the edge to traverse when calculating the pagerank.
+ */
+ public static final String edges = Graph.Hidden.hide("tinkerpop.connectedComponent.edges");
+
+ /**
+ * Configures the name of the property within which to store the pagerank value.
+ */
+ public static final String propertyName = Graph.Hidden.hide("tinkerpop.connectedComponent.propertyName");
+}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponentVertexProgramStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponentVertexProgramStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponentVertexProgramStep.java
new file mode 100644
index 0000000..edeb497
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponentVertexProgramStep.java
@@ -0,0 +1,98 @@
+/*
+ * 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.GraphFilter;
+import org.apache.tinkerpop.gremlin.process.computer.Memory;
+import org.apache.tinkerpop.gremlin.process.computer.clustering.connected.ConnectedComponentVertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.TraversalVertexProgram;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.Configuring;
+import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.Parameters;
+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;
+
+/**
+ * @author Stephen Mallette (http://stephen.genoprime.com)
+ */
+public final class ConnectedComponentVertexProgramStep extends VertexProgramStep implements TraversalParent, Configuring {
+
+ private Parameters parameters = new Parameters();
+ private PureTraversal<Vertex, Edge> edgeTraversal;
+ private String clusterProperty = ConnectedComponentVertexProgram.COMPONENT;
+
+ public ConnectedComponentVertexProgramStep(final Traversal.Admin traversal) {
+ super(traversal);
+ this.configure(ConnectedComponent.edges, __.<Vertex>bothE());
+ }
+
+ @Override
+ public void configure(final Object... keyValues) {
+ if (keyValues[0].equals(ConnectedComponent.edges)) {
+ if (!(keyValues[1] instanceof Traversal))
+ throw new IllegalArgumentException("ConnectedComponent.edges requires a Traversal as its argument");
+ this.edgeTraversal = new PureTraversal<>(((Traversal<Vertex,Edge>) keyValues[1]).asAdmin());
+ this.integrateChild(this.edgeTraversal.get());
+ } else if (keyValues[0].equals(ConnectedComponent.propertyName)) {
+ if (!(keyValues[1] instanceof String))
+ throw new IllegalArgumentException("ConnectedComponent.propertyName requires a String as its argument");
+ this.clusterProperty = (String) keyValues[1];
+ } else {
+ this.parameters.set(this, keyValues);
+ }
+ }
+
+ @Override
+ public Parameters getParameters() {
+ return parameters;
+ }
+
+ @Override
+ public int hashCode() {
+ return super.hashCode() ^ this.clusterProperty.hashCode();
+ }
+
+ @Override
+ public String toString() {
+ return StringFactory.stepString(this, this.clusterProperty, new GraphFilter(this.computer));
+ }
+
+ @Override
+ public ConnectedComponentVertexProgram generateProgram(final Graph graph, final Memory memory) {
+ final Traversal.Admin<Vertex, Edge> detachedTraversal = this.edgeTraversal.getPure();
+ detachedTraversal.setStrategies(TraversalStrategies.GlobalCache.getStrategies(graph.getClass()));
+ return ConnectedComponentVertexProgram.build().
+ hasHalted(memory.exists(TraversalVertexProgram.HALTED_TRAVERSERS)).
+ edges(detachedTraversal).
+ property(this.clusterProperty).create(graph);
+ }
+
+ @Override
+ public ConnectedComponentVertexProgramStep clone() {
+ return (ConnectedComponentVertexProgramStep) super.clone();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/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 f19d5fa..9bc1771 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
@@ -48,6 +48,10 @@ import java.util.Iterator;
@Graph.OptIn(Graph.OptIn.SUITE_PROCESS_STANDARD)
@Graph.OptIn(Graph.OptIn.SUITE_PROCESS_COMPUTER)
@Graph.OptOut(
+ test = "org.apache.tinkerpop.gremlin.process.traversal.step.map.ConnectedComponentTest",
+ method = "*",
+ reason = "hmmmm")
+@Graph.OptOut(
test = "org.apache.tinkerpop.gremlin.process.traversal.CoreTraversalTest",
method = "*",
reason = "The test suite does not support profiling or lambdas and for groovy tests: 'Could not locate method: GraphTraversalSource.withStrategies([{traversalCategory=interface org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy$DecorationStrategy}])'")
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/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..4fd247f 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
@@ -19,6 +19,8 @@
package org.apache.tinkerpop.gremlin.process.traversal.dsl.graph;
import org.apache.tinkerpop.gremlin.process.computer.VertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.clustering.connected.ConnectedComponentVertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ConnectedComponentVertexProgramStep;
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;
@@ -2452,6 +2454,18 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> {
}
/**
+ * Executes a Connected Component algorithm over the graph.
+ *
+ * @return the traversal with the appended {@link ConnectedComponentVertexProgram}
+ * @see <a href="http://tinkerpop.apache.org/docs/${project.version}/reference/#connectedcomponent-step" target="_blank">Reference Documentation - ConnectedComponent Step</a>
+ * @since 3.4.0
+ */
+ public default GraphTraversal<S, E> connectedComponent() {
+ this.asAdmin().getBytecode().addStep(Symbols.connectedComponent);
+ return this.asAdmin().addStep((Step<E, E>) new ConnectedComponentVertexProgramStep(this.asAdmin()));
+ }
+
+ /**
* Executes an arbitrary {@link VertexProgram} over the graph.
*
* @return the traversal with the appended {@link ProgramVertexProgramStep}
@@ -2882,6 +2896,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 connectedComponent = "connectedComponent";
public static final String program = "program";
public static final String by = "by";
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/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..40ca312 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", "connectedComponent", "peerPressure", "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/0acceb90/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..e2fa3e1 100644
--- a/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs
+++ b/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs
@@ -401,6 +401,15 @@ namespace Gremlin.Net.Process.Traversal
}
/// <summary>
+ /// Adds the connectedComponent step to this <see cref="GraphTraversal{SType, EType}" />.
+ /// </summary>
+ public GraphTraversal<S, E> ConnectedComponent ()
+ {
+ Bytecode.AddStep("connectedComponent");
+ return Wrap<S, E>(this);
+ }
+
+ /// <summary>
/// Adds the constant step to this <see cref="GraphTraversal{SType, EType}" />.
/// </summary>
public GraphTraversal<S, E2> Constant<E2> (E2 e)
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/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..1c8d639 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
@@ -353,6 +353,16 @@ class GraphTraversal extends Traversal {
}
/**
+ * Graph traversal connectedComponent method.
+ * @param {...Object} args
+ * @returns {GraphTraversal}
+ */
+ connectedComponent(...args) {
+ this.bytecode.addStep('connectedComponent', args);
+ return this;
+ }
+
+ /**
* Graph traversal constant method.
* @param {...Object} args
* @returns {GraphTraversal}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/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 f8b8285..b073aa8 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
@@ -194,6 +194,10 @@ class GraphTraversal(Traversal):
self.bytecode.add_step("coin", *args)
return self
+ def connectedComponent(self, *args):
+ self.bytecode.add_step("connectedComponent", *args)
+ return self
+
def constant(self, *args):
self.bytecode.add_step("constant", *args)
return self
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/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 eab562d..6466ae8 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
@@ -50,6 +50,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.filter.TailTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.WhereTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.AddEdgeTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.CoalesceTest;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.ConnectedComponentTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.ConstantTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.CountTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.FlatMapTest;
@@ -143,6 +144,7 @@ public class ProcessComputerSuite extends AbstractGremlinSuite {
// map
CoalesceTest.Traversals.class,
+ ConnectedComponentTest.Traversals.class,
ConstantTest.Traversals.class,
CountTest.Traversals.class,
FlatMapTest.Traversals.class,
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
new file mode 100644
index 0000000..25e618a
--- /dev/null
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
@@ -0,0 +1,117 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.tinkerpop.gremlin.process.traversal.step.map;
+
+import org.apache.tinkerpop.gremlin.LoadGraphWith;
+import org.apache.tinkerpop.gremlin.process.computer.clustering.connected.ConnectedComponentVertexProgram;
+import org.apache.tinkerpop.gremlin.process.AbstractGremlinProcessTest;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ConnectedComponent;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.junit.Test;
+
+import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.MODERN;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.bothE;
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author Stephen Mallette (http://stephen.genoprime.com)
+ */
+public abstract class ConnectedComponentTest extends AbstractGremlinProcessTest {
+
+ public abstract Traversal<Vertex, Vertex> get_g_V_connectedComponent();
+
+ public abstract Traversal<Vertex, Vertex> get_g_V_hasLabelXsoftwareX_connectedComponent();
+
+ public abstract Traversal<Vertex, Vertex> get_g_V_connectedComponent_withXedges_bothEXknowsXX_withXpropertyName_clusterX();
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_connectedComponent() {
+ final Traversal<Vertex, Vertex> traversal = get_g_V_connectedComponent();
+ printTraversalForm(traversal);
+ int counter = 0;
+ while (traversal.hasNext()) {
+ final Vertex vertex = traversal.next();
+ counter++;
+ assertEquals("1", vertex.value(ConnectedComponentVertexProgram.COMPONENT));
+ }
+ assertEquals(6, counter);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_hasLabelXsoftwareX_connectedComponent() {
+ final Traversal<Vertex, Vertex> traversal = get_g_V_hasLabelXsoftwareX_connectedComponent();
+ printTraversalForm(traversal);
+ int counter = 0;
+ while (traversal.hasNext()) {
+ final Vertex vertex = traversal.next();
+ final String name = vertex.value("name");
+ switch (name) {
+ case "lop":
+ case "ripple":
+ assertEquals("3", vertex.value(ConnectedComponentVertexProgram.COMPONENT));
+ break;
+ }
+ counter++;
+ }
+ assertEquals(2, counter);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_connectedComponent_withXEDGES_bothEXknowsXX_withXPROPERTY_NAME_clusterX() {
+ final Traversal<Vertex, Vertex> traversal = get_g_V_connectedComponent_withXedges_bothEXknowsXX_withXpropertyName_clusterX();
+ printTraversalForm(traversal);
+ int counter = 0;
+ while (traversal.hasNext()) {
+ final Vertex vertex = traversal.next();
+ final String name = vertex.value("name");
+ switch (name) {
+ case "marko":
+ case "vadas":
+ case "josh":
+ assertEquals("1", vertex.value("cluster"));
+ break;
+ case "peter":
+ assertEquals("6", vertex.value("cluster"));
+ break;
+ }
+ counter++;
+ }
+ assertEquals(4, counter);
+ }
+
+ public static class Traversals extends ConnectedComponentTest {
+ @Override
+ public Traversal<Vertex, Vertex> get_g_V_connectedComponent() {
+ return g.V().connectedComponent();
+ }
+
+ @Override
+ public Traversal<Vertex, Vertex> get_g_V_hasLabelXsoftwareX_connectedComponent() {
+ return g.V().hasLabel("software").connectedComponent();
+ }
+ @Override
+ public Traversal<Vertex, Vertex> get_g_V_connectedComponent_withXedges_bothEXknowsXX_withXpropertyName_clusterX() {
+ return g.V().hasLabel("person").connectedComponent().with(ConnectedComponent.edges, bothE("knows")).with(ConnectedComponent.propertyName, "cluster");
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0acceb90/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/SparkHadoopGraphProvider.java
----------------------------------------------------------------------
diff --git a/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/SparkHadoopGraphProvider.java b/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/SparkHadoopGraphProvider.java
index c778c6d..2f727c8 100644
--- a/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/SparkHadoopGraphProvider.java
+++ b/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/SparkHadoopGraphProvider.java
@@ -39,6 +39,7 @@ import org.apache.tinkerpop.gremlin.process.computer.Computer;
import org.apache.tinkerpop.gremlin.process.computer.GraphComputer;
import org.apache.tinkerpop.gremlin.process.computer.util.ComputerGraph;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.ConnectedComponentTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.PageRankTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.PeerPressureTest;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.ProgramTest;
@@ -115,6 +116,7 @@ public class SparkHadoopGraphProvider extends AbstractFileGraphProvider {
if (null != loadGraphWith &&
!test.equals(ProgramTest.Traversals.class) &&
!test.equals(PageRankTest.Traversals.class) &&
+ !test.equals(ConnectedComponentTest.Traversals.class) &&
!test.equals(PeerPressureTest.Traversals.class) &&
!test.equals(FileSystemStorageCheck.class) &&
!testMethodName.equals("shouldSupportJobChaining") && // GraphComputerTest.shouldSupportJobChaining
[04/14] tinkerpop git commit: Merged vtslab recipe for connected
components
Posted by dk...@apache.org.
Merged vtslab recipe for connected components
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/002560a5
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/002560a5
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/002560a5
Branch: refs/heads/TINKERPOP-1990
Commit: 002560a5d9584119d5a5af7f874d110583390741
Parents: 0acceb9
Author: HadoopMarc <vt...@xs4all.nl>
Authored: Mon May 21 14:03:54 2018 +0200
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Thu Aug 9 10:54:41 2018 -0400
----------------------------------------------------------------------
docs/src/recipes/connected-components.asciidoc | 123 +++++++++++++-------
1 file changed, 83 insertions(+), 40 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/002560a5/docs/src/recipes/connected-components.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/recipes/connected-components.asciidoc b/docs/src/recipes/connected-components.asciidoc
index 70abdbd..edbeec5 100644
--- a/docs/src/recipes/connected-components.asciidoc
+++ b/docs/src/recipes/connected-components.asciidoc
@@ -14,17 +14,31 @@ 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.
////
+
+// @author Daniel Kuppitz (anwer on gremlin user list)
+// @author Robert Dale (answer on gremlin user list)
+// @author Marc de Lignie
+
[[connected-components]]
== Connected Components
Gremlin can be used to find link:https://en.wikipedia.org/wiki/Connected_component_(graph_theory)[connected components]
-in a graph. As of TinkerPop 3.4.0, the process has been simplified to the `connectedComponent()`-step which is
-described in more detail in the link:
-link:http://tinkerpop.apache.org/docs/x.y.z/reference/#connectedcomponent-step[Reference Documentation].
+in a graph. In a directed graph like in TinkerPop, components can be weakly or strongly connected. This recipe is
+restricted to finding link:https://en.wikipedia.org/wiki/Directed_graph#Directed_graph_connectivity[weakly
+connected components], in which the direction of edges is not taken into account.
+
+Depending on the size of the graph, three solution regimes can be discriminated:
+
+1. Small graphs that fit in the memory of a single machine
+
+2. Medium graphs backed by storage for which a linear scan is still feasible. This regime is left to third party
+TinkerPop implementations, since TinkerPop itself has no storage-backed reference implementations. The idea is that
+component membership is stored in the graph, rather than in memory.
-The `connectedComponent()`-step replaces the original recipe described below from earlier versions of TinkerPop,
-however the algorithm from that old recipe remains interesting for educational purposes and has thus not been removed.
-The original recipe considers the following graph which has three connected components:
+3. Large graphs requiring an OLAP approach to yield results in a reasonable time.
+
+
+These regimes are discussed separately using the following graph with three weakly connected components:
image:connected-components.png[width=600]
@@ -41,46 +55,75 @@ g.addV().property(id, "A").as("a").
addE("link").from("d").to("e").iterate()
----
-One way to detect the various subgraphs would be to do something like this:
+
+===== Small graphs
+
+Connected components in a small graph can be determined with both an OLTP traversal and the OLAP
+`connectedComponent()`-step. The `connectedComponent()`-step is available as of TinkerPop 3.4.0 and is
+described in more detail in the
+link:http://tinkerpop.apache.org/docs/x.y.z/reference/#connectedcomponent-step[Reference Documentation].
+
+A straightforward way to detect the various subgraphs with an OLTP traversal is to do this:
[gremlin-groovy,existing]
----
-g.V().emit(cyclicPath().or().not(both())).repeat(both()).until(cyclicPath()). <1>
- path().aggregate("p"). <2>
- unfold().dedup(). <3>
- map(__.as("v").select("p").unfold(). <4>
- filter(unfold().where(eq("v"))).
- unfold().dedup().order().by(id).fold()).
- dedup() <5>
+g.V().emit(cyclicPath().or().not(both())). <1>
+ repeat(__.where(without('a')).store('a').both()).until(cyclicPath()). <2>
+ group().by(path().unfold().limit(1)). <3>
+ by(path().unfold().dedup().fold()). <4>
+ select(values).unfold() <5>
----
-<1> Iterate all vertices and repeatedly traverse over both incoming and outgoing edges (TinkerPop doesn't support
-unidirectional graphs directly so it must be simulated by ignoring the direction with `both`). Note the use of `emit`
-prior to `repeat` as this allows for return of a single length path.
-<2> Aggregate the `path()` of the emitted vertices to "p". It is within these paths that the list of connected
-components will be identified. Obviously the paths list are duplicative in the sense that they contains different
-paths traveled over the same vertices.
-<3> Unroll the elements in the path list with `unfold` and `dedup`.
-<4> Use the first vertex in each path to filter against the paths stored in "p". When a path is found that has the
-vertex in it, dedup the vertices in the path, order it by the identifier. Each path output from this `map` step
-represents a connected component.
-<5> The connected component list is duplicative given the nature of the paths in "p", but now that the vertices within
-the paths are ordered, a final `dedup` will make the list of connective components unique.
-
-NOTE: This is a nice example of where running smaller pieces of a large Gremlin statement make it easier to see what
-is happening at each step. Consider running this example one line at a time (or perhaps even in a step at a time) to
-see the output at each point.
-
-While the above approach returns results nicely, the traversal doesn't appear to work with OLAP. A less efficient
-approach, but one more suited for OLAP execution looks quite similar but does not use `dedup` as heavily (thus
-`GraphComputer` is forced to analyze far more paths):
+<1> The initial emit() step allows for output of isolated vertices, in addition to the discovery of
+components as described in (2).
+
+<2> The entire component to which the first returned vertex belongs, is visited. To allow for components of any
+structure, a repeat loop is applied that only stops for a particular branch of the component when it detects a cyclic
+path. Collection `'a'` is used to keep track of visited vertices, for both subtraversals within a component
+and new traversals resulting from the `g.V()` linear scan.
+
+<3> While `'a'` nicely keeps track of vertices already visited, the actual components need to be extracted from the
+path information of surviving traversers. The `path().unfold().limit(1)` closure provides the starting vertex
+of surviving traversers, which can be used to group the components.
+
+<4> This clause collects the unique vertices from all paths with the same starting vertex, thus from the same
+weak component.
+
+<5> The values of the groupby map contain the lists of vertices making up the requested components.
+
+This algorithm completes in linear time with the number of vertices and edges, because a traversal is started for each
+vertex and each edge with its associated out-vertex is visited exactly once.
+
+
+==== Large graphs
+
+Large graphs require an OLAP solution with a custom VertexProgram that can be run using a graph implementation's
+GraphComputer, in particular `SparkGraphComputer` on a `HadoopGraph`. The OLAP solution also runs faster for most
+medium-sized graphs, that is when these graph have a 'natural' structure with a limited maximum path length.
+
+The TinkerPop library of vertex programs contains the `WeakComponentsVertexProgram` which can be run in the same
+way as the link:http://tinkerpop.apache.org/docs/x.y.z/reference/#peerpressurevertexprogram[PeerPressureVertexProgram]:
[gremlin-groovy,existing]
----
-g.withComputer().V().emit(cyclicPath().or().not(both())).repeat(both()).until(cyclicPath()).
- aggregate("p").by(path()).cap("p").unfold().limit(local, 1).
- map(__.as("v").select("p").unfold().
- filter(unfold().where(eq("v"))).
- unfold().dedup().order().by(id).fold()
- ).toSet()
+result = g.getGraph().compute().
+ program(WeakComponentsVertexProgram.build().maxIterations(100).create()).
+ mapReduce(ClusterPopulationMapReduce.build().create()).
+ mapReduce(ClusterCountMapReduce.build().create()).
+ submit().get()
+result.memory().clusterPopulation
+gResult = result.graph().traversal()
+gResult.V().valueMap(true)
----
+
+The vertex program has interconnected vertices exchange id's and store the lowest id until no vertex receives a
+lower id. This algorithm is commonly applied in
+link:https://en.wikipedia.org/wiki/Bulk_synchronous_parallel[bulk synchronous parallel] systems, e.g. in
+link:https://spark.apache.org/graphx[Apache Spark GraphX].
+
+==== Scalability
+
+ToDo:
+ - limits and run time regime 1
+ - test of friendster graph regime 3
+ - discuss: link:http://www.vldb.org/pvldb/vol7/p1821-yan.pdf[http://www.vldb.org/pvldb/vol7/p1821-yan.pdf]
\ No newline at end of file
[11/14] tinkerpop git commit: TINKERPOP-1967 Rewrote
connectedComponent() test to be more GLV friendly
Posted by dk...@apache.org.
TINKERPOP-1967 Rewrote connectedComponent() test to be more GLV friendly
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/2cc2aed5
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/2cc2aed5
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/2cc2aed5
Branch: refs/heads/TINKERPOP-1990
Commit: 2cc2aed50d95f0f943fb012b421d4bcd0761a24d
Parents: cbae0a3
Author: Stephen Mallette <sp...@genoprime.com>
Authored: Thu Aug 9 11:25:55 2018 -0400
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Thu Aug 9 11:25:55 2018 -0400
----------------------------------------------------------------------
.../step/map/ConnectedComponentTest.java | 70 +++++++++-----------
1 file changed, 30 insertions(+), 40 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2cc2aed5/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
index 3133382..a542bed 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
@@ -19,13 +19,15 @@
package org.apache.tinkerpop.gremlin.process.traversal.step.map;
import org.apache.tinkerpop.gremlin.LoadGraphWith;
-import org.apache.tinkerpop.gremlin.process.computer.clustering.connected.ConnectedComponentVertexProgram;
import org.apache.tinkerpop.gremlin.process.AbstractGremlinProcessTest;
import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ConnectedComponent;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
import org.junit.Test;
+import java.util.Map;
+
import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.MODERN;
import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.bothE;
import static org.junit.Assert.assertEquals;
@@ -35,55 +37,43 @@ import static org.junit.Assert.assertEquals;
*/
public abstract class ConnectedComponentTest extends AbstractGremlinProcessTest {
- public abstract Traversal<Vertex, Vertex> get_g_V_connectedComponent();
+ public abstract Traversal<Vertex, Vertex> get_g_V_connectedComponent_hasXcomponentX();
- public abstract Traversal<Vertex, Vertex> get_g_V_hasLabelXsoftwareX_connectedComponent();
+ public abstract Traversal<Vertex, Map<String,Object>> get_g_V_hasLabelXsoftwareX_connectedComponent_project_byXnameX_byXcomponentX();
- public abstract Traversal<Vertex, Vertex> get_g_V_dedup_connectedComponent();
+ public abstract Traversal<Vertex, Vertex> get_g_V_dedup_connectedComponent_hasXcomponentX();
- public abstract Traversal<Vertex, Vertex> get_g_V_connectedComponent_withXedges_bothEXknowsXX_withXpropertyName_clusterX();
+ public abstract Traversal<Vertex, Map<String,Object>> get_g_V_connectedComponent_withXedges_bothEXknowsXX_withXpropertyName_clusterX_project_byXnameX_byXclusterX();
@Test
@LoadGraphWith(MODERN)
- public void g_V_connectedComponent() {
- final Traversal<Vertex, Vertex> traversal = get_g_V_connectedComponent();
+ public void g_V_connectedComponent_hasXcomponentX() {
+ final Traversal<Vertex, Vertex> traversal = get_g_V_connectedComponent_hasXcomponentX();
printTraversalForm(traversal);
- int counter = 0;
- while (traversal.hasNext()) {
- final Vertex vertex = traversal.next();
- counter++;
- assertEquals("1", vertex.value(ConnectedComponentVertexProgram.COMPONENT));
- }
- assertEquals(6, counter);
+ assertEquals(6, IteratorUtils.count(traversal));
}
@Test
@LoadGraphWith(MODERN)
- public void g_V_dedup_connectedComponent() {
- final Traversal<Vertex, Vertex> traversal = get_g_V_dedup_connectedComponent();
+ public void g_V_dedup_connectedComponent_hasXcomponentX() {
+ final Traversal<Vertex, Vertex> traversal = get_g_V_dedup_connectedComponent_hasXcomponentX();
printTraversalForm(traversal);
- int counter = 0;
- while (traversal.hasNext()) {
- final Vertex vertex = traversal.next();
- counter++;
- assertEquals("1", vertex.value(ConnectedComponentVertexProgram.COMPONENT));
- }
- assertEquals(6, counter);
+ assertEquals(6, IteratorUtils.count(traversal));
}
@Test
@LoadGraphWith(MODERN)
- public void g_V_hasLabelXsoftwareX_connectedComponent() {
- final Traversal<Vertex, Vertex> traversal = get_g_V_hasLabelXsoftwareX_connectedComponent();
+ public void g_V_hasLabelXsoftwareX_connectedComponent_project_byXnameX_byXcomponentX() {
+ final Traversal<Vertex, Map<String,Object>> traversal = get_g_V_hasLabelXsoftwareX_connectedComponent_project_byXnameX_byXcomponentX();
printTraversalForm(traversal);
int counter = 0;
while (traversal.hasNext()) {
- final Vertex vertex = traversal.next();
- final String name = vertex.value("name");
+ final Map<String,Object> m = traversal.next();
+ final String name = m.get("name").toString();
switch (name) {
case "lop":
case "ripple":
- assertEquals("1", vertex.value(ConnectedComponentVertexProgram.COMPONENT));
+ assertEquals(convertToVertexId("marko").toString(), m.get("component"));
break;
}
counter++;
@@ -93,21 +83,21 @@ public abstract class ConnectedComponentTest extends AbstractGremlinProcessTest
@Test
@LoadGraphWith(MODERN)
- public void g_V_connectedComponent_withXEDGES_bothEXknowsXX_withXPROPERTY_NAME_clusterX() {
- final Traversal<Vertex, Vertex> traversal = get_g_V_connectedComponent_withXedges_bothEXknowsXX_withXpropertyName_clusterX();
+ public void g_V_connectedComponent_withXEDGES_bothEXknowsXX_withXPROPERTY_NAME_clusterX_project_byXnameX_byXclusterX() {
+ final Traversal<Vertex, Map<String,Object>> traversal = get_g_V_connectedComponent_withXedges_bothEXknowsXX_withXpropertyName_clusterX_project_byXnameX_byXclusterX();
printTraversalForm(traversal);
int counter = 0;
while (traversal.hasNext()) {
- final Vertex vertex = traversal.next();
- final String name = vertex.value("name");
+ final Map<String,Object> m = traversal.next();
+ final String name = m.get("name").toString();
switch (name) {
case "marko":
case "vadas":
case "josh":
- assertEquals("1", vertex.value("cluster"));
+ assertEquals(convertToVertexId("marko").toString(), m.get("cluster"));
break;
case "peter":
- assertEquals("6", vertex.value("cluster"));
+ assertEquals(convertToVertexId("peter").toString(), m.get("cluster"));
break;
}
counter++;
@@ -117,22 +107,22 @@ public abstract class ConnectedComponentTest extends AbstractGremlinProcessTest
public static class Traversals extends ConnectedComponentTest {
@Override
- public Traversal<Vertex, Vertex> get_g_V_connectedComponent() {
+ public Traversal<Vertex, Vertex> get_g_V_connectedComponent_hasXcomponentX() {
return g.V().connectedComponent();
}
@Override
- public Traversal<Vertex, Vertex> get_g_V_dedup_connectedComponent() {
+ public Traversal<Vertex, Vertex> get_g_V_dedup_connectedComponent_hasXcomponentX() {
return g.V().dedup().connectedComponent();
}
@Override
- public Traversal<Vertex, Vertex> get_g_V_hasLabelXsoftwareX_connectedComponent() {
- return g.V().hasLabel("software").connectedComponent();
+ public Traversal<Vertex, Map<String,Object>> get_g_V_hasLabelXsoftwareX_connectedComponent_project_byXnameX_byXcomponentX() {
+ return g.V().hasLabel("software").connectedComponent().project("name","component").by("name").by(ConnectedComponent.component);
}
@Override
- public Traversal<Vertex, Vertex> get_g_V_connectedComponent_withXedges_bothEXknowsXX_withXpropertyName_clusterX() {
- return g.V().hasLabel("person").connectedComponent().with(ConnectedComponent.edges, bothE("knows")).with(ConnectedComponent.propertyName, "cluster");
+ public Traversal<Vertex, Map<String,Object>> get_g_V_connectedComponent_withXedges_bothEXknowsXX_withXpropertyName_clusterX_project_byXnameX_byXclusterX() {
+ return g.V().hasLabel("person").connectedComponent().with(ConnectedComponent.edges, bothE("knows")).with(ConnectedComponent.propertyName, "cluster").project("name","cluster").by("name").by("cluster");
}
}
}
[14/14] tinkerpop git commit: TINKERPOP-1990 Implemented
`ShortestPathVertexProgram` and `ShortestPathVertexProgramStep`.
Posted by dk...@apache.org.
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/0324c820
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/0324c820
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/0324c820
Branch: refs/heads/TINKERPOP-1990
Commit: 0324c820bd91cbf316bcbd87e954b133afadae74
Parents: 0c2fc21
Author: Daniel Kuppitz <da...@hotmail.com>
Authored: Wed May 23 08:46:34 2018 -0400
Committer: Daniel Kuppitz <da...@hotmail.com>
Committed: Thu Aug 9 17:02:02 2018 -0700
----------------------------------------------------------------------
CHANGELOG.asciidoc | 1 +
docs/src/recipes/shortest-path.asciidoc | 62 ++
docs/src/reference/the-graphcomputer.asciidoc | 51 ++
docs/src/reference/the-traversal.asciidoc | 61 ++
.../tinkerpop/gremlin/jsr223/CoreImports.java | 4 +
.../search/path/ShortestPathVertexProgram.java | 611 +++++++++++++++++++
.../traversal/step/map/ShortestPath.java | 108 ++++
.../step/map/ShortestPathVertexProgramStep.java | 185 ++++++
.../gremlin/process/remote/RemoteGraph.java | 4 +
.../gremlin/process/traversal/Traversal.java | 16 +-
.../traversal/dsl/graph/GraphTraversal.java | 21 +
.../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 | 9 +
.../lib/process/graph-traversal.js | 10 +
.../test/cucumber/feature-steps.js | 17 +-
.../gremlin_python/process/graph_traversal.py | 4 +
gremlin-test/features/map/Path.feature | 2 +-
gremlin-test/features/map/ShortestPath.feature | 361 +++++++++++
.../tinkerpop/gremlin/AbstractGremlinTest.java | 6 +-
.../process/AbstractGremlinProcessTest.java | 7 +-
.../gremlin/process/ProcessComputerSuite.java | 5 +
.../search/path/ShortestPathTestHelper.java | 100 +++
.../path/ShortestPathVertexProgramTest.java | 297 +++++++++
.../traversal/step/map/ShortestPathTest.java | 353 +++++++++++
pom.xml | 3 +
36 files changed, 2360 insertions(+), 25 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 481a7d3..f6233ba 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/0324c820/docs/src/recipes/shortest-path.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/recipes/shortest-path.asciidoc b/docs/src/recipes/shortest-path.asciidoc
index 2e33055..04c542d 100644
--- a/docs/src/recipes/shortest-path.asciidoc
+++ b/docs/src/recipes/shortest-path.asciidoc
@@ -49,6 +49,16 @@ length three), but this example is not considering that.
<2> It might be interesting to know the path lengths for all paths between vertex "1" and "5".
<3> Alternatively, one might wish to do a path length distribution over all the paths.
+The following code block demonstrates how the shortest path from `v[1]` to `v[5]` can be queried in OLAP, using the `shortestPath()` step.
+
+[gremlin-groovy,existing]
+----
+g = g.withComputer()
+g.V(1).shortestPath().
+ with(ShortestPath.edges, Direction.OUT).
+ with(ShortestPath.target, hasId(5))
+----
+
The previous example defines the length of the path by the number of vertices in the path, but the "path" might also
be measured by data within the graph itself. The following example use the same graph structure as the previous example,
but includes a "weight" on the edges, that will be used to help determine the "cost" of a particular path:
@@ -95,6 +105,17 @@ calculated cost. With some slight modifications given the use of `select` it bec
the output. Note that the path with the lowest "cost" actually has a longer path length as determined by the graph
structure.
+The next code block demonstrates how the `shortestPath()` step can be used in OLAP to determine the shortest weighted path.
+
+[gremlin-groovy,existing]
+----
+g = g.withComputer()
+g.V(1).shortestPath().
+ with(ShortestPath.edges, Direction.OUT).
+ with(ShortestPath.distance, 'weight').
+ with(ShortestPath.target, hasId(5))
+----
+
The following query illustrates how `select(<traversal>)` can be used to find all shortest weighted undirected paths
in the modern toy graph.
@@ -136,3 +157,44 @@ g.withSack(0.0).V().as("from"). <1>
<7> Order the output by the start vertex id and then the end vertex id (for better readability).
<8> Deduplicate vertex pairs (the shortest path from `v[1]` to `v[6]` is the same as the path from `v[6]` to `v[1]`).
+Again, this can be translated into an OLAP query using the `shortestPath()` step.
+
+[gremlin-groovy,existing]
+----
+result = g.withComputer().V().
+ shortestPath().
+ with(ShortestPath.distance, 'weight').
+ with(ShortestPath.includeEdges, true).
+ filter(count(local).is(gt(1))).
+ group().
+ by(project('from','to').
+ by(limit(local, 1)).
+ by(tail(local, 1))).
+ unfold().
+ order().
+ by(select(keys).select('from').id()).
+ by(select(keys).select('to').id()).toList()
+----
+
+The obvious difference in the result is the absence of property values in the OLAP result. Since OLAP traversers are not
+allowed to leave the local star graph, it's not possible to have the exact same result in an OLAP query. However, the determined
+shortest paths can be passed back into the OLTP `GraphTraversalSource`, which can then be used to query the values.
+
+[gremlin-groovy,existing]
+----
+g.withSideEffect('v', []). <1>
+ inject(result.toArray()).as('kv').select(values).
+ unfold().
+ map(unfold().as('v_or_e').
+ coalesce(V().where(eq('v_or_e')).store('v'),
+ select('v').tail(local, 1).bothE().where(eq('v_or_e'))).
+ values('name','weight').
+ fold()).
+ group().
+ by(select('kv').select(keys)).unfold().
+ order().
+ by(select(keys).select('from').id()).
+ by(select(keys).select('to').id()).toList()
+----
+
+<1> The side-effect `v` is used to keep track of the last processed vertex, hence it needs to be an order-preserving list. Without this explicit definition `v` would become a `BulkSet` which doesn't preserve the insert order.
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/docs/src/reference/the-graphcomputer.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/reference/the-graphcomputer.asciidoc b/docs/src/reference/the-graphcomputer.asciidoc
index 9cd1c76..f363342 100644
--- a/docs/src/reference/the-graphcomputer.asciidoc
+++ b/docs/src/reference/the-graphcomputer.asciidoc
@@ -409,6 +409,57 @@ g.V().peerPressure().by(outE('knows')).by('cluster').valueMap()
The `ConnectedComponentVertexProgram` identifies link:https://en.wikipedia.org/wiki/Connected_component_(graph_theory)[Connected Component]
instances in a graph. See <<connectedcomponent-step,`connectedComponent()`>>-step for more information.
+[[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/0324c820/docs/src/reference/the-traversal.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/reference/the-traversal.asciidoc b/docs/src/reference/the-traversal.asciidoc
index 4d5b48a..f2a8375 100644
--- a/docs/src/reference/the-traversal.asciidoc
+++ b/docs/src/reference/the-traversal.asciidoc
@@ -2698,6 +2698,67 @@ 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]
+----
+g = g.withComputer()
+g.V().shortestPath() <1>
+g.V().has('person','name','marko').shortestPath() <2>
+g.V().shortestPath().with(ShortestPath.target, __.has('name','peter')) <3>
+g.V().shortestPath().
+ with(ShortestPath.edges, Direction.IN).
+ with(ShortestPath.target, __.has('name','josh')) <4>
+g.V().has('person','name','marko').
+ shortestPath().
+ with(ShortestPath.target, __.has('name','josh')) <5>
+g.V().has('person','name','marko').
+ shortestPath().
+ with(ShortestPath.target, __.has('name','josh')).
+ with(ShortestPath.distance, 'weight') <6>
+g.V().has('person','name','marko').
+ shortestPath().
+ with(ShortestPath.target, __.has('name','josh')).
+ with(ShortestPath.includeEdges, true) <7>
+----
+
+<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.
+
+[gremlin-groovy,modern]
+----
+g.inject(g.withComputer().V().shortestPath().
+ with(ShortestPath.distance, 'weight').
+ with(ShortestPath.includeEdges, true).
+ with(ShortestPath.maxDistance, 1).toList().toArray()).
+ map(unfold().values('name','weight').fold()) <1>
+----
+
+<1> 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/0324c820/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 eb3b831..2b1e33e 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
@@ -48,11 +48,13 @@ 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.ConnectedComponent;
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;
@@ -272,6 +274,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/0324c820/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..1949c53
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java
@@ -0,0 +1,611 @@
+/*
+ * 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;
+ }
+ }
+ }
+
+ // restore halted traversers from the configuration and build an index for direct access
+ 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()) {
+
+ // Use the first iteration to copy halted traversers from the halted traverser index to the respective
+ // vertices. This way the rest of the code can be simplified and always expect the HALTED_TRAVERSERS
+ // property to be available (if halted traversers exist for this vertex).
+ copyHaltedTraversersFromMemory(vertex);
+
+ // ignore vertices that don't pass the start-vertex filter
+ if (!isStartVertex(vertex)) return;
+
+ // start to track paths for all valid start-vertices
+ 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);
+
+ // send messages to valid adjacent vertices
+ processEdges(vertex, path, 0, messenger);
+
+ voteToHalt = false;
+
+ } else {
+
+ // load existing paths to this vertex and extend them based on messages received from adjacent vertices
+ 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;
+
+ // already know a path coming from this source vertex?
+ 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) {
+ // if the path length is smaller than the current shortest path's length, replace the
+ // current set of shortest paths
+ final Set<Path> pathSet = new HashSet<>();
+ pathSet.add(newPath);
+ paths.put(sourceVertex, Pair.with(distance, pathSet));
+ } else {
+ // if the path length is equal to the current shortest path's length, add the new path
+ // to the set of shortest paths
+ paths.get(sourceVertex).getValue1().add(newPath);
+ }
+ }
+ } else if (!exceedsMaxDistance(distance)) {
+ // store the new path as the shortest path from the source vertex to the current vertex
+ final Set<Path> pathSet = new HashSet<>();
+ pathSet.add(newPath = extendPath(sourcePath, triplet.getValue1(), vertex));
+ paths.put(sourceVertex, Pair.with(distance, pathSet));
+ }
+
+ // if a new path was found, send messages to adjacent vertices, otherwise do nothing as there's no
+ // chance to find any new paths going forward
+ if (newPath != null) {
+ vertex.property(VertexProperty.Cardinality.single, PATHS, paths);
+ processEdges(vertex, newPath, distance, messenger);
+ voteToHalt = false;
+ }
+ }
+ }
+
+ // VOTE_TO_HALT will be set to true if an iteration hasn't found any new paths
+ 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) {
+ // After paths were collected,
+ // a) the VP is done in standalone mode (paths will be in memory) or
+ // b) the halted traversers will be updated in order to have the paths available in the traversal
+ 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); // collect paths if no new paths were found
+ 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) {
+ // use the sourceVertexFilterTraversal if the VP is running in standalone mode (not part of a traversal)
+ if (this.standalone) {
+ final Traversal.Admin<Vertex, ?> filterTraversal = this.sourceVertexFilterTraversal.getPure();
+ filterTraversal.addStart(filterTraversal.getTraverserGenerator().generate(vertex, filterTraversal.getStartStep(), 1));
+ return filterTraversal.hasNext();
+ }
+ // ...otherwise use halted traversers to determine whether this is a start vertex
+ 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();
+
+ // only send message if the adjacent vertex is not yet part of the current path
+ 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()) {
+ // replace the current set of halted traversers with new new traversers that hold the shortest paths
+ // found for this vertex
+ 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;
+ }
+
+ /**
+ * Move any valid path into the VP's memory.
+ * @param vertex The current vertex.
+ * @param memory The VertexProgram's memory.
+ */
+ 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/0324c820/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/0324c820/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..e9a09e2
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPathVertexProgramStep.java
@@ -0,0 +1,185 @@
+/*
+ * 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.ComputerResult;
+import org.apache.tinkerpop.gremlin.process.computer.GraphFilter;
+import org.apache.tinkerpop.gremlin.process.computer.Memory;
+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.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.step.Configuring;
+import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+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.Arrays;
+import java.util.Base64;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * @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);
+
+ // There are two locations in which halted traversers can be stored: in memory or as vertex properties. In the
+ // former case they need to be copied to this VertexProgram's configuration as the VP won't have access to the
+ // previous VP's memory.
+ 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/0324c820/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 bf59651..91221bd 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
@@ -76,6 +76,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/0324c820/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/0324c820/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 4fd247f..0f8677e 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
@@ -24,6 +24,7 @@ import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.Connecte
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;
@@ -2465,6 +2466,25 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> {
return this.asAdmin().addStep((Step<E, E>) new ConnectedComponentVertexProgramStep(this.asAdmin()));
}
+
+ /**
+ * 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.
*
@@ -2897,6 +2917,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 connectedComponent = "connectedComponent";
+ 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/0324c820/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/0324c820/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/0324c820/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/0324c820/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/0324c820/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/0324c820/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/0324c820/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/0324c820/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/0324c820/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/0324c820/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/0324c820/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/0324c820/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 40ca312..0d57f49 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", "connectedComponent", "peerPressure", "program", "none"));
+ private static Set<String> NO_GRAPH = new HashSet<>(Arrays.asList("asAdmin", "by", "read", "write", "with", "option", "iterate", "to", "from", "profile", "pageRank", "connectedComponent", "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/0324c820/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 e2fa3e1..83dbe85 100644
--- a/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs
+++ b/gremlin-dotnet/src/Gremlin.Net/Process/Traversal/GraphTraversal.cs
@@ -1395,6 +1395,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/0324c820/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 1c8d639..a38cfa2 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
@@ -963,6 +963,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}
[03/14] tinkerpop git commit: TINKERPOP-1967 Referenced
TINKERPOP-1976 in OptOut for connectedComponent on RemoteGraph
Posted by dk...@apache.org.
TINKERPOP-1967 Referenced TINKERPOP-1976 in OptOut for connectedComponent on RemoteGraph
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/dd7fc261
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/dd7fc261
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/dd7fc261
Branch: refs/heads/TINKERPOP-1990
Commit: dd7fc261fde9837bde954962b4e7777a57a01327
Parents: b2cb187
Author: Stephen Mallette <sp...@genoprime.com>
Authored: Mon Jul 30 11:22:25 2018 -0400
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Thu Aug 9 10:54:41 2018 -0400
----------------------------------------------------------------------
.../org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/dd7fc261/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 9bc1771..bf59651 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
@@ -50,7 +50,7 @@ import java.util.Iterator;
@Graph.OptOut(
test = "org.apache.tinkerpop.gremlin.process.traversal.step.map.ConnectedComponentTest",
method = "*",
- reason = "hmmmm")
+ reason = "https://issues.apache.org/jira/browse/TINKERPOP-1976")
@Graph.OptOut(
test = "org.apache.tinkerpop.gremlin.process.traversal.CoreTraversalTest",
method = "*",
[10/14] tinkerpop git commit: TINKERPOP-1967 fixed up halted
traversers
Posted by dk...@apache.org.
TINKERPOP-1967 fixed up halted traversers
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/b2cb1874
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/b2cb1874
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/b2cb1874
Branch: refs/heads/TINKERPOP-1990
Commit: b2cb187470794bfca352c8a9c7d0c444d102e46b
Parents: 8954c27
Author: Stephen Mallette <sp...@genoprime.com>
Authored: Mon Jul 30 10:51:35 2018 -0400
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Thu Aug 9 10:54:41 2018 -0400
----------------------------------------------------------------------
.../ConnectedComponentVertexProgram.java | 42 +++++++++++++++-----
.../ConnectedComponentVertexProgramStep.java | 26 ++++++++++--
.../step/map/ConnectedComponentTest.java | 2 +-
3 files changed, 57 insertions(+), 13 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b2cb1874/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java
index de718f1..82907eb 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java
@@ -32,7 +32,10 @@ import org.apache.tinkerpop.gremlin.process.computer.traversal.TraversalVertexPr
import org.apache.tinkerpop.gremlin.process.computer.util.AbstractVertexProgramBuilder;
import org.apache.tinkerpop.gremlin.process.traversal.Operator;
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.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;
@@ -40,6 +43,8 @@ import org.apache.tinkerpop.gremlin.structure.Graph;
import org.apache.tinkerpop.gremlin.structure.Vertex;
import org.apache.tinkerpop.gremlin.structure.VertexProperty;
+import java.util.Arrays;
+import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
@@ -61,12 +66,14 @@ public class ConnectedComponentVertexProgram implements VertexProgram<String> {
private static final String VOTE_TO_HALT = "gremlin.connectedComponentVertexProgram.voteToHalt";
private static final Set<MemoryComputeKey> MEMORY_COMPUTE_KEYS = Collections.singleton(MemoryComputeKey.of(VOTE_TO_HALT, Operator.and, false, true));
+
private MessageScope.Local<?> scope = MessageScope.Local.of(__::bothE);
private Set<MessageScope> scopes;
private String property = COMPONENT;
- private boolean hasHalted = false;
private PureTraversal<Vertex, Edge> edgeTraversal = null;
private Configuration configuration;
+ private TraverserSet<Vertex> haltedTraversers;
+ private IndexedTraverserSet<Vertex, Vertex> haltedTraversersIndex;
private ConnectedComponentVertexProgram() {}
@@ -85,7 +92,12 @@ public class ConnectedComponentVertexProgram implements VertexProgram<String> {
scopes = new HashSet<>(Collections.singletonList(scope));
this.property = configuration.getString(PROPERTY, COMPONENT);
- this.hasHalted = configuration.getBoolean(HAS_HALTED, false);
+
+ this.haltedTraversers = TraversalVertexProgram.loadHaltedTraversers(configuration);
+ this.haltedTraversersIndex = new IndexedTraverserSet<>(v -> v);
+ for (final Traverser.Admin<Vertex> traverser : this.haltedTraversers) {
+ this.haltedTraversersIndex.add(traverser.split());
+ }
}
@Override
@@ -104,6 +116,8 @@ public class ConnectedComponentVertexProgram implements VertexProgram<String> {
@Override
public void execute(final Vertex vertex, final Messenger<String> messenger, final Memory memory) {
if (memory.isInitialIteration()) {
+ copyHaltedTraversersFromMemory(vertex);
+
// on the first pass, just initialize the component to its own id then pass it to all adjacent vertices
// for evaluation
vertex.property(VertexProperty.Cardinality.single, property, vertex.id().toString());
@@ -113,7 +127,7 @@ public class ConnectedComponentVertexProgram implements VertexProgram<String> {
// halting traversers. only want to send messages from traversers that are still hanging about after
// the filter. the unfiltered vertices can only react to messages sent to them. of course, this can
// lead to weirdness in results.
- if (vertex.edges(Direction.BOTH).hasNext() && !(hasHalted && !vertex.property(TraversalVertexProgram.HALTED_TRAVERSERS).isPresent())) {
+ if (vertex.edges(Direction.BOTH).hasNext()) {
// since there was message passing we don't want to halt on the first round. this should only trigger
// a single pass finish if the graph is completely disconnected (technically, it won't even really
// work in cases where halted traversers come into play
@@ -148,7 +162,9 @@ public class ConnectedComponentVertexProgram implements VertexProgram<String> {
@Override
public Set<VertexComputeKey> getVertexComputeKeys() {
- return new HashSet<>(Collections.singletonList(VertexComputeKey.of(property, false)));
+ return new HashSet<>(Arrays.asList(
+ VertexComputeKey.of(property, false),
+ VertexComputeKey.of(TraversalVertexProgram.HALTED_TRAVERSERS, false)));
}
@Override
@@ -158,6 +174,10 @@ public class ConnectedComponentVertexProgram implements VertexProgram<String> {
@Override
public boolean terminate(final Memory memory) {
+ if (memory.isInitialIteration() && this.haltedTraversersIndex != null) {
+ this.haltedTraversersIndex.clear();
+ }
+
final boolean voteToHalt = memory.<Boolean>get(VOTE_TO_HALT);
if (voteToHalt) {
return true;
@@ -206,6 +226,15 @@ public class ConnectedComponentVertexProgram implements VertexProgram<String> {
};
}
+ 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);
+ }
+ }
+
public static ConnectedComponentVertexProgram.Builder build() {
return new ConnectedComponentVertexProgram.Builder();
}
@@ -216,11 +245,6 @@ public class ConnectedComponentVertexProgram implements VertexProgram<String> {
super(ConnectedComponentVertexProgram.class);
}
- public ConnectedComponentVertexProgram.Builder hasHalted(final boolean hasHalted) {
- this.configuration.setProperty(HAS_HALTED, hasHalted);
- return this;
- }
-
public ConnectedComponentVertexProgram.Builder edges(final Traversal.Admin<Vertex, Edge> edgeTraversal) {
PureTraversal.storeState(this.configuration, EDGE_TRAVERSAL, edgeTraversal);
return this;
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b2cb1874/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponentVertexProgramStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponentVertexProgramStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponentVertexProgramStep.java
index edeb497..c222cfa 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponentVertexProgramStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponentVertexProgramStep.java
@@ -29,11 +29,16 @@ import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
import org.apache.tinkerpop.gremlin.process.traversal.step.Configuring;
import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.Parameters;
+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.Base64;
/**
* @author Stephen Mallette (http://stephen.genoprime.com)
@@ -84,10 +89,25 @@ public final class ConnectedComponentVertexProgramStep extends VertexProgramStep
public ConnectedComponentVertexProgram generateProgram(final Graph graph, final Memory memory) {
final Traversal.Admin<Vertex, Edge> detachedTraversal = this.edgeTraversal.getPure();
detachedTraversal.setStrategies(TraversalStrategies.GlobalCache.getStrategies(graph.getClass()));
- return ConnectedComponentVertexProgram.build().
- hasHalted(memory.exists(TraversalVertexProgram.HALTED_TRAVERSERS)).
+
+ final ConnectedComponentVertexProgram.Builder builder = ConnectedComponentVertexProgram.build().
edges(detachedTraversal).
- property(this.clusterProperty).create(graph);
+ property(this.clusterProperty);
+
+ 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
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b2cb1874/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
index 25e618a..8b1904f 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
@@ -67,7 +67,7 @@ public abstract class ConnectedComponentTest extends AbstractGremlinProcessTest
switch (name) {
case "lop":
case "ripple":
- assertEquals("3", vertex.value(ConnectedComponentVertexProgram.COMPONENT));
+ assertEquals("1", vertex.value(ConnectedComponentVertexProgram.COMPONENT));
break;
}
counter++;
[09/14] tinkerpop git commit: TINKERPOP-1967 Minor text cleanup for
connectedComponent() docs
Posted by dk...@apache.org.
TINKERPOP-1967 Minor text cleanup for connectedComponent() docs
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/16231d6e
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/16231d6e
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/16231d6e
Branch: refs/heads/TINKERPOP-1990
Commit: 16231d6ed9b6c5f00a6f28da6f03a96d664fcf99
Parents: a011964
Author: Stephen Mallette <sp...@genoprime.com>
Authored: Fri Jun 15 08:24:22 2018 -0400
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Thu Aug 9 10:54:41 2018 -0400
----------------------------------------------------------------------
docs/src/recipes/connected-components.asciidoc | 16 +++++-----------
1 file changed, 5 insertions(+), 11 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/16231d6e/docs/src/recipes/connected-components.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/recipes/connected-components.asciidoc b/docs/src/recipes/connected-components.asciidoc
index 850c31f..e6d0f7a 100644
--- a/docs/src/recipes/connected-components.asciidoc
+++ b/docs/src/recipes/connected-components.asciidoc
@@ -37,7 +37,6 @@ component membership is stored in the graph, rather than in memory.
3. Large graphs requiring an approach with `HadoopGraph` and `SparkGraphComputer` to yield results in a reasonable time.
-
These regimes are discussed separately using the following graph with three weakly connected components:
image:connected-components.png[width=600]
@@ -70,6 +69,7 @@ g.withComputer().V().connectedComponent().
----
A straightforward way to detect the various subgraphs with an OLTP traversal is to do this:
+
[gremlin-groovy,existing]
----
g.V().emit(cyclicPath().or().not(both())). <1>
@@ -95,8 +95,6 @@ weak component.
<5> The values of the groupby map contain the lists of vertices making up the requested components.
-
-
==== Small graph scalability
The scalability of the OLTP traversal and the `connectedComponent()`-step for in-memory graphs is shown in the figures
@@ -118,7 +116,6 @@ every cycle each vertex has to be checked for being
pure depth-first-search or breadth-first-search implementations, connected-component algotithms should scale
as [.big]##O##(V+E). For the traversals in the figure above this is almost the case.
-
[[cc-scale-ratio]]
.Run times for finding connected components in a randomly generated graph with 10 components, each consisting of 6400 vertices
image::cc-scale-ratio.png[width=600]
@@ -130,7 +127,6 @@ characteristics show clearly from the graph. Indeed, for a given number of verti
`connectedComponent()`-step does not depend on the number of edges, but rather on the maximum shortest path length in
the graph.
-
==== Large graphs
Large graphs in TinkerPop require distributed processing by `SparkGraphComputer` to get results in a reasonable time (OLAP
@@ -142,10 +138,8 @@ either with the `gremlin.hadoop.defaultGraphComputer` property or as part of the
Scalability of the the `connectedComponent()`-step with `SparkGraphComputer` is high, but note that:
-* the graph should fit in the memory of the Spark cluster to allow the VertexProgram to run its cycles without spilling
-intermediate results to disk and loosing most of the gains from the distributed processing
-
-* as discussed for small graphs, the BSP algorithm does not play well with graphs having a large shortest path between
+* The graph should fit in the memory of the Spark cluster to allow the VertexProgram to run its cycles without spilling
+intermediate results to disk and loosing most of the gains from the distributed processing.
+* As discussed for small graphs, the BSP algorithm does not play well with graphs having a large shortest path between
any pair of vertices. Overcoming this limitation is still a
-link:http://www.vldb.org/pvldb/vol7/p1821-yan.pdf[subject of academic research].
-
+link:http://www.vldb.org/pvldb/vol7/p1821-yan.pdf[subject of academic research].
\ No newline at end of file
[05/14] tinkerpop git commit: TINKERPOP-1967 Added a test for
regressions on halted traversers
Posted by dk...@apache.org.
TINKERPOP-1967 Added a test for regressions on halted traversers
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/0eb6cb1a
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/0eb6cb1a
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/0eb6cb1a
Branch: refs/heads/TINKERPOP-1990
Commit: 0eb6cb1a0d7df0790cb5c2f82a792cd80bef6f3f
Parents: dd7fc26
Author: Stephen Mallette <sp...@genoprime.com>
Authored: Mon Jul 30 14:13:33 2018 -0400
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Thu Aug 9 10:54:41 2018 -0400
----------------------------------------------------------------------
.../step/map/ConnectedComponentTest.java | 21 ++++++++++++++++++++
1 file changed, 21 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0eb6cb1a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
index 8b1904f..3133382 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
@@ -39,6 +39,8 @@ public abstract class ConnectedComponentTest extends AbstractGremlinProcessTest
public abstract Traversal<Vertex, Vertex> get_g_V_hasLabelXsoftwareX_connectedComponent();
+ public abstract Traversal<Vertex, Vertex> get_g_V_dedup_connectedComponent();
+
public abstract Traversal<Vertex, Vertex> get_g_V_connectedComponent_withXedges_bothEXknowsXX_withXpropertyName_clusterX();
@Test
@@ -57,6 +59,20 @@ public abstract class ConnectedComponentTest extends AbstractGremlinProcessTest
@Test
@LoadGraphWith(MODERN)
+ public void g_V_dedup_connectedComponent() {
+ final Traversal<Vertex, Vertex> traversal = get_g_V_dedup_connectedComponent();
+ printTraversalForm(traversal);
+ int counter = 0;
+ while (traversal.hasNext()) {
+ final Vertex vertex = traversal.next();
+ counter++;
+ assertEquals("1", vertex.value(ConnectedComponentVertexProgram.COMPONENT));
+ }
+ assertEquals(6, counter);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
public void g_V_hasLabelXsoftwareX_connectedComponent() {
final Traversal<Vertex, Vertex> traversal = get_g_V_hasLabelXsoftwareX_connectedComponent();
printTraversalForm(traversal);
@@ -106,6 +122,11 @@ public abstract class ConnectedComponentTest extends AbstractGremlinProcessTest
}
@Override
+ public Traversal<Vertex, Vertex> get_g_V_dedup_connectedComponent() {
+ return g.V().dedup().connectedComponent();
+ }
+
+ @Override
public Traversal<Vertex, Vertex> get_g_V_hasLabelXsoftwareX_connectedComponent() {
return g.V().hasLabel("software").connectedComponent();
}
[08/14] tinkerpop git commit: TINKERPOP-1967 Added
ConnectedComponentVertexProgram to core javadoc
Posted by dk...@apache.org.
TINKERPOP-1967 Added ConnectedComponentVertexProgram to core javadoc
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/eb6a4de6
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/eb6a4de6
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/eb6a4de6
Branch: refs/heads/TINKERPOP-1990
Commit: eb6a4de63ac62181d8237c0ad7ec5b3aa072e0b7
Parents: 0eb6cb1
Author: Stephen Mallette <sp...@genoprime.com>
Authored: Thu Aug 2 08:20:17 2018 -0400
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Thu Aug 9 10:54:41 2018 -0400
----------------------------------------------------------------------
pom.xml | 3 +++
1 file changed, 3 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/eb6a4de6/pom.xml
----------------------------------------------------------------------
diff --git a/pom.xml b/pom.xml
index 4badaa1..ea42197 100644
--- a/pom.xml
+++ b/pom.xml
@@ -1262,6 +1262,9 @@ limitations under the License.
<include>org/apache/tinkerpop/gremlin/process/computer/*.java
</include>
<include>
+ org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java
+ </include>
+ <include>
org/apache/tinkerpop/gremlin/process/computer/clustering/peerpressure/PeerPressureVertexProgram.java
</include>
<include>
[07/14] tinkerpop git commit: TINKERPOP-1967 Added a component field
to the ConnectedComponent class
Posted by dk...@apache.org.
TINKERPOP-1967 Added a component field to the ConnectedComponent class
In this way the user can access the default more readily and is available in GLVs
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/8954c271
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/8954c271
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/8954c271
Branch: refs/heads/TINKERPOP-1990
Commit: 8954c2713d6b2b2736b2892c03b0fe6dbe6bf018
Parents: 16231d6
Author: Stephen Mallette <sp...@genoprime.com>
Authored: Mon Jul 30 08:29:13 2018 -0400
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Thu Aug 9 10:54:41 2018 -0400
----------------------------------------------------------------------
docs/src/recipes/connected-components.asciidoc | 5 ++++-
.../computer/traversal/step/map/ConnectedComponent.java | 7 +++++++
2 files changed, 11 insertions(+), 1 deletion(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/8954c271/docs/src/recipes/connected-components.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/recipes/connected-components.asciidoc b/docs/src/recipes/connected-components.asciidoc
index e6d0f7a..c46180f 100644
--- a/docs/src/recipes/connected-components.asciidoc
+++ b/docs/src/recipes/connected-components.asciidoc
@@ -64,10 +64,13 @@ The traversal looks like:
[gremlin-groovy,existing]
----
g.withComputer().V().connectedComponent().
- group().by('gremlin.connectedComponentVertexProgram.component').
+ group().by(component).
select(values).unfold()
----
+NOTE: The `component` option passed to `by()` is statically imported from `ConnectedComponent` and refers to the
+default property key within which the result of the algorithm is stored.
+
A straightforward way to detect the various subgraphs with an OLTP traversal is to do this:
[gremlin-groovy,existing]
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/8954c271/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponent.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponent.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponent.java
index 85558bc..a2223d8 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponent.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponent.java
@@ -18,6 +18,7 @@
*/
package org.apache.tinkerpop.gremlin.process.computer.traversal.step.map;
+import org.apache.tinkerpop.gremlin.process.computer.clustering.connected.ConnectedComponentVertexProgram;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal;
import org.apache.tinkerpop.gremlin.structure.Graph;
@@ -26,6 +27,12 @@ import org.apache.tinkerpop.gremlin.structure.Graph;
* {@link GraphTraversal#connectedComponent()} ()}.
*/
public class ConnectedComponent {
+
+ /**
+ * The default property key name that will hold the result of the algorithm.
+ */
+ public static final String component = ConnectedComponentVertexProgram.COMPONENT;
+
/**
* Configures the edge to traverse when calculating the pagerank.
*/
[02/14] tinkerpop git commit: TINKERPOP-1967 Removed some dead
comments/code
Posted by dk...@apache.org.
TINKERPOP-1967 Removed some dead comments/code
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/cbae0a30
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/cbae0a30
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/cbae0a30
Branch: refs/heads/TINKERPOP-1990
Commit: cbae0a30093303aeab1257c8ff344abd62f806cb
Parents: eb6a4de
Author: Stephen Mallette <sp...@genoprime.com>
Authored: Fri Aug 3 06:51:55 2018 -0400
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Thu Aug 9 10:54:41 2018 -0400
----------------------------------------------------------------------
.../clustering/connected/ConnectedComponentVertexProgram.java | 7 +------
1 file changed, 1 insertion(+), 6 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/cbae0a30/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java
index 82907eb..acc8f3c 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java
@@ -62,7 +62,6 @@ public class ConnectedComponentVertexProgram implements VertexProgram<String> {
public static final String COMPONENT = "gremlin.connectedComponentVertexProgram.component";
private static final String PROPERTY = "gremlin.connectedComponentVertexProgram.property";
private static final String EDGE_TRAVERSAL = "gremlin.pageRankVertexProgram.edgeTraversal";
- private static final String HAS_HALTED = "gremlin.connectedComponentVertexProgram.hasHalted";
private static final String VOTE_TO_HALT = "gremlin.connectedComponentVertexProgram.voteToHalt";
private static final Set<MemoryComputeKey> MEMORY_COMPUTE_KEYS = Collections.singleton(MemoryComputeKey.of(VOTE_TO_HALT, Operator.and, false, true));
@@ -122,11 +121,7 @@ public class ConnectedComponentVertexProgram implements VertexProgram<String> {
// for evaluation
vertex.property(VertexProperty.Cardinality.single, property, vertex.id().toString());
- // no need to send messages from traversers that were filtered - happens for stuff like
- // g.V().hasLabel('software').connectedComponent() (i.e. when there is a TraversalVertexProgram in the mix
- // halting traversers. only want to send messages from traversers that are still hanging about after
- // the filter. the unfiltered vertices can only react to messages sent to them. of course, this can
- // lead to weirdness in results.
+ // vertices that have no edges remain in their own component - nothing to message pass here
if (vertex.edges(Direction.BOTH).hasNext()) {
// since there was message passing we don't want to halt on the first round. this should only trigger
// a single pass finish if the graph is completely disconnected (technically, it won't even really
[12/14] tinkerpop git commit: TINKERPOP-1967 Added GLV tests for
connectedComponent()
Posted by dk...@apache.org.
TINKERPOP-1967 Added GLV tests for connectedComponent()
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/0c2fc21f
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/0c2fc21f
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/0c2fc21f
Branch: refs/heads/TINKERPOP-1990
Commit: 0c2fc21fb9534060aa8758406e5e38d553ea12be
Parents: 2cc2aed
Author: Stephen Mallette <sp...@genoprime.com>
Authored: Thu Aug 9 12:29:40 2018 -0400
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Thu Aug 9 12:29:40 2018 -0400
----------------------------------------------------------------------
.../test/cucumber/feature-steps.js | 4 ++
.../features/map/ConnectedComponent.feature | 76 ++++++++++++++++++++
.../step/map/ConnectedComponentTest.java | 4 +-
3 files changed, 82 insertions(+), 2 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0c2fc21f/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js
----------------------------------------------------------------------
diff --git a/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js b/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js
index 96eeaaf..a0ae7ca 100644
--- a/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js
+++ b/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js
@@ -63,6 +63,10 @@ const ignoreReason = {
const ignoredScenarios = {
// An associative array containing the scenario name as key, for example:
+ 'g_V_connectedComponent_hasXcomponentX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_dedup_connectedComponent_hasXcomponentX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasLabelXsoftwareX_connectedComponent_project_byXnameX_byXcomponentX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_connectedComponent_withXEDGES_bothEXknowsXX_withXPROPERTY_NAME_clusterX_project_byXnameX_byXclusterX': new IgnoreError(ignoreReason.computerNotSupported),
'g_V_pageRank_hasXpageRankX': new IgnoreError(ignoreReason.computerNotSupported),
'g_V_outXcreatedX_pageRank_byXbothEX_byXprojectRankX_timesX0X_valueMapXname_projectRankX': new IgnoreError(ignoreReason.computerNotSupported),
'g_V_pageRank_order_byXpageRank_decrX_byXnameX_name': new IgnoreError(ignoreReason.computerNotSupported),
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0c2fc21f/gremlin-test/features/map/ConnectedComponent.feature
----------------------------------------------------------------------
diff --git a/gremlin-test/features/map/ConnectedComponent.feature b/gremlin-test/features/map/ConnectedComponent.feature
new file mode 100644
index 0000000..0f95488
--- /dev/null
+++ b/gremlin-test/features/map/ConnectedComponent.feature
@@ -0,0 +1,76 @@
+# 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.
+
+Feature: Step - connectedComponent()
+
+ Scenario: g_V_connectedComponent_hasXcomponentX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().connectedComponent().has("gremlin.connectedComponentVertexProgram.component")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | v[marko] |
+ | v[vadas] |
+ | v[lop] |
+ | v[josh] |
+ | v[ripple] |
+ | v[peter] |
+
+ Scenario: g_V_dedup_connectedComponent_hasXcomponentX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().dedup().connectedComponent().has("gremlin.connectedComponentVertexProgram.component")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | v[marko] |
+ | v[vadas] |
+ | v[lop] |
+ | v[josh] |
+ | v[ripple] |
+ | v[peter] |
+
+ Scenario: g_V_hasLabelXsoftwareX_connectedComponent_project_byXnameX_byXcomponentX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().hasLabel("software").connectedComponent().project("name","component").by("name").by("gremlin.connectedComponentVertexProgram.component")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | m[{"name": "lop", "component": "1"}] |
+ | m[{"name": "ripple", "component": "1"}] |
+
+ Scenario: g_V_connectedComponent_withXEDGES_bothEXknowsXX_withXPROPERTY_NAME_clusterX_project_byXnameX_byXclusterX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().hasLabel("person").connectedComponent().with("~tinkerpop.connectedComponent.edges", __.bothE("knows")).with("~tinkerpop.connectedComponent.propertyName", "cluster").project("name","cluster").by("name").by("cluster")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | m[{"name": "marko", "cluster": "1"}] |
+ | m[{"name": "vadas", "cluster": "1"}] |
+ | m[{"name": "josh", "cluster": "1"}] |
+ | m[{"name": "peter", "cluster": "6"}] |
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0c2fc21f/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
index a542bed..bf0d047 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
@@ -108,12 +108,12 @@ public abstract class ConnectedComponentTest extends AbstractGremlinProcessTest
public static class Traversals extends ConnectedComponentTest {
@Override
public Traversal<Vertex, Vertex> get_g_V_connectedComponent_hasXcomponentX() {
- return g.V().connectedComponent();
+ return g.V().connectedComponent().has(ConnectedComponent.component);
}
@Override
public Traversal<Vertex, Vertex> get_g_V_dedup_connectedComponent_hasXcomponentX() {
- return g.V().dedup().connectedComponent();
+ return g.V().dedup().connectedComponent().has(ConnectedComponent.component);
}
@Override
[06/14] tinkerpop git commit: Extended the connected-components recipe
Posted by dk...@apache.org.
Extended the connected-components recipe
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/a0119640
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/a0119640
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/a0119640
Branch: refs/heads/TINKERPOP-1990
Commit: a011964030f36c87b1ecb22eefb1e7deeffed3b9
Parents: 002560a
Author: HadoopMarc <vt...@xs4all.nl>
Authored: Sun Jun 10 15:17:17 2018 +0200
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Thu Aug 9 10:54:41 2018 -0400
----------------------------------------------------------------------
docs/src/recipes/connected-components.asciidoc | 94 ++++++++++++--------
docs/static/images/cc-scale-ratio.png | Bin 0 -> 14393 bytes
docs/static/images/cc-scale-size.png | Bin 0 -> 12220 bytes
3 files changed, 58 insertions(+), 36 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a0119640/docs/src/recipes/connected-components.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/recipes/connected-components.asciidoc b/docs/src/recipes/connected-components.asciidoc
index edbeec5..850c31f 100644
--- a/docs/src/recipes/connected-components.asciidoc
+++ b/docs/src/recipes/connected-components.asciidoc
@@ -31,11 +31,11 @@ Depending on the size of the graph, three solution regimes can be discriminated:
1. Small graphs that fit in the memory of a single machine
-2. Medium graphs backed by storage for which a linear scan is still feasible. This regime is left to third party
+2. Medium-sized graphs backed by storage for which an OLTP linear scan is still feasible. This regime is left to third party
TinkerPop implementations, since TinkerPop itself has no storage-backed reference implementations. The idea is that
component membership is stored in the graph, rather than in memory.
-3. Large graphs requiring an OLAP approach to yield results in a reasonable time.
+3. Large graphs requiring an approach with `HadoopGraph` and `SparkGraphComputer` to yield results in a reasonable time.
These regimes are discussed separately using the following graph with three weakly connected components:
@@ -55,16 +55,21 @@ g.addV().property(id, "A").as("a").
addE("link").from("d").to("e").iterate()
----
+==== Small graph traversals
-===== Small graphs
-
-Connected components in a small graph can be determined with both an OLTP traversal and the OLAP
+Connected components in a small graph can be determined with either an OLTP traversal or the OLAP
`connectedComponent()`-step. The `connectedComponent()`-step is available as of TinkerPop 3.4.0 and is
described in more detail in the
link:http://tinkerpop.apache.org/docs/x.y.z/reference/#connectedcomponent-step[Reference Documentation].
+The traversal looks like:
+[gremlin-groovy,existing]
+----
+g.withComputer().V().connectedComponent().
+ group().by('gremlin.connectedComponentVertexProgram.component').
+ select(values).unfold()
+----
A straightforward way to detect the various subgraphs with an OLTP traversal is to do this:
-
[gremlin-groovy,existing]
----
g.V().emit(cyclicPath().or().not(both())). <1>
@@ -73,7 +78,6 @@ g.V().emit(cyclicPath().or().not(both())). <1
by(path().unfold().dedup().fold()). <4>
select(values).unfold() <5>
----
-
<1> The initial emit() step allows for output of isolated vertices, in addition to the discovery of
components as described in (2).
@@ -83,7 +87,7 @@ path. Collection `'a'` is used to keep track of visited vertices, for both subt
and new traversals resulting from the `g.V()` linear scan.
<3> While `'a'` nicely keeps track of vertices already visited, the actual components need to be extracted from the
-path information of surviving traversers. The `path().unfold().limit(1)` closure provides the starting vertex
+path information. The `path().unfold().limit(1)` closure provides the starting vertex
of surviving traversers, which can be used to group the components.
<4> This clause collects the unique vertices from all paths with the same starting vertex, thus from the same
@@ -91,39 +95,57 @@ weak component.
<5> The values of the groupby map contain the lists of vertices making up the requested components.
-This algorithm completes in linear time with the number of vertices and edges, because a traversal is started for each
-vertex and each edge with its associated out-vertex is visited exactly once.
-
-==== Large graphs
-Large graphs require an OLAP solution with a custom VertexProgram that can be run using a graph implementation's
-GraphComputer, in particular `SparkGraphComputer` on a `HadoopGraph`. The OLAP solution also runs faster for most
-medium-sized graphs, that is when these graph have a 'natural' structure with a limited maximum path length.
+==== Small graph scalability
-The TinkerPop library of vertex programs contains the `WeakComponentsVertexProgram` which can be run in the same
-way as the link:http://tinkerpop.apache.org/docs/x.y.z/reference/#peerpressurevertexprogram[PeerPressureVertexProgram]:
+The scalability of the OLTP traversal and the `connectedComponent()`-step for in-memory graphs is shown in the figures
+below.
-[gremlin-groovy,existing]
-----
-result = g.getGraph().compute().
- program(WeakComponentsVertexProgram.build().maxIterations(100).create()).
- mapReduce(ClusterPopulationMapReduce.build().create()).
- mapReduce(ClusterCountMapReduce.build().create()).
- submit().get()
-result.memory().clusterPopulation
-gResult = result.graph().traversal()
-gResult.V().valueMap(true)
-----
+[[cc-scale-size]]
+.Run times for finding connected components in a randomly generated graph with 10 components of equal size and with an edge/vertex ratio of 6
+image::cc-scale-size.png[width=600, side=bottom]
-The vertex program has interconnected vertices exchange id's and store the lowest id until no vertex receives a
-lower id. This algorithm is commonly applied in
+In general, the `connectedComponent()`-step is almost a factor two faster than the OLTP traversal. Only, for very
+small graphs the overhead of running the ConnectedComponentVertexProgram is larger than that of the OLTP traversal.
+The vertex program works by having interconnected vertices exchange id's and store the lowest id until no vertex
+receives a lower id. This algorithm is commonly applied in
link:https://en.wikipedia.org/wiki/Bulk_synchronous_parallel[bulk synchronous parallel] systems, e.g. in
-link:https://spark.apache.org/graphx[Apache Spark GraphX].
+link:https://spark.apache.org/graphx[Apache Spark GraphX]. Overhead for the vertex program arises because it has to run
+as many cycles as the largest length of the shortest paths between any two vertices in a component of the graph. In
+every cycle each vertex has to be checked for being
+"halted". Overhead of the OLTP traversal consists of each traverser having to carry complete path information. For
+pure depth-first-search or breadth-first-search implementations, connected-component algotithms should scale
+as [.big]##O##(V+E). For the traversals in the figure above this is almost the case.
+
+
+[[cc-scale-ratio]]
+.Run times for finding connected components in a randomly generated graph with 10 components, each consisting of 6400 vertices
+image::cc-scale-ratio.png[width=600]
+
+The random graphs used for the scalability tests can be modulated with the edge/vertex ratio. For small ratios the
+components generated are more lint-like and harder to process by the `connectedComponent()`-step. For high ratios
+the components are more mesh-like and the ConnectedComponentVertexProgram needs few cycles to process the graph. These
+characteristics show clearly from the graph. Indeed, for a given number of vertices, the run time of the
+`connectedComponent()`-step does not depend on the number of edges, but rather on the maximum shortest path length in
+the graph.
+
+
+==== Large graphs
+
+Large graphs in TinkerPop require distributed processing by `SparkGraphComputer` to get results in a reasonable time (OLAP
+approach). This means that the graph must be available as `HadoopGraph` (third party TinkerPop implementations often
+allow to make a graph available as an `HadoopGraph` by providing an Hadoop `InputFormat`). Running the
+`connectedComponent()`-step on
+an `HadoopGraph` works the same as for a small graph, provided that `SparkGraphComputer` is specified as the graph computer,
+either with the `gremlin.hadoop.defaultGraphComputer` property or as part of the `withComputer()`-step.
+
+Scalability of the the `connectedComponent()`-step with `SparkGraphComputer` is high, but note that:
+
+* the graph should fit in the memory of the Spark cluster to allow the VertexProgram to run its cycles without spilling
+intermediate results to disk and loosing most of the gains from the distributed processing
-==== Scalability
+* as discussed for small graphs, the BSP algorithm does not play well with graphs having a large shortest path between
+any pair of vertices. Overcoming this limitation is still a
+link:http://www.vldb.org/pvldb/vol7/p1821-yan.pdf[subject of academic research].
-ToDo:
- - limits and run time regime 1
- - test of friendster graph regime 3
- - discuss: link:http://www.vldb.org/pvldb/vol7/p1821-yan.pdf[http://www.vldb.org/pvldb/vol7/p1821-yan.pdf]
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a0119640/docs/static/images/cc-scale-ratio.png
----------------------------------------------------------------------
diff --git a/docs/static/images/cc-scale-ratio.png b/docs/static/images/cc-scale-ratio.png
new file mode 100644
index 0000000..33a842d
Binary files /dev/null and b/docs/static/images/cc-scale-ratio.png differ
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a0119640/docs/static/images/cc-scale-size.png
----------------------------------------------------------------------
diff --git a/docs/static/images/cc-scale-size.png b/docs/static/images/cc-scale-size.png
new file mode 100644
index 0000000..2b08a89
Binary files /dev/null and b/docs/static/images/cc-scale-size.png differ
[13/14] tinkerpop git commit: TINKERPOP-1990 Implemented
`ShortestPathVertexProgram` and `ShortestPathVertexProgramStep`.
Posted by dk...@apache.org.
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js
----------------------------------------------------------------------
diff --git a/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js b/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js
index a0ae7ca..0cdcd21 100644
--- a/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js
+++ b/gremlin-javascript/src/main/javascript/gremlin-javascript/test/cucumber/feature-steps.js
@@ -80,6 +80,21 @@ const ignoredScenarios = {
'g_V_peerPressure_byXclusterX_byXoutEXknowsXX_pageRankX1X_byXrankX_byXoutEXknowsXX_timesX2X_group_byXclusterX_byXrank_sumX_limitX100X': new IgnoreError(ignoreReason.computerNotSupported),
'g_V_hasXname_rippleX_inXcreatedX_peerPressure_byXoutEX_byXclusterX_repeatXunionXidentity__bothX_timesX2X_dedup_valueMapXname_clusterX': new IgnoreError(ignoreReason.computerNotSupported),
'g_V_hasXname_rippleX_inXcreatedX_peerPressure_withXEDGES_outEX_withXPROPERTY_NAME_clusterX_repeatXunionXidentity__bothX_timesX2X_dedup_valueMapXname_clusterX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_both_dedup_shortestPath': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath_edgesIncluded': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath_directionXINX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath_edgesXoutEX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath_edgesIncluded_edgesXoutEX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXname_markoX_shortestPath': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath_targetXhasXname_markoXX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_shortestPath_targetXvaluesXnameX_isXmarkoXX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXname_markoX_shortestPath_targetXhasLabelXsoftwareXX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXname_markoX_shortestPath_targetXhasXname_joshXX_distanceXweightX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXname_danielX_shortestPath_targetXhasXname_stephenXX_edgesXbothEXusesXX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXsong_name_MIGHT_AS_WELLX_shortestPath_targetXhasXsong_name_MAYBE_YOU_KNOW_HOW_I_FEELXX_edgesXoutEXfollowedByXX_distanceXweightX': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXname_markoX_shortestPath_maxDistanceX1X': new IgnoreError(ignoreReason.computerNotSupported),
+ 'g_V_hasXname_vadasX_shortestPath_distanceXweightX_maxDistanceX1_3X': new IgnoreError(ignoreReason.computerNotSupported),
};
defineSupportCode(function(methods) {
@@ -352,4 +367,4 @@ function IgnoreError(reason) {
Error.captureStackTrace(this, IgnoreError);
}
-util.inherits(IgnoreError, Error);
\ No newline at end of file
+util.inherits(IgnoreError, Error);
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/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 b073aa8..a54853b 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
@@ -438,6 +438,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/0324c820/gremlin-test/features/map/Path.feature
----------------------------------------------------------------------
diff --git a/gremlin-test/features/map/Path.feature b/gremlin-test/features/map/Path.feature
index b0cb9dd..0bb7573 100644
--- a/gremlin-test/features/map/Path.feature
+++ b/gremlin-test/features/map/Path.feature
@@ -15,7 +15,7 @@
# specific language governing permissions and limitations
# under the License.
-Feature: Step - count()
+Feature: Step - path()
Scenario: g_VX1X_name_path
Given the modern graph
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/gremlin-test/features/map/ShortestPath.feature
----------------------------------------------------------------------
diff --git a/gremlin-test/features/map/ShortestPath.feature b/gremlin-test/features/map/ShortestPath.feature
new file mode 100644
index 0000000..eff743f
--- /dev/null
+++ b/gremlin-test/features/map/ShortestPath.feature
@@ -0,0 +1,361 @@
+# 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.
+
+Feature: Step - shortestPath()
+
+ Scenario: g_V_shortestPath
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath()
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],v[lop],v[peter]] |
+ | p[v[josh],v[lop]] |
+ | p[v[josh],v[marko],v[vadas]] |
+ | p[v[josh],v[marko]] |
+ | p[v[josh],v[ripple]] |
+ | p[v[josh]] |
+ | p[v[lop],v[josh],v[ripple]] |
+ | p[v[lop],v[josh]] |
+ | p[v[lop],v[marko],v[vadas]] |
+ | p[v[lop],v[marko]] |
+ | p[v[lop],v[peter]] |
+ | p[v[lop]] |
+ | p[v[marko],v[josh],v[ripple]] |
+ | p[v[marko],v[josh]] |
+ | p[v[marko],v[lop],v[peter]] |
+ | p[v[marko],v[lop]] |
+ | p[v[marko],v[vadas]] |
+ | p[v[marko]] |
+ | p[v[peter],v[lop],v[josh],v[ripple]] |
+ | p[v[peter],v[lop],v[josh]] |
+ | p[v[peter],v[lop],v[marko],v[vadas]] |
+ | p[v[peter],v[lop],v[marko]] |
+ | p[v[peter],v[lop]] |
+ | p[v[peter]] |
+ | p[v[ripple],v[josh],v[lop],v[peter]] |
+ | p[v[ripple],v[josh],v[lop]] |
+ | p[v[ripple],v[josh],v[marko],v[vadas]] |
+ | p[v[ripple],v[josh],v[marko]] |
+ | p[v[ripple],v[josh]] |
+ | p[v[ripple]] |
+ | p[v[vadas],v[marko],v[josh],v[ripple]] |
+ | p[v[vadas],v[marko],v[josh]] |
+ | p[v[vadas],v[marko],v[lop],v[peter]] |
+ | p[v[vadas],v[marko],v[lop]] |
+ | p[v[vadas],v[marko]] |
+ | p[v[vadas]] |
+
+ Scenario: g_V_both_dedup_shortestPath
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().both().dedup().shortestPath()
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],v[lop],v[peter]] |
+ | p[v[josh],v[lop]] |
+ | p[v[josh],v[marko],v[vadas]] |
+ | p[v[josh],v[marko]] |
+ | p[v[josh],v[ripple]] |
+ | p[v[josh]] |
+ | p[v[lop],v[josh],v[ripple]] |
+ | p[v[lop],v[josh]] |
+ | p[v[lop],v[marko],v[vadas]] |
+ | p[v[lop],v[marko]] |
+ | p[v[lop],v[peter]] |
+ | p[v[lop]] |
+ | p[v[marko],v[josh],v[ripple]] |
+ | p[v[marko],v[josh]] |
+ | p[v[marko],v[lop],v[peter]] |
+ | p[v[marko],v[lop]] |
+ | p[v[marko],v[vadas]] |
+ | p[v[marko]] |
+ | p[v[peter],v[lop],v[josh],v[ripple]] |
+ | p[v[peter],v[lop],v[josh]] |
+ | p[v[peter],v[lop],v[marko],v[vadas]] |
+ | p[v[peter],v[lop],v[marko]] |
+ | p[v[peter],v[lop]] |
+ | p[v[peter]] |
+ | p[v[ripple],v[josh],v[lop],v[peter]] |
+ | p[v[ripple],v[josh],v[lop]] |
+ | p[v[ripple],v[josh],v[marko],v[vadas]] |
+ | p[v[ripple],v[josh],v[marko]] |
+ | p[v[ripple],v[josh]] |
+ | p[v[ripple]] |
+ | p[v[vadas],v[marko],v[josh],v[ripple]] |
+ | p[v[vadas],v[marko],v[josh]] |
+ | p[v[vadas],v[marko],v[lop],v[peter]] |
+ | p[v[vadas],v[marko],v[lop]] |
+ | p[v[vadas],v[marko]] |
+ | p[v[vadas]] |
+
+ Scenario: g_V_shortestPath_edgesIncluded
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath().with("~tinkerpop.shortestPath.includeEdges", true)
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],e[josh-created->lop],v[lop],e[peter-created->lop],v[peter]] |
+ | p[v[josh],e[josh-created->lop],v[lop]] |
+ | p[v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[josh],e[marko-knows->josh],v[marko],e[marko-knows->vadas],v[vadas]] |
+ | p[v[josh],e[marko-knows->josh],v[marko]] |
+ | p[v[josh]] |
+ | p[v[lop],e[josh-created->lop],v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[lop],e[josh-created->lop],v[josh]] |
+ | p[v[lop],e[marko-created->lop],v[marko],e[marko-knows->vadas],v[vadas]] |
+ | p[v[lop],e[marko-created->lop],v[marko]] |
+ | p[v[lop],e[peter-created->lop],v[peter]] |
+ | p[v[lop]] |
+ | p[v[marko],e[marko-created->lop],v[lop],e[peter-created->lop],v[peter]] |
+ | p[v[marko],e[marko-created->lop],v[lop]] |
+ | p[v[marko],e[marko-knows->josh],v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[marko],e[marko-knows->josh],v[josh]] |
+ | p[v[marko],e[marko-knows->vadas],v[vadas]] |
+ | p[v[marko]] |
+ | p[v[peter],e[peter-created->lop],v[lop],e[josh-created->lop],v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[peter],e[peter-created->lop],v[lop],e[josh-created->lop],v[josh]] |
+ | p[v[peter],e[peter-created->lop],v[lop],e[marko-created->lop],v[marko],e[marko-knows->vadas],v[vadas]] |
+ | p[v[peter],e[peter-created->lop],v[lop],e[marko-created->lop],v[marko]] |
+ | p[v[peter],e[peter-created->lop],v[lop]] |
+ | p[v[peter]] |
+ | p[v[ripple],e[josh-created->ripple],v[josh],e[josh-created->lop],v[lop],e[peter-created->lop],v[peter]] |
+ | p[v[ripple],e[josh-created->ripple],v[josh],e[josh-created->lop],v[lop]] |
+ | p[v[ripple],e[josh-created->ripple],v[josh],e[marko-knows->josh],v[marko],e[marko-knows->vadas],v[vadas]] |
+ | p[v[ripple],e[josh-created->ripple],v[josh],e[marko-knows->josh],v[marko]] |
+ | p[v[ripple],e[josh-created->ripple],v[josh]] |
+ | p[v[ripple]] |
+ | p[v[vadas],e[marko-knows->vadas],v[marko],e[marko-created->lop],v[lop],e[peter-created->lop],v[peter]] |
+ | p[v[vadas],e[marko-knows->vadas],v[marko],e[marko-created->lop],v[lop]] |
+ | p[v[vadas],e[marko-knows->vadas],v[marko],e[marko-knows->josh],v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[vadas],e[marko-knows->vadas],v[marko],e[marko-knows->josh],v[josh]] |
+ | p[v[vadas],e[marko-knows->vadas],v[marko]] |
+ | p[v[vadas]] |
+
+ Scenario: g_V_shortestPath_directionXINX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath().with("~tinkerpop.shortestPath.edges", Direction.IN)
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],v[marko]] |
+ | p[v[josh]] |
+ | p[v[lop],v[josh]] |
+ | p[v[lop],v[marko]] |
+ | p[v[lop],v[peter]] |
+ | p[v[lop]] |
+ | p[v[marko]] |
+ | p[v[peter]] |
+ | p[v[ripple],v[josh],v[marko]] |
+ | p[v[ripple],v[josh]] |
+ | p[v[ripple]] |
+ | p[v[vadas],v[marko]] |
+ | p[v[vadas]] |
+
+ Scenario: g_V_shortestPath_edgesXoutEX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath().with("~tinkerpop.shortestPath.edges", __.outE())
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],v[lop]] |
+ | p[v[josh],v[ripple]] |
+ | p[v[josh]] |
+ | p[v[lop]] |
+ | p[v[marko],v[josh],v[ripple]] |
+ | p[v[marko],v[josh]] |
+ | p[v[marko],v[lop]] |
+ | p[v[marko],v[vadas]] |
+ | p[v[marko]] |
+ | p[v[peter],v[lop]] |
+ | p[v[peter]] |
+ | p[v[ripple]] |
+ | p[v[vadas]] |
+
+ Scenario: g_V_shortestPath_edgesIncluded_edgesXoutEX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath().
+ with("~tinkerpop.shortestPath.includeEdges", true).
+ with("~tinkerpop.shortestPath.edges", __.outE())
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],e[josh-created->lop],v[lop]] |
+ | p[v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[josh]] |
+ | p[v[lop]] |
+ | p[v[marko],e[marko-created->lop],v[lop]] |
+ | p[v[marko],e[marko-knows->josh],v[josh],e[josh-created->ripple],v[ripple]] |
+ | p[v[marko],e[marko-knows->josh],v[josh]] |
+ | p[v[marko],e[marko-knows->vadas],v[vadas]] |
+ | p[v[marko]] |
+ | p[v[peter],e[peter-created->lop],v[lop]] |
+ | p[v[peter]] |
+ | p[v[ripple]] |
+ | p[v[vadas]] |
+
+ Scenario: g_V_hasXname_markoX_shortestPath
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().has("name","marko").shortestPath()
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[marko],v[josh],v[ripple]] |
+ | p[v[marko],v[josh]] |
+ | p[v[marko],v[lop],v[peter]] |
+ | p[v[marko],v[lop]] |
+ | p[v[marko],v[vadas]] |
+ | p[v[marko]] |
+
+ Scenario: g_V_shortestPath_targetXhasXname_markoXX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath().with("~tinkerpop.shortestPath.target", __.has("name","marko"))
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],v[marko]] |
+ | p[v[lop],v[marko]] |
+ | p[v[marko]] |
+ | p[v[peter],v[lop],v[marko]] |
+ | p[v[ripple],v[josh],v[marko]] |
+ | p[v[vadas],v[marko]] |
+
+ Scenario: g_V_shortestPath_targetXvaluesXnameX_isXmarkoXX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().shortestPath().with("~tinkerpop.shortestPath.target", __.values("name").is("marko"))
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[josh],v[marko]] |
+ | p[v[lop],v[marko]] |
+ | p[v[marko]] |
+ | p[v[peter],v[lop],v[marko]] |
+ | p[v[ripple],v[josh],v[marko]] |
+ | p[v[vadas],v[marko]] |
+
+ Scenario: g_V_hasXname_markoX_shortestPath_targetXhasLabelXsoftwareXX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().has("name","marko").shortestPath().with("~tinkerpop.shortestPath.target", __.hasLabel("software"))
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[marko],v[josh],v[ripple]] |
+ | p[v[marko],v[lop]] |
+
+ Scenario: g_V_hasXname_markoX_shortestPath_targetXhasXname_joshXX_distanceXweightX
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().has("name","marko").shortestPath().
+ with("~tinkerpop.shortestPath.target", __.has("name","josh")).
+ with("~tinkerpop.shortestPath.distance", "weight")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[marko],v[lop],v[josh]] |
+
+ Scenario: g_V_hasXname_danielX_shortestPath_targetXhasXname_stephenXX_edgesXbothEXusesXX
+ Given the crew graph
+ And the traversal of
+ """
+ g.withComputer().V().has("name","daniel").shortestPath().
+ with("~tinkerpop.shortestPath.target", __.has("name","stephen")).
+ with("~tinkerpop.shortestPath.edges", __.bothE("uses"))
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[daniel],v[gremlin],v[stephen]] |
+ | p[v[daniel],v[tinkergraph],v[stephen]] |
+
+ Scenario: g_V_hasXsong_name_MIGHT_AS_WELLX_shortestPath_targetXhasXsong_name_MAYBE_YOU_KNOW_HOW_I_FEELXX_edgesXoutEXfollowedByXX_distanceXweightX
+ Given the grateful graph
+ And the traversal of
+ """
+ g.withComputer().V().has("song","name","MIGHT AS WELL").
+ shortestPath().
+ with("~tinkerpop.shortestPath.target", __.has("song","name","MAYBE YOU KNOW HOW I FEEL")).
+ with("~tinkerpop.shortestPath.edges", __.outE("followedBy")).
+ with("~tinkerpop.shortestPath.distance", "weight")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[MIGHT AS WELL],v[DRUMS],v[MAYBE YOU KNOW HOW I FEEL]] |
+ | p[v[MIGHT AS WELL],v[SHIP OF FOOLS],v[MAYBE YOU KNOW HOW I FEEL]] |
+
+ Scenario: g_V_hasXname_markoX_shortestPath_maxDistanceX1X
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().has("name","marko").shortestPath().with("~tinkerpop.shortestPath.maxDistance", 1)
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[marko],v[josh]] |
+ | p[v[marko],v[lop]] |
+ | p[v[marko],v[vadas]] |
+ | p[v[marko]] |
+
+ Scenario: g_V_hasXname_vadasX_shortestPath_distanceXweightX_maxDistanceX1_3X
+ Given the modern graph
+ And the traversal of
+ """
+ g.withComputer().V().has("name","vadas").shortestPath().
+ with("~tinkerpop.shortestPath.distance", "weight").
+ with("~tinkerpop.shortestPath.maxDistance", 1.3)
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | p[v[vadas],v[marko],v[lop],v[josh]] |
+ | p[v[vadas],v[marko],v[lop],v[peter]] |
+ | p[v[vadas],v[marko],v[lop]] |
+ | p[v[vadas],v[marko]] |
+ | p[v[vadas]] |
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/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/0324c820/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 4749e93..0a2a405 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
@@ -127,7 +127,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);
@@ -145,11 +145,10 @@ public abstract class AbstractGremlinProcessTest extends AbstractGremlinTest {
}
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) {
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/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 6466ae8..5a39908 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
@@ -26,6 +26,7 @@ import org.apache.tinkerpop.gremlin.process.computer.bulkloading.BulkLoaderVerte
import org.apache.tinkerpop.gremlin.process.computer.clone.CloneVertexProgramTest;
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;
@@ -72,6 +73,7 @@ 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.ReadTest;
+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;
@@ -168,6 +170,7 @@ public class ProcessComputerSuite extends AbstractGremlinSuite {
ProgramTest.Traversals.class,
PropertiesTest.Traversals.class,
ReadTest.Traversals.class,
+ ShortestPathTest.Traversals.class,
SelectTest.Traversals.class,
UnfoldTest.Traversals.class,
ValueMapTest.Traversals.class,
@@ -196,6 +199,7 @@ public class ProcessComputerSuite extends AbstractGremlinSuite {
// algorithms
PageRankVertexProgramTest.class,
PeerPressureVertexProgramTest.class,
+ ShortestPathVertexProgramTest.class,
BulkLoaderVertexProgramTest.class,
BulkDumperVertexProgramTest.class,
CloneVertexProgramTest.class,
@@ -260,6 +264,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/0324c820/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..7f3aa63
--- /dev/null
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathTestHelper.java
@@ -0,0 +1,100 @@
+/*
+ * 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.process.traversal.step.util.MapHelper;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.MutablePath;
+import org.apache.tinkerpop.gremlin.structure.Edge;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.hamcrest.Matchers;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import static org.hamcrest.Matchers.equalTo;
+import static org.hamcrest.Matchers.is;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertThat;
+
+/**
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+public class ShortestPathTestHelper {
+
+ private final AbstractGremlinProcessTest test;
+ private final GraphTraversalSource g;
+ private final Map<String, Vertex> vertexCache;
+ private final Map<Object, Map<Object, Edge>> edgeCache;
+
+ public ShortestPathTestHelper(final AbstractGremlinProcessTest test, final GraphTraversalSource g) {
+ this.test = test;
+ this.g = g;
+ this.vertexCache = new HashMap<>();
+ this.edgeCache = new HashMap<>();
+ }
+
+ 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 = vertexCache.computeIfAbsent(name, test::convertToVertex);
+ if (!first) {
+ if (includeEdges) {
+ final Object id1 = ((Vertex) path.get(path.size() - 1)).id();
+ final Object id2 = vertex.id();
+ final Edge edge;
+ if (edgeCache.containsKey(id1)) {
+ edge = edgeCache.get(id1).computeIfAbsent(id2, id -> getEdge(id1, id));
+ } else if (edgeCache.containsKey(id2)) {
+ edge = edgeCache.get(id2).computeIfAbsent(id1, id -> getEdge(id, id2));
+ } else {
+ edgeCache.put(id1, new HashMap<>());
+ edgeCache.get(id1).put(id2, edge = getEdge(id1, id2));
+ }
+ path = path.extend(edge, Collections.emptySet());
+ }
+ }
+ path = path.extend(vertex, Collections.emptySet());
+ first = false;
+ }
+ return path;
+ }
+
+ private Edge getEdge(final Object id1, final Object id2) {
+ return g.V(id1)
+ .bothE().filter(__.otherV().hasId(id2))
+ .next();
+ }
+}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/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..303299d
--- /dev/null
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgramTest.java
@@ -0,0 +1,297 @@
+/*
+ * 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 java.util.stream.Stream;
+
+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);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void shouldRespectMaxDistance() throws Exception {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(ShortestPathVertexProgram.build()
+ .source(__.has("name", "marko"))
+ .maxDistance(1).create(graph)).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[0].equals("marko") && p.length <= 2).map(helper::makePath).collect(Collectors.toList());
+ helper.checkResults(expected, shortestPaths);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void shouldRespectMaxCustomDistance() throws Exception {
+ final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).
+ program(ShortestPathVertexProgram.build()
+ .source(__.has("name", "vadas"))
+ .distanceProperty("weight").maxDistance(1.3).create(graph)).submit().get();
+ assertTrue(result.memory().exists(ShortestPathVertexProgram.SHORTEST_PATHS));
+ final List<Path> shortestPaths = result.memory().get(ShortestPathVertexProgram.SHORTEST_PATHS);
+ final List<Path> expected = Stream.concat(Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[0].equals("vadas") &&
+ Arrays.asList("vadas", "marko", "lop", "peter").contains(p[p.length - 1]))
+ .map(helper::makePath),
+ Stream.of(helper.makePath("vadas", "marko", "lop", "josh")))
+ .collect(Collectors.toList());
+ helper.checkResults(expected, shortestPaths);
+ }
+
+ public static String[][] ALL_SHORTEST_PATHS = new String[][]{
+ new String[]{"marko"},
+ new String[]{"marko", "vadas"},
+ new String[]{"marko", "lop"},
+ new String[]{"marko", "lop", "peter"},
+ new String[]{"marko", "josh"},
+ new String[]{"marko", "josh", "ripple"},
+ new String[]{"vadas"},
+ new String[]{"vadas", "marko"},
+ new String[]{"vadas", "marko", "lop"},
+ new String[]{"vadas", "marko", "lop", "peter"},
+ new String[]{"vadas", "marko", "josh", "ripple"},
+ new String[]{"vadas", "marko", "josh"},
+ new String[]{"lop"},
+ new String[]{"lop", "marko"},
+ new String[]{"lop", "marko", "vadas"},
+ new String[]{"lop", "josh"},
+ new String[]{"lop", "josh", "ripple"},
+ new String[]{"lop", "peter"},
+ new String[]{"josh"},
+ new String[]{"josh", "marko"},
+ new String[]{"josh", "marko", "vadas"},
+ new String[]{"josh", "lop"},
+ new String[]{"josh", "lop", "peter"},
+ new String[]{"josh", "ripple"},
+ new String[]{"ripple"},
+ new String[]{"ripple", "josh"},
+ new String[]{"ripple", "josh", "marko"},
+ new String[]{"ripple", "josh", "marko", "vadas"},
+ new String[]{"ripple", "josh", "lop"},
+ new String[]{"ripple", "josh", "lop", "peter"},
+ new String[]{"peter"},
+ new String[]{"peter", "lop"},
+ new String[]{"peter", "lop", "marko"},
+ new String[]{"peter", "lop", "marko", "vadas"},
+ new String[]{"peter", "lop", "josh"},
+ new String[]{"peter", "lop", "josh", "ripple"}
+ };
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ShortestPathTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ShortestPathTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ShortestPathTest.java
new file mode 100644
index 0000000..a55215b
--- /dev/null
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ShortestPathTest.java
@@ -0,0 +1,353 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.tinkerpop.gremlin.process.traversal.step.map;
+
+import org.apache.tinkerpop.gremlin.LoadGraphWith;
+import org.apache.tinkerpop.gremlin.process.AbstractGremlinProcessTest;
+import org.apache.tinkerpop.gremlin.process.GremlinProcessRunner;
+import org.apache.tinkerpop.gremlin.process.computer.search.path.ShortestPathTestHelper;
+import org.apache.tinkerpop.gremlin.process.traversal.Path;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.structure.Direction;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+import java.util.Arrays;
+import java.util.List;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.CREW;
+import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.GRATEFUL;
+import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.MODERN;
+import static org.apache.tinkerpop.gremlin.process.computer.search.path.ShortestPathVertexProgramTest.ALL_SHORTEST_PATHS;
+import static org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ShortestPath.*;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+/**
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+@RunWith(GremlinProcessRunner.class)
+public abstract class ShortestPathTest extends AbstractGremlinProcessTest {
+
+ private ShortestPathTestHelper helper;
+
+ @Before
+ public void initializeHelper() throws Exception {
+ this.helper = new ShortestPathTestHelper(this, g);
+ }
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath();
+
+ public abstract Traversal<Vertex, Path> get_g_V_both_dedup_shortestPath();
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath_edgesIncluded();
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath_directionXINX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath_edgesXoutEX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath_edgesIncluded_edgesXoutEX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath();
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath_targetXhasXname_markoXX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_shortestPath_targetXvaluesXnameX_isXmarkoXX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath_targetXhasLabelXsoftwareXX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath_targetXhasXname_joshXX_distanceXweightX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXname_danielX_shortestPath_targetXhasXname_stephenXX_edgesXbothEXusesXX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXsong_name_MIGHT_AS_WELLX_shortestPath_targetXhasXsong_name_MAYBE_YOU_KNOW_HOW_I_FEELXX_edgesXoutEXfollowedByXX_distanceXweightX();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath_maxDistanceX1X();
+
+ public abstract Traversal<Vertex, Path> get_g_V_hasXname_vadasX_shortestPath_distanceXweightX_maxDistanceX1_3X();
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS).map(helper::makePath)
+ .collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_both_dedup_shortestPath() {
+ final Traversal<Vertex, Path> traversal = get_g_V_both_dedup_shortestPath();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS).map(helper::makePath)
+ .collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath_edgesIncluded() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath_edgesIncluded();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS).map(p -> helper.makePath(true, p))
+ .collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath_directionXINX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath_directionXINX();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> (p[0].equals("marko") && p.length == 1)
+ || (p[0].equals("vadas") && Arrays.asList("marko", "vadas").contains(p[p.length - 1]))
+ || (p[0].equals("lop") && Arrays.asList("marko", "lop", "josh", "peter").contains(p[p.length - 1]))
+ || (p[0].equals("josh") && Arrays.asList("marko", "josh").contains(p[p.length - 1]))
+ || (p[0].equals("ripple") && Arrays.asList("marko", "josh", "ripple").contains(p[p.length - 1]))
+ || (p[0].equals("peter") && p.length == 1))
+ .map(helper::makePath).collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath_edgesXoutEX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath_edgesXoutEX();
+ printTraversalForm(traversal);
+ checkOutDirectedPaths(false, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath_edgesIncluded_edgesXoutEX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath_edgesIncluded_edgesXoutEX();
+ printTraversalForm(traversal);
+ checkOutDirectedPaths(true, traversal);
+ }
+
+ private void checkOutDirectedPaths(final boolean includeEdges, final Traversal<Vertex, Path> traversal) {
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> (p[0].equals("marko") && !p[p.length - 1].equals("peter"))
+ || (p[0].equals("vadas") && p.length == 1)
+ || (p[0].equals("lop") && p.length == 1)
+ || (p[0].equals("josh") && Arrays.asList("lop", "josh", "ripple").contains(p[p.length - 1]))
+ || (p[0].equals("ripple") && p.length == 1)
+ || (p[0].equals("peter") && Arrays.asList("lop", "peter").contains(p[p.length - 1])))
+ .map(names -> helper.makePath(includeEdges, names)).collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_hasXname_markoX_shortestPath() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXname_markoX_shortestPath();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[0].equals("marko")).map(helper::makePath).collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath_targetXhasXname_markoXX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath_targetXhasXname_markoXX();
+ printTraversalForm(traversal);
+ checkPathsToMarko(traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_shortestPath_targetXvaluesXnameX_isXmarkoXX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_shortestPath_targetXvaluesXnameX_isXmarkoXX();
+ printTraversalForm(traversal);
+ checkPathsToMarko(traversal);
+ }
+
+ private void checkPathsToMarko(final Traversal<Vertex, Path> traversal) {
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[p.length - 1].equals("marko")).map(helper::makePath).collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_hasXname_markoX_shortestPath_targetXhasLabelXsoftwareXX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXname_markoX_shortestPath_targetXhasLabelXsoftwareXX();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p ->
+ p[0].equals("marko") && Arrays.asList("lop", "ripple").contains(p[p.length - 1]))
+ .map(helper::makePath).collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_hasXname_markoX_shortestPath_targetXhasXname_joshXX_distanceXweightX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXname_markoX_shortestPath_targetXhasXname_joshXX_distanceXweightX();
+ printTraversalForm(traversal);
+ assertTrue(traversal.hasNext());
+ assertEquals(helper.makePath("marko", "lop", "josh"), traversal.next());
+ assertFalse(traversal.hasNext());
+ }
+
+ @Test
+ @LoadGraphWith(CREW)
+ public void g_V_hasXname_danielX_shortestPath_targetXhasXname_stephenXX_edgesXbothEXusesXX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXname_danielX_shortestPath_targetXhasXname_stephenXX_edgesXbothEXusesXX();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.asList(
+ helper.makePath("daniel", "gremlin", "stephen"),
+ helper.makePath("daniel", "tinkergraph", "stephen"));
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(GRATEFUL)
+ public void g_V_hasXsong_name_MIGHT_AS_WELLX_shortestPath_targetXhasXsong_name_MAYBE_YOU_KNOW_HOW_I_FEELXX_edgesXoutEXfollowedByXX_distanceXweightX() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXsong_name_MIGHT_AS_WELLX_shortestPath_targetXhasXsong_name_MAYBE_YOU_KNOW_HOW_I_FEELXX_edgesXoutEXfollowedByXX_distanceXweightX();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.asList(
+ helper.makePath("MIGHT AS WELL", "DRUMS", "MAYBE YOU KNOW HOW I FEEL"),
+ helper.makePath("MIGHT AS WELL", "SHIP OF FOOLS", "MAYBE YOU KNOW HOW I FEEL"));
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_hasXname_markoX_shortestPath_maxDistanceX1X() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXname_markoX_shortestPath_maxDistanceX1X();
+ printTraversalForm(traversal);
+ final List<Path> expected = Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[0].equals("marko") && p.length <= 2).map(helper::makePath).collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_hasXname_vadasX_shortestPath_distanceXweightX_maxDistanceX1_3X() {
+ final Traversal<Vertex, Path> traversal = get_g_V_hasXname_vadasX_shortestPath_distanceXweightX_maxDistanceX1_3X();
+ printTraversalForm(traversal);
+ final List<Path> expected = Stream.concat(Arrays.stream(ALL_SHORTEST_PATHS)
+ .filter(p -> p[0].equals("vadas") &&
+ Arrays.asList("vadas", "marko", "lop", "peter").contains(p[p.length - 1]))
+ .map(helper::makePath),
+ Stream.of(helper.makePath("vadas", "marko", "lop", "josh")))
+ .collect(Collectors.toList());
+ checkResults(expected, traversal);
+ }
+
+ public static class Traversals extends ShortestPathTest {
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath() {
+ return g.V().shortestPath();
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_both_dedup_shortestPath() {
+ return g.V().both().dedup().shortestPath();
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath_edgesIncluded() {
+ return g.V().shortestPath().with(includeEdges, true);
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath_directionXINX() {
+ return g.V().shortestPath().with(edges, Direction.IN);
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath_edgesXoutEX() {
+ return g.V().shortestPath().with(edges, __.outE());
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath_edgesIncluded_edgesXoutEX() {
+ return g.V().shortestPath().with(includeEdges, true).with(edges, __.outE());
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath() {
+ return g.V().has("name", "marko").shortestPath();
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath_targetXhasXname_markoXX() {
+ return g.V().shortestPath().with(target, __.has("name", "marko"));
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_shortestPath_targetXvaluesXnameX_isXmarkoXX() {
+ return g.V().shortestPath().with(target, __.<Vertex, String>values("name").is("marko"));
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath_targetXhasLabelXsoftwareXX() {
+ return g.V().has("name", "marko").shortestPath().with(target, __.hasLabel("software"));
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath_targetXhasXname_joshXX_distanceXweightX() {
+ return g.V().has("name", "marko").shortestPath()
+ .with(target, __.has("name","josh"))
+ .with(distance, "weight");
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXname_danielX_shortestPath_targetXhasXname_stephenXX_edgesXbothEXusesXX() {
+ return g.V().has("name", "daniel").shortestPath()
+ .with(target, __.has("name","stephen"))
+ .with(edges, __.bothE("uses"));
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXsong_name_MIGHT_AS_WELLX_shortestPath_targetXhasXsong_name_MAYBE_YOU_KNOW_HOW_I_FEELXX_edgesXoutEXfollowedByXX_distanceXweightX() {
+ return g.V().has("song", "name", "MIGHT AS WELL")
+ .shortestPath().
+ with(target, __.has("song", "name", "MAYBE YOU KNOW HOW I FEEL")).
+ with(edges, __.outE("followedBy")).
+ with(distance, "weight");
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXname_markoX_shortestPath_maxDistanceX1X() {
+ return g.V().has("name", "marko").shortestPath()
+ .with(maxDistance, 1);
+ }
+
+ @Override
+ public Traversal<Vertex, Path> get_g_V_hasXname_vadasX_shortestPath_distanceXweightX_maxDistanceX1_3X() {
+ return g.V().has("name", "vadas").shortestPath()
+ .with(distance, "weight")
+ .with(maxDistance, 1.3);
+ }
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0324c820/pom.xml
----------------------------------------------------------------------
diff --git a/pom.xml b/pom.xml
index ea42197..a3496f3 100644
--- a/pom.xml
+++ b/pom.xml
@@ -1271,6 +1271,9 @@ limitations under the License.
org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
</include>
<include>
+ org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java
+ </include>
+ <include>
org/apache/tinkerpop/gremlin/process/computer/traversal/TraversalVertexProgram.java
</include>
<!-- traversal -->