Class ConnectedComponents
public class ConnectedComponents extends Object
The compute(ImmutableGraph, int, ProgressLogger)
method of this class will return an
instance that contains the data computed by visiting the graph (using an instance of
ParallelBreadthFirstVisit
). Note that it is your responsibility to pass a symmetric graph
to compute(ImmutableGraph, int, ProgressLogger)
. Otherwise, results will be
unpredictable.
After getting an instance, it is possible to run the computeSizes()
and
sortBySize(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.
Performance issues
This class uses an instance of ParallelBreadthFirstVisit
to ensure a high degree of
parallelism (see its documentation for memory requirements).

Field Summary
Fields Modifier and Type Field Description long[][]
component
The component of each node.long
numberOfComponents
The number of connected components. 
Constructor Summary
Constructors Modifier Constructor Description protected
ConnectedComponents(long numberOfComponents, long[][] component)

Method Summary
Modifier and Type Method Description static ConnectedComponents
compute(ImmutableGraph symGraph, int threads, ProgressLogger pl)
Computes the connected components of a symmetric graph.long[][]
computeSizes()
Returns the size big array for this set of strongly connected components.static void
main(String[] arg)
void
sortBySize(long[][] size)
Renumbers by decreasing size the components of this set.

Field Details

numberOfComponents
public final long numberOfComponentsThe number of connected components. 
component
public final long[][] componentThe component of each node.


Constructor Details

ConnectedComponents
protected ConnectedComponents(long numberOfComponents, long[][] component)


Method Details

compute
Computes the connected components of a symmetric graph. Parameters:
symGraph
 a symmetric graph.threads
 the requested number of threads (0 forRuntime.availableProcessors()
).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
 Throws:
IOException
JSAPException
