Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::DynamicSPQRForest Class Reference

Dynamic SPQR-forest. More...

#include <ogdf/decomposition/DynamicSPQRForest.h>

+ Inheritance diagram for ogdf::DynamicSPQRForest:

Public Types

enum  TNodeType { TNodeType::SComp = static_cast<int>(SPQRTree::NodeType::SNode), TNodeType::PComp = static_cast<int>(SPQRTree::NodeType::PNode), TNodeType::RComp = static_cast<int>(SPQRTree::NodeType::RNode) }
 Enumeration type for characterizing the SPQR-tree-vertices. More...
 
- Public Types inherited from ogdf::BCTree
enum  BNodeType { BNodeType::BComp, BNodeType::CComp }
 Enumeration type for characterizing the BC-tree-vertices. More...
 
enum  GNodeType { GNodeType::Normal, GNodeType::CutVertex }
 Enumeration type for characterizing the vertices of the original graph. More...
 

Public Member Functions

 DynamicSPQRForest (Graph &G)
 A constructor. More...
 
 ~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. More...
 
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 SPQR-tree-vertex. More...
 
SList< node > & findPathSPQR (node sH, node tH) const
 Finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to. More...
 
edge virtualEdge (node vT, node wT) const
 Returns the virtual edge which leads from one vertex of an SPQR-tree to another one. More...
 
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. More...
 
- Public Member Functions inherited from ogdf::DynamicBCTree
 DynamicBCTree (Graph &G, bool callInitConnected=false)
 
 DynamicBCTree (Graph &G, node vG, bool callInitConnected=false)
 A constructor. More...
 
node bcproper (node vG) const override
 
node bcproper (edge eG) const override
 Returns the BC-tree-vertex representing the biconnected component which a given edge of the original graph is belonging to. More...
 
node repVertex (node uG, node vB) const override
 
node cutVertex (node uB, node vB) const override
 Returns the copy of a cut-vertex in the biconnected components graph which belongs to a certain B-component and leads to another B-component. More...
 
edge insertEdge (node sG, node tG)
 Inserts a new edge into the original graph and updates the BC-tree. More...
 
node insertNode (edge eG)
 Inserts a new vertex into the original graph and updates the BC-tree. More...
 
node bComponent (node uG, node vG) const
 
- Public Member Functions inherited from ogdf::BCTree
 BCTree (Graph &G, bool callInitConnected=false)
 A constructor. More...
 
 BCTree (Graph &G, List< node > &vG)
 Constructor for not connected graphs. More...
 
 BCTree (Graph &G, node vG, bool callInitConnected=false)
 A constructor. More...
 
virtual ~BCTree ()
 Virtual destructor. More...
 
const GraphauxiliaryGraph () const
 Returns the biconnected components graph. More...
 
const GraphbcTree () const
 Returns the BC-tree graph. More...
 
int numberOfBComps () const
 Returns the number of B-components. More...
 
int numberOfCComps () const
 Returns the number of C-components. More...
 
const GraphoriginalGraph () const
 Returns the original graph. More...
 
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. More...
 
edge rep (edge eG) const
 Returns the edge of the biconnected components graph corresponding to a given edge of the original graph. More...
 
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. More...
 
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 BC-tree-vertex. More...
 
int numberOfEdges (node vB) const
 Returns the number of edges belonging to the biconnected component represented by a given BC-tree-vertex. More...
 
int numberOfNodes (node vB) const
 Returns the number of vertices belonging to the biconnected component represented by a given BC-tree-vertex. More...
 
node bComponent (node uG, node vG) const
 
SList< node > & findPath (node sG, node tG) const
 Calculates a path in the BC-tree. More...
 
SList< node > * findPathBCTree (node sB, node tB) const
 Calculates a path in the BC-tree. More...
 

Protected Member Functions

void addHEdge (edge eH, node vT) const
 Adds edge eH to a vertex vT of the SPQRForest. More...
 
void createSPQR (node vB) const
 Creates the SPQR-tree for a given B-component of the BC-tree. More...
 
void delHEdge (edge eH, node vT) const
 Deletes edge eH from m_H and removes its connection to a vertex vT of the SPQRForest. More...
 
void init ()
 Initialization. More...
 
node newSPQRNode (node vB, const TNodeType spqrNodeType) const
 Creates a new node in the SPQR-tree for a given B-component of the BC-tree. More...
 
