Class BlockCutpointGraph<V,​E>

  • 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
    Author:
    Guillaume Boulmier
    See Also:
    Serialized Form
    • Constructor Detail

      • BlockCutpointGraph

        public BlockCutpointGraph​(UndirectedGraph<V,​E> graph)
        Running time = O(m) where m is the number of edges.
    • 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.
      • getCutpoints

        public java.util.Set<V> getCutpoints()
        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.