|
|||
|
|
|
|||
|
|
SPQR-trees of planar graphs. More...
#include <ogdf/decomposition/StaticPlanarSPQRTree.h>
Inheritance diagram for ogdf::StaticPlanarSPQRTree:Public Member Functions | |
| StaticPlanarSPQRTree (const Graph &G, bool isEmbedded=false) | |
Creates an SPQR tree T for planar graph G rooted at the first edge of G. | |
| StaticPlanarSPQRTree (const Graph &G, edge e, bool isEmbedded=false) | |
Creates an SPQR tree T for planar graph G rooted at edge e. | |
| Public Member Functions inherited from ogdf::StaticSPQRTree | |
| StaticSPQRTree (const Graph &G) | |
Creates an SPQR tree T for graph G rooted at the first edge of G. | |
| StaticSPQRTree (const Graph &G, edge e) | |
Creates an SPQR tree T for graph G rooted at the edge e. | |
| StaticSPQRTree (const Graph &G, Triconnectivity &tricComp) | |
Creates an SPQR tree T for graph G rooted at the first edge of G. | |
| ~StaticSPQRTree () | |
| Destructor. | |
| const Graph & | originalGraph () const override |
| Returns a reference to the original graph G. | |
| const Graph & | tree () const override |
| Returns a reference to the tree T. | |
| edge | rootEdge () const override |
| Returns the edge of G at which T is rooted. | |
| node | rootNode () const override |
| Returns the root node of T. | |
| int | numberOfSNodes () const override |
| Returns the number of S-nodes in 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. | |
| NodeType | typeOf (node v) const override |
Returns the type of node v. | |
| List< node > | nodesOfType (NodeType t) const override |
Returns the list of all nodes with type t. | |
| Skeleton & | skeleton (node v) const override |
Returns the skeleton of node v. | |
| edge | skeletonEdgeSrc (edge e) const |
Returns the edge in skeleton of source(e) that corresponds to tree edge e. | |
| edge | skeletonEdgeTgt (edge e) const |
Returns the edge in skeleton of target(e) that corresponds to tree edge e. | |
| const Skeleton & | skeletonOfReal (edge e) const override |
Returns the skeleton that contains the real edge e. | |
| edge | copyOfReal (edge e) const override |
Returns the skeleton edge that corresponds to the real edge e. | |
| 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. | |
| 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::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... | |
| Protected Member Functions inherited from ogdf::StaticSPQRTree | |
| 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. | |
| void | init (edge e) |
| Initialization (called by constructor). | |
| void | init (edge eRef, Triconnectivity &tricComp) |
| Initialization (called by constructor). | |
| void | rootRec (node v, edge ef) |
| Recursively performs rooting of tree. | |
| 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::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::StaticSPQRTree | |
| EdgeArray< edge > | m_copyOf |
| skeleton edge corresponding to real edge e | |
| int | m_numP |
| number of P-nodes | |
| int | m_numR |
| number of R-nodes | |
| int | m_numS |
| number of S-nodes | |
| const Graph * | m_pGraph |
| pointer to original graph | |
| edge | m_rootEdge |
| edge of G at which T is rooted | |
| node | m_rootNode |
| root node of T | |
| NodeArray< StaticSkeleton * > | m_sk |
| pointer to skeleton of a node in T | |
| EdgeArray< edge > | m_skEdgeSrc |
| corresponding edge in skeleton(source(e)) | |
| EdgeArray< edge > | m_skEdgeTgt |
| corresponding edge in skeleton(target(e)) | |
| EdgeArray< StaticSkeleton * > | m_skOf |
| skeleton containing real edge e | |
| Graph | m_tree |
| underlying tree graph | |
| NodeArray< NodeType > | m_type |
| type of nodes in T | |
| 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::PlanarSPQRTree | |
| bool | m_finished |
SPQR-trees of planar graphs.
The class StaticPlanarSPQRTree 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 56 of file StaticPlanarSPQRTree.h.
|
inlineexplicit |
Creates an SPQR tree T 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 68 of file StaticPlanarSPQRTree.h.
|
inline |
Creates an SPQR tree T 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 81 of file StaticPlanarSPQRTree.h.