Package org.jgrapht.alg.connectivity

Class BiconnectivityInspector<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    public class BiconnectivityInspector<V,​E>
extends Object
    Allows obtaining various connectivity aspects of a graph. The inspected graph is specified at construction time and cannot be modified. No restrictions are imposed on the input graph. Multigraphs and pseudographs are also supported. The inspector traverses connected components (undirected graphs) or weakly connected components (directed graphs). To find strongly connected components, use KosarajuStrongConnectivityInspector instead. This class offers an alternative implementation of some of the functionality encountered in ConnectivityInspector. It is likely to perform somewhat slower than ConnectivityInspector, but offers more functionality in return.

    The algorithm implemented in this class is Hopcroft and Tarjan's biconnected components algorithm, described in: Hopcroft, J. Tarjan, R. Algorithm 447: efficient algorithms for graph manipulation, 1973. Communications of the ACM. 16 (6): 372–378. This implementation runs in linear time $O(|V|+|E|)$ and is based on a recursive depth-first search. More information about this subject be be found in this wikipedia article.

    The inspector methods work in a lazy fashion: no computations are performed unless immediately necessary. Computation are done once and results are cached within this class for future need. The core of this class is built around a recursive Depth-first search.

    Author:
    Joris Kinable

    • Constructor Detail

      • BiconnectivityInspector

        public BiconnectivityInspector​(Graph<V,​E> graph)
        Constructs a new BiconnectivityInspector
        Parameters:
        graph - the input graph

    • Method Detail

      • getCutpoints

        public Set<V> getCutpoints()
        Returns the cutpoints (articulation points) of the graph. A vertex is a cutpoint if removal of that vertex (and all edges incident to that vertex) would increase the number of (weakly) connected components in the graph.
        Returns:
        the cutpoints of the graph

      • getBridges

        public Set<E> getBridges()
        Returns the graph's bridges. An edge is a bridge if removal of that edge would increase the number of (weakly) connected components in the graph. Note that this definition remains applicable in case of multigraphs or pseudographs.
        Returns:
        the graph's bridges

      • getBlocks

        public Set<Graph<V,​E>> getBlocks​(V vertex)
        Returns a set of blocks (biconnected components) containing the specified vertex. A block is a maximal biconnected subgraph. Each non-cutpoint resides in at most one block. Each cutpoint resides in at least two blocks.
        Parameters:
        vertex - vertex in the initial graph.
        Returns:
        the blocks containing the given vertex

      • getBlocks

        public Set<Graph<V,​E>> getBlocks()
        Returns all blocks (biconnected components) in the graph. A block is a maximal biconnected subgraph.
        Returns:
        all blocks (biconnected components) in the graph.

      • getConnectedComponents

        public Set<Graph<V,​E>> getConnectedComponents()
        Returns all connected components in the graph. In case the graph is directed, this method returns all weakly connected components.
        Returns:
        all connected components in the graph if the graph is undirected, or all weakly connected components if the graph is directed.

      • getConnectedComponent

        public Graph<V,​E> getConnectedComponent​(V vertex)
        Returns the connected component containing the given vertex. If the underlying graph is directed, this method returns a weakly connected component.
        Parameters:
        vertex - vertex
        Returns:
        the connected component containing the given vertex, or a weakly connected component if the underlying graph is directed.

      • isBiconnected

        public boolean isBiconnected()
        Tests if the inspected graph is biconnected. A biconnected graph is a connected graph on two or more vertices having no cutpoints.
        Returns:
        true if the graph is biconnected, false otherwise

      • isConnected

        public boolean isConnected()
        Test if the inspected graph is connected. A graph is connected when, while ignoring edge directionality, there exists a path between every pair of vertices. In a connected graph, there are no unreachable vertices. When the inspected graph is a directed graph, this method returns true if and only if the inspected graph is weakly connected. An empty graph is not considered connected.
        Returns:
        true if and only if inspected graph is connected.