Dynamic SPQRforest. More...
#include <ogdf/decomposition/DynamicSPQRForest.h>
Public Types  
enum class  TNodeType { SComp , PComp , RComp } 
Enumeration type for characterizing the SPQRtreevertices. More...  
Public Types inherited from ogdf::BCTree  
enum class  BNodeType { BComp , CComp } 
Enumeration type for characterizing the BCtreevertices. More...  
enum class  GNodeType { Normal , CutVertex } 
Enumeration type for characterizing the vertices of the original graph. More...  
Public Member Functions  
DynamicSPQRForest (Graph &G)  
A constructor.  
~DynamicSPQRForest ()  
node  spqrproper (edge eH) const 
edge  twinEdge (edge eH) const 
Returns the twin edge of a given edge of m_H, if it is virtual, or nullptr, if it is real.  
TNodeType  typeOfTNode (node vT) const 
const List< edge > &  hEdgesSPQR (node vT) const 
Returns a linear list of the edges in m_H belonging to the triconnected component represented by a given SPQRtreevertex.  
SList< node > &  findPathSPQR (node sH, node tH) const 
Finds the shortest path between the two sets of SPQRtreevertices which sH and tH are belonging to.  
edge  virtualEdge (node vT, node wT) const 
Returns the virtual edge which leads from one vertex of an SPQRtree to another one.  
edge  updateInsertedEdge (edge eG) override 
node  updateInsertedNode (edge eG, edge fG) override 
Updates the whole data structure after a new vertex has been inserted into the original graph by splitting an edge into eG and fG .  
Public Member Functions inherited from ogdf::DynamicBCTree  
DynamicBCTree (Graph &G, bool callInitConnected=false)  
DynamicBCTree (Graph &G, node vG, bool callInitConnected=false)  
A constructor.  
node  bcproper (node vG) const override 
node  bcproper (edge eG) const override 
Returns the BCtreevertex representing the biconnected component which a given edge of the original graph is belonging to.  
node  repVertex (node uG, node vB) const override 
node  cutVertex (node uB, node vB) const override 
Returns the copy of a cutvertex in the biconnected components graph which belongs to a certain Bcomponent and leads to another Bcomponent.  
edge  insertEdge (node sG, node tG) 
Inserts a new edge into the original graph and updates the BCtree.  
node  insertNode (edge eG) 
Inserts a new vertex into the original graph and updates the BCtree.  
node  bComponent (node uG, node vG) const 
Public Member Functions inherited from ogdf::BCTree  
BCTree (Graph &G, bool callInitConnected=false)  
A constructor.  
BCTree (Graph &G, List< node > &vG)  
Constructor for not connected graphs.  
BCTree (Graph &G, node vG, bool callInitConnected=false)  
A constructor.  
virtual  ~BCTree () 
Virtual destructor.  
const Graph &  originalGraph () const 
Returns the original graph.  
const Graph &  bcTree () const 
Returns the BCtree graph.  
const Graph &  auxiliaryGraph () const 
Returns the biconnected components graph.  
int  numberOfBComps () const 
Returns the number of Bcomponents.  
int  numberOfCComps () const 
Returns the number of Ccomponents.  
GNodeType  typeOfGNode (node vG) const 
node  rep (node vG) const 
Returns a vertex of the biconnected components graph corresponding to a given vertex of the original graph.  
edge  rep (edge eG) const 
Returns the edge of the biconnected components graph corresponding to a given edge of the original graph.  
node  original (node vH) 
edge  original (edge eH) const 
Returns the edge of the original graph which a given edge of the biconnected components graph is corresponding to.  
BNodeType  typeOfBNode (node vB) const 
const SList< edge > &  hEdges (node vB) const 
Returns a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by a given BCtreevertex.  
int  numberOfEdges (node vB) const 
Returns the number of edges belonging to the biconnected component represented by a given BCtreevertex.  
int  numberOfNodes (node vB) const 
Returns the number of vertices belonging to the biconnected component represented by a given BCtreevertex.  
node  bComponent (node uG, node vG) const 
SList< node > &  findPath (node sG, node tG) const 
Calculates a path in the BCtree.  
SList< node > *  findPathBCTree (node sB, node tB) const 
Calculates a path in the BCtree.  
Protected Member Functions  
void  addHEdge (edge eH, node vT) const 
Adds edge eH to a vertex vT of the SPQRForest.  
void  createSPQR (node vB) const 
Creates the SPQRtree for a given Bcomponent of the BCtree.  
void  delHEdge (edge eH, node vT) const 
Deletes edge eH from m_H and removes its connection to a vertex vT of the SPQRForest.  
void  init () 
Initialization.  
node  newSPQRNode (node vB, const TNodeType spqrNodeType) const 
Creates a new node in the SPQRtree for a given Bcomponent of the BCtree.  
edge  newTwinEdge (edge eH, node vT) const 
Creates a twin edge for eH , adds it to vT and returns it.  
node  uniteSPQR (node vB, node sT, node tT) 
node  findSPQR (node vT) const 
Finds the proper representative of an SPQRtreevertex (FIND part of UNION/FIND).  
node  findNCASPQR (node sT, node tT) const 
SList< node > &  findPathSPQR (node sH, node tH, node &rT) const 
Finds the shortest path between the two sets of SPQRtreevertices which sH and tH are belonging to.  
edge  updateInsertedEdgeSPQR (node vB, edge eG) 
node  updateInsertedNodeSPQR (node vB, edge eG, edge fG) 
Updates an SPQRtree after a new vertex has been inserted into the original graph by splitting an edge into eG and fG .  
Protected Member Functions inherited from ogdf::DynamicBCTree  
void  init () 
node  unite (node uB, node vB, node wB) 
node  find (node vB) const 
The FIND function of the UNION/FIND structure.  
node  parent (node vB) const override 
node  condensePath (node sG, node tG) 
Performs path condensation.  
Protected Member Functions inherited from ogdf::BCTree  
void  biComp (adjEntry adjuG, node vG) 
Generates the BCtree and the biconnected components graph recursively.  
void  initNotConnected (List< node > &vG) 
Initialization for not connected graphs.  
void  initNotConnected (node vG) 
Initialization for not connected graphs.  
node  findNCA (node uB, node vB) const 
Calculates the nearest common ancestor of two vertices of the BCtree.  
void  init (node vG) 
Protected Attributes  
Graph  m_T 
A Graph structure containing all SPQRtrees.  
NodeArray< node >  m_bNode_SPQR 
NodeArray< int >  m_bNode_numS 
The numbers of Scomponents.  
NodeArray< int >  m_bNode_numP 
The numbers of Pcomponents.  
NodeArray< int >  m_bNode_numR 
The numbers of Rcomponents.  
NodeArray< TNodeType >  m_tNode_type 
The types of the SPQRtreevertices.  
NodeArray< node >  m_tNode_owner 
The owners of the SPQRtreevertices in the UNION/FIND structure.  
NodeArray< edge >  m_tNode_hRefEdge 
The virtual edges leading to the parents of the SPQRtree vertices.  
NodeArray< List< edge > * >  m_tNode_hEdges 
Lists of real and virtual edges belonging to SPQRtree vertices.  
EdgeArray< ListIterator< edge > >  m_hEdge_position 
The positions of real and virtual edges in their m_tNode_hEdges lists.  
EdgeArray< node >  m_hEdge_tNode 
The SPQRtreevertices which the real and virtual edges are belonging to.  
EdgeArray< edge >  m_hEdge_twinEdge 
The partners of virtual edges (nullptr if real).  
NodeArray< node >  m_htogc 
Auxiliary array used by createSPQR().  
NodeArray< bool >  m_tNode_isMarked 
Auxiliary array used by findNCASPQR()  
Protected Attributes inherited from ogdf::DynamicBCTree  
NodeArray< int >  m_bNode_degree 
Array that contains for each proper BCtreevertex its degree.  
NodeArray< node >  m_bNode_owner 
Array that contains for each BCtreevertex its parent in its UNION/FINDtree structure.  
Protected Attributes inherited from ogdf::BCTree  
Graph  m_B 
The BCtree.  
Graph &  m_G 
The original graph.  
Graph  m_H 
The biconnected components graph.  
int  m_numB 
The number of Bcomponents.  
int  m_numC 
The number of Ccomponents.  
NodeArray< bool >  m_gNode_isMarked 
NodeArray< node >  m_gNode_hNode 
An injective mapping vertices(G) > vertices(H).  
EdgeArray< edge >  m_gEdge_hEdge 
A bijective mapping edges(G) > edges(H).  
NodeArray< BNodeType >  m_bNode_type 
Array that contains the type of each BCtreevertex.  
NodeArray< bool >  m_bNode_isMarked 
Array of marks for the BCtreevertices.  
NodeArray< node >  m_bNode_hRefNode 
Array that contains for each BCtreevertex the representantive of its parent within the subgraph in the biconnected components graph belonging to the biconnected component represented by the respective BCtreevertex.  
NodeArray< node >  m_bNode_hParNode 
Array that contains for each BCtreevertex the representant of itself within the subgraph in the biconnected components graph belonging to the biconnected component represented by the parent of the respective BCtreevertex.  
NodeArray< SList< edge > >  m_bNode_hEdges 
Array that contains for each BCtreevertex a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by the respective BCtreevertex.  
NodeArray< int >  m_bNode_numNodes 
Array that contains for each BCtreevertex the number of vertices belonging to the biconnected component represented by the respective BCtreevertex.  
NodeArray< node >  m_hNode_bNode 
EdgeArray< node >  m_hEdge_bNode 
A surjective mapping edges(H) > vertices(B).  
NodeArray< node >  m_hNode_gNode 
A surjective mapping vertices(H) > vertices(G).  
EdgeArray< edge >  m_hEdge_gEdge 
A bijective mapping edges(H) > edges(G).  
int  m_count 
NodeArray< int >  m_number 
Temporary array.  
NodeArray< int >  m_lowpt 
Temporary array.  
ArrayBuffer< adjEntry >  m_eStack 
Temporary stack.  
NodeArray< node >  m_gtoh 
Temporary array.  
SList< node >  m_nodes 
Temporary list.  
Dynamic SPQRforest.
This class is an extension of DynamicBCTree.
It provides a set of SPQRtrees for each Bcomponent of a BCtree. These SPQRtrees are dynamic, i.e. there are member functions for dynamic updates (edge insertion and node insertion).
Definition at line 49 of file DynamicSPQRForest.h.
Enumeration type for characterizing the SPQRtreevertices.
Enumerator  

