it.unimi.dsi.webgraph.algo
Class StronglyConnectedComponents

java.lang.Object
  extended by it.unimi.dsi.webgraph.algo.StronglyConnectedComponents

public class StronglyConnectedComponents
extends Object

Computes the strongly connected components (and optionally the buckets) of an immutable graph.

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. 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.

Stack size

The method compute(ImmutableGraph, boolean, ProgressLogger) might require a large stack size, that should be set using suitable JVM options. Note, however, that the stack size must be enlarged also on the operating-system side—for instance, using ulimit -s unlimited.


Field Summary
 BitSet buckets
          The bit set 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.
 
Constructor Summary
protected StronglyConnectedComponents(int numberOfComponents, int[] component, BitSet buckets)
           
 
Method Summary
static StronglyConnectedComponents compute(ArcLabelledImmutableGraph graph, Transform.LabelledArcFilter filter, boolean computeBuckets, ProgressLogger pl)
          Computes the strongly connected components of a given arc-labelled 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(String[] arg)
           
 void sortBySize(int[] size)
          Renumbers by decreasing size the components of this set.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

numberOfComponents

public final int numberOfComponents
The number of strongly connected components.


component

public final int[] component
The component of each node.


buckets

public final BitSet buckets
The bit set for buckets, or null, in which case buckets have not been computed.

Constructor Detail

StronglyConnectedComponents

protected StronglyConnectedComponents(int numberOfComponents,
                                      int[] component,
                                      BitSet buckets)
Method Detail

compute

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

Parameters:
graph - the graph whose strongly connected components are to be computed.
computeBuckets - if true, buckets will be computed.
pl - a progress logger, or null.
Returns:
an instance of this class containing the computed components.

compute

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

Parameters:
graph - the arc-labelled 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.
Returns:
an instance of this class containing the computed components.

computeSizes

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

Returns:
the size array for this set of strongly connected components.

sortBySize

public void sortBySize(int[] size)
Renumbers by decreasing size the components of this set.

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.

Parameters:
size - the components sizes, as returned by computeSizes().

main

public static void main(String[] arg)
                 throws IOException,
                        JSAPException
Throws:
IOException
JSAPException