Aleph::Eppstein_K_Shortest_Paths< GT, Distance, SA > Class Template Reference

Functor wrapper for Eppstein-style k-shortest paths API. More...

#include <K_Shortest_Paths.H>

Public Member Functions
	Eppstein_K_Shortest_Paths (Distance distance=Distance(), SA sa=SA())
DynList< K_Shortest_Path_Item< GT, typename Distance::Distance_Type > >	operator() (const GT &g, typename GT::Node *source, typename GT::Node *target, const size_t k) const
	Compute k shortest general (loopy) paths.

Private Attributes
Distance	distance_
SA	sa_

Detailed Description

template<class GT, class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>
class Aleph::Eppstein_K_Shortest_Paths< GT, Distance, SA >

Functor wrapper for Eppstein-style k-shortest paths API.

Definition at line 1221 of file K_Shortest_Paths.H.

Constructor & Destructor Documentation

Eppstein_K_Shortest_Paths()

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

Aleph::Eppstein_K_Shortest_Paths< GT, Distance, SA >::Eppstein_K_Shortest_Paths ( Distance  distance = Distance(), SA  sa = SA()  )

inline

Definition at line 1227 of file K_Shortest_Paths.H.

Member Function Documentation

operator()()

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

DynList< K_Shortest_Path_Item< GT, typename Distance::Distance_Type > > Aleph::Eppstein_K_Shortest_Paths< GT, Distance, SA >::operator() ( const GT &  g, typename GT::Node *  source, typename GT::Node *  target, const size_t  k  ) const

inline

Compute k shortest general (loopy) paths.

Wrapper for eppstein_k_shortest_paths using the stored distance and filter.

Parameters

[in]	g	Graph.
[in]	source	Source node.
[in]	target	Target node.
[in]	k	Maximum number of paths to return.

Returns

DynList<K_Shortest_Path_Item<GT, Cost_Type>> containing the paths found.

Exceptions

std::domain_error	If source or target is null.
std::domain_error	If negative arc weights are detected.

Complexity

Same as eppstein_k_shortest_paths: O(E + V log V + k * log k).

Note

This implementation is NOT thread-safe.

Definition at line 1255 of file K_Shortest_Paths.H.

References Aleph::Eppstein_K_Shortest_Paths< GT, Distance, SA >::distance_, Aleph::divide_and_conquer_partition_dp(), k, and Aleph::Eppstein_K_Shortest_Paths< GT, Distance, SA >::sa_.

Member Data Documentation

distance_

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

Distance Aleph::Eppstein_K_Shortest_Paths< GT, Distance, SA >::distance_

private

Definition at line 1223 of file K_Shortest_Paths.H.

Referenced by Aleph::Eppstein_K_Shortest_Paths< GT, Distance, SA >::operator()().

sa_

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

SA Aleph::Eppstein_K_Shortest_Paths< GT, Distance, SA >::sa_

private

Definition at line 1224 of file K_Shortest_Paths.H.

Referenced by Aleph::Eppstein_K_Shortest_Paths< GT, Distance, SA >::operator()().

---

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

• K_Shortest_Paths.H