Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::DynamicPlanarSPQRTree Class Reference

SPQR-trees of planar graphs. More...

#include <ogdf/decomposition/DynamicPlanarSPQRTree.h>

+ Inheritance diagram for ogdf::DynamicPlanarSPQRTree:

Public Member Functions

 DynamicPlanarSPQRTree (Graph &G, bool isEmbedded=false)
 Creates an SPQR tree for planar graph G rooted at the first edge of G. More...
 
 DynamicPlanarSPQRTree (Graph &G, edge e, bool isEmbedded=false)
 Creates an SPQR tree for planar graph G rooted at edge e. More...
 
- Public Member Functions inherited from ogdf::DynamicSPQRTree
 DynamicSPQRTree (Graph &G)
 Creates an SPQR tree T for graph G rooted at the first edge of G. More...
 
 DynamicSPQRTree (Graph &G, edge e)
 Creates an SPQR tree T for graph G rooted at the edge e. More...
 
 ~DynamicSPQRTree ()
 
edge copyOfReal (edge e) const override
 Returns the skeleton edge that corresponds to the real edge e. More...
 
SList< node > & findPath (node s, node t)
 Finds the shortest path between the two sets of vertices of T which s and t of G belong to. More...
 
List< nodenodesOfType (NodeType t) const override
 Returns the list of all nodes with type t. More...
 
int numberOfPNodes () const override
 Returns the number of P-nodes in T. More...
 
int numberOfRNodes () const override
 Returns the number of R-nodes in T. More...
 
int numberOfSNodes () const override
 Returns the number of S-nodes in T. More...
 
const GraphoriginalGraph () const override
 Returns a reference to the original graph G. More...
 
edge rootEdge () const override
 Returns the edge of G at which T is rooted. More...
 
node rootNode () const override
 Returns the root node of T. More...
 
node rootTreeAt (edge e) override
 Roots T at edge e and returns the new root node of T. More...
 
node rootTreeAt (node v) override
 Roots T at node v and returns v. More...
 
Skeletonskeleton (node v) const override
 Returns the skeleton of node v. More...
 
edge skeletonEdge (node v, node w) const
 Returns the virtual edge in the skeleton of w that corresponds to the tree edge between v and w. More...
 
const SkeletonskeletonOfReal (edge e) const override
 Returns the skeleton that contains the real edge e. More...
 
const Graphtree () const override
 Returns a reference to the tree T. More...
 
NodeType typeOf (node v) const override
 Returns the type of node v. More...
 
edge updateInsertedEdge (edge e) override
 Updates the whole data structure after a new edge e has been inserted into G. More...
 
node updateInsertedNode (edge e, edge f) override
 Updates the whole data structure after a new vertex has been inserted into G by splitting an edge into e and f. More...
 
- Public Member Functions inherited from ogdf::SPQRTree
 SPQRTree ()
 
 SPQRTree (const SPQRTree &copy)=delete
 
 SPQRTree (SPQRTree &&move)=delete
 
virtual ~SPQRTree ()
 
SPQRTreeoperator= (const SPQRTree &copy)=delete
 
SPQRTreeoperator= (SPQRTree &&move)=delete
 
void pertinentGraph (node v, PertinentGraph &Gp) const
 Returns the pertinent graph of tree node v in Gp. More...
 
void directSkEdge (node vT, edge e, node src)
 
void replaceSkEdgeByPeak (node vT, edge e)
 
- Public Member Functions inherited from ogdf::DynamicSPQRForest
 DynamicSPQRForest (Graph &G, bool not_connected=false)
 A constructor. More...
 
 DynamicSPQRForest (Graph &G, node vG, bool not_connected=false)
 A constructor. More...
 
 ~DynamicSPQRForest ()
 
node spqrproper (edge eH) const
 
void createSPQR (node vB) const
 Creates the SPQR-tree for a given B-component of the BC-tree. More...
 
node spqrroot (node vB) const
 Returns the root of the SPQR-tree for a given B-component of the BC-tree. More...
 
int numberOfSNodes (node vB) const
 Returns the number of S-nodes in the SPQR-tree for a given B-component of the BC-tree. More...
 
int numberOfPNodes (node vB) const
 Returns the number of P-nodes in the SPQR-tree for a given B-component of the BC-tree. More...
 
int numberOfRNodes (node vB) const
 Returns the number of R-nodes in the SPQR-tree for a given B-component of the BC-tree. More...
 
