# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
Hence, at the end of Algorithm 2, \(\textsc{L}\) is a 2 hc-sp labeling for \(G\). Finally, note that the algorithm described in Section 6.6 applies the definition of extended stop labeling, by updating the entry of a stop with the proper hub vertices, times and distances values. Hence, after the execution of algorithm described in Section 6.6, e-sl is still an extended stop labeling of l.

### On Handling Arc Removals or Arc Weight Increases by dag-decpll

In this section, we provide an overview on how to extend dag-decpll to handle arc removals and arc weight increases. In details, given an arc \((u,v)\) to be removed from \(G\), then to update a 2 hc-sp labeling l via dag-decpll, we model the removal as the removal of a virtual vertex, say \(x^{\prime}\), having arcs \((u,x^{\prime})\) and \((x^{\prime},v)\) in \(G\). In particular, we remove \((u,v)\) from \(G\) and run the dag-decpll procedure by considering \(x^{\prime}\) as the vertex to be removed. It is easy to observe that this has the same effect of updating l after the removal of \((u,v)\) from \(G\). It is important to mention that as \(x^{\prime}\) is a virtual vertex in \(G^{\prime}\), therefore no label set exists that is associated to \(x^{\prime}\). To handle an arc weight increase for a generic arc \((u,v)\), as a first step, we remove \((u,v)\) and then update l using the approach mentioned above. We then insert a new arc \((u,v)\) with the updated arc weight value, and run incpll which update l by possibly adding new label entries to l.

### Compacting a Multi-Criteria Public Transit Labeling

In this section, we propose an extension of the notion of stop labeling sl, named _extended stop labeling_ (shortly, e-sl), suited for answering to multi-criteria queries. In particular, given a 2 hc-sp labeling l of a wred-te graph \(G\), we associate to each stop \(s_{i}\in\mathbb{S}\) two sets, namely a _forward stop label_\(\textsc{e-sl}_{out}(i)\) and a _backward stop label_\(\textsc{e-sl}_{in}(i)\) where, in this case, the forward (backward, respectively) stop label is a list of _triples_ of the form \((v,stoptime_{i}(v),transf_{i}(v))\) where

* \(v\) is a _hub vertex_ reachable from (that reaches, respectively) at least one vertex in \(\textsc{dv}[i]\) (\(\textsc{av}[i]\), respectively);
* \(stoptime_{i}(v)\) encodes the latest departure (earliest arrival, respectively) time to reach hub vertex \(v\) from one vertex in \(\textsc{dv}[i]\) (to reach a vertex in \(\textsc{Av}[i]\) from vertex \(v\), respectively);
* \(transf_{i}(v)\) encodes the minimum number of transfers to reach hub vertex \(v\) from one vertex in \(\textsc{dv}[i]\) (to reach a vertex in \(\textsc{av}[i]\) from vertex \(v\), respectively). Our approach to compact a labeling for multi-criteria queries is as follows. To compute \(\textsc{e-sl}_{out}(i)\), we process vertices in \(\textsc{dv}[i]\) in decreasing order with respect to departure time. In particular, let \(v\) be the vertex under consideration. Then, for each \((h,\delta_{vh})\in\textsc{l}_{out}(v)\), we add \((h,stoptime_{i}(h)=time(v),transf_{i}(h)=\delta_{vh})\) to \(\textsc{e-sl}_{out}(i)\) only if one of the following conditions hold:

1. there is no entry \((h,stoptime_{i}(h),transf_{i}(h))\) in \(\textsc{e-sl}_{out}(i)\);
2. there exists an entry \((h,stoptime_{i}(h),transf_{i}(h))\) in \(\textsc{e-sl}_{out}(i)\) but \(\delta_{vh}<\textsc{mt}\) where \[\textsc{mt}=\min_{(h,stoptime_{i}(h),transf_{i}(h))\in\textsc{e-sl}_{out}(i)} transfers_{i}(h).\]

To compute \(\textsc{e-sl}_{in}(i)\), symmetrically, we process vertices in \(\textsc{av}[i]\) in increasing order with respect to arrival times.