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 "paal/distance_oracle/vertex_vertex/thorup_2kminus1.hpp"
#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;

    auto oracle = paal::make_distance_oracle_thorup2kminus1approximation(g, k);

    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].