# 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 o_removal\([v]\leftarrow\emptyset\);
5 mark\([x]\leftarrow\) true;
6 Q_Insert\((\langle x,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{b}}(x,y)\) : \(h\in\operatorname{L}_{\texttt{out}}(v)\)dooutdated\([h]\leftarrow\) true; /* Removal Test */
10 foreach\(u\in\operatorname{N}_{\texttt{out}}(v)\) : \(u\
ot\in\texttt{OUT}\)do
11 foreach\(h\in\operatorname{H}_{\texttt{b}}(x,y)\) : \(h\in\operatorname{L}_{\texttt{out}}(v)\)do
12 if\(h\in\operatorname{L}_{\texttt{out}}(u)\wedge\delta_{vh}=w(v,u)+\delta_{uh}\)then
13 OUTdated\([h]\leftarrow\) false;
14 break;
15
16 foreach\(h\in\operatorname{H}_{\texttt{b}}(x,y)\) : \(h\in\operatorname{L}_{\texttt{out}}(v)\)do
17 ifoutdated\([h]=\) truethen /* Selected for Removal */
18 o_removal\([v]\leftarrow\) o_removal\([v]\cup\{h\}\);
19 if\(\{h^{\prime}\in V\) : \(h^{\prime}\in\operatorname{L}_{\texttt{out}}(v)\wedge h^{\prime}\in \operatorname{L}_{\texttt{in}}(y),\delta_{vh^{\prime}}+\delta_{h^{\prime}y}= \delta\}\
eq\emptyset\)then /* Membership to Forward Cover Graph */
20 OUT\(\leftarrow\) OUT \(\cup\{v\}\);
21\(\texttt{relax}(\delta,v,\operatorname{N}_{\texttt{in}}(u),\texttt{false})\);
22 return(o_removal,OUT);
```

**Algorithm 5**Procedure fclean

```
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\);
2 foreach\(v\in V\)do
3 mark\([v]\leftarrow\) false;
4 i_removal\([v]\leftarrow\emptyset\);
5 mark\([y]\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 foreach\(h\in\operatorname{H}_{\texttt{f}}(x,y)\) : \(h\in\operatorname{L}_{\texttt{in}}(v)\)do
16 ifoutdated\([h]=\) truethen /* Selected for Removal */
17 i_removal\([v]\leftarrow\) i_removal\([v]\cup\{h\}\);
18 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 */
19 IN\(\leftarrow\) IN\(\cup\{v\}\);
20 RELAX\((\delta,v,\operatorname{N}_{\texttt{out}}(u),\texttt{true})\);
21 return(i_removal,IN);
```

**Algorithm 6**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.