Functor wrapper for Yen's k-shortest loopless paths algorithm. More...

#include <K_Shortest_Paths.H>

Public Member Functions
	Yen_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 loopless 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::Yen_K_Shortest_Paths< GT, Distance, SA >

Functor wrapper for Yen's k-shortest loopless paths algorithm.

Stores a distance accessor and arc filter so that repeated calls on different graphs or node pairs reuse the same configuration. Delegates to yen_k_shortest_paths<GT, Distance, SA>.

Template Parameters

GT	Graph type (undirected or digraph).
Distance	Arc cost accessor; must expose `Distance_Type` and `operator()(Arc*)`. Defaults to `Dft_Dist<GT>`.
SA	Arc filter functor. Defaults to `Dft_Show_Arc<GT>`.

Definition at line 1162 of file K_Shortest_Paths.H.

Constructor & Destructor Documentation

◆ Yen_K_Shortest_Paths()

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

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

inline

Definition at line 1168 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::Yen_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 loopless paths.

Wrapper for yen_k_shortest_paths<GT, Distance, SA> using the stored distance accessor and arc filter.

Parameters

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

Returns: DynList<K_Shortest_Path_Item<GT, typename Distance::Distance_Type>> containing up to k simple paths in non-decreasing cost order. Fewer than k entries are returned when fewer paths exist.

Exceptions

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

Complexity: O(k * V * (E + V log V)) in the worst case. Same as yen_k_shortest_paths.

Note: This implementation is NOT thread-safe due to internal use of const_cast and Cookie_Saver that mutate node/arc cookies on the graph object passed as g. Concurrent access to the same graph from multiple threads will cause data races.

Definition at line 1203 of file K_Shortest_Paths.H.

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