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 = 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 = 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_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 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

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 40 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 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 >::context_t = context_t_of<automaton_t>

Definition at line 43 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 80 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 = path_t_of<automaton_t>

Definition at line 47 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 48 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 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 >::transition_t = transition_t_of<automaton_t>

Definition at line 46 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 51 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 50 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 45 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 53 of file k-lightest-path.hh.

Member Function Documentation

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 118 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 127 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_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 92 of file k-lightest-path.hh.

References vcsn::res.

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