# Path Algorithms for Contact Sequence Temporal Graphs +
## 1 Introduction  
This paper extends our previous paper on contact sequence temporal graphs [1]. We have extended our previous work mainly by adding two path-finding algorithms to our proposed TRG data structure. Also, we have considered the case when the TRG graph is acyclic and proposed path-finding algorithms that can further benefit from that property. Temporal graphs are graphs that change over time. Therefore, temporal information is incorporated in the edges or vertices. In this paper, we are only concerned with graphs in which the temporal information is incorporated in the edges. Temporal graphs have applications in modeling a wide range of phenomena, such as communication networks, computational biology, transportation networks, the spread of viruses, social networks, etc. [2; 3; 4; 5; 6]. In a _contact sequence temporal graph_\(G=(V,E)\), each edge \(e\in E\) has the format \((u,v,t,w)\) where \(u\) and \(v\) are the source and target vertices, respectively, of the edge; \(t\) is its time stamp and \(w\) (\(w\geq 0\)) is the time it takes to get from \(u\) to \(v\) along this edge. We may begin traveling from \(u\) only at the time indicated by the timestamp \(t\). We arrive at \(v\) at the time \(=t+w\). Contact sequence temporal graphs may have multiple edges with the same source and target vertices, each with a different time stamp and possibly different weight. An example of a real-life application of contact sequence temporal graphs is transportation networks such as the flight network of a particular airline. The nodes of the contact sequence temporal graph represent airports, and the edges model scheduled flights. Each flight can be described with (source, destination, start time and duration). There can be multiple flights between any two airports, each departing at a different time and possibly having a different duration. Another model for describing temporal graphs is the _interval temporal graph_, \(G=(V,E)\). This model has at most one edge between any pair of vertices (\(u\) and \(v\)). Each edge is labeled with a set of triplets of the form \((s,f,w)\) where \(s\) and \(f\) denote the start and the end of a time interval when we are allowed to commence travel from \(u\) (i.e., one can begin to travel on this edge at any time \(T,s\leq T\leq f\)). Like the contact sequence model, \(w\) is the weight and denotes the travel time. One can easily verify that every contact sequence temporal graph has an equivalent interval temporal graph and that the reverse is also true when time is discrete. To make it clear, assume in a contact sequence temporal graph \(G\), we have the edges \(e_{1}=(u,v,t_{1},w_{1})\) and \(e_{2}=(u,v,t_{2},w_{2})\). In the equivalent interval temporal graph, we will have only one edge between the nodes \(u\) and \(v\) and that edge is labeled with the following sequence of intervals: \(\{(t_{1},t_{1},w_{1}),(t_{2},t_{2},w_{2})\}\). Similarly, consider an interval temporal graph \(G^{\prime}\) (assume time is restricted to integer values) containing an edge \(e^{\prime}\) between nodes \(u^{\prime}\) and \(v^{\prime}\) which is labeled with the following interval \(\{(s^{\prime},f^{\prime},w^{\prime})\}\) where \(f^{\prime}=s^{\prime}+d^{\prime}\). In the equivalent contact sequence temporal graph, we will have the \(d^{\prime}+1\) edges between \(u^{\prime}\) and \(v^{\prime}\): \(e_{i}=(u^{\prime},v^{\prime},s^{\prime}+i,w^{\prime})\) where \(0\leq i\leq d^{\prime}\). Whether we use contact sequence temporal graphs or interval temporal graphs depends on the nature of the application at hand [4]. A _time-respecting path_ is defined as a path in which the departure time from each vertex is \(\geq\) the arrival time at the same vertex. We note that the terms \"path\" and \"time-respecting path\" may be used interchangeably in this paper. Our focus is on four types of time-respecting paths: \"earliest arrival\" (also known as \"foremost\") paths, \"fastest\" paths, \"shortest\" paths and \"min-hop\" paths.