|
|||
|
|
|
|||
|
|
SPQR-trees of planar graphs. More...
#include <ogdf/decomposition/PlanarSPQRTree.h>
Inheritance diagram for ogdf::PlanarSPQRTree:Public Member Functions | |
| 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... | |
| Public Member Functions inherited from ogdf::SPQRTree | |
| SPQRTree () | |
| SPQRTree (const SPQRTree ©)=delete | |
| SPQRTree (SPQRTree &&move)=delete | |
| virtual | ~SPQRTree () |
| SPQRTree & | operator= (const SPQRTree ©)=delete |
| SPQRTree & | operator= (SPQRTree &&move)=delete |
| virtual const Graph & | originalGraph () const =0 |
| Returns a reference to the original graph G. More... | |
| virtual const Graph & | tree () const =0 |
| Returns a reference to the tree T. More... | |
| virtual edge | rootEdge () const =0 |
| Returns the edge of G at which T is rooted. More... | |
| virtual node | rootNode () const =0 |
| Returns the root node of T. More... | |
| virtual int | numberOfSNodes () const =0 |
| Returns the number of S-nodes in T. More... | |
| virtual int | numberOfPNodes () const =0 |
| Returns the number of P-nodes in T. More... | |
| virtual int | numberOfRNodes () const =0 |
| Returns the number of R-nodes in T. More... | |
| virtual NodeType | typeOf (node v) const =0 |
Returns the type of node v. More... | |
| virtual List< node > | nodesOfType (NodeType t) const =0 |
Returns the list of all nodes with type t. More... | |
| virtual Skeleton & | skeleton (node v) const =0 |
Returns the skeleton of node v. More... | |
| virtual const Skeleton & | skeletonOfReal (edge e) const =0 |
Returns the skeleton that contains the real edge e. More... | |
| virtual edge | copyOfReal (edge e) const =0 |
Returns the skeleton edge that corresponds to the real edge e. More... | |
| void | pertinentGraph (node v, PertinentGraph &Gp) const |
Returns the pertinent graph of tree node v in Gp. More... | |
| virtual node | rootTreeAt (edge e)=0 |
Roots T at edge e and returns the new root node of T. More... | |
| virtual node | rootTreeAt (node v)=0 |
Roots T at node v and returns v. More... | |
| void | directSkEdge (node vT, edge e, node src) |
| void | replaceSkEdgeByPeak (node vT, edge e) |
Protected Member Functions | |
| 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 > ¤tCopy, NodeArray< adjEntry > &lastAdj, SListPure< node > ¤t, const Skeleton &S, adjEntry adj) |
| Protected Member Functions inherited from ogdf::SPQRTree | |
| virtual void | cpRec (node v, PertinentGraph &Gp) const =0 |
Recursively performs the task of adding edges (and nodes) to the pertinent graph Gp for each involved skeleton graph. More... | |
| 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 Attributes | |
| bool | m_finished |
| Protected Attributes inherited from ogdf::SPQRTree | |
| NodeArray< node > * | m_cpV |
| node in pertinent graph corresponding to an original node (auxiliary member) More... | |
| SList< node > | m_cpVAdded |
| list of added nodes (auxiliary member) 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... | |
SPQR-trees of planar graphs.
The class PlanarSPQRTree 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 58 of file PlanarSPQRTree.h.
|
protected |
| void ogdf::PlanarSPQRTree::embed | ( | Graph & | G | ) |
Embeds G according to the current embeddings of the skeletons of T.
G is the graph passed to the constructor of T | void ogdf::PlanarSPQRTree::embed | ( | node & | vT, |
| long long | x | ||
| ) |
Embeds the skeleton of the node vT with the specific embedding numbered by x.
|
protected |
| void ogdf::PlanarSPQRTree::firstEmbedding | ( | Graph & | G | ) |
Embeds the original graph G canonically by the indices of their adjEntries.
G is the graph passed to the constructor of T
|
protected |
|
protected |
Initialization (adaption of embeding).
| bool ogdf::PlanarSPQRTree::nextEmbedding | ( | Graph & | G | ) |
Embeds the original graph G with the next embedding.
It returns false iff there is no feasible (planar) embedding left
G is the graph passed to the constructor of T
|
protected |
|
protected |
|
inline |
Returns the number of possible embeddings of G.
Definition at line 65 of file PlanarSPQRTree.h.
| double ogdf::PlanarSPQRTree::numberOfEmbeddings | ( | node | v | ) | const |
Returns the number of possible embeddings of the pertinent graph of node v.
v is a node in T | long long ogdf::PlanarSPQRTree::numberOfNodeEmbeddings | ( | node | vT | ) | const |
Returns the number of possible embeddings of the skeleton of node vT.
vT is a node in T Returns 1 if vT is a S-node, 2 if vT is a R-node, and (number of edges in the sekeleton - 1)! if vT is a P-node. | void ogdf::PlanarSPQRTree::randomEmbed | ( | ) |
Embeds all skeleton graphs randomly.
|
inline |
Embeds all skeleton graphs randomly and embeds G according to the embeddings of the skeletons.
G is the graph passed to the constructor of T Definition at line 118 of file PlanarSPQRTree.h.
| void ogdf::PlanarSPQRTree::reverse | ( | node | vT | ) |
Flips the skeleton S of vT around its poles.
Reverses the order of adjacency entries of each vertex in S.
vT is an R- or P-node in T
|
protected |
Exchanges the positions of the two edges corresponding to adj1 and adj2 in skeleton of vT.
vT is a P-node in T and adj1 and adj2 are in adjacency entries in skeleton(vT) at the same owner node. Exchanges the positions of edges e1 and e2 in skeleton of vT.
vT is a P-node in T and e1 and e2 are in edges in skeleton(vT)
|
protected |
Definition at line 162 of file PlanarSPQRTree.h.