# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
: _For any vertex \(v\in\textsc{left}_{x}\), a label entry \((h,\delta_{\mathit{th}})\) in \(\textsc{l}_{\mathit{out}}(v)\) may be affected only if \(h\in\textsc{right}_{x}\) or if \(v=x\)._

**Lemma 3**. : _For any pair of vertices \(u,v\) in \(V\), if \(u\in\textsc{left}_{x}\) and \(v\
ot\in\textsc{right}_{x}\), then \(\textsc{query}(u,v,\textsc{l})=d_{G^{\prime}}(u,v)\). Symmetrically, if \(v\in\textsc{right}_{x}\) and \(u\
otin\textsc{left}_{x}\) then \(\textsc{query}(v,u,\textsc{l})=d_{G^{\prime}}(v,u)\)._

Proof. : The above easily follows by Properties 1 and 2. Notice that, when \(h\
ot\in\textsc{left}_{x}\cup\{x\}\) (\(h\
ot\in\textsc{right}_{x}\cup\{x\}\), respectively), the shortest path from \(h\) to \(v\) (from \(v\) to \(h\), respectively) cannot pass through \(x\) by the definition of \(\textsc{left}_{x}\) (\(\textsc{right}_{x}\), respectively). According to the previous observations, we now provide a strategy to carefully identify the label entries that are affected by the removal of a vertex \(x\) from \(G\). In particular, for each vertex \(v\in\textsc{right}_{x}\) (\(v\in\textsc{left}_{x}\), respectively) we know that \(\textsc{l}_{\mathit{in}}(v)\) (\(\textsc{l}_{\mathit{out}}(v)\), respectively) can contain affected label entries, which must be either removed or updated in order to preserve the correctness of the query algorithm. The routine to achieve the update is based on the notion of _marking_ label entries, that is we assume to store an additional boolean field, attached to each label entry, encoding the information \"the label entry is marked or not\". We assume initially all these bits are set to false. Given the additional boolean field, we define a so-called _marked query_ between two vertices \(u\) and \(v\), denoted as \(\textsc{mquery}(u,v,\textsc{l})\), that behaves as a regular query on the labeling with the difference that it considers only those label entries that are either marked or such that their associated vertices do not belong to either \(\textsc{left}_{x}\) or \(\textsc{right}_{x}\). This is done with the purpose of distinguishing label entries that have already been updated with the correct distance or such that the attached distance is not changed by the removal of \(x\). We will show later in the section how this modified query is used to retrieve correct distances during the update. Algorithm 1, whose pseudocode is given in Algorithm 7, exploits the above properties and definitions and works as follows. Given the vertex \(x\), the algorithm first computes a topological order \(T\)of the graph in linear time. Then, sets \(\textsc{right}_{x}\) and \(\textsc{left}_{x}\) are determined, again in linear time via a forward and backward, respectively, execution of the well known breadth-first search (BFS, for short) algorithm, starting from \(x\). This is followed by the removal of \(x\) from \(G\). Now, if either \(\textsc{right}_{x}\) or \(\textsc{left}_{x}\) are empty, the algorithm simply removes all entries that have \(x\) as first field in the labeling \(\textsc{l}\), by linearly scanning it, and terminates. Note that, it is very unlikely for \(\textsc{right}_{x}\) or \(\textsc{left}_{x}\) to be empty, therefore the removal of \(x\) from \(\textsc{l}\) is done in the trivial way, rather than employing explicitly some data structure storing an inverted index for each label entry in \(\textsc{l}\). Otherwise, the algorithm proceeds in two phases, called _forward update_ and _backward update_, that scan vertices that can contain obsolete label entries (namely vertices in \(\textsc{left}_{x}\) and \(\textsc{right}_{x}\), respectively) with the purpose of either removing them or updating the associated distances. The two phases are described in details separately in the following sections. At the end of the two, \(\textsc{dag-decpll}\) removes \(\textsc{l}_{\mathit{out}}(x)\) and \(\textsc{l}_{\mathit{in}}(x)\) from \(\textsc{l}\) and returns the updated label set.