Class BicomponentClusterer<V,​E>

  • All Implemented Interfaces:
    com.google.common.base.Function<UndirectedGraph<V,​E>,​java.util.Set<java.util.Set<V>>>, java.util.function.Function<UndirectedGraph<V,​E>,​java.util.Set<java.util.Set<V>>>

    public class BicomponentClusterer<V,​E>
    extends java.lang.Object
    implements com.google.common.base.Function<UndirectedGraph<V,​E>,​java.util.Set<java.util.Set<V>>>
    Finds all biconnected components (bicomponents) of an undirected graph. A graph is a biconnected component if at least 2 vertices must be removed in order to disconnect the graph. (Graphs consisting of one vertex, or of two connected vertices, are also biconnected.) Biconnected components of three or more vertices have the property that every pair of vertices in the component are connected by two or more vertex-disjoint paths.

    Running time: O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges

    See Also:
    "Depth first search and linear graph algorithms by R. E. Tarjan (1972), SIAM J. Comp."
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected int converse_depth  
      protected java.util.Map<V,​java.lang.Number> dfs_num  
      protected java.util.Map<V,​java.lang.Number> high  
      protected java.util.Map<V,​V> parents  
      protected java.util.Stack<E> stack  
    • Constructor Summary

      Constructors 
      Constructor Description
      BicomponentClusterer()
      Constructs a new bicomponent finder
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.Set<java.util.Set<V>> apply​(UndirectedGraph<V,​E> theGraph)
      Extracts the bicomponents from the graph.
      protected void findBiconnectedComponents​(UndirectedGraph<V,​E> g, V v, java.util.Set<java.util.Set<V>> bicomponents)
      Stores, in bicomponents, all the biconnected components that are reachable from v.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
      • Methods inherited from interface com.google.common.base.Function

        equals
      • Methods inherited from interface java.util.function.Function

        andThen, compose
    • Field Detail

      • dfs_num

        protected java.util.Map<V,​java.lang.Number> dfs_num
      • high

        protected java.util.Map<V,​java.lang.Number> high
      • parents

        protected java.util.Map<V,​V> parents
      • stack

        protected java.util.Stack<E> stack
      • converse_depth

        protected int converse_depth
    • Constructor Detail

      • BicomponentClusterer

        public BicomponentClusterer()
        Constructs a new bicomponent finder
    • Method Detail

      • apply

        public java.util.Set<java.util.Set<V>> apply​(UndirectedGraph<V,​E> theGraph)
        Extracts the bicomponents from the graph.
        Specified by:
        apply in interface com.google.common.base.Function<V,​E>
        Specified by:
        apply in interface java.util.function.Function<V,​E>
        Parameters:
        theGraph - the graph whose bicomponents are to be extracted
        Returns:
        the ClusterSet of bicomponents
      • findBiconnectedComponents

        protected void findBiconnectedComponents​(UndirectedGraph<V,​E> g,
                                                 V v,
                                                 java.util.Set<java.util.Set<V>> bicomponents)

        Stores, in bicomponents, all the biconnected components that are reachable from v.

        The algorithm basically proceeds as follows: do a depth-first traversal starting from v, marking each vertex with a value that indicates the order in which it was encountered (dfs_num), and with a value that indicates the highest point in the DFS tree that is known to be reachable from this vertex using non-DFS edges (high). (Since it is measured on non-DFS edges, "high" tells you how far back in the DFS tree you can reach by two distinct paths, hence biconnectivity.) Each time a new vertex w is encountered, push the edge just traversed on a stack, and call this method recursively. If w.high is no greater than v.dfs_num, then the contents of the stack down to (v,w) is a biconnected component (and v is an articulation point, that is, a component boundary). In either case, set v.high to max(v.high, w.high), and continue. If w has already been encountered but is not v's parent, set v.high max(v.high, w.dfs_num) and continue.

        (In case anyone cares, the version of this algorithm on p. 224 of Udi Manber's "Introduction to Algorithms: A Creative Approach" seems to be wrong: the stack should be initialized outside this method, (v,w) should only be put on the stack if w hasn't been seen already, and there's no real benefit to putting v on the stack separately: just check for (v,w) on the stack rather than v. Had I known this, I could have saved myself a few days. JRTOM)

        Parameters:
        g - the graph to check for biconnected components
        v - the starting place for searching for biconnected components
        bicomponents - storage for the biconnected components found by this algorithm