Yen's algorithm of the K lightest paths. More...

#include <k-lightest-path.hh>

Collaboration diagram for vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >:

Classes
struct	profile

Public Types
using	automaton_t = Aut

using	context_t = context_t_of< automaton_t >

using	state_t = state_t_of< automaton_t >

using	weight_t = weight_t_of< automaton_t >

using	transition_t = transition_t_of< automaton_t >

using	path_t = path_t_of< automaton_t >

using	paths_t = std::vector< path_t >

using	valueset_t = ValueSet

using	value_t = typename valueset_t::value_t

using	heap_t = vcsn::min_fibonacci_heap< profile >
	Min heap according to the weight. More...

Public Member Functions
	yen_impl (const automaton_t &aut, const ValueSet &vs, Mul mul, GetValue get_value)

template<Automaton AnyAut>
path_t_of< AnyAut >	path (const AnyAut &aut, const predecessors_t_of< AnyAut > &path, state_t_of< AnyAut > src=AnyAut::element_type::pre(), state_t_of< AnyAut > dst=AnyAut::element_type::post())
	Transform a map transition_t -> transition_t representing the predecessors of each transition into a list of transitions used for concatenating paths. More...

template<Automaton AnyAut>
predecessors_t_of< AnyAut >	compute_lightest_path (const AnyAut &aut, state_t_of< AnyAut > src=Aut::element_type::pre(), state_t_of< AnyAut > dst=Aut::element_type::post())
	Compute a lightest path on a part of the automaton. More...

paths_t	operator() (state_t src, state_t dst, unsigned k)

Public Attributes
const automaton_t &	aut_

const ValueSet &	vs_

Mul	mul_

GetValue	get_value_

Detailed Description

template<Automaton Aut, typename ValueSet, typename Mul, typename GetValue>
struct vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >

Yen's algorithm of the K lightest paths.

Functor initialized by the automaton on which the lightest paths will be computed. And called with the source and destination states of the path, as long as the number (k) of paths to retrieve.

Template Parameters

Aut	The type of the automaton.
ValueSet	could be either a labelset or weightset. Must have a less and a one member function.
Mul	lambda multiplying the current best candidate with the value taken from the transition given in parameter.
GetValue	lambda used to retrieve the value_type expected by the single lightest path algorithm from a monomial.

Definition at line 43 of file k-lightest-path.hh.

Member Typedef Documentation

◆ automaton_t

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

using vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::automaton_t = Aut

Definition at line 45 of file k-lightest-path.hh.

◆ context_t

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

using vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::context_t = context_t_of<automaton_t>

Definition at line 46 of file k-lightest-path.hh.

◆ heap_t

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

using vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::heap_t = vcsn::min_fibonacci_heap<profile>

Min heap according to the weight.

Definition at line 84 of file k-lightest-path.hh.

◆ path_t

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

using vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::path_t = path_t_of<automaton_t>

Definition at line 50 of file k-lightest-path.hh.

◆ paths_t

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

using vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::paths_t = std::vector<path_t>

Definition at line 51 of file k-lightest-path.hh.

◆ state_t

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

using vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::state_t = state_t_of<automaton_t>

Definition at line 47 of file k-lightest-path.hh.

◆ transition_t

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

using vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::transition_t = transition_t_of<automaton_t>

Definition at line 49 of file k-lightest-path.hh.

◆ value_t

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

using vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::value_t = typename valueset_t::value_t

Definition at line 54 of file k-lightest-path.hh.

◆ valueset_t

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

using vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::valueset_t = ValueSet

Definition at line 53 of file k-lightest-path.hh.

◆ weight_t

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

using vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::weight_t = weight_t_of<automaton_t>

Definition at line 48 of file k-lightest-path.hh.

Constructor & Destructor Documentation

◆ yen_impl()

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::yen_impl	(	const automaton_t &	aut,
		const ValueSet &	vs,
		Mul	mul,
		GetValue	get_value
	)

inline

Definition at line 56 of file k-lightest-path.hh.

Member Function Documentation

◆ compute_lightest_path()

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

template<Automaton AnyAut>

predecessors_t_of<AnyAut> vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::compute_lightest_path	(	const AnyAut &	aut,
		state_t_of< AnyAut >	src = `Aut::element_type::pre()`,
		state_t_of< AnyAut >	dst = `Aut::element_type::post()`
	)

inline

Compute a lightest path on a part of the automaton.

Template Parameters

AnyAut the automaton parameter needs to be generic as this function could be used with either automaton_t or the filter automaton version of automaton_t.

Definition at line 122 of file k-lightest-path.hh.

References vcsn::detail::make_dijkstra_impl().

Here is the call graph for this function:

◆ operator()()

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

paths_t vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::operator()	(	state_t	src,
		state_t	dst,
		unsigned	k
	)

inline

Definition at line 131 of file k-lightest-path.hh.

References vcsn::format_lightest(), vcsn::lightest_path(), vcsn::detail::make_word_polynomialset(), vcsn::detail::none_of(), vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::profile::path_, vcsn::path_monomial(), vcsn::res, and vcsn::u().

Here is the call graph for this function:

◆ path()

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

template<Automaton AnyAut>

path_t_of<AnyAut> vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::path	(	const AnyAut &	aut,
		const predecessors_t_of< AnyAut > &	path,
		state_t_of< AnyAut >	src = `AnyAut::element_type::pre()`,
		state_t_of< AnyAut >	dst = `AnyAut::element_type::post()`
	)

inline

Transform a map transition_t -> transition_t representing the predecessors of each transition into a list of transitions used for concatenating paths.

Template Parameters

AnyAut the automaton parameter needs to be generic as this function could be used with either automaton_t or the filter automaton version of automaton_t.

Definition at line 96 of file k-lightest-path.hh.

References vcsn::res.

Member Data Documentation

◆ aut_

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

const automaton_t& vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::aut_

Definition at line 190 of file k-lightest-path.hh.

◆ get_value_

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

GetValue vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::get_value_

Definition at line 193 of file k-lightest-path.hh.

◆ mul_

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

Mul vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::mul_

Definition at line 192 of file k-lightest-path.hh.

◆ vs_

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >

const ValueSet& vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::vs_

Definition at line 191 of file k-lightest-path.hh.

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

vcsn/algos/k-lightest-path.hh

Classes

Public Types

Public Member Functions

Public Attributes

Detailed Description

template<Automaton Aut, typename ValueSet, typename Mul, typename GetValue> struct vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >

Member Typedef Documentation

◆ automaton_t

◆ context_t

◆ heap_t

◆ path_t

◆ paths_t

◆ state_t

◆ transition_t

◆ value_t

◆ valueset_t

◆ weight_t

Constructor & Destructor Documentation

◆ yen_impl()

Member Function Documentation

◆ compute_lightest_path()

◆ operator()()

◆ path()

Member Data Documentation

◆ aut_

◆ get_value_

◆ mul_

◆ vs_

template<Automaton Aut, typename ValueSet, typename Mul, typename GetValue>
struct vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >