# Foremost Walks and Paths in Interval Temporal Graphs +
## 5 Min-Wait Foremost Walks in Interval Temporal Graphs
### Algorithm to Find \(mwf\) Walks
#### 5.4.2 Algorithm Description  
1. [noitemsep]
2. INPUT: 1. Temporal graph represented by data structure described in Section 5.4.1, item 1. 2. Source vertex \(s\)
3. OUTPUT: - Array \(mwfWalks\) as described in Section 5.4.1, item 7. For simplicity, we assume that all the edge travel times are \(>\)0. Our algorithm for solving the \(mwf\) problem (Algorithm 2) can easily be extended to the case when some travel times are \(\geq\)0. Later, we show how to carry out this extension. Algorithm 2 looks at all possible departure intervals in non-decreasing order of their arrival times when departing at the start of the interval \((intvl.strtTm+intvl.\lambda)\). In Step 8, it saves the arrival time of the latest interval being considered in the variable \(curTm\). In the subsequent \(while\) loop, it keeps fetching new intervals as long as they have the same arrival time as \(curTm\), when departing at the start of the interval. For each fetched interval \(newIntvl\), at the originating vertex \(u\) of \(newIntvl\), it finds a walk class \(prevW\) with latest arrival time of the start of the walk class \(prevW.strtTm\) such that \(prevW.strtTm\leq newIntvl.st\). No other walk arriving at \(u\) needs to be considered for expansion on this interval due to Theorem 10. Using this previous walk at the originating vertex \(u\), a new walk is created from \(u\) to \(v\) at the start of the \(newIntvl\) using the function \(createNewW\). This function creates a new walk from the previous walk departing at start of \(newIntvl\) only if the second part of Theorem 12 is satisfied. The first part of Theorem 12 is already taken care of because the intervals are examined only in non-decreasing order of \(intvl.st+intvl.\lambda\). ```
1:Create a new \(newWClass\leftarrow(t_{start},\infty,0,nbrs_{s}[0])\) as an instance of \(mwfWClass\). Values are assigned to fields \(arrivTmStrt,arrivTmEnd,wtTm,lastExpAt\), respectively. Last field is an array of size out degree of vertex \(s\). 2:Initialize \(mwfWalks[s]\leftarrow\)\(newWClass\); initialize \(listWClass[s].pushback(newWClass)\); \(\forall v\in V,v\
eq s,mwfWalks[v]\gets null\)
3:\(nodesRchd\gets 1;staticIntvls\gets intvlList.size\); \(idxStaticIntvls\gets 0\)
4:\(setupNewWClass(s,newWClass.arrivTmStrt)\)
5:\(reachableNodes\gets getReachableNodes(G,s)\)
6:\(newIntvl\gets removeMinIntvl()\)
7:while (\((indxStaticIntvls<staticIntvls)\) or \(!PQ.empty()\)) and (\(nodesRchd<reachableNodes\)) do
8:\(curTm\gets newIntvl.st+newIntvl.\lambda\)
9:\(u=newIntvl.u;v=newIntvl.v\)
10:\(newVs\gets 0\)
11:while (\(curTm==newIntvl.st+newIntvl.\lambda\)) do
12:if (\(newIntvl.v\
eq s\)) then
13:\(prevWIntx\gets getPreW(newIntvl)\)
14:if\(prevWIntx\
eq-1\)then
15:\(newW\gets createNewW(listWClasses[u][prevWIdx],newIntvl)\)
16:if\(newW\)then
17:\(ints\leftarrow\)\(insNewW(newW,v)\)\(\triangleright\) Inserts \(newW\) in list of walks at \(v\). If \(newW\) is best \(mwf\) walk it is recorded in \(mwfWalks[v]\)
18:if\(ins==NEW\)then
19:\(newVs++\)
20:endif
21:if\(ins\
eq 0\)then
22:\(setupNewWClass(v,newW.strtTm)\)
23:endif
24:endif
25:endif
26:endif
27:\(newIntvl\gets removeMinIntvl()\)
28:endwhile
29:\(nodesRchd+=newVs\)
30:endwhile
```  
**Algorithm 2** Min-wait foremost walks algorithm  
After the new walk is created on an edge \((u,v)\), it is appended to the list of walks at \(v\). To qualify as a valid walk to be appended to the list of walks at \(v\), it needs to be compared for dominance with only the last walk in the list at \(v\) due to Theorem 9. This walk is appended to the list at \(v\) only if it is not dominated. The insert function also checks if this is the first walk arriving at \(v\). If so, it updates the \(mwfWalks\) for vertex \(v\) and increments the count of \(newVs\). If this is not the first walk to arrive at \(v\), but if it is _better_ w.r.t \(mwf\) arrival than the best known walk at \(v\), \(mwfWalks\) is updated for vertex \(v\).