org.apache.flink.examples.java.graph

Class ConnectedComponents

java.lang.Object

org.apache.flink.examples.java.graph.ConnectedComponents

All Implemented Interfaces:

ProgramDescription

public class ConnectedComponents
extends Object
implements ProgramDescription

An implementation of the connected components algorithm, using a delta iteration.

Initially, the algorithm assigns each vertex an unique ID. In each step, a vertex picks the minimum of its own ID and its neighbors' IDs, as its new ID and tells its neighbors about its new ID. After the algorithm has completed, all vertices in the same component will have the same ID.

A vertex whose component ID did not change needs not propagate its information in the next step. Because of that, the algorithm is easily expressible via a delta iteration. We here model the solution set as the vertices with their current component ids, and the workset as the changed vertices. Because we see all vertices initially as changed, the initial workset and the initial solution set are identical. Also, the delta to the solution set is consequently also the next workset.

Input files are plain text files and must be formatted as follows:

• Vertices represented as IDs and separated by new-line characters.
  For example "1\n2\n12\n42\n63" gives five vertices (1), (2), (12), (42), and (63).
• Edges are represented as pairs for vertex IDs which are separated by space characters. Edges are separated by new-line characters.
  For example "1 2\n2 12\n1 12\n42 63" gives four (undirected) edges (1)-(2), (2)-(12), (1)-(12), and (42)-(63).

Usage: ConnectedComponents --vertices <path> --edges <path> --output <path> --iterations <n>
If no parameters are provided, the program is run with default data from ConnectedComponentsData and 10 iterations.

This example shows how to use:

• Delta Iterations
• Generic-typed Functions

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	ConnectedComponents.ComponentIdFilter
static class	ConnectedComponents.DuplicateValue<T> Function that turns a value into a 2-tuple where both fields are that value.
static class	ConnectedComponents.NeighborWithComponentIDJoin UDF that joins a (Vertex-ID, Component-ID) pair that represents the current component that a vertex is associated with, with a (Source-Vertex-ID, Target-VertexID) edge.
static class	ConnectedComponents.UndirectEdge Undirected edges by emitting for each input edge the input edges itself and an inverted version.

Constructor Summary

Constructors

Constructor and Description
ConnectedComponents()

Method Summary

Modifier and Type	Method and Description
String	getDescription() Returns a description of the plan that is generated by the assembler and also of the arguments if they are available.
static void	main(String... args)

Methods inherited from class java.lang.Object

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

Constructor Detail

ConnectedComponents

public ConnectedComponents()

Method Detail

main

public static void main(String... args)
                 throws Exception

Throws:

Exception

getDescription

public String getDescription()

Description copied from interface: ProgramDescription

Returns a description of the plan that is generated by the assembler and also of the arguments if they are available. The description should be simple text as it may be rendered in different environments (console, web interface, ...). Typical things that should be included are:

• expected input format
• description of output
• description of what is done
• description of arguments to customize plan if available

Specified by:

getDescription in interface ProgramDescription

Returns:

A description of the program and of its arguments if available.