public class StronglyConnectedComponents
extends java.lang.Object
The compute(ImmutableGraph, boolean, ProgressLogger)
method of this class will return
an instance that contains the data computed by running a variant of Tarjan's algorithm on an immutable graph.
The implementation is iterative, rather than recursive, to work around known limitations on the size of
the stack in current JVMs.
Besides the usually strongly connected components, it is possible to compute the buckets of the
graph, that is, nodes belonging to components that are terminal, but not dangling, in the component DAG.
After getting an instance, it is possible to run the computeSizes()
and sortBySize(int[])
methods to obtain further information. This scheme has been devised to exploit the available memory as much
as possible—after the components have been computed, the returned instance keeps no track of
the graph, and the related memory can be freed by the garbage collector.
Modifier and Type  Field and Description 

LongArrayBitVector 
buckets
The bit vector for buckets, or
null , in which case buckets have not been computed. 
int[] 
component
The component of each node.

int 
numberOfComponents
The number of strongly connected components.

Modifier  Constructor and Description 

protected 
StronglyConnectedComponents(int numberOfComponents,
int[] status,
LongArrayBitVector buckets) 
Modifier and Type  Method and Description 

static StronglyConnectedComponents 
compute(ArcLabelledImmutableGraph graph,
Transform.LabelledArcFilter filter,
boolean computeBuckets,
ProgressLogger pl)
Computes the strongly connected components of a given arclabelled graph, filtering its arcs.

static StronglyConnectedComponents 
compute(ImmutableGraph graph,
boolean computeBuckets,
ProgressLogger pl)
Computes the strongly connected components of a given graph.

int[] 
computeSizes()
Returns the size array for this set of strongly connected components.

static void 
main(java.lang.String[] arg) 
void 
sortBySize(int[] size)
Renumbers by decreasing size the components of this set.

public final int numberOfComponents
public final int[] component
public final LongArrayBitVector buckets
null
, in which case buckets have not been computed.protected StronglyConnectedComponents(int numberOfComponents, int[] status, LongArrayBitVector buckets)
public static StronglyConnectedComponents compute(ImmutableGraph graph, boolean computeBuckets, ProgressLogger pl)
graph
 the graph whose strongly connected components are to be computed.computeBuckets
 if true, buckets will be computed.pl
 a progress logger, or null
.public static StronglyConnectedComponents compute(ArcLabelledImmutableGraph graph, Transform.LabelledArcFilter filter, boolean computeBuckets, ProgressLogger pl)
graph
 the arclabelled graph whose strongly connected components are to be computed.filter
 a filter selecting the arcs that must be taken into consideration.computeBuckets
 if true, buckets will be computed.pl
 a progress logger, or null
.public int[] computeSizes()
public void sortBySize(int[] size)
After a call to this method, both the internal status of this class and the argument array are permuted so that the sizes of strongly connected components are decreasing in the component index.
size
 the components sizes, as returned by computeSizes()
.public static void main(java.lang.String[] arg) throws java.io.IOException, JSAPException
java.io.IOException
JSAPException