www.sdmetrics.com

com.sdmetrics.metrics
Class StronglyConnectedComponents<T>

java.lang.Object
  extended by 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
static interface StronglyConnectedComponents.Graph<T>
          Provides the strongly connected components algorithm with the information it requires about the directed graph.
 
Constructor Summary
StronglyConnectedComponents()
           
 
Method Summary
 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.

www.sdmetrics.com