The {@link #compute(ImmutableGraph, int, ProgressLogger)} method of this class will return an * instance that contains the data computed by visiting the graph (loaded offline). * *
After getting an instance, it is possible to run the {@link #computeSizes()} and
* {@link #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.
*/
public class ConnectedComponents {
private static final Logger LOGGER = LoggerFactory.getLogger( ConnectedComponents.class );
/** The number of connected components. */
public final int numberOfComponents;
/** The component of each node. */
public final int component[];
protected ConnectedComponents( final int numberOfComponents, final int[] component ) {
this.numberOfComponents = numberOfComponents;
this.component = component;
}
/**
* Computes the diameter of a symmetric graph.
*
* @param symGraph a symmetric graph.
* @param pl a progress logger, or null.
* @return an instance of this class containing the computed components.
*/
public static ConnectedComponents compute( final ImmutableGraph g, final ProgressLogger pl ) {
DisjointSet set = new DisjointSet(g.numNodes());
LOGGER.info("Computing CCs...");
pl.start("Processing " + g.numNodes() + " nodes...");
pl.expectedUpdates = g.numNodes();
pl.itemsName = "nodes";
NodeIterator nIter = g.nodeIterator();
while (nIter.hasNext()) {
int u = nIter.nextInt();
LazyIntIterator eIter = nIter.successors();
int v = 0;
while ((v = eIter.nextInt()) != -1) {
set.unionSet(u, v);
}
pl.update();
}
pl.done();
int ccid = 0;
final int[] component = new int[ g.numNodes() ];
for ( int i = component.length; i-- != 0; )
component[ i ] = -1;
for ( int i = component.length; i-- != 0; ) {
if (component[ set.findSet(i) ] == -1)
component[ set.findSet(i) ] = ccid++;
component[ i ] = component[ set.findSet(i) ];
}
return new ConnectedComponents( ccid, component );
}
/**
* Returns the size array for this set of connected components.
*
* @return the size array for this set of connected components.
*/
public int[] computeSizes() {
final int[] size = new int[ numberOfComponents ];
for ( int i = component.length; i-- != 0; )
size[ component[ i ] ]++;
return 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. * * @param size the components sizes, as returned by {@link #computeSizes()}. */ public void sortBySize( final int[] size ) { final int[] perm = Util.identity( size.length ); IntArrays.quickSort( perm, 0, perm.length, new AbstractIntComparator() { public int compare( final int x, final int y ) { return size[ y ] - size[ x ]; } } ); final int[] copy = size.clone(); for ( int i = size.length; i-- != 0; ) size[ i ] = copy[ perm[ i ] ]; Util.invertPermutationInPlace( perm ); for ( int i = component.length; i-- != 0; ) component[ i ] = perm[ component[ i ] ]; } public static void main( String arg[] ) throws IOException, JSAPException { SimpleJSAP jsap = new SimpleJSAP( ConnectedComponents.class.getName(), "Computes the connected components of a symmetric graph of given basename. The resulting data is saved " + "in files stemmed from the given basename with extension .scc (a list of binary integers specifying the " + "component of each node) and .sccsizes (a list of binary integer specifying the size of each component).", new Parameter[] { new Switch( "sizes", 's', "sizes", "Compute component sizes." ), new Switch( "renumber", 'r', "renumber", "Renumber components in decreasing-size order." ), new FlaggedOption( "logInterval", JSAP.LONG_PARSER, Long.toString( ProgressLogger.DEFAULT_LOG_INTERVAL ), JSAP.NOT_REQUIRED, 'l', "log-interval", "The minimum time interval between activity logs in milliseconds." ), new UnflaggedOption( "basename", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, JSAP.NOT_GREEDY, "The basename of the graph." ), new UnflaggedOption( "resultsBasename", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.NOT_REQUIRED, JSAP.NOT_GREEDY, "The basename of the resulting files." ), } ); JSAPResult jsapResult = jsap.parse( arg ); if ( jsap.messagePrinted() ) System.exit( 1 ); final String basename = jsapResult.getString( "basename" ); final String resultsBasename = jsapResult.getString( "resultsBasename", basename ); ProgressLogger pl = new ProgressLogger( LOGGER, jsapResult.getLong( "logInterval" ), TimeUnit.MILLISECONDS ); final ConnectedComponents components = ConnectedComponents.compute( ImmutableGraph.loadOffline( basename ), pl ); if ( jsapResult.getBoolean( "sizes" ) || jsapResult.getBoolean( "renumber" ) ) { final int size[] = components.computeSizes(); if ( jsapResult.getBoolean( "renumber" ) ) components.sortBySize( size ); if ( jsapResult.getBoolean( "sizes" ) ) BinIO.storeInts( size, resultsBasename + ".sccsizes" ); } BinIO.storeInts( components.component, resultsBasename + ".scc" ); } }