![]() |
Vcsn
2.3a
Be Rational
|
Yen implementation of the K lightest automaton algorithm. More...
#include <k-lightest-path.hh>
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_ |
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.
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.
using vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::automaton_t = Aut |
Definition at line 42 of file k-lightest-path.hh.
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.
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.
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.
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.
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.
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.
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.
using vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::valueset_t = ValueSet |
Definition at line 50 of file k-lightest-path.hh.
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.
|
inline |
Definition at line 53 of file k-lightest-path.hh.
|
inline |
Compute a lightest path on a part of the automaton.
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()().
|
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_.
|
inline |
Transform a map transition_t -> transition_t representing the predecessors of each transition into a list of transitions used for concatenating paths.
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()().
const automaton_t& vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::aut_ |
Definition at line 203 of file k-lightest-path.hh.
Referenced by vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::operator()().
GetValue vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::get_value_ |
Definition at line 206 of file k-lightest-path.hh.
Referenced by vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::operator()().
Mul vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::mul_ |
Definition at line 205 of file k-lightest-path.hh.
Referenced by vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::compute_lightest_path().
const ValueSet& vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::vs_ |
Definition at line 204 of file k-lightest-path.hh.
Referenced by vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::compute_lightest_path(), and vcsn::detail::yen_impl< Aut, ValueSet, Mul, GetValue >::operator()().