Package com.jgalgo.alg

Interface StronglyConnectedComponentsAlgo

public interface StronglyConnectedComponentsAlgo

Strongly Connected components algorithm.

Given a graph \(G=(V,E)\), two vertices \(u,v \in V\) are strongly connected if there is a path from \(u\) to \(v\) and from \(v\) to \(u\). A strongly connected component is a maximal set of vertices that each pair in the set is strongly connected. This definition hold for both directed and undirected graphs. For undirected graphs, the strongly and weakly connected components are identical. The set of vertices \(V\) can be partitioned into disjoint strongly connected components.

The blocks graph of a strongly connected components partition is a directed acyclic graph, where each vertex is a strongly connected component, and there is an edge from \(B_1\) to \(B_2\) if there is an edge \((u, v)\) in \(G\) such that \(u \in B_1\) and \(v \in B_2\). This blocks graph is sometimes called the condensation of \(G\).

Use newInstance() to get a default implementation of this interface. A builder obtained via builder() may support different options to obtain different implementations.

Author:

Barak Ugav

See Also:

WeaklyConnectedComponentsAlgo, BiConnectedComponentsAlgo, KVertexConnectedComponentsAlgo

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	StronglyConnectedComponentsAlgo.Builder	A builder for StronglyConnectedComponentsAlgo objects.

Method Summary

Modifier and Type	Method	Description
static StronglyConnectedComponentsAlgo.Builder	builder()	Create a new strongly connected algorithm builder.
<V,E> VertexPartition<V,E>	findStronglyConnectedComponents(Graph<V,E> g)	Find all strongly connected components in a graph.
<V,E> boolean	isStronglyConnected(Graph<V,E> g)	Check whether a graph is strongly connected.
static StronglyConnectedComponentsAlgo	newInstance()	Create a new strongly connected components algorithm object.

Method Detail

findStronglyConnectedComponents

<V,E> VertexPartition<V,E> findStronglyConnectedComponents(Graph<V,E> 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\).

If g is IntGraph, the returned object is IVertexPartition.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

Returns:

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

isStronglyConnected

<V,E> boolean isStronglyConnected(Graph<V,E> g)

Check whether a graph is strongly connected.

A graph is strongly connected if there is a path from any vertex to any other vertex. Namely if the the whole graph is a single strongly connected component.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

Returns:

true if the graph is strongly connected, false otherwise

newInstance

static StronglyConnectedComponentsAlgo newInstance()

Create a new strongly connected components algorithm object.

This is the recommended way to instantiate a new StronglyConnectedComponentsAlgo object. The StronglyConnectedComponentsAlgo.Builder might support different options to obtain different implementations.

Returns:

a default implementation of StronglyConnectedComponentsAlgo

builder

static StronglyConnectedComponentsAlgo.Builder builder()

Create a new strongly connected algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build StronglyConnectedComponentsAlgo objects