Package org.jgrapht.alg

Class BlockCutpointGraph<V,E>

java.lang.Object
org.jgrapht.graph.AbstractGraph<UndirectedGraph<V,E>,DefaultEdge>
org.jgrapht.graph.AbstractBaseGraph<UndirectedGraph<V,E>,DefaultEdge>
org.jgrapht.graph.SimpleGraph<UndirectedGraph<V,E>,DefaultEdge>
org.jgrapht.alg.BlockCutpointGraph<V,E>
All Implemented Interfaces:
Serializable, 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:

  • Constructor Details

    • BlockCutpointGraph

      public BlockCutpointGraph(UndirectedGraph<V,E> graph)
      Running time = O(m) where m is the number of edges.

  • Method Details

    • 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 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.