# Subpath Queries on Compressed Graphs: A Survey
## 3 Indexing Labeled Graphs and Regular Languages
### Further Generalizations  
As we have seen, prefix sorting generalizes quite naturally to labeled trees. There is no reason to stop here: trees are just a particular graph topology. A few years after the successful XBWT was introduced, [PERSON] et al. [72; 73; 74] showed that finite sets of circular strings, i.e., finite collections of disjoint labeled cycles, do enjoy the same _prefix-sortability_ property: the nodes of these particular labeled graphs can be arranged by the strings labeling their incoming paths, thus speeding up subsequent substring searches on the graph. Seven years later, [PERSON] et al. [75] added one more topology to the family: de Bruijn graphs. A de Bruijn graph of order \(k\) for a string \(S\) (or for a collection of strings; the generalization is straightforward) has one node for each distinct substring of length \(k\) (a \(k\)-mer) appearing in \(S\). Two nodes, representing \(k\)-mers \(s_{1}\) and \(s_{2}\), are connected if and only if they overlap by \(k-1\) characters (that is, the suffix of length \(k-1\) of \(s_{1}\) equals the prefix of the same length of \(s_{2}\)) _and_ their concatenation of length \(k+1\) is a substring of \(S\). The topology of a de Bruijn graph could be quite complex; in fact, one could define such a graph starting from the \(k\)-mers read on the paths of an arbitrary labeled graph. For large enough \(k\), the set of strings read on the paths of the original graph and the derived de Bruijn graph coincide. [PERSON] et al. [76] exploited this observation to design a tool to index pan-genomes (that is, genome collections represented as labeled graphs). Given an arbitrary input labeled graph, their GCSA (Generalized Compressed Suffix Array) builds a de Bruijn graph that is equivalent to (i.e., in which paths spell the same strings of) the input graph. While this idea allows to index arbitrary labeled graphs, in the worst case, this conversion could generate an exponentially-larger de Bruijn graph (even though they observe that, in practice, due to the particular distribution of DNA mutations, this exponential explosion does not occur too frequently in bioinformatics applications). A second, more space-efficient version of their tool [77] fixes the maximum order \(k\) of the target de Bruijn graph, thus indexing only paths of length at most \(k\) of the input graph. Finally, _repeat-free founder block graphs_[78] are yet another recent class of indexable labeled graphs.  
In this survey, we do not enter into the details of the above generalizations since they are all particular cases of a larger class of labeled graphs which will be covered in the next subsection: Wheeler graphs. As a result, the search mechanism for Wheeler graphs automatically applies to those particular graph topologies. We redirect the curious reader to the seminal work of [PERSON] et al. [50] for more details of how these graphs, as well as several other combinatorial objects (FM index of an alignment [79; 80], Positional BWT [81], wavelet matrices [82], and wavelet trees [83]), can be elegantly described in the Wheeler graphs framework. In turn, in Section 3.8, we will see that Wheeler graphs are just the \"base case\" of a larger family of prefix-sortable graphs, ultimately encompassing all labeled graphs: \(p\)-sortable graphs.