Computing earliest-arrival paths in temporal graphs
Shortest path is a frequently used tool, particularly regarding route planning. But in some graph problems, the edges change as time progresses and so we can not use popular algorithms such as Djikstra. Instead we must use a class of algorithms which consider the properties of temporal edges.
(Need a quick reference? Scroll down for the algorithm pseudocode and a Go implementation.)
Shortest path analysis, and variants thereof, is a useful tool many of us use every day, particularly with regard to making travel decisions - "If I leave now, how long will it take to drive to work?" is a question we might ask our sat. nav. having overslept slightly and waking up to a 9am meeting invite that you're pretty sure wasn't there as you left yesterday.
Despite being disguised as a time-related question ("how long will it take to get there?") this problem is more easily treated as a distance-related1 question since the routes that are available tend not to change depending on what time it is.
Dijkstra's shortest path algorithm [1] is a famous example of a solution to such a question - it operates on a graph and works by pruning the edges until each edge that remains in the tree leads to the next node on the shortest path to the destination. This graph may then serve as a useful reference to lookup the shortest path to the destination from any node, provided that the graph from which this tree was derived does not change.
If however, like me, you prefer to take the bus instead, the question might be reframed to be something like: "If I leave, what is the fastest route to work by public transport?". At first glance this seems like it could be the same problem, but there is a key difference in that a bus departs from specific locations at specific times and once it has departed, it can not be caught. In other words, the routes that are available to take change as time progresses. A graph that describes this kind of behaviour is not 'static' - instead it is described as time variant, dynamic, or temporal.
As a result we can not apply Djikstra or other algorithms that operate on static graphs - in a temporal graph these method are not reliable. Even though the shortest path may go next via one node, delays between opportunities to traverse the edges on this path may mean that the fastest path may be via a different one. It is also possible that the shortest path might never be available when time is considered. Instead we must look to a class of algorithms which take into account the properties of temporal edges.
Edges in a temporal graph differ from their static graph counterparts by having the properties of starting time and traversal time. These are the times at which the edge is able to be traversed and how much time will have elapsed by the moment of arriving at the adjacent node. In the context of catching a bus, for example, the starting time could be the scheduled deparature time and the traversal time the expected duration to the next stop. Traversal time can be seen as analogous to edge weight in non-temporal graphs, but starting time is fundamentally different in that once it is passed the edge may never be traversed - cue flash back to the trauma of running for, and then missing, a bus by merely seconds.
Computing earliest-arrival times in temporal graphs
The authors of [2] propose an algorithm for computing the earliest-arrival time from the start node x to every other node v starting at time tα and bounded by end time tω.
Here is an equivalent pseudocode for [2] (Algorithm 1):
procedure earliest(G, x, tα, tω):
for each vertex v in G do:
t[v] ← ∞
t[x] ← tα
for each edge e = (u, v, t, λ) in edge stream of G do:
if t + λ ≤ tω and t ≥ t[u] then:
if t + λ < t[v] then:
t[v] ← t + λ
else if t ≥ tω:
break loop
return t[v] for each v ∈ V
Let's dissect the algorithm.
for each vertex v in G do:
t[v] ← ∞
t[x] ← tα
In other words, maintain a map of earliest-arrival at each destination nodes, t[v]. Assume that x is reachable by time tα, so set earliest-arrival at x, t[x] = tα.
t[v] now represents the earliest-arrival time at v. By extension, t[v] is also the earliest-departure at v, since it is not possible to depart from a node you have not yet arrived at. If t[v] = ∞, then v is not reachable from x starting at time tα 2.
for each edge e = (u, v, t, λ) in edge stream of G do:
The algorithm processes what [2] describes as the 'edge stream' representation of the graph. This is simply the set of edges in the graph ordered by starting time, t. If we process the edges in ascending time order, then it is not necessary to store any historical results - the map will be consistent for the start time of every edge.
if t + λ ≤ tω and t ≥ t[u] then:
If the edge ending time (starting time, t, plus traversal time λ), t + λ, is outside the scope of the search then ignore it.
If the edge starting time is before the earliest-arrival time of the starting node then it is impossible to reach in time to traverse it, so also ignore it.
if t + λ < t[v] then:
t[v] ← t + λ
If the edge ending time is before the earliest-arrival time of the ending node, then a new earliest-arrival time has been found.
else if t ≥ tω:
break loop
Given that we're processing edges in ascending time order, this is just a short-circuit to avoid processing/ignoring the remainder of the edge stream.
return t[v] for each v ∈ V
After all edges have been processed then the resulting map, t[v] is the map of earliest-arrival time at v, starting at u at time tα.
Computing earliest-arrival paths in temporal graphs
In most applications where knowing the earliest-arrival time is useful, knowing the path taken to realise that arrival-time is also required. [2], however, does not describe steps for constructing the earliest-arrival path.
Constructing the earliest-arrival path is possible with no modifications to the algorithm by maintaining the earliest-arrival path alongside the earliest-arrival time for each destination node.
Here is an extended pseudocode including earliest-arrival path construction:
procedure earliest(G, x, tα, tω):
for each vertex v in G do:
t[v] ← ∞
t[x] ← tα
p[x] ← {} // Empty list
for each edge e = (u, v, t, λ) in edge stream of G do:
if t + λ ≤ tω and t ≥ t[u] then:
if t + λ < t[v] then:
t[v] ← t + λ
p[v] ← append(p[u], u)
else if t ≥ tω:
break loop
return t[v], append(p[v], v) for each v ∈ V
And a brief explanation of why this works:
p[x] ← {} // Empty list
p[x] represents the nodes prior to x in the earliest-arrival path. Since x is the starting node, no nodes have been visited beforehand to get to x.
if t + λ < t[v] then:
p[v] ← append(p[u], u)
Every time a new earliest-arrival time for v is discovered, we know that time t[v] is the edge ending time t + λ. It follows that the new earliest-arrival path preceding v, p[v] is the earliest-arrival path preceding u, p[u] plus u itself.
return append(p[v], v) for each v ∈ V
It should be clear that the complete earliest-arrival path from x to v is the earliest-arrival path preceding v, p[v] plus v itself.
Computing earliest-arrival paths in temporal graphs - a Go implementation
The following is an implementation in Go, the structure of which is inspired by similar algorithms from the excellent Gonum scientific and numerical library [3].
package path
import (
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/temporal"
)
type Earliest struct {
from graph.Node
at uint64
until uint64
nodes map[int64]struct {
earliest uint64
via []int64
}
}
func (e *Earliest) set(v graph.Node, t uint64, p []int64) {
e.nodes[v.ID()] = struct {
earliest uint64
via []int64
}{
t,
p,
}
}
func EarliestArrivalFrom(g graph.TemporalStream, from graph.Node, at uint64, until uint64) Earliest {
earliest := Earliest{
from: from,
at: at,
until: until,
nodes: make(map[int64]struct {
earliest uint64
via []int64
}),
}
earliest.set(from, at, []int64{})
s := g.LineStream()
for s.Next() {
l := s.TemporalLine()
u := l.From()
uid := u.ID()
eu, ok := earliest.nodes[uid]
tl := l.At()
dtl := l.Duration()
if !ok {
continue
}
if tl+dtl <= until && tl >= eu.earliest {
v := l.To()
vid := v.ID()
ev, ok := earliest.nodes[vid]
if !ok || tl+dtl < ev.earliest {
earliest.set(v, tl+dtl, append(eu.via, uid))
}
} else if tl >= until {
break
}
}
return earliest
}
1 Here 'distance' refers to the time-distance cost of traversing a length of road with a particular speed limit.
2 I recommend avoiding floating-point representations of time (ain't nobody got time for debugging issues due to rounding errors), so get creative with representing infinity in the language of your choice e.g. in my Go implementation I use an unsigned type to represent discrete time and consider v not in map[v]uint to mean infinity.
[1] Djikstra's shortest path algorithm