Vcsn  2.4
Be Rational
vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue > Struct Template Reference

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_taut_
 
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
AutThe type of the automaton.
ValueSetcould be either a labelset or weightset. Must have a less and a one member function.
Mullambda multiplying the current best candidate with the value taken from the transition given in parameter.
GetValuelambda 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
AnyAutthe 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
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
AnyAutthe 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()().

Member Data Documentation

template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >
const automaton_t& vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::aut_
template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >
GetValue vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::get_value_
template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >
Mul vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::mul_
template<Automaton Aut, typename ValueSet , typename Mul , typename GetValue >
const ValueSet& vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::vs_

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