Graph::ApproximateShortestPathProblem< Node, Edge > Class Template Reference

Approximate single-source shortest paths, whose output is at most (1+epsilon)^d times the true shortest path, where d is the depth of the node. This can be somewhat faster than running true shortest paths. More...

#include <ApproximateShortestPaths.h>

Public Member Functions
	ApproximateShortestPathProblem (const Graph< Node, Edge > &g, Real epsilon=0)
void	InitializeSource (int s)
void	InitializeSources (const vector< int > &s)
template<typename WeightFunc , typename Iterator >
void	FindPath (int t, WeightFunc w, Iterator it)
template<typename WeightFunc , typename Iterator >
int	FindAPath (const set< int > &t, WeightFunc w, Iterator it)
template<typename WeightFunc , typename Iterator >
void	FindAllPaths (WeightFunc w, Iterator it)
template<typename WeightFunc , typename InIterator , typename OutIterator >
void	IncreaseUpdate (int u, int v, WeightFunc w, InIterator in, OutIterator out)
template<typename WeightFunc , typename InIterator , typename OutIterator >
void	DecreaseUpdate (int u, int v, WeightFunc w, InIterator in, OutIterator out)
template<typename WeightFunc , typename InIterator , typename OutIterator >
void	DeleteUpdate (int u, int v, WeightFunc w, InIterator in, OutIterator out)
template<typename WeightFunc , typename Iterator >
bool	HasShortestPaths (int s, WeightFunc w, Iterator it, Real epsilon=-1)
template<typename WeightFunc >
void	FindPath_Directed (int t, WeightFunc w)
template<typename WeightFunc >
int	FindAPath_Directed (const set< int > &t, WeightFunc w)
template<typename WeightFunc >
void	FindAllPaths_Directed (WeightFunc w)
template<typename WeightFunc >
void	IncreaseUpdate_Directed (int u, int v, WeightFunc w)
template<typename WeightFunc >
void	DecreaseUpdate_Directed (int u, int v, WeightFunc w)
template<typename WeightFunc >
void	DeleteUpdate_Directed (int u, int v, WeightFunc w)
template<typename WeightFunc >
bool	HasShortestPaths_Directed (int s, WeightFunc w, Real epsilon=-1)
template<typename WeightFunc >
void	FindPath_Undirected (int t, WeightFunc w)
template<typename WeightFunc >
int	FindAPath_Undirected (const set< int > &t, WeightFunc w)
template<typename WeightFunc >
void	FindAllPaths_Undirected (WeightFunc w)
template<typename WeightFunc >
void	IncreaseUpdate_Undirected (int u, int v, WeightFunc w)
template<typename WeightFunc >
void	DecreaseUpdate_Undirected (int u, int v, WeightFunc w)
template<typename WeightFunc >
void	DeleteUpdate_Undirected (int u, int v, WeightFunc w)
template<typename WeightFunc >
bool	HasShortestPaths_Undirected (int s, WeightFunc w, Real epsilon=-1)
virtual void	SetDistance (int n, Real dn, int pn)

Public Attributes
const Graph< Node, Edge > &	g
Real	epsilon
std::vector< int >	p
std::vector< Weight >	d

Detailed Description

template<class Node, class Edge>
class Graph::ApproximateShortestPathProblem< Node, Edge >

Approximate single-source shortest paths, whose output is at most (1+epsilon)^d times the true shortest path, where d is the depth of the node. This can be somewhat faster than running true shortest paths.

See also

ShortestPathProblem

Member Function Documentation

template<class Node , class Edge >

virtual void Graph::ApproximateShortestPathProblem< Node, Edge >::SetDistance ( int  n, Real  dn, int  pn  )

inlinevirtual

Optional: a callback that is called to change the distance/parent to the node n. Subclasses can intercept this call if desired but it is the responsibility of the subclass to call 'd[n]=dn,p[n]=pn'. Otherwise undefined behavior will result!

References Math::IsInf().

---

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

• ApproximateShortestPaths.h