edge newTwinEdge (edge eH, node vT) const
 Creates a twin edge for eH, adds it to vT and returns it. More...
 
node uniteSPQR (node vB, node sT, node tT)
 
node findSPQR (node vT) const
 Finds the proper representative of an SPQR-tree-vertex (FIND part of UNION/FIND). More...
 
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 SPQR-tree-vertices which sH and tH are belonging to. More...
 
edge updateInsertedEdgeSPQR (node vB, edge eG)
 
node updateInsertedNodeSPQR (node vB, edge eG, edge fG)
 Updates an SPQR-tree after a new vertex has been inserted into the original graph by splitting an edge into eG and fG. More...
 
- 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. More...
 
node parent (node vB) const override
 
node condensePath (node sG, node tG)
 Performs path condensation. More...
 
- Protected Member Functions inherited from ogdf::BCTree
void biComp (adjEntry adjuG, node vG)
 Generates the BC-tree and the biconnected components graph recursively. More...
 
void init (node vG)
 Initialization. More...
 
void initNotConnected (List< node > &vG)
 Initialization for not connected graphs. More...
 
void initNotConnected (node vG)
 Initialization for not connected graphs. More...
 
node findNCA (node uB, node vB) const
 Calculates the nearest common ancestor of two vertices of the BC-tree. More...
 

Protected Attributes

Graph m_T
 A Graph structure containing all SPQR-trees. More...
 
NodeArray< nodem_bNode_SPQR
 
NodeArray< int > m_bNode_numS
 The numbers of S-components. More...
 
NodeArray< int > m_bNode_numP
 The numbers of P-components. More...
 
NodeArray< int > m_bNode_numR
 The numbers of R-components. More...
 
NodeArray< TNodeTypem_tNode_type
 The types of the SPQR-tree-vertices. More...
 
NodeArray< nodem_tNode_owner
 The owners of the SPQR-tree-vertices in the UNION/FIND structure. More...
 
NodeArray< edgem_tNode_hRefEdge
 The virtual edges leading to the parents of the SPQR-tree vertices. More...
 
NodeArray< List< edge > * > m_tNode_hEdges
 Lists of real and virtual edges belonging to SPQR-tree vertices. More...
 
EdgeArray< ListIterator< edge > > m_hEdge_position
 The positions of real and virtual edges in their m_tNode_hEdges lists. More...
 
EdgeArray< nodem_hEdge_tNode
 The SPQR-tree-vertices which the real and virtual edges are belonging to. More...
 
EdgeArray< edgem_hEdge_twinEdge
 The partners of virtual edges (nullptr if real). More...
 
NodeArray< nodem_htogc
 Auxiliary array used by createSPQR(). More...
 
NodeArray< bool > m_tNode_isMarked
 Auxiliary array used by findNCASPQR() More...
 
- Protected Attributes inherited from ogdf::DynamicBCTree
NodeArray< int > m_bNode_degree
 Array that contains for each proper BC-tree-vertex its degree. More...
 
NodeArray< nodem_bNode_owner
 Array that contains for each BC-tree-vertex its parent in its UNION/FIND-tree structure. More...
 
- Protected Attributes inherited from ogdf::BCTree
Graph m_B
 The BC-tree. More...
 
Graphm_G
 The original graph. More...
 
Graph m_H
 The biconnected components graph. More...
 
int m_numB
 The number of B-components. More...
 
int m_numC
 The number of C-components. More...
 
NodeArray< bool > m_gNode_isMarked
 
NodeArray< nodem_gNode_hNode
 An injective mapping vertices(G) -> vertices(H). More...
 
EdgeArray< edgem_gEdge_hEdge
 A bijective mapping edges(G) -> edges(H). More...
 
NodeArray< BNodeTypem_bNode_type
 Array that contains the type of each BC-tree-vertex. More...
 
NodeArray< bool > m_bNode_isMarked
 Array of marks for the BC-tree-vertices. More...
 
NodeArray< nodem_bNode_hRefNode
 Array that contains for each BC-tree-vertex the representantive of its parent within the subgraph in the biconnected components graph belonging to the biconnected component represented by the respective BC-tree-vertex. More...
 
NodeArray< nodem_bNode_hParNode
 Array that contains for each BC-tree-vertex the representant of itself within the subgraph in the biconnected components graph belonging to the biconnected component represented by the parent of the respective BC-tree-vertex. More...
 
