# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 3 A New Algorithm: queue-2 hc
### Profiling of Algorithm bidir-2 hc
1\(\texttt{Q}\leftarrow\emptyset\);
2 foreach\(v\in V\)do
3 mark\([v]\leftarrow\) false;
4 i_removal\([v]\leftarrow\emptyset\);
5 mark\([v]\leftarrow\) true;
6 Q_Insert\((\langle y,w(x,y)\rangle)\);
7 while\(\texttt{Q}\
eq\emptyset\)do
8\((v,\delta)\leftarrow\texttt{Q.deleteMin}()\);
9 foreach\(h\in\operatorname{H}_{\texttt{f}}(x,y)\) : \(h\in\operatorname{L}_{\texttt{in}}(v)\)dooutdated\([h]\leftarrow\) true; /* Removal Test */
10 foreach\(u\in\operatorname{N}_{\texttt{in}}(v)\) : \(u\
ot\in\texttt{IN}\)do
11 foreach\(h\in\operatorname{H}_{\texttt{f}}(x,y)\) : \(h\in\operatorname{L}_{\texttt{in}}(v)\)do
12 if\(h\in\operatorname{L}_{\texttt{in}}(u)\wedge\delta_{hv}=\delta_{hu}+w(v,u)\)then
13 OUTdated\([h]\leftarrow\) false;
14 break;
15 break;
16 foreach\(h\in\operatorname{H}_{\texttt{f}}(x,y)\) : \(h\in\operatorname{L}_{\texttt{in}}(v)\)do
17 ifoutdated\([h]=\) truethen /* Selected for Removal */
18 i_removal\([v]\leftarrow\) i_removal\([v]\cup\{h\}\);
19 if\(\{h^{\prime}\in V\) : \(h^{\prime}\in\operatorname{L}_{\texttt{out}}(x)\wedge h^{\prime}\in \operatorname{L}_{\texttt{in}}(v),\delta_{kh^{\prime}}+\delta_{h^{\prime}v}= \delta\}\
eq\emptyset\)then /* Membership to Backward Cover Graph */
20 IN\(\leftarrow\) IN\(\cup\{v\}\);
21 RELAX\((\delta,v,\operatorname{N}_{\texttt{out}}(u),\texttt{true})\);
22 return(i_removal,IN);
```

**Algorithm 7**Procedure bclean

```
Input: Graph G, 2-hop-cover labeling L of G, \(\operatorname{arc}\left(x,y\right)\) subject to update, set \(\operatorname{H}_{\texttt{f}}(x,y)\). Output: Set i_removal of entries to remove from incoming labels, set IN. 1\(\texttt{Q}\leftarrow\emptyset\);
23 foreach\(v\in V\)do
3 mark\([v]\leftarrow\) false;
4 i_removal\([v]\leftarrow\) false;
5 mark\([v]\leftarrow\) false;  
67 Q_Insert\((\langle x,w(x,y)
```
Input: Value \(\delta\) extracted from the queue, Vertex \(v\), neighbor set \(N\), Boolean OUTGOING. 1 if\(\textsc{OUTGOING}=\texttt{true}\)then
2 foreach\(u\in N\)do
3 if\(\
eg\texttt{mark}[u]\)then
4\(\textsc{Q.Insert}((u,\delta+w(v,u)))\);
5\(\texttt{mark}[u]\leftarrow\texttt{true}\);
6 elseif\(\textsc{Q.key}(u)>\delta+w(v,u)\)then
7\(\textsc{Q.decreaseKey}((u,\delta+w(v,u)))\);
8 else
9 foreach\(u\in N\)do
10 if\(\
eg\texttt{mark}[u]\)then
11\(\textsc{Q.Insert}((u,\delta+w(u,v)))\);
12\(\texttt{mark}[u]\leftarrow\texttt{true}\);
13 elseif\(\textsc{Q.key}(u)>\delta+w(u,v)\)then
14\(\textsc{Q.decreaseKey}((u,\delta+w(u,v)))\);
```
**Algorithm 7**Sub-Procedure relax used in Procedures fclean and bclean  
Lemma 1: _Let \(L\) be a minimal well-ordered \(2\)-hop-cover labeling of a graph \(G\). Let us assume that an arc \((x,y)\) of \(G\) undergoes a decremental update. Let \(F^{L}_{G}(x,y)\) (\(B^{L}_{G}(x,y)\), resp.) be the forward (backward, resp.) cover graph. Then, if a vertex \(v\) is in \(F^{L}_{G}(x,y)\) (in \(B^{L}_{G}(x,y)\), resp. ), we have that vertex \(v\) is added to set \(\textsc{OUT}\) by Algorithm 5 (to set \(\textsc{IN}\) by Algorithm 6, resp. )._  
Proof. : The proof is by induction on the number \(|Q|\) of deleteMin operations on the queue \(Q\). We first focus on Algorithm 5. Consider that at least one vertex is always inserted in the queue, namely \(x\), with a priority of \(w(x,y)\), the weight of the arc in \(G\). Observe that \(|Q|\) is a monotonically increasing value. _Base case_ (\(|Q|=1\)). The only time when we have \(|Q|=1\) is when \(Q=\{x\}\). Hence \(v=x\) and this shows the inductive basis since, if \(x\) is in \(F^{L}_{G}(x,y)\) we have that \(\{h^{\prime}\in V\ :\ h^{\prime}\in L_{out}(v)\wedge h^{\prime}\in L_{in}(y), \delta_{vh^{\prime}}+\delta_{h^{\prime}y}=\delta\}\
eq\emptyset\) with \(\delta=\delta_{xx}+\delta_{xy}=d_{G}(v,y)=d_{G}(v,x)+w(x,y)=d_{G}(x,x)+w(x,y)=w (x,y)\). Therefore, the vertex is added to \(\textsc{OUT}\) by the algorithm. Please note that \(x\) is always added to \(Q\). _Inductive Hypothesis._ We assume the claim holds when \(|Q|=k\), i.e., we have \(k\) extracted vertices that are in \(F^{L}_{G}(x,y)\) and have been visited by Algorithm 5.