You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by sp...@apache.org on 2018/05/21 13:06:36 UTC
tinkerpop git commit: TINKERPOP-1967 Added connectedComponent() step
Repository: tinkerpop
Updated Branches:
refs/heads/TINKERPOP-1967 [created] f91d3d9d2
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/f91d3d9d
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/f91d3d9d
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/f91d3d9d
Branch: refs/heads/TINKERPOP-1967
Commit: f91d3d9d21f1e921a071200668b0fd0e33b321a8
Parents: 489592e
Author: Stephen Mallette <sp...@genoprime.com>
Authored: Thu May 17 14:44:01 2018 -0400
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Thu May 17 14:44:01 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 | 27 +++
docs/src/upgrade/release-3.4.x.asciidoc | 32 +++
.../ConnectedComponentVertexProgram.java | 216 +++++++++++++++++++
.../ConnectedComponentVertexProgramStep.java | 69 ++++++
.../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 | 89 ++++++++
.../computer/SparkHadoopGraphProvider.java | 2 +
16 files changed, 494 insertions(+), 2 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f91d3d9d/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 2851506..d9d628c 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>>.
+* Added `connectedComponent()` step and related `VertexProgram`.
* `min()` and `max()` now support all types implementing `Comparable`.
* Change the `toString()` of `Path` to be standardized as other graph elements are.
* `hadoop-gremlin` no longer generates a test artifact.
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f91d3d9d/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/f91d3d9d/docs/src/reference/the-graphcomputer.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/reference/the-graphcomputer.asciidoc b/docs/src/reference/the-graphcomputer.asciidoc
index af599eb..990bbe7 100644
--- a/docs/src/reference/the-graphcomputer.asciidoc
+++ b/docs/src/reference/the-graphcomputer.asciidoc
@@ -402,6 +402,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]]
=== BulkDumperVertexProgram
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f91d3d9d/docs/src/reference/the-traversal.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/reference/the-traversal.asciidoc b/docs/src/reference/the-traversal.asciidoc
index f62b665..9aaf739 100644
--- a/docs/src/reference/the-traversal.asciidoc
+++ b/docs/src/reference/the-traversal.asciidoc
@@ -608,6 +608,33 @@ 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().by('component').
+ project('name','component').
+ by('name').
+ by('component')
+g.V().hasLabel('person').
+ connectedComponent().by('component').
+ project('name','component').
+ by('name').
+ by('component')
+----
+
+*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/f91d3d9d/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 a3de9e7..70c588f 100644
--- a/docs/src/upgrade/release-3.4.x.asciidoc
+++ b/docs/src/upgrade/release-3.4.x.asciidoc
@@ -29,6 +29,38 @@ Please see the link:https://github.com/apache/tinkerpop/blob/3.4.0/CHANGELOG.asc
=== Upgrading for Users
+==== 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]
+
==== Removal of Giraph Support
Support for Giraph has been removed as of this version. There were a number of reasons for this decision which were
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f91d3d9d/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..2d09d6f
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/clustering/connected/ConnectedComponentVertexProgram.java
@@ -0,0 +1,216 @@
+/*
+ * 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.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.structure.Direction;
+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> {
+ private static final MessageScope.Local<?> scope = MessageScope.Local.of(__::bothE);
+ private static final Set<MessageScope> scopes = new HashSet<>(Collections.singletonList(scope));
+
+ public static final String COMPONENT = "gremlin.connectedComponentVertexProgram.component";
+ private static final String PROPERTY = "gremlin.connectedComponentVertexProgram.property";
+ 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 String property = COMPONENT;
+ private boolean hasHalted = false;
+ 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);
+ }
+ 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) {
+ // exit if the traverser was filtered - happens for stuff like g.V().hasLabel('person').connectedComponent()
+ // (i.e. when there is a TraversalVertexProgram in the mix halting traversers
+ if (hasHalted && !vertex.property(TraversalVertexProgram.HALTED_TRAVERSERS).isPresent()) return;
+
+ 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());
+
+ 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
+ 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 property(final String key) {
+ this.configuration.setProperty(PROPERTY, key);
+ return this;
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f91d3d9d/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..39900ee
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ConnectedComponentVertexProgramStep.java
@@ -0,0 +1,69 @@
+/*
+ * 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.clustering.peerpressure.PeerPressureVertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.TraversalVertexProgram;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.step.ByModulating;
+import org.apache.tinkerpop.gremlin.structure.Graph;
+import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
+
+/**
+ * @author Stephen Mallette (http://stephen.genoprime.com)
+ */
+public final class ConnectedComponentVertexProgramStep extends VertexProgramStep implements ByModulating {
+
+ private String clusterProperty = ConnectedComponentVertexProgram.COMPONENT;
+
+ public ConnectedComponentVertexProgramStep(final Traversal.Admin traversal) {
+ super(traversal);
+ }
+
+ @Override
+ public int hashCode() {
+ return super.hashCode() ^ this.clusterProperty.hashCode();
+ }
+
+ @Override
+ public void modulateBy(final String clusterProperty) {
+ this.clusterProperty = clusterProperty;
+ }
+
+ @Override
+ public String toString() {
+ return StringFactory.stepString(this, this.clusterProperty, new GraphFilter(this.computer));
+ }
+
+ @Override
+ public ConnectedComponentVertexProgram generateProgram(final Graph graph, final Memory memory) {
+ return ConnectedComponentVertexProgram.build().
+ hasHalted(memory.exists(TraversalVertexProgram.HALTED_TRAVERSERS)).
+ property(this.clusterProperty).create(graph);
+ }
+
+ @Override
+ public ConnectedComponentVertexProgramStep clone() {
+ return (ConnectedComponentVertexProgramStep) super.clone();
+ }
+}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f91d3d9d/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java
index da12114..d2093e4 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
@@ -57,6 +57,10 @@ import java.util.Iterator;
method = "*",
reason = "hmmmm")
@Graph.OptOut(
+ test = "org.apache.tinkerpop.gremlin.process.traversal.step.map.ConnectedComponentTest",
+ method = "*",
+ reason = "hmmmm")
+@Graph.OptOut(
test = "org.apache.tinkerpop.gremlin.process.traversal.step.map.PageRankTest",
method = "*",
reason = "hmmmm")
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f91d3d9d/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 8a865ca..8441926 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;
@@ -2421,6 +2423,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 a Peer Pressure community detection algorithm over the graph.
*
* @return the traversal with the appended {@link PeerPressureVertexProgramStep}
@@ -2798,6 +2812,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/f91d3d9d/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 6decbe0..0140801 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalTest.java
@@ -42,7 +42,7 @@ import static org.junit.Assert.assertEquals;
public class GraphTraversalTest {
private static final Logger logger = LoggerFactory.getLogger(GraphTraversalTest.class);
- private static Set<String> NO_GRAPH = new HashSet<>(Arrays.asList("asAdmin", "by", "option", "iterate", "to", "from", "profile", "pageRank", "peerPressure", "program", "none"));
+ private static Set<String> NO_GRAPH = new HashSet<>(Arrays.asList("asAdmin", "by", "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", "iterate", "mapValues", "mapKeys"));
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f91d3d9d/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 9952455..5a3208b 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/f91d3d9d/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 edeb2cb..739d91a 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
@@ -343,6 +343,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/f91d3d9d/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 d5630c0..2e78100 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
@@ -189,6 +189,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/f91d3d9d/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessComputerSuite.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessComputerSuite.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessComputerSuite.java
index 3d51a94..c19d4c2 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
@@ -49,6 +49,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;
@@ -140,6 +141,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/f91d3d9d/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..88c9cbc
--- /dev/null
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ConnectedComponentTest.java
@@ -0,0 +1,89 @@
+/*
+ * 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.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.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_hasLabelXpersonX_connectedComponent();
+
+ @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_hasLabelXpersonX_connectedComponent() {
+ final Traversal<Vertex, Vertex> traversal = get_g_V_hasLabelXpersonX_connectedComponent();
+ printTraversalForm(traversal);
+ int counter = 0;
+ while (traversal.hasNext()) {
+ final Vertex vertex = traversal.next();
+ final String name = vertex.value("name");
+ switch (name) {
+ case "marko":
+ case "josh":
+ case "vadas":
+ assertEquals("1", vertex.value(ConnectedComponentVertexProgram.COMPONENT));
+ break;
+ case "peter":
+ assertEquals("6", vertex.value(ConnectedComponentVertexProgram.COMPONENT));
+ 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_hasLabelXpersonX_connectedComponent() {
+ return g.V().hasLabel("person").connectedComponent();
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f91d3d9d/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