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/2cb61e36 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/2cb61e36 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/2cb61e36 Branch: refs/heads/TINKERPOP-1967 Commit: 2cb61e368eadab552ba8bab7fd4ccd48026ac4f8 Parents: 23b766a Author: Stephen Mallette <sp...@genoprime.com> Authored: Thu May 17 14:44:01 2018 -0400 Committer: Stephen Mallette <sp...@genoprime.com> Committed: Fri Jun 1 08:05:11 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/2cb61e36/CHANGELOG.asciidoc ---------------------------------------------------------------------- diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc index 92d00b2..c42f99a 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`. * 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/2cb61e36/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/2cb61e36/docs/src/reference/the-graphcomputer.asciidoc ---------------------------------------------------------------------- diff --git a/docs/src/reference/the-graphcomputer.asciidoc b/docs/src/reference/the-graphcomputer.asciidoc index 4bf39d0..566651b 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]] === BulkDumperVertexProgram http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2cb61e36/docs/src/reference/the-traversal.asciidoc ---------------------------------------------------------------------- diff --git a/docs/src/reference/the-traversal.asciidoc b/docs/src/reference/the-traversal.asciidoc index b3e5ef5..539af85 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/2cb61e36/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 3c881c3..e90eb7f 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/2cb61e36/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/2cb61e36/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/2cb61e36/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/2cb61e36/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 0fd3599..3b301be 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 an arbitrary {@link VertexProgram} over the graph. * * @return the traversal with the appended {@link ProgramVertexProgramStep} @@ -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/2cb61e36/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/2cb61e36/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 bb3d5d8..73e85c9 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/2cb61e36/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 901f9b0..939606d 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/2cb61e36/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 a492f9c..f8d49a4 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/2cb61e36/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/2cb61e36/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/2cb61e36/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