Yen implementation of the K lightest automaton algorithm. 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 = std::vector< transition_t >

using	paths_t = std::vector< path_t >

using	valueset_t = ValueSet

using	value_t = typename valueset_t::value_t

using	heap_t = boost::heap::fibonacci_heap< profile >

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

template<Automaton AnyAut>
path_t	path (const AnyAut &aut, const path_t &path, state_t_of< Aut > src=Aut::element_type::pre(), state_t_of< Aut > dst=Aut::element_type::post())

template<Automaton AnyAut>
path_t	compute_lightest_path (const AnyAut &aut, state_t_of< Aut > src=Aut::element_type::pre(), state_t_of< Aut > dst=Aut::element_type::post())

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 implementation of the K lightest automaton algorithm.

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

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 34 of file k-lightest-path.hh.

Member Typedef Documentation

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

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

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

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 37 of file k-lightest-path.hh.

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

using vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::heap_t = boost::heap::fibonacci_heap<profile>

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

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

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

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

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 42 of file k-lightest-path.hh.

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 38 of file k-lightest-path.hh.

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 40 of file k-lightest-path.hh.

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 45 of file k-lightest-path.hh.

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

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

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

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 39 of file k-lightest-path.hh.

Constructor & Destructor Documentation

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 47 of file k-lightest-path.hh.

Member Function Documentation

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

template<Automaton AnyAut>

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

inline

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

References vcsn::detail::make_dijkstra_impl(), vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::mul_, and vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::vs_.

Referenced by vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::operator()().

Here is the call graph for this function:

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 105 of file k-lightest-path.hh.

References vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::aut_, vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::compute_lightest_path(), vcsn::format_lightest(), vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::get_value_, vcsn::detail::make_word_polynomialset(), vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::path(), vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::profile::path_, vcsn::path_monomial(), vcsn::res, vcsn::u(), and vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::vs_.

Here is the call graph for this function:

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

template<Automaton AnyAut>

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