com.sdmetrics.metrics

Class StronglyConnectedComponents<T>

java.lang.Object

com.sdmetrics.metrics.StronglyConnectedComponents<T>

Type Parameters:

T - Type of the nodes on the graph

public class StronglyConnectedComponents<T>
extends java.lang.Object

Calculates the strongly connected components of a directed graph. The algorithm used to calculate the strongly connected components is not self-explanatory, but is described in most "algorithms and data structures 101" text books. This implementation is based on T. Ottmann, P. Widmayer, "Algorithmen und Datenstukturen", BI Wissenschaftsverlag, 1991, pp. 566-570. The complexity of the algorithm is O(|N|+|E|) (N=set of nodes, E=set of edges).

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	StronglyConnectedComponents.Graph<T> Provides the strongly connected components algorithm with the information it requires about the directed graph.

Constructor Summary

Constructors

Constructor and Description
StronglyConnectedComponents()

Method Summary

Modifier and Type	Method and Description
void	calculateConnectedComponents(StronglyConnectedComponents.Graph<T> inputGraph, int minSize, boolean isoIfSelfref) Calculates the strongly connected components for a graph.
java.util.Collection<T>	getConnectedComponent(int index) Gets the node set for a strongly connected component.
int	getConnectedComponentCount() Gets the number of strongly connected components found.
int	getIndexFor(T node) Gets the index of the strongly connected component of a node.

Methods inherited from class java.lang.Object

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

Constructor Detail

StronglyConnectedComponents

public StronglyConnectedComponents()

Method Detail

getConnectedComponentCount

public int getConnectedComponentCount()

Gets the number of strongly connected components found.

Returns:

The number N of strongly connected components. The components are addressed by an index, valid indices run from 0 to N-1.

getConnectedComponent

public java.util.Collection<T> getConnectedComponent(int index)

Gets the node set for a strongly connected component.

Parameters:

index - Index of the strongly connected component.

Returns:

The nodes of the strongly connected component.

getIndexFor

public int getIndexFor(T node)

Gets the index of the strongly connected component of a node.

Parameters:

node - The node of interest.

Returns:

Index of the strongly connected component that contains the node, or -1 if the node is not part of a strongly connected component.

calculateConnectedComponents

public void calculateConnectedComponents(StronglyConnectedComponents.Graph<T> inputGraph,
                                         int minSize,
                                         boolean isoIfSelfref)
                                  throws SDMetricsException

Calculates the strongly connected components for a graph.

Parameters:

inputGraph - The graph to operate on.

minSize - The minimum size a strongly connected component must have to be reported by the algorithm.

isoIfSelfref - When this is set to true, isolated nodes ("connected components of size one") are reported only if the node has an edge to itself. When set to false, such connected components are always reported. If minSize is greater than one, this parameter is ignored.

Throws:

SDMetricsException - The set of neighbors of a node could not be calculated.