Time-Dependent Graphs: Definitions, Applications, and Algorithms

An edge on a discrete time-dependent graph is activated by disjoint time points. Formally, there are several ways of modeling discrete time-dependent graphs.

One is to build labels for the edges which has well-defined attributes [15, 35, 73]. A time-dependent graph with a label \(\lambda :E\rightarrow 2^{\mathbb {N}}\) is denoted by \(G=(V,E,\lambda (G))\). The label set of \(\lambda (G)\) is a collection of natural numbers on each edge, which can be denoted by \(\lambda (E)\) where \(|\lambda |=\sum _{e\in E}|\lambda (e)|\). This modeling method is widely available and can build unified searching schemes for time-dependent graphs.

Another is to build snapshots for the time-dependent graph, that is, the time-dependent graph is considered as an ordered pair of disjoint sets [9, 49, 80]. A time-dependent graph is denoted by \(G=(V,A)\), where A is a set of time-dependent edges. A function \(A(t)=\{e:(e,t)\in A\}\) contains all edges in G at time t which is also called the tth instance of G. Accordingly, a snapshot of G at t is denoted by \(G(t)=(V,A(t))\). In this case, a time-dependant graph can be considered as a sequence of static graphs \(G=\{G_{1},G_{2},\ldots ,G_{t}\}\). This modeling method is most commonly used for modeling discrete time-dependent graphs, which is suitable for the time-dependent graph with a specific time structure, especially in real-time networks.

The third is to transfer the time-dependent graph into a static graph by building copies of vertices [35, 75, 76]. The reason for doing this is mainly because the technology tends to be perfect on static graph. If a time-dependent graph can be transformed into a static graph without losing any time-dependent information, it can provide a good foundation for future studies on time-dependent graphs. [75] provides a transfer method which has two steps to transform a time-dependent graph \(G=(V,E)\) into a static graph \(\hat{G}=(\hat{V},\hat{E})\) as illustrated in Fig. 2. Firstly, create copies of each vertex \(v\in V\) in \(\hat{V}\) , where \(\hat{V}\) composed of two parts \(T_{\mathrm{in}}(u,v) = \{t+\lambda : (u,v,t,\lambda )\in \prod (u,v)\}\) and \(T_{\mathrm{out}}(v,u) = \{t:(u,v,t,\lambda )\in \prod (v,u)\}\). Here, \(T_{\mathrm{in}}(u,v)\) maintains all vertices which are in-neighbors of v. Symmetrically, \(T_{\mathrm{out}}(u,v)\) maintains all vertices which are out-neighbors of v. Secondly, create edges from \((v,t_{\mathrm{in}})\) to \((v, t_{\mathrm{out}})\) for each vertex \(v\in V\) by order vertex in \(\hat{V}_{\mathrm{in}}(v)\) according to time instances order, then create a directed edge from each v to its copes. This modeling method can transplant algorithms of static graphs to problems of time-dependant graphs. But the disadvantage is obvious that building multiple copies of the vertices increase the scale of graphs. And [75] also shows that the results obtain directly from the time-dependent graph are quite different from the results obtained from the converted static graph for queries that need to consider time order.

There are two drawbacks of the discrete time model. First, this model cannot represent the state of the graph between two discrete time points, which might yield inaccurate results. Second, the memory and processing requirements are high. A more precise way to describe a time-dependent network is to use the continuous time-dependent function. For a continuous time-dependent graph whose edges are activated in a sequence of time intervals, there are two modeling methods.

One is to define an index function, called presence function, to determine whether a pair of vertices is connected at a given time interval [65]. If vertex u and v is connected at time t, then the presence function \(f(u,v,t)=1\). Otherwise, \(f(u,v,t)=0\). This modeling method applies to time-dependent graphs where the time intervals are discrete and disjoint and the edges are only active and inactive.

The other is to treat a time-dependent graph as a flow-dependent graph which means the weight it takes for flow to traverse an edge is different in different time intervals [19, 22, 24]. For \(e\in E\), the flow function \(f_{e}:[0,T)\rightarrow {\mathbb {R}}^+\), where \(f_{e}(t)\) defines the rate of flow entering edge e at time t. For example, a road network can be modeled as a continuous time-dependent graph, where a non-negative travel time function \(\tau _{e}\) determines the time it takes for flow to traverse an edge e [42]. The flow arrives at the end node of e at time \(t+\tau _{e}(f_{e}(t))\). Accordingly, this modeling method applies to time-dependent graphs where the time intervals are continuous and the functions on edges change over time.