const GraphspqrTree () const
 Returns the SPQR-tree graph. More...
 
node spqrParent (node vT) const
 Returns the parent node of a node of the SPQR-tree Graph, or nullptr if vT is a root. More...
 
edge spqrParentEdge (node vT) const
 Returns the virtual edge leading to the parents of a SPQR-tree vertex, or nullptr if vT is a root. More...
 
node spqrNodeOf (edge eH) const
 The SPQR-tree-vertex which a real or virtual edge eH belongs to, if the SPQR-tree has been created using createSPQR. More...
 
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...
 
- Public Member Functions inherited from ogdf::DynamicBCTree
 DynamicBCTree (Graph &G, bool not_connected=false)
 
 DynamicBCTree (Graph &G, node vG, bool not_connected=false)
 A constructor. More...
 
node bccomp (node vH) const override
 
node bccomp (edge eH) const override
 Returns the BC-tree-vertex representing the biconnected component which a given edge of the auxiliary 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 (BCTree &&move)=delete
 
 BCTree (const BCTree &copy)=delete
 
 BCTree (Graph &G, bool not_connected=false)
 A constructor. More...
 
 BCTree (Graph &G, List< node > &vG)
 Constructor for not connected graphs. More...
 
 BCTree (Graph &G, node vG, bool not_connected=false)
 A constructor. More...
 
virtual ~BCTree ()
 Virtual destructor. More...
 
void consistencyCheck () const
 Asserts that this BCTree is consistent. More...
 
BCTreeoperator= (BCTree &&move)=delete
 
BCTreeoperator= (const BCTree &copy)=delete
 
const GraphoriginalGraph () const
 Returns the original graph. More...
 
const GraphbcTree () const
 Returns the BC-tree graph. More...
 
const GraphauxiliaryGraph () const
 Returns the biconnected components graph. More...
 
int numberOfBComps () const
 Returns the number of B-components. More...
 
int numberOfCComps () const
 Returns the number of C-components. More...
 
GNodeType typeOfGNode (node vG) const
 
node bcproper (node vG) const
 Returns a BC-tree-vertex representing a biconnected component which a given vertex of the original graph is belonging to. More...
 
node bcproper (edge eG) const
 Returns the BC-tree-vertex representing the biconnected component which a given edge of the original graph is belonging to. More...
 
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) const
 
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...
 
- Public Member Functions inherited from ogdf::PlanarSPQRTree
void embed (Graph &G)
 Embeds G according to the current embeddings of the skeletons of T. More...
 
void embed (node &vT, long long x)
 Embeds the skeleton of the node vT with the specific embedding numbered by x. More...
 
void firstEmbedding (Graph &G)
 Embeds the original graph G canonically by the indices of their adjEntries. More...
 
bool nextEmbedding (Graph &G)
 Embeds the original graph G with the next embedding. More...
 
double numberOfEmbeddings () const
 Returns the number of possible embeddings of G. More...
 
double numberOfEmbeddings (node v) const
 Returns the number of possible embeddings of the pertinent graph of node v. More...
 
long long numberOfNodeEmbeddings (node vT) const
 Returns the number of possible embeddings of the skeleton of node vT. More...
 
void randomEmbed ()
 Embeds all skeleton graphs randomly. More...
 
void randomEmbed (Graph &G)
 Embeds all skeleton graphs randomly and embeds G according to the embeddings of the skeletons. More...
 
void reverse (node vT)
 Flips the skeleton S of vT around its poles. More...
 
void swap (node vT, adjEntry adj1, adjEntry adj2)
 Exchanges the positions of the two edges corresponding to adj1 and adj2 in skeleton of vT. More...
 
void swap (node vT, edge e1, edge e2)
 Exchanges the positions of edges e1 and e2 in skeleton of vT. More...
 

Additional Inherited Members

- Public Types inherited from ogdf::SPQRTree
enum  NodeType { NodeType::SNode, NodeType::PNode, NodeType::RNode }
 The type of a tree node in T. More...
 
- Public Types inherited from ogdf::DynamicSPQRForest
enum  TNodeType { TNodeType::SComp, TNodeType::PComp, TNodeType::RComp }
 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...
 
- Protected Member Functions inherited from ogdf::DynamicSPQRTree
void cpRec (node v, PertinentGraph &Gp) const override
 Recursively performs the task of adding edges (and nodes) to the pertinent graph Gp for each involved skeleton graph. More...
 
