|
|||
|
|
|
|||
|
|
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. | |
| DynamicPlanarSPQRTree (Graph &G, edge e, bool isEmbedded=false) | |
Creates an SPQR tree for planar graph G rooted at edge e. | |
| 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. | |
| DynamicSPQRTree (Graph &G, edge e) | |
Creates an SPQR tree T for graph G rooted at the edge e. | |
| ~DynamicSPQRTree () | |
| edge | copyOfReal (edge e) const override |
Returns the skeleton edge that corresponds to the real edge e. | |
| 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. | |
| List< node > | nodesOfType (NodeType t) const override |
Returns the list of all nodes with type t. | |
| int | numberOfPNodes () const override |
| Returns the number of P-nodes in T. | |
| int | numberOfRNodes () const override |
| Returns the number of R-nodes in T. | |
| int | numberOfSNodes () const override |
| Returns the number of S-nodes in T. | |
| const Graph & | originalGraph () const override |
| Returns a reference to the original graph G. | |
| edge | rootEdge () const override |
| Returns the edge of G at which T is rooted. | |
| node | rootNode () const override |
| Returns the root node of T. | |
| node | rootTreeAt (edge e) override |
Roots T at edge e and returns the new root node of T. | |
| node | rootTreeAt (node v) override |
Roots T at node v and returns v. | |
| Skeleton & | skeleton (node v) const override |
Returns the skeleton of node v. | |
| 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. | |
| const Skeleton & | skeletonOfReal (edge e) const override |
Returns the skeleton that contains the real edge e. | |
| const Graph & | tree () const override |
| Returns a reference to the tree T. | |
| NodeType | typeOf (node v) const override |
Returns the type of node v. | |
| edge | updateInsertedEdge (edge e) override |
Updates the whole data structure after a new edge e has been inserted into G. | |
| 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. | |
| Public Member Functions inherited from ogdf::SPQRTree | |
| virtual | ~SPQRTree () |
| void | pertinentGraph (node v, PertinentGraph &Gp) const |
Returns the pertinent graph of tree node v in Gp. | |
| void | directSkEdge (node vT, edge e, node src) |
| void | replaceSkEdgeByPeak (node vT, edge e) |
| Public Member Functions inherited from ogdf::DynamicSPQRForest | |
| 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 SPQR-tree-vertex. | |
| 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. | |
| edge | virtualEdge (node vT, node wT) const |
| Returns the virtual edge which leads from one vertex of an SPQR-tree to another one. | |
| 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 BC-tree-vertex 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 cut-vertex in the biconnected components graph which belongs to a certain B-component and leads to another B-component. | |
| edge | insertEdge (node sG, node tG) |
| Inserts a new edge into the original graph and updates the BC-tree. | |
| node | insertNode (edge eG) |
| Inserts a new vertex into the original graph and updates the BC-tree. | |
| 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 BC-tree graph. | |
| const Graph & | auxiliaryGraph () const |
| Returns the biconnected components graph. | |
| int | numberOfBComps () const |
| Returns the number of B-components. | |
| int | numberOfCComps () const |
| Returns the number of C-components. | |
| 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 BC-tree-vertex. | |
| int | numberOfEdges (node vB) const |
| Returns the number of edges belonging to the biconnected component represented by a given BC-tree-vertex. | |
| int | numberOfNodes (node vB) const |
| Returns the number of vertices belonging to the biconnected component represented by a given BC-tree-vertex. | |
| node | bComponent (node uG, node vG) const |
| SList< node > & | findPath (node sG, node tG) const |
| Calculates a path in the BC-tree. | |
| SList< node > * | findPathBCTree (node sB, node tB) const |
| Calculates a path in the BC-tree. | |
| Public Member Functions inherited from ogdf::PlanarSPQRTree | |
| void | embed (Graph &G) |
Embeds G according to the current embeddings of the skeletons of T. | |
| void | embed (node &vT, long long x) |
| Embeds the skeleton of the node vT with the specific embedding numbered by x. | |
| void | firstEmbedding (Graph &G) |
Embeds the original graph G canonically by the indices of their adjEntries. | |
| bool | nextEmbedding (Graph &G) |
Embeds the original graph G with the next embedding. | |
| double | numberOfEmbeddings () const |
| Returns the number of possible embeddings of G. | |
| double | numberOfEmbeddings (node v) const |
Returns the number of possible embeddings of the pertinent graph of node v. | |
| long long | numberOfNodeEmbeddings (node vT) const |
Returns the number of possible embeddings of the skeleton of node vT. | |
| void | randomEmbed () |
| Embeds all skeleton graphs randomly. | |
| void | randomEmbed (Graph &G) |
Embeds all skeleton graphs randomly and embeds G according to the embeddings of the skeletons. | |
| void | reverse (node vT) |
Flips the skeleton S of vT around its poles. | |
| void | swap (node vT, adjEntry adj1, adjEntry adj2) |
Exchanges the positions of the two edges corresponding to adj1 and adj2 in skeleton of vT. | |
| void | swap (node vT, edge e1, edge e2) |
Exchanges the positions of edges e1 and e2 in skeleton of vT. | |
Additional Inherited Members | |
| Public Types inherited from ogdf::SPQRTree | |
| enum class | NodeType { SNode , PNode , RNode } |
| The type of a tree node in T. More... | |
| Public Types inherited from ogdf::DynamicSPQRForest | |
| enum class | TNodeType { SComp , PComp , RComp } |
| Enumeration type for characterizing the SPQR-tree-vertices. More... | |
| Public Types inherited from ogdf::BCTree | |
| enum class | BNodeType { BComp , CComp } |
| Enumeration type for characterizing the BC-tree-vertices. More... | |
| enum class | GNodeType { Normal , 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. | |
| DynamicSkeleton & | createSkeleton (node vT) const |
Creates the skeleton graph belonging to a given vertex vT of T. | |
| void | init (edge e) |
| Initialization (called by constructors). | |
| Protected Member Functions inherited from ogdf::SPQRTree | |
| edge | cpAddEdge (edge eOrig, PertinentGraph &Gp) const |
Add an edge to Gp corresponding to eOrig. | |
| node | cpAddNode (node vOrig, PertinentGraph &Gp) const |
Add a node to Gp corresponding to vOrig if required. | |
| Protected Member Functions inherited from ogdf::DynamicSPQRForest | |
| void | addHEdge (edge eH, node vT) const |
Adds edge eH to a vertex vT of the SPQRForest. | |
| void | createSPQR (node vB) const |
| Creates the SPQR-tree for a given B-component of the BC-tree. | |
| 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 SPQR-tree for a given B-component of the BC-tree. | |
| 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 SPQR-tree-vertex (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 SPQR-tree-vertices which sH and tH are belonging to. | |
| 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. | |
| 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 BC-tree 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 BC-tree. | |
| 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). | |
| 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 > ¤tCopy, NodeArray< adjEntry > &lastAdj, SListPure< node > ¤t, const Skeleton &S, adjEntry adj) |
| Protected Attributes inherited from ogdf::DynamicSPQRTree | |
| NodeArray< node > | m_mapV |
| temporary array used by createSkeleton() | |
| edge | m_rootEdge |
| edge of G at which T is rooted | |
| NodeArray< DynamicSkeleton * > | m_sk |
| pointer to skeleton of a node in T | |
| EdgeArray< edge > | m_skelEdge |
| copies of real and virtual edges in their skeleton graphs (invalid, if the skeleton does not actually exist) | |
| Protected Attributes inherited from ogdf::SPQRTree | |
| NodeArray< node > * | m_cpV |
| node in pertinent graph corresponding to an original node (auxiliary member) | |
| SList< node > | m_cpVAdded |
| list of added nodes (auxiliary member) | |
| Protected Attributes inherited from ogdf::DynamicSPQRForest | |
| Graph | m_T |
| A Graph structure containing all SPQR-trees. | |
| NodeArray< node > | m_bNode_SPQR |
| NodeArray< int > | m_bNode_numS |
| The numbers of S-components. | |
| NodeArray< int > | m_bNode_numP |
| The numbers of P-components. | |
| NodeArray< int > | m_bNode_numR |
| The numbers of R-components. | |
| NodeArray< TNodeType > | m_tNode_type |
| The types of the SPQR-tree-vertices. | |
| NodeArray< node > | m_tNode_owner |
| The owners of the SPQR-tree-vertices in the UNION/FIND structure. | |
| NodeArray< edge > | m_tNode_hRefEdge |
| The virtual edges leading to the parents of the SPQR-tree vertices. | |
| NodeArray< List< edge > * > | m_tNode_hEdges |
| Lists of real and virtual edges belonging to SPQR-tree 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 SPQR-tree-vertices 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 BC-tree-vertex its degree. | |
| NodeArray< node > | m_bNode_owner |
| Array that contains for each BC-tree-vertex its parent in its UNION/FIND-tree structure. | |
| Protected Attributes inherited from ogdf::BCTree | |
| Graph | m_B |
| The BC-tree. | |
| Graph & | m_G |
| The original graph. | |
| Graph | m_H |
| The biconnected components graph. | |
| int | m_numB |
| The number of B-components. | |
| int | m_numC |
| The number of C-components. | |
| 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 BC-tree-vertex. | |
| NodeArray< bool > | m_bNode_isMarked |
| Array of marks for the BC-tree-vertices. | |
| NodeArray< node > | m_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. | |
| NodeArray< node > | m_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. | |
| 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. | |
| 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. | |
| 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. | |
| Protected Attributes inherited from ogdf::PlanarSPQRTree | |
| bool | m_finished |
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.
|
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.
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.
|
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.
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.