|
|||
|
|
|
|||
|
|
#include <SPQRTree.h>
Public Types | |
| enum | NodeType { SNode, PNode, RNode } |
| The type of a tree node in T. More... | |
Public Member Functions | |
| virtual | ~SPQRTree () |
| virtual const Graph & | originalGraph () const =0 |
| Returns a reference to the original graph G. | |
| virtual const Graph & | tree () const =0 |
| Returns a reference to the tree T. | |
| virtual edge | rootEdge () const =0 |
| Returns the edge of G at which T is rooted. | |
| virtual node | rootNode () const =0 |
| Returns the root node of T. | |
| virtual int | numberOfSNodes () const =0 |
| Returns the number of S-nodes in T. | |
| virtual int | numberOfPNodes () const =0 |
| Returns the number of P-nodes in T. | |
| virtual int | numberOfRNodes () const =0 |
| Returns the number of R-nodes in T. | |
| virtual NodeType | typeOf (node v) const =0 |
| Returns the type of node v. | |
| virtual List< node > | nodesOfType (NodeType t) const =0 |
| Returns the list of all nodes with type t. | |
| virtual Skeleton & | skeleton (node v) const =0 |
| Returns the skeleton of node v. | |
| virtual const Skeleton & | skeletonOfReal (edge e) const =0 |
| Returns the skeleton that contains the real edge e. | |
| virtual edge | copyOfReal (edge e) const =0 |
| Returns the skeleton edge that corresponds to the real edge e. | |
| void | pertinentGraph (node v, PertinentGraph &Gp) const |
| Returns the pertinent graph of tree node v in Gp. | |
| virtual node | rootTreeAt (edge e)=0 |
| Roots T at edge e and returns the new root node of T. | |
| virtual node | rootTreeAt (node v)=0 |
| Roots T at node v and returns v. | |
| void | directSkEdge (node vT, edge e, node src) |
| void | replaceSkEdgeByPeak (node vT, edge e) |
Protected Member Functions | |
| 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. | |
| 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 Attributes | |
| 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) | |
The class SPQRTree maintains the arrangement of the triconnected components of a biconnected multi-graph G [Hopcroft, Tarjan 1973] as a so-called SPQR tree T [Fi Battista, Tamassia, 1996]. We call G the original graph of T.
Each node of the tree has an associated type (represented by SPQRTree::NodeType), which is either SNode, PNode, or RNode, and a skeleton (represented by the class Skeleton). The skeletons of the nodes of T are in one-to-one correspondence to the triconnected components of G, i.e., S-nodes correspond to polygons, P-nodes to bonds, and R-nodes to triconnected graphs.
In our representation of SPQR-trees, Q-nodes are omitted. Instead, the skeleton S of a node v in T contains two types of edges: real edges, which correspond to edges in G, and virtual edges, which correspond to edges in T having v as an endpoint. There is a special edge er in G at which T is rooted, i.e., the root node of T is the node whose skeleton contains the real edge corresponding to er.
The reference edge of the skeleton of the root node is er, the reference edge of the skeleton S of a non-root node v is the virtual edge in S that corresponds to the tree edge (parent(v),v).
Definition at line 101 of file SPQRTree.h.
| virtual ogdf::SPQRTree::~SPQRTree | ( | ) | [inline, virtual] |
Definition at line 111 of file SPQRTree.h.
| virtual const Graph& ogdf::SPQRTree::originalGraph | ( | ) | const [pure virtual] |
Returns a reference to the original graph G.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
| virtual const Graph& ogdf::SPQRTree::tree | ( | ) | const [pure virtual] |
| virtual edge ogdf::SPQRTree::rootEdge | ( | ) | const [pure virtual] |
Returns the edge of G at which T is rooted.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
| virtual node ogdf::SPQRTree::rootNode | ( | ) | const [pure virtual] |
| virtual int ogdf::SPQRTree::numberOfSNodes | ( | ) | const [pure virtual] |
| virtual int ogdf::SPQRTree::numberOfPNodes | ( | ) | const [pure virtual] |
| virtual int ogdf::SPQRTree::numberOfRNodes | ( | ) | const [pure virtual] |
Returns the type of node v.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Returns the skeleton of node v.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Returns the skeleton that contains the real edge e.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Returns the skeleton edge that corresponds to the real edge e.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
| void ogdf::SPQRTree::pertinentGraph | ( | node | v, | |
| PertinentGraph & | Gp | |||
| ) | const [inline] |
Returns the pertinent graph of tree node v in Gp.
Definition at line 170 of file SPQRTree.h.
Roots T at edge e and returns the new root node of T.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Roots T at node v and returns v.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
Definition at line 205 of file SPQRTree.h.
Definition at line 213 of file SPQRTree.h.
| virtual void ogdf::SPQRTree::cpRec | ( | node | v, | |
| PertinentGraph & | Gp | |||
| ) | const [protected, pure virtual] |
Recursively performs the task of adding edges (and nodes) to the pertinent graph Gp for each involved skeleton graph.
Implemented in ogdf::DynamicSPQRTree, and ogdf::StaticSPQRTree.
| edge ogdf::SPQRTree::cpAddEdge | ( | edge | eOrig, | |
| PertinentGraph & | Gp | |||
| ) | const [inline, protected] |
| node ogdf::SPQRTree::cpAddNode | ( | node | vOrig, | |
| PertinentGraph & | Gp | |||
| ) | const [inline, protected] |
NodeArray<node>* ogdf::SPQRTree::m_cpV [mutable, protected] |
node in pertinent graph corresponding to an original node (auxiliary member)
Definition at line 249 of file SPQRTree.h.
SList<node> ogdf::SPQRTree::m_cpVAdded [mutable, protected] |
