Package com.jgalgo.alg.connect

Class StronglyConnectedComponentsAlgoAbstract

java.lang.Object

com.jgalgo.alg.connect.StronglyConnectedComponentsAlgoAbstract

All Implemented Interfaces:

StronglyConnectedComponentsAlgo

Direct Known Subclasses:

StronglyConnectedComponentsPathBasedDfs, StronglyConnectedComponentsTarjan

public abstract class StronglyConnectedComponentsAlgoAbstract
extends Object
implements StronglyConnectedComponentsAlgo

Abstract class for computing strongly connected components in a graph.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Constructor Summary

Constructors

Constructor	Description
StronglyConnectedComponentsAlgoAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<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.

Methods inherited from class java.lang.Object

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

Constructor Detail

StronglyConnectedComponentsAlgoAbstract

public StronglyConnectedComponentsAlgoAbstract()

Default constructor.

Method Detail

findStronglyConnectedComponents

public <V,E> VertexPartition<V,E> findStronglyConnectedComponents(Graph<V,E> g)

Description copied from interface: StronglyConnectedComponentsAlgo

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.

Specified by:

findStronglyConnectedComponents in interface StronglyConnectedComponentsAlgo

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

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

Description copied from interface: StronglyConnectedComponentsAlgo

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.

Specified by:

isStronglyConnected in interface StronglyConnectedComponentsAlgo

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

Returns:

true if the graph is strongly connected, false otherwise