Skeletons ( Skeleton )

Definition

The class Skeleton maintains the skeleton S of a node v_$\protectT$ of an SPQR-tree $\protectT$. We call $\protectT$ the owner tree of S and v_$\protectT$ the corresponding tree node. Let G be the original graph of $\protectT$.

S consists of an undirected multi-graph M, which is represented as a map, i.e., for each edge e = (u, v) $\in$ M exists the reversal edge rev(e) = (v, u) $\in$ M. The two edges e and rev(e) represent one undirected edge. If the owner tree of S is a PlanarSPQRTree, then M is a planar map. The vertices in M correspond to vertices in G. The edges in M are of two types: Real edges correspond to edges in G and virtual edges correspond to tree-edges in $\protectT$ having v_$\protectT$ as an endpoint.

Let e $\in$ M be a virtual edge and e_$\protectT$ be the corresponding tree-edge. Then there exists exactly one edge e' in another skeleton S' of $\protectT$ that corresponds to e_$\protectT$ as well. We call e' the twin edge of e.

#include < AGD/Skeleton.h >

Creation

Skeletons are created by the constructor of SPQRTree and can be accessed with the skeleton() function of SPQRTree.

Operations

const SPQRTree&	S.owner()	returns the owner tree $\protectT$.
leda_node	S.tree_node()	returns the corresponding node in the owner tree $\protectT$ to which S belongs.
leda_edge	S.reference_edge()	returns the reference edge of S in M. The reference edge is a real edge if S is the skeleton of the root node of $\protectT$, and a virtual edge otherwise.
const leda_graph&	S.get_graph()	returns a reference to the skeleton graph M.
leda_node	S.original(leda_node v)	returns the vertex in the original graph G that corresponds to v. Precondition: v $\in$ M.
bool	S.is_virt(leda_edge e)	returns true iff e is a virtual edge. Precondition: e $\in$ M
leda_edge	S.real_edge(leda_edge e)	returns the real edge that corresponds to skeleton edge e if e is not virtual, nil otherwiese. Precondition: e $\in$ M
leda_edge	S.tree_edge(leda_edge e)	returns the tree edge which is associated with skeleton edge e if e is virtual, nil otherwise. Precondition: e $\in$ M
leda_edge	S.twin_edge(leda_edge e)	returns the twin edge of skeleton edge e if e is virtual, nil otherwise. Precondition: e $\in$ M.
leda_node	S.twin_tree_node(leda_edge e)
		returns the tree node in $\protectT$ containing the twin edge of skeleton edge e if e is virtual, nil otherwise. Precondition: e $\in$ M.

Implementation

All operations take constant time. The data structure uses $\protectO$(| M|) space.