Class StronglyConnectedComponents
- java.lang.Object
-
- it.unimi.dsi.big.webgraph.algo.StronglyConnectedComponents
-
public class StronglyConnectedComponents extends java.lang.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 '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 Java. 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()
andsortBySize(long[][])
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.
-
-
Field Summary
Fields Modifier and Type Field Description it.unimi.dsi.bits.LongArrayBitVector
buckets
The bit vector for buckets, ornull
, in which case buckets have not been computed.long[][]
component
The component of each node.long
numberOfComponents
The number of strongly connected components.
-
Constructor Summary
Constructors Modifier Constructor Description protected
StronglyConnectedComponents(long numberOfComponents, long[][] component, it.unimi.dsi.bits.LongArrayBitVector buckets)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description static StronglyConnectedComponents
compute(ImmutableGraph graph, boolean computeBuckets, it.unimi.dsi.logging.ProgressLogger pl)
Computes the strongly connected components of a given graph.static StronglyConnectedComponents
compute(ArcLabelledImmutableGraph graph, Transform.LabelledArcFilter filter, boolean computeBuckets, it.unimi.dsi.logging.ProgressLogger pl)
Computes the strongly connected components of a given arc-labelled graph, filtering its arcs.long[][]
computeSizes()
Returns the size big array for this set of strongly connected components.static void
main(java.lang.String[] arg)
void
sortBySize(long[][] size)
Renumbers by decreasing size the components of this set.
-
-
-
Field Detail
-
numberOfComponents
public final long numberOfComponents
The number of strongly connected components.
-
component
public final long[][] component
The component of each node.
-
buckets
public final it.unimi.dsi.bits.LongArrayBitVector buckets
The bit vector for buckets, ornull
, in which case buckets have not been computed.
-
-
Method Detail
-
compute
public static StronglyConnectedComponents compute(ImmutableGraph graph, boolean computeBuckets, it.unimi.dsi.logging.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, ornull
.- Returns:
- an instance of this class containing the computed components.
-
compute
public static StronglyConnectedComponents compute(ArcLabelledImmutableGraph graph, Transform.LabelledArcFilter filter, boolean computeBuckets, it.unimi.dsi.logging.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, ornull
.- Returns:
- an instance of this class containing the computed components.
-
computeSizes
public long[][] computeSizes()
Returns the size big array for this set of strongly connected components.- Returns:
- the size big array for this set of strongly connected components.
-
sortBySize
public void sortBySize(long[][] 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 big array are permuted so that the sizes of strongly connected components are decreasing in the component index.
- Parameters:
size
- the components sizes, as returned bycomputeSizes()
.
-
main
public static void main(java.lang.String[] arg) throws java.io.IOException, com.martiansoftware.jsap.JSAPException
- Throws:
java.io.IOException
com.martiansoftware.jsap.JSAPException
-
-