# Direct Superbubble Detection
## Theory  
### Oriented Trees and DFS-trees  
A directed graph (digraph) \(G\) consists of a vertex set \(V=V(G)\) and a set \(E=E(G)\) of directed edges such that \((u,v)\in E(G)\) implies \(u,v\in V(G)\). \(H\) is a sub-digraph of \(G\) if \(V(H)\subseteq V(G)\) and \(E(H)\subseteq E(G)\). \(G[W]\) is the subgraph induced by \(W\) if \(V(G[W])=W\subseteq V(G)\) and \((u,v)\in E(G[W])\) if and only if \((u,v)\in E(G)\) and \(u,v\in W\). An oriented tree \(T\) is a connected digraph in which there is a single vertex, called the _root_ with indegree zero, and every other vertex has in-degree one. The vertices with out-degree zero are the _leaves_. Given an edge \((u,v)\in E(T)\), we say \(u\) is the parent of \(v\), in symbols \(u=par(v)\), while \(v\) is a child of \(u\). By definition, there is a unique directed path \(p_{T}(v)\) from \(r\) to \(v\in V(T)\). The _ancestor partial order_\(\preceq\) on \(V(T)\) is defined by \(u\prec v\) if and only if \(v\) is on the path \(p_{T}(u)\). The _least common ancestor_ (lca) of two vertices \(x,y\in V(T)\) is the \(\prec\)-minimal vertex in \(p_{T}(x)\cap p_{T}(v)\). The subtree \(T(v)\) rooted in \(v\) is the subgraph of \(T\) induced by the vertex set \(\{v^{\prime}\in V|v^{\prime}\preceq v\}\), i.e., those that are reachable along the directed path that contain \(v\). We assume that \(G\) is endowed with an arbitrary order of out-neighbors for each \(v\in V(T)\). We say that \(T(u)\) is a prior subtree of \(T(v)\) when \(u\) and \(v\) are both children of a common parent \(w=par(u)=par(v)\) and \(u\) comes before \(v\) in the local ordering of the out-neighborhood of \(v\). Now, consider two vertices \(u\) and \(v\) such that \(u\) and \(v\) are incomparable w.r.t. to the ancestor order and set \(w=\operatorname{lca}(u,v)\). Note that \(u\), \(v\), and \(w\) are pairwise distinct. Let \(x\) and \(y\) be the children of \(w\) such that \(u\in T(x)\) and \(y\in T(y)\). Then, we say that \(u\) is prior to \(v\), in symbols \(u\triangleleft v\), if \(T(x)\) is a prior subtree of \(T(y)\), i.e., \(x\) comes before \(y\) in the local ordering of the out-neighborhood of \(w\). The relation \(\triangleleft\) is a partial order known as the _sibling partial order_ of \(T\). The ancestor and the sibling orders are orthogonal, i.e., for any pair of vertices, exactly one of the relations \(x=y\), \(x\prec y\), \(y\prec x\), \(x\triangleleft y\), or \(y\triangleleft x\) is true. It is well known that the two fundamental traversal orders of trees are obtained as the two natural compositions of the ancestor and the sibling partial orders. Denote by \(\rho\) and \(\pi\) the order in which vertices are reported in _preorder_ and _postorder_ traversal, respectively. We have:  
\[ \begin{split}\rho(x)<\rho(y)\text{ iff }x\triangleleft y\text{ or }y \prec x\\ \pi(x)<\pi(y)\text{ iff }x\triangleleft y\text{ or }x\prec y \end{split}  \tag{1}\]  
It follows immediately that preorder and postorder together determine the ancestor and sibling order:  
\[ \begin{split} x\triangleleft y\text{ iff }\rho(x)<\rho(y) \text{ and }\pi(x)<\pi(y)\\ x\prec y\text{ iff }\rho(x)>\rho(y)\text{ and }\pi(x)<\pi(y) \end{split}  \tag{2}\]  
Let \(G\) be a digraph. For every vertex \(r\in V(G)\), denote by \(V[r]\subseteq V(G)\) the subset of vertices that are reachable from \(r\), i.e., for which there is a directed path from \(r\) to \(x\in V[r]\). These paths can be chosen such that every \(x\in V[r]\) is reachable from \(r\) along a unique path, and hence, there is an oriented tree \(T\) with \(V(T)=V[r]\) that is a subgraph of \(G\). An oriented tree \(T\) with root \(r\) is a _search tree_ on \(G\) if there is no directed edge \((x,y)\in E(G)\) with \(x\in V(T)\) and \(y\
ot\in V(T)\). An ordered tree \(T\) is a search tree if and only \(V(T)=V[r]\) because a vertex \(y\in V(G)\setminus V(T)\) by definition cannot be reached from anywhere in \(V(T)\), and thus also not from the root, while every \(y\in V(T)\) is by definition reachable from the root \(r\).