SComp  denotes a vertex representing an Scomponent 
PComp  denotes a vertex representing a Pcomponent 
RComp  denotes a vertex representing an Rcomponent 
Definition at line 52 of file DynamicSPQRForest.h.

inlineexplicit 
A constructor.
This constructor does only create the dynamic BCtree rooted at the first edge of G
. The data structure is prepared for dealing with SPQRtrees, but they will only be created on demand. Cf. member functions findPathSPQR() and updateInsertedEdge().
G  is the original graph. 
Definition at line 318 of file DynamicSPQRForest.h.

inline 
Definition at line 320 of file DynamicSPQRForest.h.
Adds edge eH
to a vertex vT
of the SPQRForest.
Definition at line 191 of file DynamicSPQRForest.h.
Creates the SPQRtree for a given Bcomponent of the BCtree.
An SPQRtree belonging to a Bcomponent of the BCtree is only created on demand, i.e. this member function is only called by findSPQRTree() and  under certain circumstances  by updateInsertedEdge().
vB  is a vertex of the BCtree representing a Bcomponent. 
vB
has to be the proper representative of its Bcomponent, i.e. it has to be the root vertex of its respective UNION/FINDtree. vB
must contain at least 3 edges. Deletes edge eH
from m_H and removes its connection to a vertex vT
of the SPQRForest.
Definition at line 203 of file DynamicSPQRForest.h.
Finds the nearest common ancestor of sT
and tT
.
sT  is a vertex of an SPQRtree. 
tT  is a vertex of an SPQRtree. 
sT
and tT
must belong to the same SPQRtree. sT
and tT
have to be proper representatives of their triconnected components, i.e. they have to be the root vertices of their respective UNION/FINDtrees. sT
and tT
. Finds the shortest path between the two sets of SPQRtreevertices which sH
and tH
are belonging to.
sH  is a vertex of m_H. 
tH  is a vertex of m_H. 
sH
and tH
must belong to the same Bcomponent, i.e. to the same SPQRtree. This SPQRtree does not need to exist. If it it does not exist, it will be created.

