SPQR-Trees ( SPQRTree )

Definition

The class SPQRTree maintains the arrangement of the triconnected components of a biconnected multi-graph G [HT73] as a so-called SPQR tree $\protectT$ [DT96a,DT96b]. We call G the original graph of $\protectT$. The class SPQRTree supports only the statical construction of an SPQR-tree for a given graph G, dynamic updates are not supported.

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 $\protectT$ 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$ $\protectT$ contains two types of edges: real edges, which correspond to edges in G, and virtual edges, which correspond to edges in $\protectT$ having v as an endpoint. There is a special edge e_r $\in$ G at which $\protectT$ is rooted, i.e., the root node of $\protectT$ is the node whose skeleton contains the real edge corresponding to e_r.

The reference edge of the skeleton of the root node is e_r, 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 (father(v), v).

#include < AGD/SPQRTree.h >

Types

SPQRTree::NodeType

the type of a tree node in $\protectT$.

Creation

SPQRTree	T(const leda_graph& G, bool is_map = false)
		creates an SPQR tree $\protectT$ for graph G rooted at the first edge of G. If is_map is set to true, G must be a map, i.e., for each edge e the reversal information rev(e) is set. In this case, e and rev(e) are considered as a single edge. Precondition: G is biconnected and contains at least 3 nodes, or G has exactly 2 nodes and at least 3 (resp. 6 if is_map is true) edges.
SPQRTree	T(const leda_graph& G, leda_edge e, bool is_map = false)
		creates an SPQR tree $\protectT$ for graph G rooted at edge e. If is_map is set to true, G must be a map, i.e., for each edge e the reversal information rev(e) is set. In this case, e and rev(e) are considered as a single edge. Precondition: e $\in$ G and G is biconnected and contains at least 3 nodes, or G has exactly 2 nodes and at least 3 (resp. 6 if is_map is true) edges.

Operations

a) Access operations

const leda_graph&	T.tree()	returns a reference to the tree $\protectT$.
const leda_graph&	T.original_graph()	returns a reference to the original graph G.
leda_edge	T.root_edge()	returns the edge er in G at which $\protectT$ is rooted.
leda_node	T.root_node()	returns the root node of $\protectT$.
int	T.number_of_S_nodes()	returns the number of S-nodes in $\protectT$.
int	T.number_of_P_nodes()	returns the number of P-nodes in $\protectT$.
int	T.number_of_R_nodes()	returns the number of R-nodes in $\protectT$.
leda_list<leda_node>	T.nodes_of_type(NodeType t)
		returns the list of all nodes with type t.
NodeType	T.type(leda_node v)	returns the type of node v. Precondition: v $\in$ $\protectT$
const Skeleton&	T.skeleton(leda_node v)	returns the skeleton of node v. Precondition: v $\in$ $\protectT$
leda_edge	T.skeleton_edge_src(leda_edge e)
		returns the edge in skeleton of source(e) that corresponds to tree edge e. Precondition: e $\in$ $\protectT$
leda_edge	T.skeleton_edge_tgt(leda_edge e)
		returns the edge in skeleton of target(e) that corresponds to tree edge e. Precondition: e $\in$ $\protectT$
const Skeleton&	T.skeleton_of_real(leda_edge e)
		returns the skeleton that contains the real edge e. Precondition: e $\in$ G
leda_edge	T.copy_of_real(leda_edge e)
		returns the skeleton edge that corresponds to the real edge e. Precondition: e $\in$ G
void	T.pertinent_graph(leda_node vT, PertinentGraph& Gp)
		returns the pertinent graph of tree node vT in Gp. Precondition: vT $\in$ $\protectT$

b) Update operations

leda_node	T.root_tree_at(leda_edge e)
		roots $\protectT$ at edge e and returns the new root node of $\protectT$. Precondition: e $\in$ G

Implementation

Let n be the number of vertices and m be the number of edges in G. Let n_$\protectT$ be the number of nodes in $\protectT$. The construction of an SPQR-tree $\protectT$ for graph G is implemented using the algorithm [HT73] by Hopcroft and Tarjan for computing the triconnected components of a biconnected graph and takes time $\protectO$(n + m).

The operations root_tree_at() and nodes_of_type() take time $\protectO$(n_$\protectT$). The first call of pertinent_graph() takes time $\protectO$(n + m), subsequent calls take time $\protectO$(| P|), where P is the computed pertinent graph. All other operations take constant time. The data structure uses $\protectO$(n + m) space.