Linear-time implementation of dynamic SPQR-trees. More...
#include <ogdf/decomposition/DynamicSPQRTree.h>
Public Member Functions | |
| 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 () | |
| const Graph & | originalGraph () const |
| Returns a reference to the original graph G. | |
| const Graph & | tree () const |
| Returns a reference to the tree T. | |
| edge | rootEdge () const |
| Returns the edge of G at which T is rooted. | |
| node | rootNode () const |
| Returns the root node of T. | |
| int | numberOfSNodes () const |
| Returns the number of S-nodes in T. | |
| int | numberOfPNodes () const |
| Returns the number of P-nodes in T. | |
| int | numberOfRNodes () const |
| Returns the number of R-nodes in T. | |
| NodeType | typeOf (node v) const |
| Returns the type of node v. | |
| List< node > | nodesOfType (NodeType t) const |
| Returns the list of all nodes with type t. | |
| 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. | |
| Skeleton & | skeleton (node v) const |
| Returns the skeleton of node v. | |
| const Skeleton & | skeletonOfReal (edge e) const |
| Returns the skeleton that contains the real edge e. | |
| edge | copyOfReal (edge e) const |
| Returns the skeleton edge that corresponds to the real edge e. | |
| 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. | |
| node | rootTreeAt (edge e) |
| Roots T at edge e and returns the new root node of T. | |
| node | rootTreeAt (node v) |
| Roots T at node v and returns v. | |
| edge | updateInsertedEdge (edge e) |
| Updates the whole data structure after a new edge e has been inserted into G. | |
| node | updateInsertedNode (edge e, edge f) |
| Updates the whole data structure after a new vertex has been inserted into G by splitting an edge into e and f. | |
Protected Member Functions | |
| void | init (edge e) |
| Initialization (called by constructors). | |
| DynamicSkeleton & | createSkeleton (node vT) const |
| Creates the skeleton graph belonging to a given vertex vT of T. | |
| void | cpRec (node v, PertinentGraph &Gp) const |
| Recursively performs the task of adding edges (and nodes) to the pertinent graph Gp for each involved skeleton graph. | |
Protected Attributes | |
| 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) | |
| NodeArray< node > | m_mapV |
| temporary array used by createSkeleton() | |
Friends | |
| class | DynamicSkeleton |
Linear-time implementation of dynamic SPQR-trees.
The class DynamicSPQRTree 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. The class DynamicSPQRTree supports the statical construction of an SPQR-tree for a given graph G, and supports dynamic updates, too.
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 DynamicSkeleton). 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 103 of file DynamicSPQRTree.h.
| ogdf::DynamicSPQRTree::DynamicSPQRTree | ( | Graph & | G | ) | [inline] |
Creates an SPQR tree T for graph G rooted at the first edge of G.
Definition at line 78 of file DynamicSPQRTree.h.
Creates an SPQR tree T for graph G rooted at the edge e.
Definition at line 85 of file DynamicSPQRTree.h.
| ogdf::DynamicSPQRTree::~DynamicSPQRTree | ( | ) |
Returns the skeleton edge that corresponds to the real edge e.
Definition at line 154 of file DynamicSPQRTree.h.
| void ogdf::DynamicSPQRTree::cpRec | ( | node | v, | |
| PertinentGraph & | Gp | |||
| ) | const [inline, protected] |
Recursively performs the task of adding edges (and nodes) to the pertinent graph Gp for each involved skeleton graph.
Definition at line 216 of file DynamicSPQRTree.h.
| DynamicSkeleton& ogdf::DynamicSPQRTree::createSkeleton | ( | node | vT | ) | const [protected] |
Creates the skeleton graph belonging to a given vertex vT of T.
Finds the shortest path between the two sets of vertices of T which s and t of G belong to.
Definition at line 131 of file DynamicSPQRTree.h.
| void ogdf::DynamicSPQRTree::init | ( | edge | e | ) | [protected] |
Initialization (called by constructors).
Returns the list of all nodes with type t.
| int ogdf::DynamicSPQRTree::numberOfPNodes | ( | ) | const [inline] |
Returns the number of P-nodes in T.
Definition at line 113 of file DynamicSPQRTree.h.
| int ogdf::DynamicSPQRTree::numberOfRNodes | ( | ) | const [inline] |
Returns the number of R-nodes in T.
Definition at line 116 of file DynamicSPQRTree.h.
| int ogdf::DynamicSPQRTree::numberOfSNodes | ( | ) | const [inline] |
Returns the number of S-nodes in T.
Definition at line 110 of file DynamicSPQRTree.h.
| const Graph& ogdf::DynamicSPQRTree::originalGraph | ( | ) | const [inline] |
Returns a reference to the original graph G.
Reimplemented from ogdf::BCTree.
Definition at line 98 of file DynamicSPQRTree.h.
| edge ogdf::DynamicSPQRTree::rootEdge | ( | ) | const [inline] |
Returns the edge of G at which T is rooted.
Definition at line 104 of file DynamicSPQRTree.h.
| node ogdf::DynamicSPQRTree::rootNode | ( | ) | const [inline] |
Returns the root node of T.
Definition at line 107 of file DynamicSPQRTree.h.
Roots T at node v and returns v.
Roots T at edge e and returns the new root node of T.
Returns the skeleton of node v.
Definition at line 137 of file DynamicSPQRTree.h.
Returns the virtual edge in the skeleton of w that corresponds to the tree edge between v and w.
Definition at line 166 of file DynamicSPQRTree.h.
Returns the skeleton that contains the real edge e.
Definition at line 148 of file DynamicSPQRTree.h.
| const Graph& ogdf::DynamicSPQRTree::tree | ( | ) | const [inline] |
Returns a reference to the tree T.
Definition at line 101 of file DynamicSPQRTree.h.
Returns the type of node v.
Definition at line 122 of file DynamicSPQRTree.h.
Updates the whole data structure after a new edge e has been inserted into G.
Reimplemented from ogdf::DynamicSPQRForest.
Updates the whole data structure after a new vertex has been inserted into G by splitting an edge into e and f.
Reimplemented from ogdf::DynamicSPQRForest.
friend class DynamicSkeleton [friend] |
Definition at line 68 of file DynamicSPQRTree.h.
NodeArray<node> ogdf::DynamicSPQRTree::m_mapV [mutable, protected] |
temporary array used by createSkeleton()
Definition at line 231 of file DynamicSPQRTree.h.
edge ogdf::DynamicSPQRTree::m_rootEdge [protected] |
edge of G at which T is rooted
Definition at line 227 of file DynamicSPQRTree.h.
NodeArray<DynamicSkeleton*> ogdf::DynamicSPQRTree::m_sk [mutable, protected] |
pointer to skeleton of a node in T
Definition at line 229 of file DynamicSPQRTree.h.
EdgeArray<edge> ogdf::DynamicSPQRTree::m_skelEdge [mutable, protected] |
copies of real and virtual edges in their skeleton graphs (invalid, if the skeleton does not actually exist)
Definition at line 230 of file DynamicSPQRTree.h.