org.apache.flink.graph.library

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

java.lang.Object

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

All Implemented Interfaces:

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

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

A gather-sum-apply implementation of the Weakly Connected Components algorithm.

This implementation uses a comparable vertex value as initial component identifier (ID). In the gather phase, each vertex collects the vertex value of their adjacent vertices. In the sum phase, the minimum among those values is selected. In the apply phase, the algorithm sets the minimum value as the new vertex value if it is smaller than the current value.

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:

ConnectedComponents

Constructor Summary

Constructors

Constructor and Description
GSAConnectedComponents(Integer maxIterations) Creates an instance of the GSA 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

GSAConnectedComponents

public GSAConnectedComponents(Integer maxIterations)

Creates an instance of the GSA 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