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>
- 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
Method Summary |
UndirectedGraph<V,E> |
getBlock(V vertex)
Returns the vertex if vertex is a cutpoint, and otherwise returns the
block (biconnected component) containing the vertex. |
java.util.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.AbstractBaseGraph |
addEdge, addEdge, addVertex, clone, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeFactory, getEdgeSource, getEdgeTarget, getEdgeWeight, incomingEdgesOf, inDegreeOf, isAllowingLoops, isAllowingMultipleEdges, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, removeVertex, setEdgeSetFactory, setEdgeWeight, vertexSet |
Methods inherited from class java.lang.Object |
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
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 |
BlockCutpointGraph
public BlockCutpointGraph(UndirectedGraph<V,E> graph)
- Running time = O(m) where m is the number of edges.
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.