# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
1\(g\gets f_{uv}\circ f_{uw}\)\(\Pi_{uv}\leftarrow\{\tau\mid f_{uw}(\tau)\leq g(\tau)\}\)\(\Pi_{[uw]}\leftarrow\{\tau\mid g(\tau)<f_{uw}(\tau)\}\)\(X_{uv}\leftarrow\{\text{NewExpansion}(x,\Pi_{uv}\cap\Pi_{x})\mid x\in X_{uv}\}\cup\{\text{NewExpansion}([u,w,v],\Pi_{[uw]})\}\)\(f_{uv}\leftarrow\min(f_{uv},g)\)\(\underline{b}_{uv}\leftarrow\min(\underline{b}_{uv},\min_{\tau}(f_{uv}(\tau)))\)\(\overline{b}_{uv}\leftarrow\min(\overline{b}_{uv},\max_{\tau}(f_{uv}(\tau)))\)return\(X_{uv},\underline{b}_{uv},\overline{b}_{uv},f_{uv}\)
```
**Algorithm 1**LowerTriangleRelax
```
Input: Expansions \(X_{uv}\) for edge \(uv\), Time \(\tau\) Output: Travel time when traversing \(uv\) at \(\tau\)
1\(x_{\tau}\gets x\in X_{s}\) such that \(\tau\in\Pi_{x}\)// binary search
2
3 if\(E(x_{\tau})=uv\in A\)then
4 return\(f_{uv}(\tau)\)
5 else
6\(w_{x}\gets E(x_{\tau})\)\(\tau^{\prime}\leftarrow\text{Eval}(X_{uw_{x}},\tau)\)return\(\tau^{\prime}\)+ \(\text{Eval}(X_{w_{x}v},\tau+\tau^{\prime})\)
```
**Algorithm 2**Eval
```
Input: Expansions \(X_{uv}\) for edge \(uv\), Time \(\tau\) Output: Unpacked path \([u,\dots,v]\)\(x_{\tau}\gets x\in X_{s}\) such that \(\tau\in\Pi_{x}\)// binary search
3 if\(E(x_{\tau})=uv\in A\)then
4 return\([u,v]\)
5 else
6\(w_{x}\gets E(x_{\tau})\)\(p\leftarrow\text{Unpack}(X_{uw_{x}},\tau)\)return\(p\)- \(\text{Unpack}(X_{w_{x}v},\tau+\text{Eval}(p,\tau))\)
```
**Algorithm 3**Unpack
```
Input: Expansions \(X_{uv}\) for edge \(uv\), Time \(\tau\) Output: Unpacked path \([u,\dots,v]\)\(x_{\tau}\gets x\in X_{s}\) such that \(\tau\in\Pi_{x}\)// binary search
7 if\(E(x_{\tau})=uv\in A\)then
8 return\([u,v]\)
9 else
10\(w_{x}\gets E(x_{\tau})\)\(p\leftarrow\text{Unpack}(X_{uw_{x}},\tau)\)return\(p\)- \(\text{Unpack}(X_{w_{x}v},\tau+\text{Eval}(p,\tau))\)
```
**Algorithm 4**Unpackbut will never shrink. Once they have grown to an appropriate size, no more memory allocations will be necessary. Each buffer can contain many travel time functions stored consecutively. The link operation will read the last two functions from one buffer and append the result to the other buffer. Then, the two input functions will be truncated from the first buffer. After swapping, the buffers can be used again for the next link operation. Swapping is necessary, because it is not possible to read from and write to the same buffer during the same operation. The same schema can be employed for joining partial functions (see Figure 4 for a visualization). ```
Input: Expansions \(X_{uv}\) for edge \(uv\), Time interval \(T\) Output: Exact travel time function \(f_{uv}|_{T}\)
1 Initialize \(f_{uv}\) as function with empty domain for\(x\in X_{uv}\)do
2\([\tau_{x},\tau_{x}]\gets T\cap\Pi_{x}\) if\(E(x_{\tau})=uv\in A\)then
3\(f_{x}\gets f_{uv}|_{[\tau_{x},\tau_{x}]}\)
4 else
5\(w_{x}\gets E(x_{\tau})\)
6\(f_{uw_{x}}\leftarrow\textsc{ReconstructTravelTimeFunction}(uw_{x},[\tau_{x}, \tau_{x}])\)
7\(f_{w_{x}v}\leftarrow\textsc{ReconstructTravelTimeFunction}(w_{x}v,\)\([\tau_{x}+f_{uw_{x}}(\tau_{x}),\tau_{x}+f_{uw_{x}}(\tau_{x})])\)
8\(f_{x}\gets f_{w_{x}v}\circ f_{uw_{x}}\)
9\(f_{uv}\gets f_{uv}\cup f_{x}\)
10 return\(f_{uv}\)
```
**Algorithm 4**ReconstructTravelTimeFunction

### Preprocessing

In this section, we present our preprocessing algorithms. The first phase of CCH preprocessing is performed only on the topology of the graph. Since no travel time functions are involved, we can adapt the algorithms of [PERSON] et al. (2017) without modification. We use InertialFlowCutter (2018) to obtain the nested dissection order. To generate the augmented graph, we implement an improved contraction algorithm first presented in ([PERSON] et al., 2019). When contracting a node, we insert all upward neighbors of the current node only into the neighborhood of its lowest ranked upward neighbor. This algorithm can be implemented to run in linear time in the size of the output graph. The goal of the second phase of preprocessing--the _customization_ --for classical CCH is to compute the shortcut weights.