Class BiconnectivityInspector<V,​E>


  • 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
    Author:
    Guillaume Boulmier
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.Set<java.util.Set<V>> getBiconnectedVertexComponents()
      Returns the biconnected vertex-components of the graph.
      java.util.Set<java.util.Set<V>> getBiconnectedVertexComponents​(V vertex)
      Returns the biconnected vertex-components containing the vertex.
      java.util.Set<V> getCutpoints()
      Returns the cutpoints of the graph.
      boolean isBiconnected()
      Returns true if the graph is biconnected (no cutpoint), false otherwise.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • BiconnectivityInspector

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

      • getBiconnectedVertexComponents

        public java.util.Set<java.util.Set<V>> getBiconnectedVertexComponents()
        Returns the biconnected vertex-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 -
        Returns:
        set of all biconnected vertex-components containing the vertex.
      • getCutpoints

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

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