# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 3 Basic Public Transit Labeling
### Reachability Labeling  
Given a graph \(G=(V,A)\), any approach for computing a so-called _2-Hop-Cover_ reachability labeling (2 hc-r labeling, for short) l of \(G\) associates two labels to each vertex \(v\in V\), namely a backward label \(\mathsf{L}_{in}(v)\) and a forward label \(\mathsf{L}_{out}(v)\), where a label is a subset of the vertices of \(G\)[26]. In particular, for any two vertices \(u,v\in V\), \(\mathsf{L}_{out}(u)\cap\mathsf{L}_{in}(v)\
eq\emptyset\) if and only if there exists a path from \(u\) to \(v\) in \(G\). Therefore, any query on the reachability between two vertices \(u,v\in V\) can be answered by a linear scan of the two labels of \(u\) and \(v\) only [26]. Vertices \(\{h:h\in\mathsf{L}_{out}(u)\cap\mathsf{L}_{in}(v)\}\) are called _hub vertices_ for pair \(u,v\), and each element in said set is a vertex lying on a path from \(u\) to \(v\) in \(G\).  
The size of a 2 hc-r labeling is given by the sum of the sizes of the label entries and it is known that computing a 2 hc-r labeling of minimum size is NP-Hard [26]. However, numerous approaches have been presented to heuristically improve both the time to compute the labeling and its size [24; 27; 28]. Among them, the one in Reference [24], called butterfly, has been shown to exhibit superior performance for DAGs and is suited for dynamic graphs, that is, the authors also provide a dynamic algorithm that is able to update the 2 hc-r labeling l of a graph \(G\) to reflect changes occurring on \(G\) itself. In particular, given a graph \(G\), a 2 hc-r labeling l of \(G\), and an update operation occurring  
Figure 1: An example of red-te graph for a timetable with three stops \(X\), \(Y\) and \(Z\), five trips \(\{a,b,c,d,e\}\). Details of the timetable are reported in Table 1. Each ellipse groups together vertices in \(\textsc{dv}[i]\cup\textsc{av}[i]\) for each stop \(i\in\{X,Y,Z\}\), where vertices on the left side of each group, filled in light blue, are arrival vertices, while vertices on the right side, filled in light yellow, are departure vertices. The latter are connected to the former via transfer arcs. The numbers within vertices show the associated time, where the minimum transfer time is assumed to be, for the sake of simplicity, \(\textsc{mtt}_{X}=\textsc{mtt}_{Y}=\textsc{mtt}_{Z}=5\) min for all stops. Departure and arrival vertices of connections of the same trip are highlighted via a same border color. Bypass arcs are drawn in green while consecutive departure vertices of a same set \(\textsc{dv}[i]\) are connected via waiting arcs.  
on \(G\), the algorithm is able to compute another labeling \(\textsc{L}^{\prime}\) that is a 2 hc-r labeling for \(G^{\prime}\), where \(G^{\prime}\) is the graph obtained by applying the update on \(G\).  
Note that, in this scenario, updates can be incremental (decremental, respectively), if they are additions (removals, respectively) of a vertex/arc. Throughout the paper, we denote by \(\textsc{INC-BU}(G,\textsc{L},v)\) (\(\textsc{dec-BU}(G,\textsc{L},v)\), respectively) the result of the application of the dynamic algorithm of Reference [24] to the labeling \(\textsc{L}\) of a graph \(G\) to handle an incremental (decremental, respectively) operation occurring on vertex \(v\) (we refer the reader to Reference [24] for more details on the above dynamic algorithms).