NodeArray< SList< edge > > m_bNode_hEdges
 Array that contains for each BC-tree-vertex a linear list of the edges of the biconnected components graph belonging to the biconnected component represented by the respective BC-tree-vertex. More...
 
NodeArray< int > m_bNode_numNodes
 Array that contains for each BC-tree-vertex the number of vertices belonging to the biconnected component represented by the respective BC-tree-vertex. More...
 
NodeArray< nodem_hNode_bNode
 
EdgeArray< nodem_hEdge_bNode
 A surjective mapping edges(H) -> vertices(B). More...
 
NodeArray< nodem_hNode_gNode
 A surjective mapping vertices(H) -> vertices(G). More...
 
EdgeArray< edgem_hEdge_gEdge
 A bijective mapping edges(H) -> edges(G). More...
 
int m_count
 
NodeArray< int > m_number
 Temporary array. More...
 
NodeArray< int > m_lowpt
 Temporary array. More...
 
ArrayBuffer< adjEntrym_eStack
 Temporary stack. More...
 
NodeArray< nodem_gtoh
 Temporary array. More...
 
SList< nodem_nodes
 Temporary list. More...
 

Detailed Description

Dynamic SPQR-forest.

This class is an extension of DynamicBCTree.
It provides a set of SPQR-trees for each B-component of a BC-tree. These SPQR-trees are dynamic, i.e. there are member functions for dynamic updates (edge insertion and node insertion).

Definition at line 49 of file DynamicSPQRForest.h.

Member Enumeration Documentation

◆ TNodeType

Enumeration type for characterizing the SPQR-tree-vertices.

Enumerator
SComp 

denotes a vertex representing an S-component

PComp 

denotes a vertex representing a P-component

RComp 

denotes a vertex representing an R-component

Definition at line 52 of file DynamicSPQRForest.h.

Constructor & Destructor Documentation

◆ DynamicSPQRForest()

ogdf::DynamicSPQRForest::DynamicSPQRForest ( Graph G)
inlineexplicit

A constructor.

This constructor does only create the dynamic BC-tree rooted at the first edge of G. The data structure is prepared for dealing with SPQR-trees, but they will only be created on demand. Cf. member functions findPathSPQR() and updateInsertedEdge().

Parameters
Gis the original graph.

Definition at line 315 of file DynamicSPQRForest.h.

◆ ~DynamicSPQRForest()

ogdf::DynamicSPQRForest::~DynamicSPQRForest ( )
inline

Definition at line 317 of file DynamicSPQRForest.h.

Member Function Documentation

◆ addHEdge()

void ogdf::DynamicSPQRForest::addHEdge ( edge  eH,
node  vT 
) const
inlineprotected

Adds edge eH to a vertex vT of the SPQRForest.

Parameters
eHis an edge in m_H.
vTis a vertex in m_T.

Definition at line 188 of file DynamicSPQRForest.h.

◆ createSPQR()

void ogdf::DynamicSPQRForest::createSPQR ( node  vB) const
protected

Creates the SPQR-tree for a given B-component of the BC-tree.

An SPQR-tree belonging to a B-component of the BC-tree is only created on demand, i.e. this member function is only called by findSPQRTree() and - under certain circumstances - by updateInsertedEdge().

Parameters
vBis a vertex of the BC-tree representing a B-component.
Precondition
vB has to be the proper representative of its B-component, i.e. it has to be the root vertex of its respective UNION/FIND-tree.
The B-component represented by vB must contain at least 3 edges.

◆ delHEdge()

void ogdf::DynamicSPQRForest::delHEdge ( edge  eH,
node  vT 
) const
inlineprotected

Deletes edge eH from m_H and removes its connection to a vertex vT of the SPQRForest.

Parameters
eHis an edge in m_H.
vTis a vertex in m_T.

Definition at line 200 of file DynamicSPQRForest.h.

◆ findNCASPQR()

node ogdf::DynamicSPQRForest::findNCASPQR ( node  sT,
node  tT 
) const
protected

Finds the nearest common ancestor of sT and tT.

Parameters
sTis a vertex of an SPQR-tree.
tTis a vertex of an SPQR-tree.
Precondition
sT and tT must belong to the same SPQR-tree.
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/FIND-trees.
Returns
the proper representative of the nearest common ancestor of sT and tT.

