Vcsn
2.1
Be Rational
|
#include <shortest.hh>
Classes | |
struct | datum_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 | 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 | datum_t = std::tuple< state_t, word_t, weight_t > |
Used in the case of non-free labelsets. More... | |
Public Member Functions | |
enumerater (const automaton_t &aut) | |
Prepare to compute an approximation of the behavior. More... | |
polynomial_t | operator() (boost::optional< unsigned > num, boost::optional< unsigned > len) |
The approximated behavior of the automaton. More... | |
Private Member Functions | |
template<typename LabelSet = labelset_t_of<context_t>> | |
auto | shortest_ (unsigned num, unsigned len) -> enable_if_t< LabelSet::is_free(), polynomial_t > |
Case of free labelsets (e.g., lal or lal x lal ). More... | |
template<typename LabelSet = labelset_t_of<context_t>> | |
auto | shortest_ (unsigned num, unsigned len) -> enable_if_t<!LabelSet::is_free(), polynomial_t > |
Case of non free labelsets (e.g., law , lan x lan ). More... | |
template<typename Queue > | |
void | show_heap_ (const Queue &q, std::ostream &os=std::cerr) const |
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() |
Definition at line 26 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::automaton_t = Aut |
Definition at line 29 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::context_t = context_t_of<Aut> |
Definition at line 30 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::datum_t = std::tuple<state_t, word_t, weight_t> |
Used in the case of non-free labelsets.
Definition at line 45 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::labelset_t = labelset_t_of<polynomialset_t> |
Wordset.
Definition at line 37 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::polynomial_t = typename polynomialset_t::value_t |
Definition at line 34 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::polynomialset_t = polynomialset<wordset_context_t> |
Definition at line 33 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::state_t = state_t_of<automaton_t> |
Definition at line 42 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::weight_t = weight_t_of<automaton_t> |
Definition at line 41 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::weightset_t = weightset_t_of<automaton_t> |
Definition at line 40 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::word_t = word_t_of<automaton_t> |
Definition at line 38 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::wordset_context_t = word_context_t<context_t> |
Definition at line 32 of file shortest.hh.
|
inline |
Prepare to compute an approximation of the behavior.
aut | the automaton to approximate |
Definition at line 63 of file shortest.hh.
|
inline |
The approximated behavior of the automaton.
num | number of words looked for. |
len | maximum length of words looked for. |
Definition at line 70 of file shortest.hh.
References vcsn::detail::enumerater< Aut >::shortest_().
|
inlineprivate |
Case of free labelsets (e.g., lal
or lal x lal
).
We maintain a list of current tuples of (state, label, weight). During one round we pass them all through outgoing transitions, which gives the next list of (state, label, weight).
Each round contributes one letter to all the labels, so once we ran len
rounds, we have all the words shorter than len
letters.
Definition at line 92 of file shortest.hh.
References vcsn::detail::enumerater< Aut >::aut_, vcsn::detail::enumerater< Aut >::ls_, vcsn::detail::enumerater< Aut >::ps_, and vcsn::detail::enumerater< Aut >::ws_.
Referenced by vcsn::detail::enumerater< Aut >::operator()().
|
inlineprivate |
Case of non free labelsets (e.g., law
, lan x lan
).
We use a unique queue composed of (state, word, weight), shortest words first.
Definition at line 146 of file shortest.hh.
References vcsn::detail::enumerater< Aut >::aut_, vcsn::detail::enumerater< Aut >::ls_, vcsn::detail::enumerater< Aut >::ps_, and vcsn::detail::enumerater< Aut >::ws_.
|
inlineprivate |
Show the heap, for debugging.
Definition at line 215 of file shortest.hh.
References vcsn::detail::enumerater< Aut >::aut_, vcsn::detail::enumerater< Aut >::ls_, os, and vcsn::detail::enumerater< Aut >::ws_.
|
private |
The automaton whose behavior to approximate.
Definition at line 231 of file shortest.hh.
Referenced by vcsn::detail::enumerater< Aut >::shortest_(), and vcsn::detail::enumerater< Aut >::show_heap_().
|
private |
Definition at line 234 of file shortest.hh.
Referenced by vcsn::detail::enumerater< Aut >::shortest_(), and vcsn::detail::enumerater< Aut >::show_heap_().
|
private |
Definition at line 233 of file shortest.hh.
Referenced by vcsn::detail::enumerater< Aut >::shortest_().
|
private |
Definition at line 232 of file shortest.hh.
Referenced by vcsn::detail::enumerater< Aut >::shortest_(), and vcsn::detail::enumerater< Aut >::show_heap_().