DynamicSkeletoncreateSkeleton (node vT) const
 Creates the skeleton graph belonging to a given vertex vT of T. More...
 
void init (edge e)
 Initialization (called by constructors). More...
 
- Protected Member Functions inherited from ogdf::SPQRTree
edge cpAddEdge (edge eOrig, PertinentGraph &Gp) const
 Add an edge to Gp corresponding to eOrig. More...
 
node cpAddNode (node vOrig, PertinentGraph &Gp) const
 Add a node to Gp corresponding to vOrig if required. More...
 
- Protected Member Functions inherited from ogdf::DynamicSPQRForest
void addHEdge (edge eH, node vT) const
 Adds edge eH to a vertex vT of the SPQRForest. 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 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...
 
void init (node vG)
 
- Protected Member Functions inherited from ogdf::PlanarSPQRTree
void adoptEmbedding ()
 
void createInnerVerticesEmbed (Graph &G, node vT)
 
void expandVirtualEmbed (node vT, adjEntry adjVirt, SListPure< adjEntry > &adjEdges)
 
void firstEmbedding (node &vT)
 
void init (bool isEmbedded)
 Initialization (adaption of embeding). More...
 
bool nextEmbedding (ListIterator< node > it)
 
bool nextEmbedding (node &vT)
 
void reverse (node &nP, adjEntry &first, adjEntry &last)
 
void setPosInEmbedding (NodeArray< SListPure< adjEntry >> &adjEdges, NodeArray< node > &currentCopy, NodeArray< adjEntry > &lastAdj, SListPure< node > &current, const Skeleton &S, adjEntry adj)
 
- Protected Attributes inherited from ogdf::DynamicSPQRTree
NodeArray< nodem_mapV
 temporary array used by createSkeleton() More...
 
edge m_rootEdge
 edge of G at which T is rooted More...
 
NodeArray< DynamicSkeleton * > m_sk
 pointer to skeleton of a node in T More...
 
EdgeArray< edgem_skelEdge
 copies of real and virtual edges in their skeleton graphs (invalid, if the skeleton does not actually exist) More...
 
- Protected Attributes inherited from ogdf::SPQRTree
NodeArray< node > * m_cpV
 node in pertinent graph corresponding to an original node (auxiliary member) More...
 
SList< nodem_cpVAdded
 list of added nodes (auxiliary member) More...
 
- Protected Attributes inherited from ogdf::DynamicSPQRForest
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...
 
- Protected Attributes inherited from ogdf::PlanarSPQRTree
bool m_finished
 

Detailed Description

SPQR-trees of planar graphs.

The class DynamicPlanarSPQRTree maintains the triconnected components of a planar biconnected graph G and represents all possible embeddings of G. Each skeleton graph is embedded.

The current embeddings of the skeletons define an embedding of G. There are two basic operations for obtaining another embedding of G: reverse(v), which flips the skeleton of an R-node v around its poles, and swap(v,e_1,e_2), which exchanges the positions of the edges e_1 and e_2 in the skeleton of a P-node v.

Definition at line 53 of file DynamicPlanarSPQRTree.h.

Constructor & Destructor Documentation

◆ DynamicPlanarSPQRTree() [1/2]

ogdf::DynamicPlanarSPQRTree::DynamicPlanarSPQRTree ( Graph G,
bool  isEmbedded = false 
)
inlineexplicit

Creates an SPQR tree for planar graph G rooted at the first edge of G.

If isEmbedded is set to true, G must represent a combinatorial embedding, i.e., the counter-clockwise order of the adjacency entries around each vertex defines an embedding.

Precondition
G is planar and biconnected and contains at least 3 nodes, or G has exactly 2 nodes and at least 3 edges.

Definition at line 65 of file DynamicPlanarSPQRTree.h.

◆ DynamicPlanarSPQRTree() [2/2]

ogdf::DynamicPlanarSPQRTree::DynamicPlanarSPQRTree ( Graph G,
edge  e,
bool  isEmbedded = false 
)
inline

Creates an SPQR tree for planar graph G rooted at edge e.

If isEmbedded is set to true, G must represent a combinatorial embedding, i.e., the counter-clockwise order of the adjacency entries around each vertex defines an embedding.

Precondition
e is an edge in G, and G is planar and biconnected and contains at least 3 nodes, or G has exactly 2 nodes and at least 3 edges.

Definition at line 78 of file DynamicPlanarSPQRTree.h.


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