org.jgrapht.alg

Class BlockCutpointGraph<V,E>

java.lang.Object

org.jgrapht.graph.AbstractGraph<V,E>

org.jgrapht.graph.AbstractBaseGraph<V,E>

org.jgrapht.graph.SimpleGraph<UndirectedGraph<V,E>,DefaultEdge>

org.jgrapht.alg.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

See Also:

Serialized Form

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
UndirectedGraph<V,E>	getBlock(V vertex) Returns the vertex if vertex is a cutpoint, and otherwise returns the block (biconnected component) containing the vertex.
Set<V>	getCutpoints() Returns the cutpoints of the initial graph.
boolean	isCutpoint(V vertex) Returns true if the vertex is a cutpoint, false otherwise.

Methods inherited from class org.jgrapht.graph.SimpleGraph

builder, builder

Methods inherited from class org.jgrapht.graph.AbstractBaseGraph

addEdge, addEdge, addVertex, clone, containsEdge, containsVertex, createDirectedSpecifics, createSpecifics, createUndirectedSpecifics, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeFactory, getEdgeSource, getEdgeTarget, getEdgeWeight, incomingEdgesOf, inDegreeOf, isAllowingLoops, isAllowingMultipleEdges, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, removeVertex, setEdgeWeight, vertexSet

Methods inherited from class org.jgrapht.graph.AbstractGraph

assertVertexExist, containsEdge, equals, hashCode, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toString, toStringFromSets

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.jgrapht.UndirectedGraph

degreeOf

Methods inherited from interface org.jgrapht.Graph

addEdge, addEdge, addVertex, containsEdge, containsEdge, containsVertex, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeFactory, getEdgeSource, getEdgeTarget, getEdgeWeight, removeAllEdges, removeAllEdges, removeAllVertices, removeEdge, removeEdge, removeVertex, vertexSet

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.