# Path Algorithms for Contact Sequence Temporal Graphs +
## 4 Discussion  
We have developed a new time-respecting graph data structure TRG_Ours for contact sequence temporal graphs. This data structure has fewer vertices and edges than previously proposed TRG structures: TRG_Wu and TRG_Zschoche. Benchmark experiments conducted for the fastest, min-hop, shortest and foremost paths problems indicate that TRG_Ours is superior to TRG_Wu on contact sequence temporal graphs whose TRG is cyclic. In fact, TRG_Ours outperformed TRG_Wu on all but one of our datasets on the fastest paths, min-hop paths, and foremost paths problems. It outperformed TRG_Wu on all 12 datasets for the shortest path problem.  
Contact sequence temporal graphs with no edge whose weight is 0 result in acyclic TRGs. For acyclic TRGs, the path problems considered in this paper may be solved more simply using an algorithm based on a topological ordering of the vertices. When there are no edges whose weight is 0, these path problems may be solved using the OSE data structure of [8]. The algorithms for acyclic TRG_Ours were faster than those for acyclic TRG_Wu on all 12 of our datasets and for all four path problems studied in this paper. The acyclic algorithms using TRG_Ours were also faster than the OSE algorithms on all 12 datasets for the fastest paths, min-hop paths, and shortest paths problems but slower on all 12 datasets for the foremost paths problem.  
Figure 5: Speedup obtained by our acyclic shortest path algorithm.  
Figure 6: Speedup obtained by our acyclic foremost path algorithm.  
We did not experiment with TRG_Zschoche as this data structure is expected to have more vertices and edges than TRG_Wu (except in the particular case when all edge weights are 1), and so it is expected to give an inferior performance than TRG_Wu. We have also pointed out that TRG structures are superior to OSE on problems requiring only local information (shallow neighborhood search problems), such as one-hop and 2-hop neighbors. So, while [PERSON] et al. [8] conclude that OSE is the data structure of choice for single-source all-destinations problems, our work indicates that TRG structures can be highly competitive with OSE while providing distinct advantages for shallow neighborhood search problems.  
All the authors were involved in the development of the algorithms. Methodology, S.G., T.B., S.R. and S.S.; Software, S.G.; Validation, S.G.; Writing--original draft, S.G.; Writing--review & editing, S.G., T.B., S.R. and S.S.; Supervision, S.R. and S.S. All authors have read and agreed to the published version of the manuscript.  
This research received no external funding.  
The \"airline\" dataset has been taken from [[https://www.transtats.bts.gov/OT_Delay/OT_DelayCausel.asp](https://www.transtats.bts.gov/OT_Delay/OT_DelayCausel.asp)]([https://www.transtats.bts.gov/OT_Delay/OT_DelayCausel.asp](https://www.transtats.bts.gov/OT_Delay/OT_DelayCausel.asp)) (accessed on 1 February 2024). All the other datasets, i.e., \"arxiv\", \"conflict\", \"digg\", \"elec\", \"enron\", \"epin\", \"tb\", \"flicker\", \"growth\", \"slash\", \"youtube\" are taken from [[http://konect.cc/networks/](http://konect.cc/networks/)]([http://konect.cc/networks/](http://konect.cc/networks/)) (accessed on 1 February 2024).  
The authors declare no conflicts of interest.