Package it.unimi.dsi.webgraph.algo

Class ConnectedComponents

java.lang.Object

it.unimi.dsi.webgraph.algo.ConnectedComponents

public class ConnectedComponents
extends 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 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.

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

Modifier and Type	Method	Description
static ConnectedComponents	compute(ImmutableGraph symGraph, int threads, 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, ProgressLogger pl)	Returns the largest connected components of a symmetric graph.
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 Details

numberOfComponents

public final int numberOfComponents

The number of connected components.

component

public final int[] component

The component of each node.

Constructor Details

ConnectedComponents

protected ConnectedComponents(int numberOfComponents,
int[] component)

Method Details

compute

public static ConnectedComponents compute(ImmutableGraph symGraph,
int threads,
ProgressLogger pl)

Computes the connected components of a symmetric graph.

Parameters:

symGraph - a symmetric graph.

threads - the requested number of threads (0 for Runtime.availableProcessors()).

pl - a progress logger, or null.

Returns:

an instance of this class containing the computed components.

getLargestComponent

public static ImmutableGraph getLargestComponent(ImmutableGraph symGraph,
int threads,
ProgressLogger pl)

Returns the largest connected components of a symmetric graph.

Parameters:

symGraph - a symmetric graph.

threads - the requested number of threads (0 for Runtime.availableProcessors()).

pl - a progress logger, or null.

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 by computeSizes().

main

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

Throws:

IOException

JSAPException