All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
Classes | Public Member Functions | List of all members
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
Graphgraph
EdgeWeightMapedge weight map
VertexIndexMapvertex index map
Randrandom 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
ggraph
indexvertex index map
edge_weightedge weight map
kapproximation parameter
random_enginerandom 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: