# Subpath Queries on Compressed Graphs: A Survey
## 1 Introduction  
Consider the classic algorithmic problem of finding the occurrences of a particular string \(\Pi\) (a _pattern_) in a text \(\mathcal{T}\). Classic algorithms, such as [PERSON]'s [1], Boyer-Moore-Galli's [2], [PERSON]'s [3], and [PERSON]'s [4], are optimal (the first only in the expected case) when both the text and the pattern are part of the query: those algorithms scan the text and find all occurrences of the pattern in linear time. What if the text is known _beforehand_ and only the patterns to be found are part of the query? In this case, it is conceivable that _preprocessing_\(\mathcal{T}\) off-line into a _fast_ and _small_ data structure (an _index_) might be convenient over the above on-line solutions. As it turns out, this is exactly the case. The _full-text indexing_ problem (where _full_ refers to the fact that we index the full set of \(\mathcal{T}\)'s substrings) has been studied for over forty years and has reached a very mature and exciting point: modern algorithmic techniques allow us to build text indexes taking a space close to that of the compressed text and able to count/locate occurrences of a pattern inside it in time proportional to the pattern's length. Note that we have emphasized two fundamental features of these data structures: query _time_ and index _space_. As shown by decades of research on the topic, these two dimensions are, in fact, strictly correlated: the structure exploited to compress text is often the same that can be used also to support fast search queries on it. Recent research has taken a step forward, motivated by the increasingly complex structure of modern massive datasets: texts can be viewed as directed labeled path graphs and compressed indexing techniques can be generalized to more complex graph topologies. While compressed text indexing has already been covered in the literature in excellent books [5; 6] and surveys [7; 8; 9], the generalizations of these advanced techniques to labeled graphs, dating back two decades, lack a single point of reference despite having reached a mature state-of-the-art. The goal of this survey is tointroduce the (non-expert) reader to the fascinating field that studies compressed indexes for labeled graphs. We start, in Section 2, with a quick overview of classical compressed text indexing techniques: compressed suffix arrays and indexes for repetitive collections. This section serves as a self-contained warm-up to fully understand the concepts contained in the next sections. Section 3 starts with an overview of the problem of compressing graphs, with a discussion on known lower bounds to the graph indexing problem, and with preliminary solutions based on hypertext indexing. We then introduce prefix sorting and discuss its extensions to increasingly complex graph topologies. Section 3.5 is devoted to the problem of indexing trees, the first natural generalization of classical labeled paths (strings). Most of the discussion in this section is spent on the eXtended Burrows-Wheeler Transform (XBWT), a tree transformation reflecting the co-lexicographic order of the root-to-node paths on the tree. We discuss how this transformation naturally supports subpath queries and compression by generalizing the ideas of Section 2. Section 3.6 adds further diversity to the set of indexable graph topologies by discussing the cases of sets of disjoints cycles and de Bruijn graphs. All these cases are finally generalized in Section 3.7 with the introduction of _Wheeler graphs_, a notion capturing the idea of totally-sortable labeled graph. This section discusses the problem of compressing and indexing Wheeler graphs, as well as recognizing and sorting them. We also spend a paragraph on the fascinating bridge that this technique builds between compressed indexing and regular language theory by briefly discussing the elegant properties of _Wheeler languages_: regular languages recognized by finite automata in which state transition is a Wheeler graph.