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>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- 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
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
BlockCutpointGraph.BCGEdge
-
Field Summary
Fields Modifier and Type Field Description private java.util.Set<V>
cutpoints
private DirectedGraph<V,DefaultEdge>
dfsTree
DFS (Depth-First-Search) tree.private UndirectedGraph<V,E>
graph
private int
numOrder
private static long
serialVersionUID
private java.util.Deque<BlockCutpointGraph.BCGEdge>
stack
private java.util.Map<V,java.util.Set<UndirectedGraph<V,E>>>
vertex2biconnectedSubgraphs
private java.util.Map<V,UndirectedGraph<V,E>>
vertex2block
private java.util.Map<V,java.lang.Integer>
vertex2numOrder
-
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 private void
biconnectedComponentFinished(V s, V n)
private int
dfsVisit(V s, V father)
private java.util.Set<UndirectedGraph<V,E>>
getBiconnectedSubgraphs(V vertex)
Returns the biconnected components containing the vertex.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.private int
getNumOrder(V vertex)
Returns the traverse order of the vertex in the DFS.boolean
isCutpoint(V vertex)
Returnstrue
if the vertex is a cutpoint,false
otherwise.private void
setNumOrder(V vertex, int numOrder)
-
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.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
-
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
cutpoints
private java.util.Set<V> cutpoints
-
dfsTree
private DirectedGraph<V,DefaultEdge> dfsTree
DFS (Depth-First-Search) tree.
-
graph
private UndirectedGraph<V,E> graph
-
numOrder
private int numOrder
-
stack
private java.util.Deque<BlockCutpointGraph.BCGEdge> stack
-
vertex2biconnectedSubgraphs
private java.util.Map<V,java.util.Set<UndirectedGraph<V,E>>> vertex2biconnectedSubgraphs
-
vertex2block
private java.util.Map<V,UndirectedGraph<V,E>> vertex2block
-
vertex2numOrder
private java.util.Map<V,java.lang.Integer> vertex2numOrder
-
-
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 java.util.Set<V> getCutpoints()
Returns the cutpoints of the initial graph.- 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.- Returns:
true
if the vertex is a cutpoint,false
otherwise.
-
getBiconnectedSubgraphs
private java.util.Set<UndirectedGraph<V,E>> getBiconnectedSubgraphs(V vertex)
Returns the biconnected components containing the vertex. A vertex which is not a cutpoint is contained in exactly one component. A cutpoint is contained is at least 2 components.- Parameters:
vertex
- vertex in the initial graph.
-
getNumOrder
private int getNumOrder(V vertex)
Returns the traverse order of the vertex in the DFS.
-
setNumOrder
private void setNumOrder(V vertex, int numOrder)
-
-