# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 3 Basic Public Transit Labeling
### Query Algorithm  
It has been shown that the above described red-te graph model, combined with 2 hc-r labeling, can be used to answer efficiently to both earliest arrival and profile queries on a timetable [13]. In particular, for answering an earliest arrival query of the form \(\textsc{ea}(s_{i},s_{j},\tau)\), the algorithm is as follows. First a vertex \(c\in\textsc{dv}[i]\) satisfying the following conditions is computed:  
1. \(time(c)\geq\tau\);
2. there is no arc \((c^{\prime},c)\) adjacent to \(c\) such that \(c^{\prime}\in\textsc{dv}[i]\) and \(time(c^{\prime})\leq time(c)\). Then, vertices in \(\textsc{Av}[j]\) are scanned to search for vertices \(v\in\textsc{Av}[j]\) such that \(\textsc{L}_{out}(c)\cap\textsc{L}_{in}(v)\
eq\emptyset\) (i.e., that are reachable). If such a vertex \(v\) exists, meaning that there exists at least a journey connecting the two stops, then \(time(v)\) is returned as the earliest arrival time, only if there is no other \(v^{\prime}\in\textsc{Av}[j]\) such that \(\textsc{L}_{out}(c)\cap\textsc{L}_{in}(v^{\prime})\
eq\emptyset\) and \(time(v^{\prime})<time(v)\) (this is easy to check as vertices are typically sorted by time). Note that the structure of the journey can be easily retrieved by applying a recursive query procedure [13; 1; 21]. To answer a profile query \(\textsc{PQ}(s_{i},s_{j},\tau,\tau^{\prime})\), instead, the algorithm needs to compute a set of non-dominated journeys, let us call it profile, by proceeding as follows. First, the routine computes a vertex \(c\in\textsc{dv}[i]\) such that:  
1. \(time(c)\geq\tau\);
2. there is no arc \((c^{\prime},c)\) adjacent to \(c\) such that \(c^{\prime}\in\textsc{dv}[i]\) and \(time(c^{\prime})\leq time(c)\). Then, vertices of \(\textsc{Av}[j]\) are scanned to search for a vertex \(v\in\textsc{Av}[j]\) such that:  
1. \(\textsc{L}_{out}(c)\cap\textsc{L}_{in}(v)\
eq\emptyset\) (i.e., \(v\) is reachable from \(c\));
2. there is no other vertex \(v^{\prime}\in\textsc{Av}[j]\) having \(time(v^{\prime})<time(v)\) and \(\textsc{L}_{out}(c)\cap\textsc{L}_{in}(v^{\prime})\
eq\emptyset\). Note that \(time(v)\) is the earliest time to arrive at stop \(s_{j}\) given the departure time \(\tau\) from \(s_{i}\). Now, since the set profile must contain all non-dominated journeys, the latest departure time that allows to reach \(s_{j}\) is also necessary to complete the computation of the query. To this aim, the algorithm computes another vertex \(c^{\prime\prime}\in\textsc{dv}[i]\) such that there is no arc \((c^{\prime\prime},c^{\prime\prime\prime})\), with \(c^{\prime\prime\prime}\in\textsc{dv}[i]\), having \(time(c^{\prime\prime})\leq time(c^{\prime\prime\prime})\) and \(\textsc{L}_{out}(c^{\prime\prime\prime})\cap\textsc{L}_{in}(v)\
eq\emptyset\). The computed time \(time(c^{\prime\prime})\) is the latest departure time that allows to reach \(s_{j}\). Hence, the algorithm adds pair \((time(c^{\prime\prime}),time(v))\) to profile (or alternately the corresponding journey, both versions of the set profile are equivalent [13]), and repeats the process above by setting the value of \(\tau\) to \(time(c^{\prime\prime})+1\). In order to obtain a very fast query time compatible with modern applications, in Reference [13] a customization of the general query approach, tailored for red-te graphs, was proposed. In particular, the main idea underlying the ptl query algorithm is to compact labels and to associate them to stops, rather than to vertices. To this aim, ptl builds a red-te (There is a one-to-one correspondence between red-te graphs and classic time-expanded graphs [2]) graph \(G\), computes a 2 hc-r labeling \(\textsc{L}\) of \(G\), and compresses it into a set of stop labels sl of \(\textsc{L}\)[13]. In detail, we have a forward stop label \(\textsc{sl}_{out}(i)\) and a backward stop label \(\textsc{sl}_{in}(i)\) for each stop \(s_{i}\in\textsc{S}\).