2k-1 Approximate Vertex-Vertex Distance Oracle

# Problem definition.

In a vertex-vertex distance oracle problem we are given a graph $$G(V,E)$$. The goal is to build an oracle, a structure that answer queries about a distance between two vertices. An oracle may return approximated distances in favor of better running time than standard shortest-path algorithms.

# Solution

We solve the problem by constructing 2k-1 Approximate Distance Oracle of Thorup and Zwick [21].

We begin a construction of the oracle by selecting a sequence of $$k+1$$ layers

\begin{eqnarray*} V = A_0 \supseteq A_1 \supseteq \dots \supseteq A_k = \emptyset \end{eqnarray*}

For each vertex $$v$$ and each layer $$A_i$$ we find a parent $$p_i(v)$$, which is a vertex of $$A_i$$ closest to $$v$$. For each vertex $$v$$ we compute distances to all vertices in its bunch

\begin{eqnarray*} B(v) = \sum_{i=0}^{k-1} \lbrace u : u \in A_i \setminus A_{i+1}, \delta(v,u) < \delta(v,A_{i+1}) \rbrace \end{eqnarray*}

As an approximate distance between vertices $$u$$ and $$v$$ the oracle returns a distance $$\delta(u,p_i(u)) + \delta(p_i(u),v)$$ with $$p_i(u) \in B(v)$$ for an appropriate $$i$$.

# Example

#include "test/test_utils/sample_graph.hpp"
#include <iostream>
int main() {
using SGM = sample_graphs_metrics;
using Graph = SGM::Graph;
const Graph g = SGM::get_graph_small();
const int k = 2;
std::cout << "Approximate distance between A and C is " << oracle(SGM::A, SGM::C) << std::endl;
}

complete example is distance_oracle_example.cpp

# Parameters

IN: const Graph& g

IN: int k - an approximation parameter

IN: const boost::bgl_named_params<P, T, R>& params = boost::no_named_parameters()

IN: Rand && random_engine=std::default_random_engine(5426u)

# Named parameters

IN: vertex_index_map(VertexIndexMap indexMap)

IN: weight_map(EdgeWeightMap weightMap) - a map containing weights of edges

# Approximation ratio

Approximation ratio equals $$2k-1$$ for a given positive integer $$k$$.

# Complexity

The query time complexity is $$O(k)$$, where $$k$$ is an approximation parameter. The oracle requires expected $$O(kmn^{1/k})$$ initialization time and expected $$O(kn^{1+1/k})$$ space, where $$n$$ is a number of graph vertices and $$m$$ is a number of its edges.

# References

The oracle is described in [21].