◆ findPathSPQR() [1/2]

SList<node>& ogdf::DynamicSPQRForest::findPathSPQR ( node  sH,
node  tH 
) const

Finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to.

Parameters
sHis a vertex of m_H.
tHis a vertex of m_H.
Precondition
sH and tH must belong to the same B-component, i.e. to the same SPQR-tree. This SPQR-tree does not need to exist. If it it does not exist, it will be created.
Returns
the path in the SPQR-tree as a linear list of vertices.
Postcondition
The SList<node> instance is created by this function and has to be destructed by the caller!

◆ findPathSPQR() [2/2]

SList<node>& ogdf::DynamicSPQRForest::findPathSPQR ( node  sH,
node  tH,
node rT 
) const
protected

Finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to.

Parameters
sHis a vertex of m_H.
tHis a vertex of m_H.
rTis a reference! It is set to the very vertex of the found path which is nearest to the root vertex of the SPQR-tree.
Precondition
sH and tH must belong to the same B-component, i.e. to the same SPQR-tree. This SPQR-tree must exist!
Returns
the path in the SPQR-tree as a linear list of vertices.
Postcondition
The SList<node> instance is created by this function and has to be destructed by the caller!

◆ findSPQR()

node ogdf::DynamicSPQRForest::findSPQR ( node  vT) const
protected

Finds the proper representative of an SPQR-tree-vertex (FIND part of UNION/FIND).

Parameters
vTis any vertex of m_T.
Returns
the owner of vT properly representing a triconnected component, i.e. the root of the UNION/FIND-tree of vT.

◆ hEdgesSPQR()

const List<edge>& ogdf::DynamicSPQRForest::hEdgesSPQR ( node  vT) const
inline

Returns a linear list of the edges in m_H belonging to the triconnected component represented by a given SPQR-tree-vertex.

Parameters
vTis a vertex of an SPQR-tree.
Precondition
vT has to be the proper representative of its triconnected component, i.e. it has to be the root vertex of its respective UNION/FIND-tree. This condition is particularly fulfilled if vT is a member of a list gained by the findPathSPQR() member function.
Returns
a linear list of the edges in m_H belonging to the triconnected component represented by vT.

Definition at line 369 of file DynamicSPQRForest.h.

◆ init()

void ogdf::DynamicSPQRForest::init ( )
protected

◆ newSPQRNode()

node ogdf::DynamicSPQRForest::newSPQRNode ( node  vB,
const TNodeType  spqrNodeType 
) const
inlineprotected

Creates a new node in the SPQR-tree for a given B-component of the BC-tree.

Parameters
vBis a vertex of the BC-tree representing a B-component.
spqrNodeTypeis the type of the new SPQR-node.
Precondition
vB has to be the proper representative of its B-component, i.e. it has to be the root vertex of its respective UNION/FIND-tree.
Returns
the newly created node in m_T.

Definition at line 165 of file DynamicSPQRForest.h.

◆ newTwinEdge()

edge ogdf::DynamicSPQRForest::newTwinEdge ( edge  eH,
node  vT 
) const
inlineprotected

Creates a twin edge for eH, adds it to vT and returns it.

Parameters
eHis an edge in m_H, whose twin edge should be created.
vTis a vertex in m_T.
Returns
the new twin edge.

Definition at line 212 of file DynamicSPQRForest.h.

◆ spqrproper()

node ogdf::DynamicSPQRForest::spqrproper ( edge  eH) const
inline

Finds the proper representative of the SPQR-tree-vertex which a given real or virtual edge is belonging to.

This member function has to be used carefully (see Precondition)!

