Class BlockCutpointGraph<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, Graph<UndirectedGraph<V,​E>,​DefaultEdge>, UndirectedGraph<UndirectedGraph<V,​E>,​DefaultEdge>

    public class BlockCutpointGraph<V,​E>
    extends SimpleGraph<UndirectedGraph<V,​E>,​DefaultEdge>
    Definition of a block of a graph in MathWorld.
    Definition and lemma taken from the article Structure-Based Resilience Metrics for Service-Oriented Networks:
    • Definition 4.5 Let G(V; E) be a connected undirected graph. The block-cut point graph (BC graph) of G, denoted by GB(VB; EB), is the bipartite graph defined as follows. (a) VB has one node corresponding to each block and one node corresponding to each cut point of G. (b) Each edge fx; yg in EB joins a block node x to a cut point y if the block corresponding to x contains the cut point node corresponding to y.
    • Lemma 4.4 Let G(V; E) be a connected undirected graph. (a) Each pair of blocks of G share at most one node, and that node is a cutpoint. (b) The BC graph of G is a tree in which each leaf node corresponds to a block of G.
    Since:
    July 5, 2007
    See Also:
    Serialized Form
    • Constructor Detail

      • BlockCutpointGraph

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

      • getBlock

        public UndirectedGraph<V,​E> getBlock​(V vertex)
        Returns the vertex if vertex is a cutpoint, and otherwise returns the block (biconnected component) containing the vertex.
        Parameters:
        vertex - vertex in the initial graph.
        Returns:
        the biconnected component containing the vertex
      • getCutpoints

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

        public boolean isCutpoint​(V vertex)
        Returns true if the vertex is a cutpoint, false otherwise.
        Parameters:
        vertex - vertex in the initial graph.
        Returns:
        true if the vertex is a cutpoint, false otherwise.
      • biconnectedComponentFinished

        private void biconnectedComponentFinished​(V s,
                                                  V n)
      • dfsVisit

        private int dfsVisit​(V s,
                             V father)
      • getBiconnectedSubgraphs

        private java.util.Set<UndirectedGraph<V,​E>> getBiconnectedSubgraphs​(V vertex)
        Returns the biconnected components containing the vertex. A vertex which is not a cutpoint is contained in exactly one component. A cutpoint is contained is at least 2 components.
        Parameters:
        vertex - vertex in the initial graph.
      • getNumOrder

        private int getNumOrder​(V vertex)
        Returns the traverse order of the vertex in the DFS.
      • setNumOrder

        private void setNumOrder​(V vertex,
                                 int numOrder)