|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.unimi.dsi.webgraph.algo.ConnectedComponents
public class ConnectedComponents
Computes the conneted components of a symmetric (a.k.a. undirected) graph using a parallel breadth-first visit.
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(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.
This class uses an instance of ParallelBreadthFirstVisit
to ensure a high degree of
parallelism (see its documentation for memory requirements).
Field Summary | |
---|---|
int[] |
component
The component of each node. |
int |
numberOfComponents
The number of connected components. |
Constructor Summary | |
---|---|
protected |
ConnectedComponents(int numberOfComponents,
int[] component)
|
Method Summary | |
---|---|
static ConnectedComponents |
compute(ImmutableGraph symGraph,
int threads,
ProgressLogger pl)
Computes the diameter of a symmetric graph. |
int[] |
computeSizes()
Returns the size array for this set of 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 |
---|
public final int numberOfComponents
public final int[] component
Constructor Detail |
---|
protected ConnectedComponents(int numberOfComponents, int[] component)
Method Detail |
---|
public static ConnectedComponents compute(ImmutableGraph symGraph, int threads, ProgressLogger pl)
symGraph
- a symmetric graph.threads
- the requested number of threads (0 for Runtime.availableProcessors()
).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 connected components are decreasing in the component index.
size
- the components sizes, as returned by computeSizes()
.public static void main(String[] arg) throws IOException, JSAPException
IOException
JSAPException
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |