paal::distance_oracle_thorup2kminus1approximation< Graph, VertexIndexMap, EdgeWeightMap, Rand > Class Template Reference

2k-1 approximate distance oracle More...

#include <thorup_2kminus1.hpp>

Public Member Functions
	distance_oracle_thorup2kminus1approximation (const Graph &g, VertexIndexMap index, EdgeWeightMap edge_weight, int k, Rand &&random_engine=Rand(5426u))
	Constructor. More...
DT	operator() (VT u, VT v) const
	Returns an 2k-1 approximate distance between two vertices in O(k) time. More...

Detailed Description

template<typename Graph, typename VertexIndexMap, typename EdgeWeightMap, typename Rand = std::default_random_engine>
class paal::distance_oracle_thorup2kminus1approximation< Graph, VertexIndexMap, EdgeWeightMap, Rand >

2k-1 approximate distance oracle

Template Parameters

Graph	graph
EdgeWeightMap	edge weight map
VertexIndexMap	vertex index map
Rand	random engine

Definition at line 51 of file thorup_2kminus1.hpp.

Constructor & Destructor Documentation

template<typename Graph , typename VertexIndexMap , typename EdgeWeightMap , typename Rand = std::default_random_engine>

paal::distance_oracle_thorup2kminus1approximation< Graph, VertexIndexMap, EdgeWeightMap, Rand >::distance_oracle_thorup2kminus1approximation ( const Graph &  g, VertexIndexMap  index, EdgeWeightMap  edge_weight, int  k, Rand &&  random_engine = Rand(5426u)  )

inline

Constructor.

Parameters

g	graph
index	vertex index map
edge_weight	edge weight map
k	approximation parameter
random_engine	random engine

Definition at line 428 of file thorup_2kminus1.hpp.

Member Function Documentation

template<typename Graph , typename VertexIndexMap , typename EdgeWeightMap , typename Rand = std::default_random_engine>

DT paal::distance_oracle_thorup2kminus1approximation< Graph, VertexIndexMap, EdgeWeightMap, Rand >::operator() ( VT  u, VT  v  ) const

inline

Returns an 2k-1 approximate distance between two vertices in O(k) time.

Returns a distance of path going through one of parents of u or v

Returns d(v, middle) + d(middle, u)

Definition at line 448 of file thorup_2kminus1.hpp.

---

The documentation for this class was generated from the following file:

• include/paal/distance_oracle/vertex_vertex/thorup_2kminus1.hpp