Package com.jgalgo

Interface ConnectedComponentsAlgo

public interface ConnectedComponentsAlgo

Connectivity components algorithm.

Author:

Barak Ugav

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	ConnectedComponentsAlgo.Builder	A builder for ConnectedComponentsAlgo objects.
static interface	ConnectedComponentsAlgo.Result	Result object for connectivity components calculation.

Method Summary

Modifier and Type	Method	Description
ConnectedComponentsAlgo.Result	computeConnectivityComponents(Graph g)	Find all (strongly) connected components in a graph.
ConnectedComponentsAlgo.Result	computeWeaklyConnectivityComponents(Graph g)	Compute all weakly connected components in a directed graph.
static ConnectedComponentsAlgo.Builder	newBuilder()	Create a new connectivity algorithm builder.

Method Detail

computeConnectivityComponents

ConnectedComponentsAlgo.Result computeConnectivityComponents(Graph g)

Find all (strongly) connected components in a graph.

A (strongly) connected component is a maximal set of vertices for which for any pair of vertices \(u, v\) in the set there exist a path from \(u\) to \(v\) and from \(v\) to \(u\).

Parameters:

g - a graph

Returns:

a result object containing the partition of the vertices into (strongly) connected components

computeWeaklyConnectivityComponents

ConnectedComponentsAlgo.Result computeWeaklyConnectivityComponents(Graph g)

Compute all weakly connected components in a directed graph.

Given a directed graph, if we replace all the directed edges with undirected edges and compute the (strong) connected components in the result undirected graph.

Parameters:

g - a graph

Returns:

a result object containing the partition of the vertices into weakly connected components

newBuilder

static ConnectedComponentsAlgo.Builder newBuilder()

Create a new connectivity algorithm builder.

This is the recommended way to instantiate a new ConnectedComponentsAlgo object.

Returns:

a new builder that can build ConnectedComponentsAlgo objects