Parameters
eHis an edge of m_H.
Precondition
The respective SPQR-tree belonging to the B-component represented by the BC-tree-vertex bcproper(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 SPQR-tree-vertex as parameter, which might have been found (and eventually created) by the findPathSPQR() member function.
Returns
the proper representative of the SPQR-tree-vertex which eH is belonging to.

Definition at line 334 of file DynamicSPQRForest.h.

◆ twinEdge()

edge ogdf::DynamicSPQRForest::twinEdge ( edge  eH) const
inline

Returns the twin edge of a given edge of m_H, if it is virtual, or nullptr, if it is real.

Parameters
eHis an edge of m_H.
Returns
the twin edge of eH, if it is virtual, or nullptr, if it is real.

Definition at line 343 of file DynamicSPQRForest.h.

◆ typeOfTNode()

TNodeType ogdf::DynamicSPQRForest::typeOfTNode ( node  vT) const
inline

Returns the type of the triconnected component represented by a given SPQR-tree-vertex.

Parameters
vTis a vertex of an SPQR-tree.
Precondition
vT has to be the proper representative of its triconnected component, i.e. it has to be the root vertex of its respective UNION/FIND-tree. This condition is particularly fulfilled if vT is a member of a list gained by the findPathSPQR() member function.
Returns
the type of the triconnected component represented by vT.

Definition at line 356 of file DynamicSPQRForest.h.

◆ uniteSPQR()

node ogdf::DynamicSPQRForest::uniteSPQR ( node  vB,
node  sT,
node  tT 
)
protected

Unites two SPQR-tree-vertices (UNION part of UNION/FIND).

Parameters
vBis a vertex of the BC-tree representing a B-component.
sTis a vertex of the SPQR-tree belonging to vB.
tTis a vertex of the SPQR-tree belonging to vB.
Precondition
vB has to be the proper representative of its B-component, i.e. it has to be the root vertex of its respective UNION/FIND-tree.
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/FIND-trees.
Returns
the proper representative of the united SPQR-tree-vertex.

◆ updateInsertedEdge()

edge ogdf::DynamicSPQRForest::updateInsertedEdge ( edge  eG)
overridevirtual

Updates the whole data structure after a new edge has been inserted into the original graph.

This member function generally updates both BC- and SPQR-trees. If any SPQR-tree of the B-components of the insertion path through the BC-tree exists, the SPQR-tree data structure of the resulting B-component will be valid afterwards. If none of the SPQR-trees does exist in advance, then only the BC-tree is updated and no SPQR-tree is created.

Parameters
eGis a new edge in the original graph.
Returns
the new edge of the original graph.

Reimplemented from ogdf::DynamicBCTree.

Reimplemented in ogdf::DynamicSPQRTree.

◆ updateInsertedEdgeSPQR()

edge ogdf::DynamicSPQRForest::updateInsertedEdgeSPQR ( node  vB,
edge  eG 
)
protected

Updates an SPQR-tree after a new edge has been inserted into the original graph.

Parameters
vBis a BC-tree-vertex representing a B-component. The SPQR-tree, which is to be updated is identified by it.
eGis a new edge in the original graph.
Precondition
vB has to be the proper representative of its B-component, i.e. it has to be the root vertex of its respective UNION/FIND-tree.
Both the source and the target vertices of eG must belong to the same B-component represented by vB.
Returns
the new edge of the original graph.

◆ updateInsertedNode()

node ogdf::DynamicSPQRForest::updateInsertedNode ( edge  eG,
edge  fG 
)
overridevirtual

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 BC-tree at first. If the SPQR-tree of the B-component which the split edge is belonging to does exist, then it is updated, too. If it does not exist, it is not created.

Parameters
eGis the incoming edge of the newly inserted vertex which has been generated by a Graph::split() operation.
fGis the outgoing edge of the newly inserted vertex which has been generated by a Graph::split() operation.
Returns
the new vertex of the original graph.

Reimplemented from ogdf::DynamicBCTree.

Reimplemented in ogdf::DynamicSPQRTree.

◆ updateInsertedNodeSPQR()

node ogdf::DynamicSPQRForest::updateInsertedNodeSPQR ( node  vB,
edge  eG,
edge  fG 
)
protected

Updates an SPQR-tree after a new vertex has been inserted into the original graph by splitting an edge into eG and fG.

Parameters
vBis a BC-tree-vertex representing a B-component. The SPQR-tree, which is to be updated is identified by it.
eGis the incoming edge of the newly inserted vertex which has been generated by a Graph::split() operation.
fGis the outgoing edge of the newly inserted vertex which has been generated by a Graph::split() operation.
Precondition
The split edge must belong to the B-component which is represented by vB.
Returns
the new vertex of the original graph.

◆ virtualEdge()

edge ogdf::DynamicSPQRForest::virtualEdge ( node  vT,
node  wT 
) const

Returns the virtual edge which leads from one vertex of an SPQR-tree to another one.

Parameters
vTis a vertex of an SPQR-tree.
wTis a vertex of an SPQR-tree.
Precondition
vT and wT must belong to the same SPQR-tree 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/FIND-trees. This condition is particularly fulfilled if vT and wT are members of a list gained by the findPathSPQR() member function.
Returns
the virtual edge in m_H which belongs to wT and leads to vT.

Member Data Documentation

◆ m_bNode_numP

NodeArray<int> ogdf::DynamicSPQRForest::m_bNode_numP
mutableprotected

The numbers of P-components.

For each vertex of the BC-tree representing a B-component, this array contains the number of P-components of the respective SPQR-tree. If the SPQR-tree does not exist, then the array member is undefined.

Definition at line 89 of file DynamicSPQRForest.h.

◆ m_bNode_numR

NodeArray<int> ogdf::DynamicSPQRForest::m_bNode_numR
mutableprotected

The numbers of R-components.

For each vertex of the BC-tree representing a B-component, this array contains the number of R-components of the respective SPQR-tree. If the SPQR-tree does not exist, then the array member is undefined.

Definition at line 99 of file DynamicSPQRForest.h.

◆ m_bNode_numS

NodeArray<int> ogdf::DynamicSPQRForest::m_bNode_numS
mutableprotected

The numbers of S-components.

For each vertex of the BC-tree representing a B-component, this array contains the number of S-components of the respective SPQR-tree. If the SPQR-tree does not exist, then the array member is undefined.

Definition at line 79 of file DynamicSPQRForest.h.

◆ m_bNode_SPQR

NodeArray<node> ogdf::DynamicSPQRForest::m_bNode_SPQR
mutableprotected

The root vertices of the SPQR-trees.

For each vertex of the BC-tree representing a B-component, this array contains the root vertex of the respective SPQR-tree, or nullptr, if the SPQR-tree does not exist.

Definition at line 69 of file DynamicSPQRForest.h.

◆ m_hEdge_position

EdgeArray<ListIterator<edge> > ogdf::DynamicSPQRForest::m_hEdge_position
mutableprotected

The positions of real and virtual edges in their m_tNode_hEdges lists.

Definition at line 118 of file DynamicSPQRForest.h.

◆ m_hEdge_tNode

EdgeArray<node> ogdf::DynamicSPQRForest::m_hEdge_tNode
mutableprotected

The SPQR-tree-vertices which the real and virtual edges are belonging to.

Definition at line 121 of file DynamicSPQRForest.h.

◆ m_hEdge_twinEdge

EdgeArray<edge> ogdf::DynamicSPQRForest::m_hEdge_twinEdge
mutableprotected

The partners of virtual edges (nullptr if real).

Definition at line 124 of file DynamicSPQRForest.h.

◆ m_htogc

NodeArray<node> ogdf::DynamicSPQRForest::m_htogc
mutableprotected

Auxiliary array used by createSPQR().

Definition at line 129 of file DynamicSPQRForest.h.

◆ m_T

Graph ogdf::DynamicSPQRForest::m_T
mutableprotected

A Graph structure containing all SPQR-trees.

Definition at line 60 of file DynamicSPQRForest.h.

◆ m_tNode_hEdges

NodeArray<List<edge>*> ogdf::DynamicSPQRForest::m_tNode_hEdges
mutableprotected

Lists of real and virtual edges belonging to SPQR-tree vertices.

Definition at line 113 of file DynamicSPQRForest.h.

◆ m_tNode_hRefEdge

NodeArray<edge> ogdf::DynamicSPQRForest::m_tNode_hRefEdge
mutableprotected

The virtual edges leading to the parents of the SPQR-tree vertices.

Definition at line 110 of file DynamicSPQRForest.h.

◆ m_tNode_isMarked

NodeArray<bool> ogdf::DynamicSPQRForest::m_tNode_isMarked
mutableprotected

Auxiliary array used by findNCASPQR()

Definition at line 132 of file DynamicSPQRForest.h.

◆ m_tNode_owner

NodeArray<node> ogdf::DynamicSPQRForest::m_tNode_owner
mutableprotected

The owners of the SPQR-tree-vertices in the UNION/FIND structure.

Definition at line 107 of file DynamicSPQRForest.h.

◆ m_tNode_type

NodeArray<TNodeType> ogdf::DynamicSPQRForest::m_tNode_type
mutableprotected

The types of the SPQR-tree-vertices.

Definition at line 104 of file DynamicSPQRForest.h.


The documentation for this class was generated from the following file: