![]() |
Vcsn
2.3a
Be Rational
|
The lightest algorithm computes the paths between pre and post with the smallest weight possible. More...
#include <lightest.hh>
Classes | |
struct | profile_less |
Public Types | |
using | automaton_t = Aut |
using | context_t = context_t_of< Aut > |
using | wordset_context_t = word_context_t< context_t > |
using | polynomialset_t = polynomialset< wordset_context_t > |
using | polynomial_t = typename polynomialset_t::value_t |
using | monomial_t = typename polynomialset_t::monomial_t |
using | labelset_t = labelset_t_of< polynomialset_t > |
Wordset. More... | |
using | word_t = word_t_of< automaton_t > |
using | weightset_t = weightset_t_of< automaton_t > |
using | weight_t = weight_t_of< automaton_t > |
using | state_t = state_t_of< automaton_t > |
using | profile_t = std::tuple< state_t, word_t, weight_t > |
using | queue_t = boost::heap::binomial_heap< profile_t, boost::heap::compare< profile_less >> |
Public Member Functions | |
lightest_impl (const automaton_t &aut) | |
Prepare to compute an approximation of the behavior. More... | |
polynomial_t | operator() (unsigned num) |
The approximated behavior of the automaton. More... | |
Private Member Functions | |
polynomial_t | lightest_ (unsigned num) |
void | show_heap_ (const queue_t &q, std::ostream &os=std::cerr) |
Show the heap, for debugging. More... | |
Private Attributes | |
automaton_t | aut_ |
The automaton whose behavior to approximate. More... | |
const weightset_t & | ws_ = *aut_->weightset() |
const polynomialset_t | ps_ = make_word_polynomialset(aut_->context()) |
const labelset_t & | ls_ = *ps_.labelset() |
The lightest algorithm computes the paths between pre and post with the smallest weight possible.
This functor will construct the polynomial composed with each one of the num
smallest paths. This implementation uses a priority queue that will order states by their weights (then labels).
Definition at line 37 of file lightest.hh.
using vcsn::detail::lightest_impl< Aut >::automaton_t = Aut |
Definition at line 40 of file lightest.hh.
using vcsn::detail::lightest_impl< Aut >::context_t = context_t_of<Aut> |
Definition at line 41 of file lightest.hh.
using vcsn::detail::lightest_impl< Aut >::labelset_t = labelset_t_of<polynomialset_t> |
Wordset.
Definition at line 49 of file lightest.hh.
using vcsn::detail::lightest_impl< Aut >::monomial_t = typename polynomialset_t::monomial_t |
Definition at line 46 of file lightest.hh.
using vcsn::detail::lightest_impl< Aut >::polynomial_t = typename polynomialset_t::value_t |
Definition at line 45 of file lightest.hh.
using vcsn::detail::lightest_impl< Aut >::polynomialset_t = polynomialset<wordset_context_t> |
Definition at line 44 of file lightest.hh.
using vcsn::detail::lightest_impl< Aut >::profile_t = std::tuple<state_t, word_t, weight_t> |
Definition at line 56 of file lightest.hh.
using vcsn::detail::lightest_impl< Aut >::queue_t = boost::heap::binomial_heap<profile_t, boost::heap::compare<profile_less>> |
Definition at line 89 of file lightest.hh.
using vcsn::detail::lightest_impl< Aut >::state_t = state_t_of<automaton_t> |
Definition at line 54 of file lightest.hh.
using vcsn::detail::lightest_impl< Aut >::weight_t = weight_t_of<automaton_t> |
Definition at line 53 of file lightest.hh.
using vcsn::detail::lightest_impl< Aut >::weightset_t = weightset_t_of<automaton_t> |
Definition at line 52 of file lightest.hh.
using vcsn::detail::lightest_impl< Aut >::word_t = word_t_of<automaton_t> |
Definition at line 50 of file lightest.hh.
using vcsn::detail::lightest_impl< Aut >::wordset_context_t = word_context_t<context_t> |
Definition at line 43 of file lightest.hh.
|
inline |
Prepare to compute an approximation of the behavior.
aut | the automaton to approximate |
Definition at line 94 of file lightest.hh.
|
inlineprivate |
Fuse equivalent cases, which might increase the first element's weight. Hence, restart loop with sorted queue.
Definition at line 108 of file lightest.hh.
References vcsn::detail::all_out(), vcsn::detail::lightest_impl< Aut >::aut_, vcsn::detail::lightest_impl< Aut >::ls_, vcsn::detail::lightest_impl< Aut >::ps_, vcsn::res, and vcsn::detail::lightest_impl< Aut >::ws_.
Referenced by vcsn::detail::lightest_impl< Aut >::operator()().
|
inline |
The approximated behavior of the automaton.
num | number of words looked for. |
Definition at line 100 of file lightest.hh.
References vcsn::detail::lightest_impl< Aut >::aut_, vcsn::has_lightening_cycle(), vcsn::detail::lightest_impl< Aut >::lightest_(), and vcsn::require().
|
inlineprivate |
Show the heap, for debugging.
Definition at line 160 of file lightest.hh.
References vcsn::detail::lightest_impl< Aut >::aut_, vcsn::detail::lightest_impl< Aut >::ls_, os, and vcsn::detail::lightest_impl< Aut >::ws_.
|
private |
The automaton whose behavior to approximate.
Definition at line 177 of file lightest.hh.
Referenced by vcsn::detail::lightest_impl< Aut >::lightest_(), vcsn::detail::lightest_impl< Aut >::operator()(), and vcsn::detail::lightest_impl< Aut >::show_heap_().
|
private |
Definition at line 180 of file lightest.hh.
Referenced by vcsn::detail::lightest_impl< Aut >::lightest_(), and vcsn::detail::lightest_impl< Aut >::show_heap_().
|
private |
Definition at line 179 of file lightest.hh.
Referenced by vcsn::detail::lightest_impl< Aut >::lightest_().
|
private |
Definition at line 178 of file lightest.hh.
Referenced by vcsn::detail::lightest_impl< Aut >::lightest_(), and vcsn::detail::lightest_impl< Aut >::show_heap_().