# Subpath Queries on Compressed Graphs: A Survey
## 3 Indexing Labeled Graphs and Regular Languages
### Wheeler Graphs  
In 2017, [PERSON] et al. [50] generalized the principle underlying the approaches described in the previous sections to all labeled graphs in which nodes can be sorted co-lexicographically in a total order. They called such objects _Wheeler graphs_ in honor of [PERSON], one of the two inventors of the ubiquitous Burrows-Wheeler transform [20] that today stands at the heart of the most successful compressors and compressed text indexes.  
Recall that, for convenience, we treat the special (not too restrictive) case of labeled graphs corresponding to the state transition of finite automata. Indexing finite automata allows us to generalize the ideas behind suffix arrays to (possibly infinite) sets of strings: all the strings read from the source to any of the automaton's final states. Said otherwise, an index for a finite automaton is capable of recognizing the substring closure of the underlying regular language. Consider the following regular language:  
\[\mathcal{L}=(\epsilon|aa)b(ab|b)^{*},\]  
as well as consider the automaton recognizing \(\mathcal{L}\) depicted in Figure 9.  
Let \(u\) be a state, and denote with \(I_{u}\) the (possibly infinite) set of all strings read from the source to \(u\). Following the example reported in Figure 9, we have \(I_{q_{1}}=\{a\}\), \(I_{q_{2}}=\{b,bb,bab,babb,aab,\dots\}\), and \(I_{q_{3}}=\{aa,aaba,aabba,\dots\}\). Intuitively, if the automaton is a DFA, then we are going to sort its states in such a way that two states are placed in the order \(u<v\) if and only if all the strings in \(I_{u}\) are co-lexicographically smaller than all the strings in \(I_{v}\) (for NFAs, the condition is slightly more involved as those sets can have a nonempty intersection). Note that, at this point of the discussion, it is not yet clear that such an ordering _always_ exists (in fact, we will see that it does not); however, from the previous subsections, we know that particular graph topologies (in particular, paths, cycles, trees, and de Bruijn graphs) do admit a solution to this sorting problem. The legitimate question, tackled for the first time in [PERSON] et al.'s work, is: what is the largest graph family admitting such an ordering?  
Let \(a,a^{\prime}\) be two characters labeling edges \((u,u^{\prime})\) and \((v,v^{\prime})\), respectively. We require the following three _Wheeler properties_[50] for our ordering \(\leq\):  
1. all states with in-degree zero come first in the ordering,
2. if \(a<a^{\prime}\), then \(u^{\prime}<v^{\prime}\), and
3. if \(a=a^{\prime}\) and \(u<v\), then \(u^{\prime}\leq v^{\prime}\).  
It is not hard to see that (i)-(iii) generalize the familiar co-lexicographic order among the prefixes of a string to labeled graphs. In this generalized context, we deal with prefixes of the recognized language, i.e., with the strings labeling paths connecting the source state with any other state. Note also that rule (ii) implicitly requires that all labels entering a state must be equal. This is not a severe restriction: at the cost of increasing the number of states by a factor \(\sigma\), any automaton can be transformed into an equivalent one with this property [65]. Figure 10 depicts the automaton of Figure 9 after having ordered (left-to  
Figure 9: Automaton recognizing the regular language \(\mathcal{L}=(\epsilon|aa)b(ab|b)^{*}\).  
right) the states according to the above three Wheeler properties.  
An ordering \(\leq\) satisfying Wheeler properties (i)-(iii) is called a _Wheeler order_. Note that a Wheeler order, when it exists, is always total (this will become important in Section 3.8). An automaton (or a labeled graph) is said to be Wheeler if its states admit at least one Wheeler order.