# OpenGraph DrawingFramework

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
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...

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.

## ◆ TNodeType

 strong

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.

## ◆ 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
 G is 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

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

Adds edge eH to a vertex vT of the SPQRForest.

Parameters
 eH is an edge in m_H. vT is 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
 vB is 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
 eH is an edge in m_H. vT is 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
 sT is a vertex of an SPQR-tree. tT is 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& 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
 sH is a vertex of m_H. tH is 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& 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
 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 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
 vT is 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& 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
 vT is 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
 vB is a vertex of the BC-tree representing a B-component. spqrNodeType is 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
 eH is an edge in m_H, whose twin edge should be created. vT is 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
 eH is 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
 eH is 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
 vT is 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
 vB is a vertex of the BC-tree representing a B-component. sT is a vertex of the SPQR-tree belonging to vB. tT is 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
 eG is 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
 vB is a BC-tree-vertex representing a B-component. The SPQR-tree, which is to be updated is identified by it. eG is 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
 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.
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
 vB is a BC-tree-vertex representing a B-component. The SPQR-tree, 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.
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
 vT is a vertex of an SPQR-tree. wT is 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.

## ◆ m_bNode_numP

 NodeArray 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 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 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 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 > 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 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 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 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*> 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 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 ogdf::DynamicSPQRForest::m_tNode_isMarked
mutableprotected

Auxiliary array used by findNCASPQR()

Definition at line 132 of file DynamicSPQRForest.h.

## ◆ m_tNode_owner

 NodeArray 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 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: