# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
In the pseudocode, we denote by \(N^{G}_{\mathit{out}}(v)\) (\(N^{G}_{\mathit{in}}(v)\), respectively) the out-neighbors (in-neighbors, respectively) of the generic vertex \(v\) of graph \(G\). ### Forward Update

The procedure processes vertices in \(\textsc{left}_{x}\) in decreasing order with respect to a topological ordering \(\textsc{Tof}\ G\). Assume we are processing a given vertex, say \(v\). If \(v\) has a maximum value in \(T\)s compared to that for the rest of vertices in \(\textsc{left}_{x}\), then we know by the definition of \(T\)that no vertex in \(N^{G^{\prime}}_{out}(v)\) belongs to \(\textsc{left}_{x}\). We also know that a label entry \((h,\delta_{ub})\in\textsc{l}_{out}(v)\) may be affected if \(h=x\) and \(h\in\textsc{right}_{x}\) (see Corollary 1). Moreover, it can be easily seen that, for any vertex \(u\in N^{G^{\prime}}_{out}(v)\) with \(u\
otin\textsc{left}_{x}\), no label entry in \(\textsc{l}_{out}(u)\) is affected by the removal of \(x\) from \(G\) (see Corollary 2). Additionally, for the rest of cases where \(u\in N^{G^{\prime}}_{out}(v)\) and \(u\in\textsc{left}_{x}\), by definition of \(T\), \(u\) must have been processed before \(v\). The routine hence proceeds by removing all affected label entries from \(\textsc{l}_{out}(v)\). Notice that, after removing such label entries, we can retrieve the correct distance in the new graph \(d_{G^{\prime}}(v,w)\) for any vertex \(w\in V^{\prime}\) such that \(w\
otin\textsc{right}_{x}\), by performing a query \(\textsc{query}(v,w,\textsc{l})\), since the path induced by the labeling does not contain \(x\) in these cases. However, to guarantee that the cover property of \(\textsc{l}\) is satisfied with respect to all pairs of vertices of the new graph \(G^{\prime}\), we may need to add new label entries to \(\textsc{l}_{out}(v)\) and possibly to backward label sets of vertices in \(\textsc{right}_{x}\). To this aim, we exploit the notion of _superset of hubs_, originally presented in Reference [24], and incorporate it in the dag-decpll update procedure after suitably adapting it in order to make it compatible with 2 hc-sp labeling. In more details, the superset of hubs for a forward label \(\textsc{l}_{out}(v)\), denoted by \(\textsc{c}_{out}(v)\), is defined as the union of the hub vertices, belonging to \(\textsc{right}_{x}\), in all forward label sets of all vertices in \(N^{G^{\prime}}_{out}(v)\). More formally:

\[\textsc{c}_{out}(v)=\bigcup_{\forall u\in N^{G^{\prime}}_{out}(v)}\{k\,|\,(k, \delta_{uk})\in\textsc{l}_{out}(u)\wedge h\in\textsc{right}_{x}\}.\]

In the case of reachability labeling one can exploit the notion of superset of hubs to update the reachability properties of a given vertex \(v\): if a neighbor of \(v\) is reachable from a given vertex, so is \(v\). Here, instead, we exploit it to simplify the update of the distances stored in the label entries. In details, since we are updating a 2 hc-sp labeling, to achieve the update of the label of a given vertex \(v\), we need to compute \(d_{G^{\prime}}(v,h)\) for all \(h\in\textsc{c}_{out}(v)\) and use it to update entries \(\delta_{ub}\in\textsc{l}_{out}(v)\) so that they correspond to distances in the new graph. One way to do this is to execute a baseline algorithm for computing shortest paths in DAGs. However, even if it is well known that this costs linear time with respect to the graph size, this can easily become a computational bottleneck when dealing with medium to large scale graphs, since we need to compute many distances during an update. To overcome this limit, we propose a hybrid approach that exploits \(G^{\prime}\) and \(\textsc{l}\) to compute distances faster. In more details, it is easy to observe that for any \(h\in\textsc{c}_{out}(v)\) and for any \(w\in V^{\prime}\) such that\(w\
otin\textsc{left}_{x}\), the correct distance \(d_{G^{\prime}}(w,h)\) can be computed via a query on the labeling \(\textsc{query}(w,h,\textsc{L})\), since the path induced by the labeling from \(w\) to \(h\) cannot include \(x\) (see Lemma 3).