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

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

aut	the 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

num	number of words looked for.
len	maximum 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>>