Package 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
-
-
Constructor Summary
Constructors Constructor Description BlockCutpointGraph(UndirectedGraph<V,E> graph)
Running time = O(m) where m is the number of edges.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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.java.util.Set<V>
getCutpoints()
Returns the cutpoints of the initial graph.boolean
isCutpoint(V vertex)
Returnstrue
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 org.jgrapht.graph.AbstractGraph
assertVertexExist, containsEdge, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toString, toStringFromSets
-
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
-
Methods inherited from interface org.jgrapht.UndirectedGraph
degreeOf
-
-
-
-
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)
Returnstrue
if the vertex is a cutpoint,false
otherwise.- Parameters:
vertex
- vertex in the initial graph.
-
-