![]() |
Vcsn
2.3a
Be Rational
|
Compute the shortest words accepted by an automaton. More...
#include <shortest.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 | 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 > |
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... | |
polynomial_t | operator() (state_t src, state_t dst) |
The approximated behavior of a part of the automaton (looks for one word of unspecified length). More... | |
Private Member Functions | |
template<typename LabelSet = labelset_t_of<context_t>> | |
auto | shortest_ (unsigned num, unsigned len, state_t_of< Aut > src=Aut::element_type::pre(), state_t_of< Aut > dst=Aut::element_type::post()) -> std::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, state_t_of< Aut > src=Aut::element_type::pre(), state_t_of< Aut > dst=Aut::element_type::post()) -> std::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() |
Shorthand to the weightset. More... | |
const polynomialset_t | ps_ = make_word_polynomialset(aut_->context()) |
Shorthand to the polynomialset of words. More... | |
const labelset_t & | ls_ = *ps_.labelset() |
Shorthand to the (word) labelset. More... | |
Compute the shortest words accepted by an automaton.
Definition at line 30 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::automaton_t = Aut |
Definition at line 33 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::context_t = context_t_of<Aut> |
Definition at line 34 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::labelset_t = labelset_t_of<polynomialset_t> |
Wordset.
Definition at line 41 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::polynomial_t = typename polynomialset_t::value_t |
Definition at line 38 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::polynomialset_t = polynomialset<wordset_context_t> |
Definition at line 37 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::profile_t = std::tuple<state_t, word_t, weight_t> |
Used in the case of non-free labelsets.
Definition at line 49 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::state_t = state_t_of<automaton_t> |
Definition at line 46 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::weight_t = weight_t_of<automaton_t> |
Definition at line 45 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::weightset_t = weightset_t_of<automaton_t> |
Definition at line 44 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::word_t = word_t_of<automaton_t> |
Definition at line 42 of file shortest.hh.
using vcsn::detail::enumerater< Aut >::wordset_context_t = word_context_t<context_t> |
Definition at line 36 of file shortest.hh.
|
inline |
Prepare to compute an approximation of the behavior.
aut | the automaton to approximate |
Definition at line 67 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 75 of file shortest.hh.
References vcsn::detail::enumerater< Aut >::shortest_().
|
inline |
The approximated behavior of a part of the automaton (looks for one word of unspecified length).
src | the starting state of the calculation |
dst | the ending state of the calculation. |
Definition at line 91 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 107 of file shortest.hh.
References vcsn::detail::all_out(), vcsn::detail::enumerater< Aut >::aut_, vcsn::detail::enumerater< Aut >::ls_, vcsn::detail::enumerater< Aut >::ps_, vcsn::res, 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 165 of file shortest.hh.
References vcsn::detail::all_out(), vcsn::detail::enumerater< Aut >::aut_, vcsn::detail::enumerater< Aut >::ls_, vcsn::detail::enumerater< Aut >::ps_, vcsn::res, and vcsn::detail::enumerater< Aut >::ws_.
|
inlineprivate |
Show the heap, for debugging.
Definition at line 243 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 259 of file shortest.hh.
Referenced by vcsn::detail::enumerater< Aut >::shortest_(), and vcsn::detail::enumerater< Aut >::show_heap_().
|
private |
Shorthand to the (word) labelset.
Definition at line 265 of file shortest.hh.
Referenced by vcsn::detail::enumerater< Aut >::shortest_(), and vcsn::detail::enumerater< Aut >::show_heap_().
|
private |
Shorthand to the polynomialset of words.
Definition at line 263 of file shortest.hh.
Referenced by vcsn::detail::enumerater< Aut >::shortest_().
|
private |
Shorthand to the weightset.
Definition at line 261 of file shortest.hh.
Referenced by vcsn::detail::enumerater< Aut >::shortest_(), and vcsn::detail::enumerater< Aut >::show_heap_().