In the static graph, a path is simply a sequence of edges from origin vertex u to destination vertex v, such as \(p_{1}=\langle D, A, B, C\rangle\) (red dotted line) and \(p_{2}=\langle D, A, C\rangle\) (blue dotted line) in Fig. 3a. However, a time-respecting path [32, 39] has to be redefined to take time into account. For example, as shown in Fig. 3b, D and C are connected only through path \(p=\langle (D,A,4),(A,B,5) ,(B,C,6)\rangle\) (red dotted line), assuming edge delay is 1. Accordingly, the time-respecting path is a sequence of edges that follow a time order. If there are paths from A to B and B to C, it does not mean that there is a time-respecting path between A and C. Consequently, as seen in the example above, a time-respecting path from A to C is existing only if the contact between A and B takes place before the contact between B and C.

In the static graph, the most basic problem associated with the path is the shortest path problem that computes the shortest distance between two reachable vertices. In [16], the time-dependent shortest path problem is refined into three types:

Earliest Arrival Path Problem. The earliest arrival path problem asks for the corresponding route with the earliest arrival time at B from A at departure time \(t_{a}\).

Latest Departure Path Problem. The latest departure path problem asks for the corresponding route with the latest departure time from A and arrives at B no later than \(t_{b}\).

Shortest Duration Path Problem. The shortest duration path problem asks for the corresponding route with shortest duration time that departs from A no sooner than \(t_{a}\) and arrives B no later than \(t_{b}\).

Due to the complexity of time-dependent information, each of the above problems can not be solved in a greedy strategy which is often used to compute the shortest path problems in a static graph. Cooke et al. [16] proposed a modified version of Bellman’s iteration scheme [3] to compute the shortest path with time-dependent information. Afterward, many algorithms [59, 70, 73, 75] are proposed to solve Cooke et al.’s three problems on the time-dependent graph. Since the path problem is the most foundational problem on graphs, most of these algorithms are discussed in Sect. 3.1.

Connectivity is a fundamental concept for both static networks and time-dependent networks. We said a graph is connectivity if there are paths between every pair of vertices. A connected component is defined as a set of vertices with paths between each pair of them. In directed static graphs, connected components can be classified into weakly and strongly connected components. In particular, a graph is said to be strongly connected, if there is a path from i to j and a path from j to i, for each pair of vertices i and j. Correspondingly, a graph is said to be weakly connected, if the corresponding undirected graph which is obtained by removing all directions in the edges is a connected graph, i.e., replace all directed edges with undirected edges. In time-dependent graphs, the order of time naturally introduces a directionality of the graph. For instance, in the time-dependent graph G (shown as Fig. 4a), there exists a time-respecting path between vertex A and vertex E (i.e., edge \(e_{AB}\) at time 1 and edge \(e_{BE}\) at time 8 in Fig. 4b), but there is no path between E and A. Hence, the connectivity of the time-dependent graph is more similar to that of the static directed graph [58]. However, the concepts of weakly and strongly connected can not be generalized for time-dependent graphs if we only hold time-respecting paths instead of paths. Nicosia et al. proposed the definition of strong and weak connectivity on time-dependent graphs (called time-varying graphs in their paper [58]) as follows.

According to above two definitions, the strongly connected component and the weakly connected component can be easily defined, that is, the vertices sets where each pair of vertices fulfills the criteria. And Nicosia et al. also showed that finding the strongly connected components of a time-dependent graph is equivalent to finding the maximal cliques of an affine graph that is an undirected static graph with the same vertices as the time-dependent graph.

Menger’s theorem [53] is one of the most basic theorems in the theory of graph connectivity. It states that the maximum number of node-disjoint s-v paths is equal to the minimum number of nodes that must be removed in order to separate s from v [8]. However, Kempe et al. [39] proved that the Menger’s theorem of static graphs does not apply to time-dependent graphs. In particular, they also proved that there is no natural analogue of Menger’s Theorem for the single-label time-dependent graph and it is NP-hard to compute the number of node-disjoint time-respecting paths. Over Kempe et al.’s work, Mertzios et al. [54] provided a natural time-dependent (called temporal in their paper) analogue of Menger’s theorem for all (both single-label and multi-label) time-dependent graphs.

By symmetry, they have that the maximum number of in-disjoint journeys from s to v is equal to the minimum number of node arrival times needed to separate s from v.

The spanning tree is an important concept related to paths in static graphs. In particular, the minimum spanning tree problem refers to the minimal connected subgraph generated for the original graph. The connected subgraph contains all the vertices of the original graph, whose number of edges connecting the subgraphs is the smallest. The minimum spanning tree problem can be solved in polynomial time and has widely used in graphs. Many complex queries are based on the minimum spanning tree problem [5, 31, 46, 68], and many efficient graph algorithms are based on building a minimum spanning tree, such as min-cut max-flow algorithm.¹

