# Path Algorithms for Contact Sequence Temporal Graphs +
## 2 Materials and Methods
### Algorithms for Acyclic TRG_Ours
#### 2.3.1 Fastest Paths Algorithm on Acyclic TRG_Ours  
For the fastest path algorithm on the acyclic TRGs, we iterate the nodes in topological order. When we visit a node, we update the fastest distance to its neighbors. For computing the fastest distance, we need to keep track of the time a path exited from the source node.  
Algorithm 3 describes our Fastest Path algorithm for acyclic TRGs. The inputs are the same as our previous algorithms with the addition of \"tp_list\" which contains the topological order of the vertices in TRG. The output is a vector of the fastest paths in the original graph \((fastest[])\). We also use a local \(distance[]\) vector to keep track of the local distances to nodes \((u,t)\) in the TRG graph. We set \(fastest[]\) to 0 for the source node \(s\) and infinity for all other nodes. The local distances for nodes in \(V_{out}\) are also initialized to 0 (and all others to infinity). We use a vector \(latest[]\) to keep track--for each node \((u,t)\)\(-f\) the latest time we exited a node in \(V_{out}(s)\) but could still arrive at \((u,t)\).  
```
1:functionAcyclicFastestPaths(G, \(s\), \(t\)_p_list, \(t_{start}\), \(t_{end}\)) \(\triangleright\)\(G=(V,E)\) is TRG_Ours graph, \(s\) is the source node and \(tp_{list}\) is the list of nodes in topological order
2:return Array \(fastest[]\) of fastest path durations
3: Initialize \(fastest[s]=0\), all other distances to infinity
4:for\((u_{s},t_{s})\in V_{out}(s)\) where \(t_{start}\leq t_{s}\leq t_{end}\)do
5:\(latest[(u_{s},t_{s})]\gets t_{s}\)
6:\(distance[(u_{s},t_{s})]\gets 0\)
7:endfor
8:for\((u,t)\in tp\_list\)do
9:if\(distance[(u,t)]\) equals infinity then
10:continue
11:endif
12:\(fastest[u]\gets min(fastest[u],distance[(u,t)])\)
13:if\(t>t_{end}\)then continue
14: Let \((u,\bar{t})\) be the next node in sorted order of \(V_{out}(u)\)
15:if\(\bar{t}\leq t_{end}\) and \(latest[(u,\bar{t})]<latest[(u,t)]\)then
16:\(latest[(u,\bar{t})]\gets latest[(u,t)]\)
17:\(distance[(u,\bar{t})]\gets min(distance[(u,\bar{t})],\)\(distance[(u,t)])\)
18:endif
19:for\((u^{\prime},t^{\prime})\in\) neighbors((u,t))do
20: Let \(w_{link}\) be the weight of link between \((u,t)\) and \((u^{\prime},t^{\prime})\)
21:arrival_time \(\gets t+w_{link}\)
22:if\(arrival\_time>t_{end}\)then
23:continue
24:endif
25:if\(distance[(u^{\prime},t^{\prime})]>arrival\_time-latest[(u,t)]\)then
26:\(distance[(u^{\prime},t^{\prime})]\gets arrival\_time-latest[(u,t)]\)
27:endif
28:if\(latest[(u^{\prime},t^{\prime})]<latest[(u,t)]\)then
29:\(latest[(u^{\prime},t^{\prime})]=latest[(u,t)]\)
30:endif
31:endfor
32:endfor
33:endfunction
```  
**Algorithm 3** Fastest paths algorithm for acyclic TRG_Ours  
The main body of the code is implemented in lines 8-32 where we iterate over the nodes in the topological order and update the \(distance[]\) and \(latest[]\) vectors for the neighbors of the visited nodes. Line 12 computes \(fastest[u]\) as \(min_{t\in t_{out}(u)}distance[(u,t)]\). Again, for each node \((u,t)\) we treat its immediate neighbor \((u,\bar{t})\) in a different manner than the other neighbors. There are two reasons for that: first, as mentioned before, in our implementation, we don't add the chain neighbors to the adjacency list of the TRG graph. Moreover,for the immediate chain neighbor \((u,\bar{t})\), we only update it if \(latest[(u,\bar{t})]\) is greater than that of \((u,t)\). If it were not for the if statement in lines 9-11, we would only need to update \(latest[(u,\bar{t})]\) and not \(distance[(u,\bar{t})]\). However, as we bypass nodes with a distance equal to infinity, \(distance[(u,\bar{t})]\) may remain equal to infinity, and its neighbors may never get updated (the immediate chain neighbor is processed in lines 14-18 and the other neighbors in lines 19-31).