# Subpath Queries on Compressed Graphs: A Survey
## 3 Indexing Labeled Graphs and Regular Languages
### p-Sortable Automata  
Despite its power, the Wheeler graph framework does not allow to index and compress _any_ labeled graph: it is easy to come up with arbitrarily large Wheeler graphs that lose their Wheeler property after the addition of just _one_ edge. Does this mean that such an augmented graph cannot be indexed efficiently? clearly not, since it would be sufficient to add a small \"patch\" (keeping track of the extra edge) to the index of the underlying Wheeler subgraph in order to index it. As another \"unsatisfying\" example, consider the union \(\mathcal{L}=\mathcal{L}_{1}\cup\mathcal{L}_{2}\) of two Wheeler languages \(\mathcal{L}_{1}\) and \(\mathcal{L}_{2}\). In general, \(\mathcal{L}\) is not a Wheeler language [88]. However, \(\mathcal{L}\) can be easily indexed by just keeping two indexes (of two Wheeler automata recognizing \(\mathcal{L}_{1}\) and \(\mathcal{L}_{2}\)), _with no asymptotic slowdown_ in query times! The latter example is on the right path to a solution of the problem. Take two Wheeler automata \(\mathcal{A}_{1}\) and \(\mathcal{A}_{2}\) recognizing two Wheeler languages \(\mathcal{L}_{1}\) and \(\mathcal{L}_{2}\), respectively, such that \(\mathcal{L}=\mathcal{L}_{1}\cup\mathcal{L}_{2}\) is not Wheeler. The union automaton \(\mathcal{A}_{1}\cup\mathcal{A}_{2}\) (obtained by simply merging the start states of \(\mathcal{A}_{1}\) and \(\mathcal{A}_{2}\)) is a nondeterministic automaton recognizing \(\mathcal{L}\). Taken individually, the states of \(\mathcal{A}_{1}\) and \(\mathcal{A}_{2}\) can be sorted in two total orders. However, taken as a whole, the two sets of states do not admit a total co-lexicographic order (which would imply that \(\mathcal{L}\) is Wheeler). The solution to this riddle is to abandon total orders in favor of _partial orders_[89]. A partial order \(\leq\) on a set \(V\) (in our case, the set of the automaton's states) is a reflexive, antisymmetric and transitive relation on \(V\). In a partial order, two elements \(u,v\) either are comparable, in which case \(u\leq v\) or \(v\leq u\) hold (both hold only if \(u=v\)), or are not comparable, in which case neither \(u\leq v\) nor \(v\leq u\) hold. The latter case is indicated as \(u\parallel v\). Our co-lexicographic partial order is defined as follows. Let \(a,a^{\prime}\) be two characters labeling edges \((u,u^{\prime})\) and \((v,v^{\prime})\), respectively. We require the following properties:  
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^{\prime}<v^{\prime}\), then \(u\leq v\). Note that, differently from the definition of Wheeler order (Section 3.7), the implication of (iii) follows the edges _backwards_. As it turns out, \(\leq\) is indeed a partial order and, as we show in the next subsections, it allows generalizing the useful properties of Wheeler graphs to arbitrary topologies. A convenient representation for any partial order is a Hasse diagram: a directed acyclic graph where we draw the elements of the order from the smallest (bottom) to largest ones (top), and two elements are connected by an edge \((u,v)\) if and only if \(u\leq v\). See Figure 12 for an example. The lower bounds discussed in Section 3.2 tell us that indexed pattern matching on graphs cannot be solved faster than quadratic time in the worst case. In particular, this means that our generalization of Wheeler graphs cannot yield an index answering subpath queries in linear time. In fact, there is a catch: the extent to which indexing and compression can be performed efficiently is proportional to the similarity of the partial order \(\leq\) to a total one. As it turns out, the correct measure of similarity to consider is the _order's width_: the minimum number \(p\) of totally-ordered chains (subsets of states) into which the set of states can be partitioned. Figure 12 makes it clear that the states of the automaton can be divided into \(p=2\) totally-ordered subsets.