Class ConnectedComponents
- java.lang.Object
-
- it.unimi.dsi.webgraph.algo.ConnectedComponents
-
public class ConnectedComponents extends java.lang.Object
Computes the connected 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 ofParallelBreadthFirstVisit
). Note that it is your responsibility to pass a symmetric graph tocompute(ImmutableGraph, int, ProgressLogger)
. Otherwise, results will be unpredictable.After getting an instance, it is possible to run the
computeSizes()
andsortBySize(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.Furthermore, it is possible to remove all components except the biggest one from a graph, using the function
getLargestComponent(it.unimi.dsi.webgraph.ImmutableGraph, int, it.unimi.dsi.logging.ProgressLogger)
.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 int[]
component
The component of each node.int
numberOfComponents
The number of connected components.
-
Constructor Summary
Constructors Modifier Constructor Description protected
ConnectedComponents(int numberOfComponents, int[] component)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description static ConnectedComponents
compute(ImmutableGraph symGraph, int threads, it.unimi.dsi.logging.ProgressLogger pl)
Computes the connected components of a symmetric graph.int[]
computeSizes()
Returns the size array for this set of connected components.static ImmutableGraph
getLargestComponent(ImmutableGraph symGraph, int threads, it.unimi.dsi.logging.ProgressLogger pl)
Returns the largest connected components of a symmetric graph.static void
main(java.lang.String[] arg)
void
sortBySize(int[] size)
Renumbers by decreasing size the components of this set.
-
-
-
Method Detail
-
compute
public static ConnectedComponents compute(ImmutableGraph symGraph, int threads, it.unimi.dsi.logging.ProgressLogger pl)
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.
-
getLargestComponent
public static ImmutableGraph getLargestComponent(ImmutableGraph symGraph, int threads, it.unimi.dsi.logging.ProgressLogger pl)
Returns the largest 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 ImmutableGraph containing the largest connected component of the input graph.
-
computeSizes
public int[] computeSizes()
Returns the size array for this set of connected components.- Returns:
- the size array for this set of 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 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
-
-