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>
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 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 Summary
ConstructorsConstructorDescriptionBlockCutpointGraph
(UndirectedGraph<V, E> graph) Running time = O(m) where m is the number of edges. -
Method Summary
Modifier and TypeMethodDescriptionReturns the vertex if vertex is a cutpoint, and otherwise returns the block (biconnected component) containing the vertex.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 Details
-
BlockCutpointGraph
Running time = O(m) where m is the number of edges.
-
-
Method Details
-
getBlock
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
Returns the cutpoints of the initial graph. -
isCutpoint
Returnstrue
if the vertex is a cutpoint,false
otherwise.- Parameters:
vertex
- vertex in the initial graph.
-