Vcsn  2.2
Be Rational
vcsn::detail::enumerater< Aut > Class Template Reference

Compute the shortest words accepted by an automaton. More...

#include <shortest.hh>

Collaboration diagram for vcsn::detail::enumerater< Aut >:

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...
 

Private Member Functions

template<typename LabelSet = labelset_t_of<context_t>>
auto shortest_ (unsigned num, unsigned len) -> 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) -> 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_tws_ = *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_tls_ = *ps_.labelset()
 Shorthand to the (word) labelset. More...
 

Detailed Description

template<Automaton Aut>
class vcsn::detail::enumerater< Aut >

Compute the shortest words accepted by an automaton.

Definition at line 29 of file shortest.hh.

Member Typedef Documentation

template<Automaton Aut>
using vcsn::detail::enumerater< Aut >::automaton_t = Aut

Definition at line 32 of file shortest.hh.

template<Automaton Aut>
using vcsn::detail::enumerater< Aut >::context_t = context_t_of<Aut>

Definition at line 33 of file shortest.hh.

template<Automaton Aut>
using vcsn::detail::enumerater< Aut >::labelset_t = labelset_t_of<polynomialset_t>

Wordset.

Definition at line 40 of file shortest.hh.

template<Automaton Aut>
using vcsn::detail::enumerater< Aut >::polynomial_t = typename polynomialset_t::value_t

Definition at line 37 of file shortest.hh.

template<Automaton Aut>
using vcsn::detail::enumerater< Aut >::polynomialset_t = polynomialset<wordset_context_t>

Definition at line 36 of file shortest.hh.

template<Automaton Aut>
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 48 of file shortest.hh.

template<Automaton Aut>
using vcsn::detail::enumerater< Aut >::state_t = state_t_of<automaton_t>

Definition at line 45 of file shortest.hh.

template<Automaton Aut>
using vcsn::detail::enumerater< Aut >::weight_t = weight_t_of<automaton_t>

Definition at line 44 of file shortest.hh.

template<Automaton Aut>
using vcsn::detail::enumerater< Aut >::weightset_t = weightset_t_of<automaton_t>

Definition at line 43 of file shortest.hh.

template<Automaton Aut>
using vcsn::detail::enumerater< Aut >::word_t = word_t_of<automaton_t>

Definition at line 41 of file shortest.hh.

template<Automaton Aut>
using vcsn::detail::enumerater< Aut >::wordset_context_t = word_context_t<context_t>

Definition at line 35 of file shortest.hh.

Constructor & Destructor Documentation

template<Automaton Aut>
vcsn::detail::enumerater< Aut >::enumerater ( const automaton_t aut)
inline

Prepare to compute an approximation of the behavior.

Parameters
autthe automaton to approximate

Definition at line 66 of file shortest.hh.

Member Function Documentation

template<Automaton Aut>
polynomial_t vcsn::detail::enumerater< Aut >::operator() ( boost::optional< unsigned >  num,
boost::optional< unsigned >  len 
)
inline

The approximated behavior of the automaton.

Parameters
numnumber of words looked for.
lenmaximum length of words looked for.

Definition at line 73 of file shortest.hh.

References vcsn::detail::enumerater< Aut >::aut_, vcsn::detail::make_dijkstra_impl(), vcsn::weightset_mixin< WeightSet >::mul(), vcsn::path_monomial(), vcsn::detail::enumerater< Aut >::ps_, and vcsn::detail::enumerater< Aut >::shortest_().

Here is the call graph for this function:

template<Automaton Aut>
template<typename LabelSet = labelset_t_of<context_t>>
auto vcsn::detail::enumerater< Aut >::shortest_ ( unsigned  num,
unsigned  len 
) -> std::enable_if_t<LabelSet::is_free(), polynomial_t>
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 111 of file shortest.hh.

References vcsn::detail::all_out(), 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()().

Here is the call graph for this function:

template<Automaton Aut>
template<typename LabelSet = labelset_t_of<context_t>>
auto vcsn::detail::enumerater< Aut >::shortest_ ( unsigned  num,
unsigned  len 
) -> std::enable_if_t<!LabelSet::is_free(), polynomial_t>
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_, and vcsn::detail::enumerater< Aut >::ws_.

Here is the call graph for this function:

template<Automaton Aut>
template<typename Queue >
void vcsn::detail::enumerater< Aut >::show_heap_ ( const Queue &  q,
std::ostream &  os = std::cerr 
) const
inlineprivate

Show the heap, for debugging.

Definition at line 234 of file shortest.hh.

References vcsn::detail::enumerater< Aut >::aut_, vcsn::detail::enumerater< Aut >::ls_, os, and vcsn::detail::enumerater< Aut >::ws_.

Member Data Documentation

template<Automaton Aut>
automaton_t vcsn::detail::enumerater< Aut >::aut_
private

The automaton whose behavior to approximate.

Definition at line 250 of file shortest.hh.

Referenced by vcsn::detail::enumerater< Aut >::operator()(), vcsn::detail::enumerater< Aut >::shortest_(), and vcsn::detail::enumerater< Aut >::show_heap_().

template<Automaton Aut>
const labelset_t& vcsn::detail::enumerater< Aut >::ls_ = *ps_.labelset()
private

Shorthand to the (word) labelset.

Definition at line 256 of file shortest.hh.

Referenced by vcsn::detail::enumerater< Aut >::shortest_(), and vcsn::detail::enumerater< Aut >::show_heap_().

template<Automaton Aut>
const polynomialset_t vcsn::detail::enumerater< Aut >::ps_ = make_word_polynomialset(aut_->context())
private

Shorthand to the polynomialset of words.

Definition at line 254 of file shortest.hh.

Referenced by vcsn::detail::enumerater< Aut >::operator()(), and vcsn::detail::enumerater< Aut >::shortest_().

template<Automaton Aut>
const weightset_t& vcsn::detail::enumerater< Aut >::ws_ = *aut_->weightset()
private

Shorthand to the weightset.

Definition at line 252 of file shortest.hh.

Referenced by vcsn::detail::enumerater< Aut >::shortest_(), and vcsn::detail::enumerater< Aut >::show_heap_().


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