Algorithms for optimal min hop and foremost paths in interval temporal graphs – Applied Network Science

Definitions

Definition 1

(Contact sequence temporal graphs) In a contact sequence temporal graph (G=(V,E)) each edge (e in E) is represented by a tuple ((u, v, t, lambda )), where t is the permissible departure time for travel from u to v using the edge e and (lambda) is the amount of time it takes to travel on edge e from u to v when one starts at time t. So, u is reached at time (t+lambda). If there are multiple time instances when departures from u to v are permissible, there will be multiple such temporal edges between u and v represented as a series of temporal edges ([(u, v, t_{1}, lambda _{1}); (u, v, t_{2}, lambda _{2}) ldots ; (u, v, t_{n}, lambda _{n})]). The number of temporal edges between vertices u and v, which is also the number of distinct permissible departure times from u to v, gives the amount of activity on the connection (u, v).

Definition 2

(Interval temporal graphs) In an interval temporal graph (G=(V,E)), each edge (e in E) is represented by a tuple (u, v, intvls). This tuple represents a connection from u to v. intvls is a time ordered sequence of tuples ([(s_{1},c_{1},lambda _{1}); (s_{2},c_{2}, lambda _{2}); ldots ; (s_{n},c_{n}, lambda _{n})]). The ith interval starts at time (s_{i}) and closes (ends) at time (c_{i}); (lambda _{i}) is the time it takes to traverse the edge when travel departs u at a time t such that ([s_{i} le t le c_{i}]) (v is reached at time (t+lambda _{i})). The intervals are in ascending order of start times (s_{i}) and collectively they define the permissible departure times from u.

We note that in the interval temporal graph model used by Bui-Xuan et al. (2003), all intervals associated with an edge (u, v) have the same (lambda) value. Further, (c_{i}) gives the time by which travel on (u, v) must finish rather than the last permissible departure time. So, in the model of Bui-Xuan et al. (2003), the permissible departure times for u defined by the ith interval are (s_{i}), (ldots), (c_{i}-lambda _{i}).

A path (equivalently, valid path, temporal path or time respecting path) in a temporal graph is an alternating sequence of vertices and departure times (u_{1}, t_{1}, u_{2}, t_{2}, ldots , u_{k}) where (t_{i}) is a permissible departure time from (u_{i}) to (u_{i+1}) where (1 le i < k), and ((t_{i} + lambda _{i}) le t_{i+1}), (t_{i} + lambda _{i}) is the arrival time at (u_{i+1}) when departing (u_{i}) at (t_{i}) using the connection ((u_{i},u_{i+1})). For this path, (u_{1}) is the source vertex and (u_{k}) the destination. (P_{1} = S,0,B,5,C) is a path from S to C in the temporal graph of Fig. 2. This path leaves S at 0 and arrives at B at time 5. It then leaves B immediately at time 5 and arrives at C at time 6. (P_{1}) is a 2-hop path from S to C with a first hop to B and then a second hop to C. (P_{2} = S,0,A,1,B,3,C) is another valid path from S to C. This path also leaves S at time 0. It gets to A at time 1 and departs immediately for vertex B where it arrives at time 2. At B, it waits for 1 unit until time 3 and departs for C getting there at time 4. (P_{2}) is a 3-hop path from S to C.

We are interested in paths in a temporal graph that start at a vertex u at a time (ge t_{start}) and end at another vertex v. Let S(u, v) comprise all valid paths from u to v that depart u at a time (ge t_{start}). A foremost path is a path in S(u, v) that gets to v at the earliest time; a min-hop path is a path in S(u, v) that has the fewest number of hops; a fastest path is a path in S(u, v) for which (arrival time at v—departure time from u) is minimum; and a shortest path is a path in S(u, v) that minimizes the sum of the (lambda)s on the path.^{Footnote 1}

Bui-Xuan et al. (2003) develop polynomial time algorithms for foremost, min-hop, and fastest paths in interval temporal graphs. Wu et al. (2016a) do this for contact sequence graphs.^{Footnote 2} They also develop algorithms for reverse-foremost paths (paths with the latest departure time and terminating at a specified vertex).

Data structures

Bui-Xuan et al. (2003) use linked adjacency lists to represent an interval temporal graph. We, instead, use array adjacency lists (Sahni 2004). For example, the interval temporal graph of Fig. 3 is represented by the array adjacency list of Fig. 4. The data structure comprises a (say) C++ vector with one slot for each vertex in the graph. This is the vertical vector in the figure. Slot for any vertex u itself contains a vector of vertices adjacent from u. For example, the slot for S in the vertical vector has the adjacent vertices vector (A.B). Associated with each adjacent vertex v from u, there is a vector of time ordered tuples for the edge (u, v). In Fig. 4, ([0–1],1), ([2–6],3) is the time ordered vector for the edge (S, A).

Example interval temporal graph

Data structure representing Interval temporal graph of Fig. 3

Wu et al. (2016a) consider two data structures for contact sequence graphs. In the first of these, the graph is simply represented as a sorted sequence of edges (tuples) of the form (e=(u,v,t,lambda )); this sequence is in non-decreasing order of t. The second representation is a graph that is quite different from that of Fig. 4 and which their experiments show to be inferior for all path problems studied by them except the fastest path problem where the two representations are competitive. Since we do not consider the fastest path problem here, we do not describe their graph representation. However, we mention that their graph representation has more edges than their sorted sequence representation. When time is discrete, every interval temporal graph can be transformed into a contact-sequence graph that has the same foremost, min-hop, shortest, fastest, and reverse-fastest paths. In this transformation, we replace each edge in the interval temporal graph by as many contact sequence edges as the number of permissible departure times for edge intervals. For example, if time is an integer, then the the connection (S, A) in Fig. 3 with the interval sequence ([0–1],1), ([2–6],3) gets replaced by the tuples (S, A, 0, 1), (S, A, 1, 1), (S, A, 2, 3), (S, A, 3, 3), (S, A, 4, 3), (S, A, 5, 3), (S, A, 6, 3). As is evident, this transformation preserves valid paths but has the potential for explosive growth in the number of edges and consequently in the memory needed. For example, the integer interval [1, 100,000] would result in 100,000 contact sequence edges. As we shall see in the next section, this explosive growth in instance size can result in a path problem being NP-hard in the interval model but polynomial in the contact sequence model.

We note also that every contact sequence temporal graph may be transformed into an equivalent interval temporal graph by coalescing the multiple edges that connect a pair of vertices (u, v) into a single edge with an appropriate time ordered sequence of intervals; each interval’s start time is (le) its close time.

The function next

Bui-Xuan et al. (2003) define a function that given a time t and vertices u and v finds the earliest permissible departure time greater than or equal to t on the edge (u, v). The function is denoted as f((u, v), t). This function simply does a binary search on the intervals associated with the edge (u, v). It runs in O(log(k)) time, where k is the number of intervals associated with the edge. This function is used by Bui-Xuan et al. (2003) in their path algorithms and also used by us in our algorithms. We call this function next.