# Finding Top-\(k\) Nodes for Temporal Closeness in Large Temporal Graphs
## 4 How to Deal with Multiple Edges  
In the previous sections, we have assumed that, for each time \(t\in\mathcal{T}(G)\), there exists at most one edge whose appearing time is equal to \(t\). Clearly, this assumption is not realistic since, in the vast majority of real-world temporal graphs, many edges can appear at the same time. In this section, we show how we can modify Algorithm 2, in order to deal with this more general case (the modification of Algorithm 1 is similar). For the sake of clarity of exposition, we will assume that, for each node \(u\), the algorithm maintains a list \(I_{u}\) of triples (instead of just one triple): it is not difficult to show that only the last two triples are really necessary at each iteration of the algorithm, thus assuring that the algorithm itself has linear space complexity.  
Let us suppose that a new temporal edge \(e=(x,y,t)\) arrives, and that the last triple inserted in \(I_{x}\) (respectively, \(I_{y}\)) is \((l_{x},r_{x},s_{x})\) (respectively, \((l_{y},r_{y},s_{y})\)). This implies that that if we want to arrive at the destination \(d\) in the interval \([l_{x},r_{x})\) (respectively, \([l_{y},r_{y})\)), then we cannot start from \(x\) (respectively, \(y\)) later than \(s_{x}\) (respectively, \(s_{y}\)). Remember that, in Algorithm 2, the temporal edges are scanned in non-increasing order with respect to their appearing times: hence, we know that \(t\leq s_{x}\leq l_{x}<r_{x}\) (respectively, \(t\leq s_{y}\leq l_{y}<r_{y}\)). We now distinguish the following cases.  
1. \(t<s_{x}\wedge t<s_{y}\). In this case, neither \(x\) nor \(y\) has yet used an edge at time \(t\). Hence, we can update the set of intervals as we did in the case of edges with distinct appearing times. That is, if \(l_{y}<l_{x}\), then add to \(l_{x}\) the triple \((l_{y},l_{x},t)\).  
2. \(t<s_{x}\wedge t=s_{y}\). In this case, \(y\) has already \"encountered\" an edge at time \(t\). Let \((l_{y}^{\prime},r_{y}^{\prime},s_{y}^{\prime})\) be the triple just before \((l_{y},r_{y},s_{y})\) in \(l_{y}\) (note that \(l_{y}^{\prime}=r_{y}\) and that \(t=s_{y}<s_{y}^{\prime}\)). If \(l_{y}^{\prime}<l_{x}\), then we add to \(l_{x}\) the triple \((l_{y}^{\prime},l_{x},t)\): indeed, since \(t<s_{y}^{\prime}\), we now know that, to arrive at \(d\) in the interval \([l_{y}^{\prime},l_{x})\), we can start from \(u\) at time \(t\) (by using the edge \(e\)), wait until time \(s_{y}^{\prime}\), and then follow the journey from \(y\) to \(d\).
3. \(t=s_{x}\wedge t<s_{y}\). In this case, \(x\) has already \"encountered\" an edge at time \(t\). If \(l_{y}<l_{x}\), then we extend to the left the triple of \(x\) until \(l_{y}\): indeed, since \(s_{x}<s_{y}\), we now know that, even to arrive at \(d\) in the interval \([l_{y},l_{x})\), we can start at time \(t\) (by using the edge \(e\)), wait until time \(s_{y}\), and then follow the journey from \(y\) to \(d\).
4. \(t=s_{x}\wedge t=s_{y}\). In this case, both \(x\) and \(y\) have already \"encountered\" an edge at time \(t\). Let \((l_{y}^{\prime},r_{y}^{\prime},s_{y}^{\prime})\) be the triple just before \((l_{y},r_{y},s_{y})\) in \(l_{y}\) (note that \(l_{y}^{\prime}=r_{y}\) and \(t=s_{y}<s_{y}^{\prime}\)). Similarly to the previous case, if \(l_{y}^{\prime}<l_{x}\), then we extend to the left the triple of \(x\) until \(l_{y}^{\prime}\).  
Note that the modification of the contribution to \(C(x,d)\) has to be done only in the first two cases (and at the end of the while loop, in order to deal with the leftmost intervals). Note also that the four above cases require constant time, in order to be implemented: hence, the time complexity of the modified algorithm is still linear in the number of temporal edges.