org.jgrapht.alg

Class BlockCutpointGraph<V,E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type
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
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 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.