Gunturi et al. [27] proposed a related concept in time-dependent graph called time-sub-interval minimum spanning tree (TSMST). TSMST refers to a collection of minimum spanning trees in an interval with minimum total cost. Further in [35], Huang et al. defined two kinds of minimum spanning trees (\(\mathrm{MST}_{s}\)) in a time-dependent graph: (1) \({\mathcal {MST}}_{a}\) which is the \(\mathrm{MST}_{s}\) with earliest arrival times and (2) \({\mathcal {MST}}_{w}\) which is the \(\mathrm{MST}_{s}\) with the smallest total weight. Huang et al. proved that \({\mathcal {MST}}_{a}\) can be computed in linear time, but \({\mathcal {MST}}_{w}\) is a MAX-SNP hard. Consequently, they transformed the \({\mathcal {MST}}_{w}\) problem to the minimum Directed Steiner Tree problem.

In the time-dependent network with discrete travel time, certain segments can only be traversed at specific discrete time instances based on a timetable. Therefore, the cost of an edge, varying as a travel time function, represents a succinctly periodic, discrete, piecewise linear (PWL) function. The public transportation network is representative of discrete time-dependent networks. According to real traffic conditions, it is always necessary to wait for a vehicle at a station. And when transfer from one vehicle to another, the vehicle schedule must be strictly followed.

As we maintained before, Cooke and Halsey [16] proposed the most basic route planning problem. Cooke and Halsey proved that these queries could be solved with a modified version of Dijkstra’s algorithm. However, it does not scale well with the size of the graph and several techniques, such as indexing have therefore been proposed to improve efficiency. Pyrga et al. [61] proposed realistic time-expanded and time-dependent models and extended their methods for a series of realistic requirements of time-dependent shortest path (TDSP) problem on discrete time-dependent graphs. Chabini [14] extended the A* algorithm to compute the minimum travel time path for one as well as for multiple departure times. They improved a lower bound on minimum travel time which is used to design an effective adaptive A*-based algorithm. To speed up the A* algorithm, Nannicini et al. [57] and Demiryurek et al. [21] presented methods based on the bidirectional A* search algorithm. Notice that the time-dependent paths must be in time order. But we cannot know the arrival time in advance during backward search. Hence, both Nannicini et al. and Demiryurek et al. run the backward search by the idea of lower bound function. Wu et al. [75] proposed efficient algorithms, named as one-pass algorithms. The one-pass algorithm is based on Dijkstra’s algorithm and solves the route planning queries by enumeration. For each vertex v, the one-pass algorithm builds a store list \(L(v)=(s[v],a[v])\), where s[v] is the departure time from source x to v, and a[v] is the arrival time at v. Then, it updates the L(v) until finding the earliest arrival time from the source vertex x to v at different starting time. In order to provide an alternative approach, they proposed a method of transferring a time-dependent graph into a static graph. Notice that Wu et al. proved that the results obtained directly from the time-dependent graph are quite different from the results obtained from the converted static graph. This calls the need for studying the time-dependent problem directly on time-dependent graphs. After that Wang et al. [73] presented an efficient indexing technique, named as Timetable Labeling (TTL), for time-dependent routing problem in public transportation networks. The TTL index is defined based on the concept of canonical paths. It builds two label sets \(L_{\mathrm{in}}(v)\) and \(L_{\mathrm{out}}(v)\) for each node v in the time-dependent graph, which contains the information about the canonical paths between v and the nodes that rank higher than v. Wang et al. showed that the TTL index enables to support three common route planning queries (described in Sect. 2.3.1).

Route planning on a continuous time-dependent network is drastically different from that on a discrete time-dependent network. Routing in continuous time-dependent networks is to calculate the optimal path from a source s to a destination d on road network without changing vehicle. It is a key component in road network, self-driving technology, navigation systems as well as in some robotics. In a continuous time-dependent network, the cost of the edge varies as a travel time function which is always a continuous and PWL function. Notice that we are not simply calculating the optimal path with a certain departure time, which is easily calculated by Dijkstra’s algorithm, but calculating the minimum travel time under certain conditions, such as the expected arrival time or the departure time interval.

