org.apache.flink.graph.library

Class ConnectedComponents<K,VV extends Comparable<VV>,EV>

java.lang.Object

org.apache.flink.graph.library.ConnectedComponents<K,VV,EV>

All Implemented Interfaces:

GraphAlgorithm<K,VV,EV,DataSet<Vertex<K,VV>>>

public class ConnectedComponents<K,VV extends Comparable<VV>,EV>
extends Object
implements GraphAlgorithm<K,VV,EV,DataSet<Vertex<K,VV>>>

A scatter-gather implementation of the Weakly Connected Components algorithm.

This implementation uses a comparable vertex value as initial component identifier (ID). Vertices propagate their current value in each iteration. Upon receiving component IDs from its neighbors, a vertex adopts a new component ID if its value is lower than its current component ID.

The algorithm converges when vertices no longer update their component ID value or when the maximum number of iterations has been reached.

The result is a DataSet of vertices, where the vertex value corresponds to the assigned component ID.

See Also:

GSAConnectedComponents

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	ConnectedComponents.CCMessenger<K,VV extends Comparable<VV>> Sends the current vertex value to all adjacent vertices.
static class	ConnectedComponents.CCUpdater<K,VV extends Comparable<VV>> Updates the value of a vertex by picking the minimum neighbor value out of all the incoming messages.

Constructor Summary

Constructors

Constructor and Description
ConnectedComponents(Integer maxIterations) Creates an instance of the Connected Components algorithm.

Method Summary

Modifier and Type	Method and Description
DataSet<Vertex<K,VV>>	run(Graph<K,VV,EV> graph)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ConnectedComponents

public ConnectedComponents(Integer maxIterations)

Creates an instance of the Connected Components algorithm. The algorithm computes weakly connected components and converges when no vertex updates its component ID or when the maximum number of iterations has been reached.

Parameters:

maxIterations - The maximum number of iterations to run.

Method Detail

run

public DataSet<Vertex<K,VV>> run(Graph<K,VV,EV> graph)
                          throws Exception

Specified by:

run in interface GraphAlgorithm<K,VV extends Comparable<VV>,EV,DataSet<Vertex<K,VV extends Comparable<VV>>>>

Throws:

Exception