# Subpath Queries on Compressed Graphs: A Survey
## 3 Indexing Labeled Graphs and Regular Languages
### Indexing Labeled Trees
#### 3.5.3 Inverting the XBWT  
As it turns out, the tree can be reconstructed from just \(OUT\). To prove this, we show that the XBWT representation can be used to perform a tree visit. First, we introduce the key property at the core of the XBWT: edges' labels appear in the same order in \(IN\) and \(OUT\), that is, the \(i\)-th occurrence (counting from left to right) of character \(c\in\Sigma\) in \(IN\) corresponds to the same edge of the \(i\)-th occurrence \(c\) in \(OUT\) (the order of characters inside each multi-set of \(OUT\) is not relevant for the following reasoning to work). For example, consider the fourth 'a' in \(IN\), appearing at \(IN[5]\). This label corresponds to the incoming edge of node \(7\), that is, to edge \((6,7)\). The fourth occurrence of 'a' in \(OUT\) appears in \(OUT[6]\), corresponding to the outgoing edges of node \(6\). By following the edge labeled 'a' from node \(6\), we reach exactly node \(7\), that is, this occurrence of 'a' labels edge \((6,7)\). Why does this property hold? precisely because we are sorting nodes co-lexicographically. Take two nodes \(u<v\) such that \(\lambda(u)=\lambda(v)=a\), for example, \(u=2\) and \(v=7\) (note that \(<\) indicates the co-lexicographic order, not pre-order). Since \(u<v\), the \(a\) labeling edge \((\pi(u),u)\) precedes the \(a\) labeling edge \((\pi(v),v)\) in sequence \(IN\), where \(\pi(u)\) indicates the parent of \(u\) in the tree. In the example, these are the two 'a's appearing at \(IN[2]\) and \(IN[5]\). Let \(\alpha_{u}\) and \(\alpha_{v}\) be the two strings labeling the two paths from the root to \(u\) and \(v\), respectively. In our example, \(\alpha_{2}=\$a\) and \(\alpha_{7}=\$ba\) (note that we prepend the artificial incoming label of the root). By the very definition of our co-lexicographic order, \(u<v\) if and only if \(\alpha_{u}<\alpha_{v}\). Note that we can write \(\alpha_{u}=\alpha_{\pi(u)}\cdot a\) and \(\alpha_{v}=\alpha_{\pi(v)}\cdot a\). Then, \(\alpha_{u}<\alpha_{v}\) holds if and only if \(\alpha_{\pi(u)}<\alpha_{\pi(v)}\), i.e., if and only if \(\pi(u)<\pi(v)\). In our example, \(\alpha_{\pi(2)}=\alpha_{1}=\$<\$b=\alpha_{6}=\alpha_{\pi(7)}\); thus, it must hold \(1=\pi(2)<\pi(7)=6\) (which, in fact, holds in the example). This means that the \(a\) labeling edge \((\pi(u),u)\) comes before the \(a\) labeling edge \((\pi(v),v)\) also in sequence \(OUT\). In our example, those are the two 'a' contained in \(OUT[1]\) and \(OUT[6]\). We finally obtain our claim: equally-labeled edges appear in the same relative order in \(IN\) and \(OUT\).  
The XBWT is a generalization to labeled trees of a well-known string transform--the Burrows-Wheeler transform (BWT) [20]--described for the first time in 1994 (the BWT is precisely sequence \(OUT\) of a path tree (To be precise, the original BWT used the symmetric lexicographic order of the string's suffixes). Its corresponding index, the FM-index [16] was first described by [PERSON] and [PERSON] in 2000. The property we just described--allowing the mapping of characters from \(IN\) to \(OUT\)--is the building block of the FM-index and takes the name \(LF\)_mapping_. The LF mapping can be used to perform a visit of the tree using just \(OUT\). First, note that \(OUT\) fully specifies \(IN\): the latter is a sorted list of all characters  
Figure 8: Prefix array (PA) and sequences \(IN\) and \(OUT\) forming the eXtended Burrows-Wheeler Transform (XBWT). \(IN\) (incoming labels) is the sequence of characters labeling the incoming edge of each node, while \(OUT\) (outgoing labels) is the sequence of multi-sets containing the characters labeling the outgoing edges of each node.  
appearing in \(OUT\), plus character $. Start from the virtual incoming edge of the root, which appears always in \(IN[1]\). The outgoing labels of the roots appear in \(OUT[1]\). Using the LF property, we map the outgoing labels of the root to sequence \(IN\), obtaining the locations in PA of the successors of the root. The reasoning can be iterated, ultimately leading to a complete visit of the tree.