# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
After completing the above, we perform the insertion phase, where we check whether we need to insert back into \(G\) some vertices and arcs, with updated associated times, to let the graph be a red-te graph of the updated timetable. This might require to execute algorithm inc-bu to add label entries induced by such insertions. Once both \(G\) and \(L\) have been updated, we reflect the changes onto the stop labeling via a suited routine (see Algorithm 3). In the next sections we describe in detail the above sub-routines. ### Removal Phase

In the negative case, we do not remove \(v_{d}^{c_{j}}\) since, after updating \(\mathit{time}(v_{d}^{c_{j}})\), all vertices of \(\textsc{dv}[s]\) do not violate the time inequalities imposed by waiting arcs. In the affirmative case (see Line 9), instead, \(v_{d}^{c_{j}}\) must be removed and the arcs adjacent to vertices in \(\textsc{dv}[s]\) and \(\textsc{av}[s]\) must be rewired. In particular, we proceed as follows: if there exists some waiting arc \((v_{d}^{c_{j}},v)\) in \(A\), that is, there is some other \(v\in\textsc{dv}[s]\) whose time was larger than or equal to that of \(v_{d}^{c_{j}}\) before the delay), and \(\mathit{time}(v_{d}^{c_{j}})>\mathit{time}(v)\) (thus the ordering imposed by waiting arcs is violated), then we compute a set \(\overline{A}\) of vertices that will be wired at \(v\), given by \(\overline{A}=\{w\ :\ (w,v_{d}^{c_{j}})\in A\ :\ w\in\textsc{av}[s]\}\). Note that the time of said vertex \(v\) is necessarily larger than the time of vertices \(w\in\textsc{av}[s]\) such that \((w,v_{d}^{c_{j}})\in A\) plus mt\({}_{s}\), thus satisfy the red-te inequality for transfer arcs. Moreover, we search for two vertices, named pred and succ respectively, defined as follows:

* pred is the unique vertex (if any) such that \(\textsc{pred}\in\textsc{dv}[s]\) and \((\textsc{pred},v_{d}^{c_{j}})\in A\);
* succ is the unique vertex (if any) such that \(\textsc{succ}\in\textsc{dv}[s]\) and \((v_{d}^{c_{j}},\textsc{succ})\in A\). These are the vertices adjacent to the waiting arcs having \(v_{d}^{c_{j}}\) as one endpoint, that we will need to rewire to preserve the red-te properties. Then, we remove \(v_{d}^{c_{j}}\) from \(V\), and run dec-bu to obtain an updated version of the 2 hc-r labeling (see Line 14). Note that the removal of a vertex \(v_{d}^{c_{j}}\) also removes all arcs \((v,v_{d}^{c_{j}})\) and \((v_{d}^{c_{j}},v)\) (if any) from \(A\). Finally, we add: a waiting arc \((\textsc{pred},\textsc{succ})\) to \(A\), if both pred and succ are vertices in the graph, and a transfer arc for each entry in \(\overline{A}\). In particular, for each vertex \(w\in\overline{A}\), we add a new transfer arc \((w,\textsc{succ})\). To reflect such changes on \(L\), we run inc-bu (see Line 16). Regarding vertex \(v_{u}^{c_{j}}\), graph \(G\) remains unchanged either if there is no transfer arc in \(A\) having \(v_{u}^{c_{j}}\) as endpoint, or if there is a transfer arc \((v_{u}^{c_{j}},v)\) but such arc is not affected by the delay, that is, when \(\mathit{time}(v)\geq\mathit{time}(v_{u}^{c_{j}})+\textsc{mt}_{L}\). In all other cases, we proceed by removing \(v_{d}^{c_{j}}\) from \(G\) and by updating \(L\) via dec-bu (see Line 21). An example of execution of the removal phase is shown in Figure 2.

As a final remark on this part, notice that (see Figure 2) the removal phase is stopped at a given connection \(c_{i}\) of trip \(\textsc{trip}_{i}=(c_{0},c_{1},\ldots,c_{m},\ldots,c_{i},\ldots,c_{k})\), with \(m\leq i\leq k\) whenever the delay does not induce a change neither in the time associated to \(v_{u}^{c_{i}}\) and \(v_{d}^{c_{i}}\) nor in their adjacent arcs, as this trivially implies that no change will be performed on all vertices \(v_{u}^{c_{j}}\) and \(v_{d}^{c_{j}}\) (and their adjacent arcs) for all \(j\), with \(i<j\leq k\). This can be detected by comparing the _status_ of vertices (namely time and set of adjacent arcs) before and after performing the procedure for a given connection.