Class BiconnectivityInspector<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    public class BiconnectivityInspector<V,​E>
    extends java.lang.Object
    Inspects a graph for the biconnectivity property. See BlockCutpointGraph for more information. A biconnected graph has only one block (i.e. no cutpoints).
    Since:
    July 5, 2007
    • Constructor Detail

      • BiconnectivityInspector

        public BiconnectivityInspector​(UndirectedGraph<V,​E> graph)
        Running time = O(m) where m is the number of edges.
        Parameters:
        graph - the input graph
    • Method Detail

      • getBiconnectedVertexComponents

        public java.util.Set<java.util.Set<V>> getBiconnectedVertexComponents()
        Returns the biconnected vertex-components of the graph.
        Returns:
        the biconnected vertec-components of the graph
      • getBiconnectedVertexComponents

        public java.util.Set<java.util.Set<V>> getBiconnectedVertexComponents​(V vertex)
        Returns the biconnected vertex-components containing the vertex. A biconnected vertex-component contains all the vertices in the component. A vertex which is not a cutpoint is contained in exactly one component. A cutpoint is contained is at least 2 components.
        Parameters:
        vertex - the input vertex
        Returns:
        set of all biconnected vertex-components containing the vertex.
      • getCutpoints

        public java.util.Set<V> getCutpoints()
        Returns the cutpoints of the graph.
        Returns:
        the cutpoints
      • isBiconnected

        public boolean isBiconnected()
        Returns true if the graph is biconnected (no cutpoint), false otherwise.
        Returns:
        true if the graph is biconnected, false otherwise