# Subpath Queries on Compressed Graphs: A Survey
## 3 Indexing Labeled Graphs and Regular Languages
### Indexing Labeled Trees
#### 3.5.4 Subpath Queries  
The LF mapping can also be used to answer counting queries. Suppose we wish to count the number of nodes reached by a path labeled with string \(\Pi[1,m]\). For example, consider the tree of Figure 7 and let \(\Pi=aa\). First, find the range \(PA[\ell,r]\) of nodes on PA reached by \(\Pi[1]\). This is easy, since characters in \(IN\) are sorted: \([\ell,r]\) is the maximal range such that \(IN[i]=\Pi[1]\) for all \(\ell\leq i\leq r\). In our example, \(\ell=2\) and \(r=5\). Now, note that \(OUT[\ell,r]\) contains the outgoing labels of all nodes reached by \(\Pi[1]\). Then, we can extend our search by one character by following all edges in \(OUT[\ell,r]\) labeled with \(\Pi[2]\). In our example, \(\Pi[2]=a\), and there are 2 edges labeled with 'a' to follow: those at positions \(OUT[2]\) and \(OUT[3]\). This requires applying the LF mapping to all those edges. Crucially, note that the LF mapping property also guarantees that the nodes we reach by following those edges form a contiguous co-lexicographic range \(PA[\ell^{\prime},r^{\prime}]\). In our example, we obtain the range \(PA[3,4]\), containing pre-order nodes 3 and 4. These are precisely the \(occ=\ell^{\prime}-r+1\) nodes reached by \(\Pi[1,2]\) (and \(occ\) is the answer to the count query for \(\Pi[1,2]\)). It is clear that the reasoning can be iterated until finding the range of all nodes reached by a pattern \(\Pi\) of any length.  
For clarity, in our discussion above, we have ignored efficiency details. If implemented as described, each extension step would require \(O(n)\) time (a linear scan of \(IN\) and \(OUT\)). It turns out that, using up-to-date data structures [69], a single character-extension step can be implemented in just \(O\left(\log\left(\frac{\log\sigma}{\log n}\right)\right)\) time! The idea is, given the range \(PA[\ell,r]\) of \(\Pi[1]\), to locate just the first and last occurrence of \(\Pi[2]\) in \(OUT[\ell,r]\). This can be implemented with a so-called _rank_ query (that is, the number of characters equal to \(\Pi[2]\) before a given position \(OUT[i]\)). We redirect the curious reader to the original articles by [PERSON] et al. [35; 68] (XBWT) and [PERSON] and [PERSON] [69] (up-to-date rank data structures) for the exquisite data structure details.  
As far as locate queries are concerned, as previously mentioned a simple strategy could be to explicitly store PA. In the above example, the result of _locate_ for pattern \(\Pi=aa\) would be the pre-order nodes \(PA[3,4]=3,\ 4\). This solution, however, uses \(n\log n\) bits on top of the XBWT. [PERSON] et al. [70] Section 5.1 and [PERSON] [49] describe a sampling strategy that solves this problem when the nodes' identifiers are DFS numbers: fix a parameter \(t\leq n\). The idea is to decompose the tree into \(\Theta(n/t)\) subtrees of size \(O(t)\), and explicitly store in \(O((n/t)\log n)\) bits the pre-order identifiers of the subtrees' roots. Then, the pre-order of any non-sampled node can be retrieved by performing a visit of a subtree using the XBWT navigation primitives. By fixing \(t=\log^{1+\epsilon}n\) for any constant \(\epsilon>0\), this strategy can compute any \(PA[i]\) (i.e., locate any pattern occurrence) in polylogarithmic time while using just \(o(n)\) bits of additional space. A more advanced mechanism [49] allows locating the DFS number of each pattern occurrence in optimal \(O(1)\) time within compressed space.