# Path Algorithms for Contact Sequence Temporal Graphs +
## 3 Results
### Setup  
The computational platform we use for our experiments is an Intel Knights Landing with a maximum CPU clock cycle of 1.7 GHz and up to 384 GB RAM. All the codes are in C++. We used the g++ compiler with the following flags: \(-std=c++11\) and \(-O3\). The codes for the OSE data structure were obtained from the authors of [8] and used with no modification. We coded the remaining algorithms. We use 11 of the datasets used by [PERSON] et al. [8] in addition to an airline dataset. The airline dataset is taken from the Bureau of Transportation Statistics website ([[https://www.transstats.bts.gov/OT_Delay/OT_DelayCause1.asp](https://www.transstats.bts.gov/OT_Delay/OT_DelayCause1.asp)]([https://www.transstats.bts.gov/OT_Delay/OT_DelayCause1.asp](https://www.transstats.bts.gov/OT_Delay/OT_DelayCause1.asp)) (accessed on 1 February 2024)). The Wu datasets are taken from The KONECT Project website ([[http://konect.cc/networks/](http://konect.cc/networks/)]([http://konect.cc/networks/](http://konect.cc/networks/)) (accessed on 1 February 2024)). The airline dataset contains information about flights in the US since 1987. For our experiments, we used data from January 2020. Self-loops were removed from all datasets in a preprocessing step, and undirected graphs were converted to directed ones by replacing each undirected edge with two directed ones. In all datasets (except the airline dataset), the weight \(w\) of every edge was set to \(1\), as was conducted in Ref. [5]). Since all edges of all datasets used by us have a strictly positive weight the TRG for each is acyclic. Hence, these datasets may be used by the algorithms for cyclic as well as acyclic TRGs and also by all OSE algorithms. We use acyclic datasets to assess our algorithms for cyclic TRGs because we expect little difference in runtime between cyclic and acyclic datasets. The runtime is expected to depend more on the number of edges and vertices and the reachability of vertices from the source rather than on whether the TRG has cycles. Additionally, this enables us to assess the performance gain obtained by the acyclic TRG algorithms relative to their cyclic counterparts. Table 2 summarizes the properties of the datasets we used. In this table, \(|V|\) is the number of vertices, and \(|E|\) is the number of temporal edges in a dataset. \(E_{s}\) is the set of static edges. These are obtained from \(E\) by removing edge weights and timestamps and eliminating duplicate \((u,v)\) pairs. The \(|E|/|E_{s}|\) values, which measure edge activity (i.e., how often a static edge becomes available), are rounded to \(2\) digits. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **Fastest** & **Minhop** & **Shortest** & **Foremost** \\ \hline \multicolumn{5}{c}{OSE and cyclic TRG algorithms} \\ \hline OSE & \(O(|T_{out}(s)|(|V|+|E|))\) & \(O(|V|+|E|log(d_{max}))\) & \(O(|V|+|E|log(d_{max}))\) & \(O(|V|+|E|)\) \\ \hline TRG\_Wu & \(O(|V^{\prime}|+|E^{\prime}|)\) & \(O(|V^{\prime}|+|E^{\prime}|log|V^{\prime}|)\) & \(O(|V^{\prime}|+|E^{\prime}|log|V^{\prime}|)\) & \(O(|V^{\prime}|+|E^{\prime}|)\) \\ \hline TRG\_Ours & \(O(|V^{\prime\prime\prime}|+|E^{\prime\prime\prime}|)\) & \(O(|V^{\prime\prime\prime}|+|E^{\prime\prime\prime}|)\) & \(O(|V^{\prime\prime\prime}|+|E^{\prime\prime\prime}|log|V^{\prime\prime}|)\) & \(O(|V^{\prime\prime\prime\prime}|+|E^{\prime\prime\prime}|)\) \\ \hline \multicolumn{5}{c}{Acyclic TRG algorithms} \\ \hline TRG\_Wu & \(O(|V^{\prime}|+|E^{\prime}|)\) & \(O(|V^{\prime}|+|E^{\prime}|)\) & \(O(|V^{\prime}|+|E^{\prime}|)\) & \(O(|V^{\prime}|+|E^{\prime}|)\) \\ ine TRG\_Ours & \(O(|V^{\prime\prime\prime}|+|E^{\prime\prime\prime}|)\) & \(O(|V^{\prime\prime\prime}|+|E^{\prime\prime\prime}|)\) & \(O(|V^{\prime\prime\prime}|+|E^{\prime\prime\prime}|)\) & \(O(|V^{\prime\prime\prime}|+|E^{\prime\prime\prime}|)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Complexity comparison between OSE, TRG_Wu and TRG_Ours algorithms. There are slight differences from the statistics reported in [8].