net.automatalib.util.graphs.scc

Class SCCs

java.lang.Object

net.automatalib.util.graphs.scc.SCCs

@ParametersAreNonnullByDefault
public final class SCCs
extends Object

Algorithms for finding strongly-connected components (SCCs) in a graph.

Author:

Malte Isberner

Method Summary

Modifier and Type	Method and Description
static <N,E> List<List<N>>	collectSCCs(Graph<N,E> graph) Collects all strongly-connected components in a graph.
static <N,E> void	findSCCs(Graph<N,E> graph, SCCListener<N> listener) Find all strongly-connected components in a graph.

Methods inherited from class java.lang.Object

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

Method Detail

collectSCCs

@Nonnull
public static <N,E> List<List<N>> collectSCCs(Graph<N,E> graph)

Collects all strongly-connected components in a graph. The SCCs are returned as a list of lists.

Tarjan's algorithm is used for realizing the SCC search.

Parameters:

graph - the graph

Returns:

a list of all SCCs, each represented as a list of its nodes

See Also:

TarjanSCCVisitor

findSCCs

public static <N,E> void findSCCs(Graph<N,E> graph,
                                  SCCListener<N> listener)

Find all strongly-connected components in a graph. When a new SCC is found, the SCCListener.foundSCC(java.util.Collection) method is invoked. The listener object may hence not be null.

Tarjan's algorithm is used for realizing the SCC search.

Parameters:

graph - the graph

listener - the SCC listener

See Also:

TarjanSCCVisitor