Ordal and Rom [59] presented a Ford-type algorithm to solve the TDSP problem when no constraints are imposed on waiting times at the nodes. On the basis of Ordal and Rom’s work, Dehne et al. [18] presented an improved method that can solve the TDSP problem in FIFO networks. They proved that the algorithm can run in polynomial time, while other methods require super-polynomial time. And they also presented an approximation method with possibly super-polynomial size output in time \(O(\tfrac{\Delta }{\epsilon }(|E|+|V|\hbox {log}|V|))\). Afterward, Foschini et al. [24] presented a method that can solve TDSP problem in super-polynomial time. The main idea of their method is to calculate primitive and minimized breakpoints and build acyclic layered graph representation of the time-dependent graph. They presented an output-sensitive algorithm whose running time depends on the number of breakpoints at the nodes and edges in the time-dependent graph. In order to speed up the technique for TDSP problem, Foschini et al. proposed \((1+\epsilon )\)-approximation schemes to compute the arrival time functions in time \(O(K\tfrac{1}{\epsilon }\hbox {log}(\tfrac{\mathrm{MaxTravelTime}}{\mathrm{MinTravelTime}}))\). Ding et al. [22] presented a query as \(\hbox {LTT}(v_{s},v_{e},T)\) to ask the minimum-travel-time path from a source s to a destination d with the best departure time selected in a given time interval. They showed that their approach, named as Two-Step-LTT, adapts both on FIFO and NON-FIFO time-dependent networks. The first step is Dijkstra-based Time-refinement in which they compute the earliest arrival time function for each node. The second step is Fast Path-selection in which they compute the optimal path. To adapt Two-Step-LTT in non-FIFO networks, they showed how to transform a non-FIFO time-dependent graph into a FIFO one. They also proved the time complexity of their algorithm is \(O((n\, \hbox {log}n+m)\alpha (T))\).

Redmond and Cunningham [64] proposed three methods for subgraph matching algorithms by considering time-dependent and topological information at different stages.

Time before Topology (Ti-To) The Ti-To first abstracts all possible time-respecting subgraphs as a candidate subgraph set from the data graph by breadth-first algorithm on edges. Then, find extracted subgraphs that satisfy the conditions of the query graph from the candidate set by the VF2 [17] subgraph isomorphism algorithm. Experiments show that the candidate set may have a large overlap and time consuming.

Time and Topology Together (Ti&To) The Ti&To considers subgraph isomorphism and time constraints at same time. The isomorphic processing is described by a state space, each state s in the state space describes a local map. In a state s, the Ti&To first determines whether a candidate pair, consisting of vertices in query graph and data graph, is isomorphic and then Ti&To determines whether the candidate pair contents the time constraint. If the candidate pair satisfies both conditions, the neighbor vertices of the candidate pair are expanded downward to become new candidate pair. Loop until all the subgraphs that satisfy the conditions are found.

To solve the SGP problem with time-dependent relation order, a Hasse diagram based algorithm is proposed by Sun et al. [69]. They used Hasse diagram to express the time-dependent partial order of the edges in the query graph. Each edge corresponds to a Hasse node, and a time-dependent relationship in the query graph is represented as a directed Hasse edge. Then, they built the Hasse-cache structure to implement the continuous time-dependent subgraph query algorithm. The algorithm uses the probability of the time-dependent graph to reduce intermediate results, while achieving topology matching and time relationship verification. Compared with searching the entire query graph, the algorithm searches whether the time-dependent relationships of the data edges match the relationship of query edges and improves the performance of the algorithm by using the Hasse-cache structure.

TCGPM-V [77] is a pattern matching method based on vertex matching. Firstly, it uses the depth-first search tree to find all matching vertex sets and then enumerates all possible time-dependent subgraphs until finding the prospective time-dependent subgraph. Unlike TCGPM-V, TCGPM-E [77] is a pattern matching method based on edge matching. TCGPM-E first selects the edge with the smallest calculation result in the query graph according to the sorting function. Then, calculate the maximum number of edges in the query graph that can be linked around by the edge. Next, find an edge set in which all edges match with this edge in the data graph and decompose the data graph into multiple subgraphs. Each subgraph contains an edge in the edge set and the number of subgraphs is equal to the size of the edge set. Finally, subgraph isomorphism is performed on each subgraph, and the prospective time-dependent subgraph is enumerated.

In addition to the basic time-dependent graph pattern query problem, there are some more complex isomorphic problems exist in the time-dependent graph. Semertzidis and Pitoura [66] presented a durable graph pattern queries that aim to find persistent matches (the top-k longest period of time) of input patterns in node-labeled time-dependent graph. The evolution of graph is expressed as a sequence of snapshots which is corresponding to graphs with different time instances. A straightforward algorithm for the top-k most durable graph pattern queries is to perform a subgraph isomorphism algorithm on each snapshot then aggregates the results. But the straightforward algorithm does not adapt to the large-scale time-dependent graphs. They merged the snapshots into a labeled version graph (LVG) which records the time interval of nodes, edges, and labels as lifespan. Then, they calculated and filtered the candidate set by neighborhood and path time indexes based on Bloom filters [6], and then they presented an algorithm to find the top-k most durable graph. The algorithm first checks if there are isomorphic matches of the query graph in the candidate sets and deletes the candidates without an isomorphic match. Then the algorithm checks if the lifespan of edges and vertices in the candidate graph is conformed to the lifespan of the query graph. The top-k most durable graphs are gotten by ordering the duration of the results.