protected 
Finds the shortest path between the two sets of SPQRtreevertices which sH
and tH
are belonging to.
sH  is a vertex of m_H. 
tH  is a vertex of m_H. 
rT  is a reference! It is set to the very vertex of the found path which is nearest to the root vertex of the SPQRtree. 
sH
and tH
must belong to the same Bcomponent, i.e. to the same SPQRtree. This SPQRtree must exist! Finds the proper representative of an SPQRtreevertex (FIND part of UNION/FIND).
vT  is any vertex of m_T. 
vT
properly representing a triconnected component, i.e. the root of the UNION/FINDtree of vT
. Returns a linear list of the edges in m_H belonging to the triconnected component represented by a given SPQRtreevertex.
vT  is a vertex of an SPQRtree. 
vT
has to be the proper representative of its triconnected component, i.e. it has to be the root vertex of its respective UNION/FINDtree. This condition is particularly fulfilled if vT
is a member of a list gained by the findPathSPQR() member function. vT
. Definition at line 377 of file DynamicSPQRForest.h.

protected 

inlineprotected 
Creates a new node in the SPQRtree for a given Bcomponent of the BCtree.
vB  is a vertex of the BCtree representing a Bcomponent. 
spqrNodeType  is the type of the new SPQRnode. 
vB
has to be the proper representative of its Bcomponent, i.e. it has to be the root vertex of its respective UNION/FINDtree. Definition at line 168 of file DynamicSPQRForest.h.
Creates a twin edge for eH
, adds it to vT
and returns it.
Definition at line 215 of file DynamicSPQRForest.h.
Finds the proper representative of the SPQRtreevertex which a given real or virtual edge is belonging to.
This member function has to be used carefully (see Precondition)!
eH  is an edge of m_H. 
eH
) must exist! Notice, that this condition is fulfilled, if eH
is a member of a list gained by the hEdgesSPQR() member function, because that member function needs an SPQRtreevertex as parameter, which might have been found (and eventually created) by the findPathSPQR() member function. eH
is belonging to. Definition at line 341 of file DynamicSPQRForest.h.
Returns the twin edge of a given edge of m_H, if it is virtual, or nullptr, if it is real.
eH  is an edge of m_H. 
eH
, if it is virtual, or nullptr, if it is real. Definition at line 350 of file DynamicSPQRForest.h.
Returns the type of the triconnected component represented by a given SPQRtreevertex.
vT  is a vertex of an SPQRtree. 
vT
has to be the proper representative of its triconnected component, i.e. it has to be the root vertex of its respective UNION/FINDtree. This condition is particularly fulfilled if vT
is a member of a list gained by the findPathSPQR() member function. vT
. Definition at line 364 of file DynamicSPQRForest.h.
Unites two SPQRtreevertices (UNION part of UNION/FIND).
vB  is a vertex of the BCtree representing a Bcomponent. 
sT  is a vertex of the SPQRtree belonging to vB . 
tT  is a vertex of the SPQRtree belonging to vB . 
vB
has to be the proper representative of its Bcomponent, i.e. it has to be the root vertex of its respective UNION/FINDtree. sT
and tT
have to be proper representatives of their triconnected components, i.e. they have to be the root vertices of their respective UNION/FINDtrees. Updates the whole data structure after a new edge has been inserted into the original graph.
This member function generally updates both BC and SPQRtrees. If any SPQRtree of the Bcomponents of the insertion path through the BCtree exists, the SPQRtree data structure of the resulting Bcomponent will be valid afterwards. If none of the SPQRtrees does exist in advance, then only the BCtree is updated and no SPQRtree is created.
eG  is a new edge in the original graph. 
Reimplemented from ogdf::DynamicBCTree.
Reimplemented in ogdf::DynamicSPQRTree.
Updates an SPQRtree after a new edge has been inserted into the original graph.
vB  is a BCtreevertex representing a Bcomponent. The SPQRtree, which is to be updated is identified by it. 
eG  is a new edge in the original graph. 
vB
has to be the proper representative of its Bcomponent, i.e. it has to be the root vertex of its respective UNION/FINDtree. eG
must belong to the same Bcomponent represented by vB
. Updates the whole data structure after a new vertex has been inserted into the original graph by splitting an edge into eG
and fG
.
This member function updates the BCtree at first. If the SPQRtree of the Bcomponent which the split edge is belonging to does exist, then it is updated, too. If it does not exist, it is not created.
eG  is the incoming edge of the newly inserted vertex which has been generated by a Graph::split() operation. 
fG  is the outgoing edge of the newly inserted vertex which has been generated by a Graph::split() operation. 
Reimplemented from ogdf::DynamicBCTree.
Reimplemented in ogdf::DynamicSPQRTree.
Updates an SPQRtree after a new vertex has been inserted into the original graph by splitting an edge into eG
and fG
.
vB  is a BCtreevertex representing a Bcomponent. The SPQRtree, which is to be updated is identified by it. 
eG  is the incoming edge of the newly inserted vertex which has been generated by a Graph::split() operation. 
fG  is the outgoing edge of the newly inserted vertex which has been generated by a Graph::split() operation. 
vB
. Returns the virtual edge which leads from one vertex of an SPQRtree to another one.
vT  is a vertex of an SPQRtree. 
wT  is a vertex of an SPQRtree. 
vT
and wT
must belong to the same SPQRtree and must be adjacent. vT
and wT
have to be proper representatives of their triconnected components, i.e. they have to be the root vertices of their respective UNION/FINDtrees. This condition is particularly fulfilled if vT
and wT
are members of a list gained by the findPathSPQR() member function. wT
and leads to vT
. The numbers of Pcomponents.
For each vertex of the BCtree representing a Bcomponent, this array contains the number of Pcomponents of the respective SPQRtree. If the SPQRtree does not exist, then the array member is undefined.
Definition at line 92 of file DynamicSPQRForest.h.
The numbers of Rcomponents.
For each vertex of the BCtree representing a Bcomponent, this array contains the number of Rcomponents of the respective SPQRtree. If the SPQRtree does not exist, then the array member is undefined.
Definition at line 102 of file DynamicSPQRForest.h.
The numbers of Scomponents.
For each vertex of the BCtree representing a Bcomponent, this array contains the number of Scomponents of the respective SPQRtree. If the SPQRtree does not exist, then the array member is undefined.
Definition at line 82 of file DynamicSPQRForest.h.
The root vertices of the SPQRtrees.
For each vertex of the BCtree representing a Bcomponent, this array contains the root vertex of the respective SPQRtree, or nullptr, if the SPQRtree does not exist.
Definition at line 72 of file DynamicSPQRForest.h.

mutableprotected 
The positions of real and virtual edges in their m_tNode_hEdges lists.
Definition at line 121 of file DynamicSPQRForest.h.
The SPQRtreevertices which the real and virtual edges are belonging to.
Definition at line 124 of file DynamicSPQRForest.h.
The partners of virtual edges (nullptr if real).
Definition at line 127 of file DynamicSPQRForest.h.
Auxiliary array used by createSPQR().
Definition at line 132 of file DynamicSPQRForest.h.

mutableprotected 
A Graph structure containing all SPQRtrees.
Definition at line 63 of file DynamicSPQRForest.h.
Lists of real and virtual edges belonging to SPQRtree vertices.
Definition at line 116 of file DynamicSPQRForest.h.
The virtual edges leading to the parents of the SPQRtree vertices.
Definition at line 113 of file DynamicSPQRForest.h.
Auxiliary array used by findNCASPQR()
Definition at line 135 of file DynamicSPQRForest.h.
The owners of the SPQRtreevertices in the UNION/FIND structure.
Definition at line 110 of file DynamicSPQRForest.h.
The types of the SPQRtreevertices.
Definition at line 107 of file DynamicSPQRForest.h.