# 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\((G^{\prime},L^{\prime},OUT,IN)\leftarrow\textsc{clean}(G,L,x,y)\);
2\(L^{\prime}\leftarrow\textsc{recover}(G^{\prime},L^{\prime},OUT,IN,



### Clean Phase

Given an arc \((x,y)\in A\) that undergoes a decremental update, the clean phase aims at performing a more efficient regarding bidir-2 hc, removal of outdated labels, by finding and removing all and only _outdated label entries_ (from now on simply referred to as outdated entries) from the labeling, i.e., by avoiding to remove any correct entry. This is obtained by scanning the labels of vertices that are actually subject to entry removals and, contextually, by identifying pairs of vertices that might remain \"uncovered\" (i.e., without an hub in the labeling) after the removal of the mentioned incorrect label entries. This last identification step is necessary to test that the cover property for the new graph efficiently, in a next phase. The two purposes above are achieved, in detail, by:

1. determining two sets of vertices, named _forward invalid hubs_ and _backward invalid hubs_, respectively, that are hubs for some pair in \(G\) but might stop being hubs in \(G^{\prime}\), due to the operation on \((x,y)\), so to remove from \(L\) the incorrect entries associated with such vertices;
2. identifying and exploring two (virtual) subgraphs of the input graph, named _forward cover graph_ and _backward cover graph_, respectively, and denoted by \(F^{L}_{G}(x,y)\) and \(B^{L}_{G}(x,y)\), respectively In more details, to define our algorithm we give the following definitions. **Definition 1** (Forward Cover Graph). : _Given a graph \(G=(V,A)\), a 2-hop-cover labeling \(L\) of \(G\), an arc \((x,y)\in A\). The forward cover graph \(F^{L}_{G}(x,y)\) is a subgraph of \(G\) with \(V^{\prime}\) and \(A^{\prime}\) as vertex and arc sets, respectively, as follows:_

* _a vertex_ \(u\) _is in_ \(V^{\prime}\) _if_ \(u\in V\) _and there exist two pairs_ \((h,\delta_{uh})\in L_{out}(u)\) _and_ \((h,\delta_{hy})\in L_{in}(y)\) _such that_ \(\delta_{uh}+\delta_{hy}=d_{G}(u,y)=d_{G}(u,x)+w(x,y)\) _(that is a shortest path from_ \(u\) _to_ \(y\) _includes_ \((x,y)\) _and_ \(h\) _is a hub vertex for pair_ \(u,y\)_);_
* _an arc_ \((u,v)\) _is in_ \(A^{\prime}\) _if_ \((u,v)\in A\) _and_ \(u,v\in V^{\prime}\) _(hence_ \(d_{G}(u,y)=w(u,v)+d_{G}(v,x)+w(x,y)\)_)._

In other words, vertices of the forward cover graph are those with, in \(G\), a shortest path toward \(y\) that might contain arc \((x,y)\) and hence whose distance toward \(y\) might change as a consequence of a decremental operation occurring on \((x,y)\). Please note that whether the distance toward \(y\) changes or not depends on the number of shortest paths from the vertex to \(y\) that are in the graph, and on the vertex ordering (see Figure 3a for a graphical example of two different vertices of the forward cover graph). Note also that the arcs of such graph are the arcs of a shortest-path arborescence of \(G\) rooted at \(x\) plus arc \((x,y)\). Symmetrically, we define a backward version of the cover graph as follows. **Definition 2** (Backward Cover Graph). : _Given a graph \(G=(V,A)\), a 2-hop-cover labeling \(L\) of \(G\) and an arc \((x,y)\in A\).