Class 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 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

      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.
      long[][] computeSizes()
      Returns the size big array for this set of strongly connected components.
      static void main​(java.lang.String[] arg)  
      void sortBySize​(long[][] 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

      • numberOfComponents

        public final long numberOfComponents
        The number of connected components.
      • component

        public final long[][] component
        The component of each node.
    • Constructor Detail

      • ConnectedComponents

        protected ConnectedComponents​(long numberOfComponents,
                                      long[][] component)
    • 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 for Runtime.availableProcessors()).
        pl - a progress logger, or null.
        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 by computeSizes().
      • 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