com.raphtory.algorithms.generic.ConnectedComponents

ConnectedComponents

ConnectedComponents()

Identify connected components

A connected component of an undirected graph is a set of vertices all of which are connected by paths to each other. This algorithm identifies the connected component each vertex belongs to.

Note

Edges here are treated as undirected, a future feature may be to calculate weakly/strongly connected components for directed networks.

States

cclabel: Long

Label of connected component the vertex belongs to (minimum vertex ID in component)

Returns

vertex name

component label

name: String

cclabel: Long

Implementation

The algorithm is similar to that of GraphX and fairly straightforward:

  1. Each node is numbered by its ID, and takes this as an initial connected components label.

  2. Each node forwards its own label to each of its neighbours.

  3. Having received a list of labels from neighbouring nodes, each node relabels itself with the smallest label it has received (or stays the same if its starting label is smaller than any received).

  4. The algorithm iterates over steps 2 and 3 until no nodes change their label within an iteration.