17 #ifndef AWALI_ALGOS_ENUMERATE_HH
18 # define AWALI_ALGOS_ENUMERATE_HH
33 namespace awali {
namespace sttc {
43 template <
typename Aut>
49 static_assert(context_t::labelset_t::is_free(),
50 "requires free labelset");
65 using queue_t = std::list<std::pair<state_t, monomial_t>>;
70 past_[aut_->pre()] = ps_.
one();
84 for (
unsigned i = 0; i <
max && !queue.empty(); ++i)
90 for (
const auto& m: past_[aut_->post()])
91 ps_.
add_here(res, ls_.undelimit(m.first), m.second);
104 while (past_[aut_->post()].size() < num && !queue.empty())
110 for (
const auto& m: past_[aut_->post()])
112 ps_.
add_here(res, ls_.undelimit(m.first), m.second);
129 tie(s, m) = std::move(q1.front());
131 for (
const auto t: aut_->all_out(s))
134 monomial_t n(ls_.concat(m.first, aut_->label_of(t)),
135 ws_.mul(m.second, aut_->weight_of(t)));
137 q2.emplace_back(aut_->dst_of(t),
n);
146 const labelset_t_of<polynomialset_t>& ls_ = *ps_.labelset();
148 std::map<state_t, polynomial_t> past_;
160 template <
typename Automaton>
181 template <
typename Automaton>
carries the algebraic settings of automata
Definition: context.hh:40
Definition: enumerate.hh:45
Aut automaton_t
Definition: enumerate.hh:47
label_t_of< automaton_t > label_t
Definition: enumerate.hh:58
enumerater(const automaton_t &aut)
Definition: enumerate.hh:67
weightset_t_of< automaton_t > weightset_t
Definition: enumerate.hh:53
weight_t_of< automaton_t > weight_t
Definition: enumerate.hh:59
std::pair< word_t, weight_t > monomial_t
Same as polynomial_t::value_type.
Definition: enumerate.hh:64
typename polynomialset_t::value_t polynomial_t
Definition: enumerate.hh:57
std::list< std::pair< state_t, monomial_t > > queue_t
Definition: enumerate.hh:65
polynomial_t shortest(unsigned num)
The shortest accepted weighted words, or throw an exception.
Definition: enumerate.hh:97
context_t_of< Aut > context_t
Definition: enumerate.hh:48
polynomial_t enumerate(unsigned max)
The weighted accepted word with length at most max.
Definition: enumerate.hh:74
typename labelset_t_of< automaton_t >::genset_t genset_t
Definition: enumerate.hh:60
typename labelset_trait< labelset_t >::wordset_t wordset_t
Definition: enumerate.hh:54
labelset_t_of< automaton_t > labelset_t
Definition: enumerate.hh:52
typename labelset_t::word_t word_t
Definition: enumerate.hh:61
polynomialset< wordset_context_t > polynomialset_t
Definition: enumerate.hh:56
The semiring of Natural numbers.
Definition: n.hh:33
Linear combination of labels: map labels to weights.
Definition: polynomialset.hh:69
const monomial_t & monomial_one() const
Definition: polynomialset.hh:334
const value_t & one() const
Definition: polynomialset.hh:327
std::map< label_t, weight_t, internal::less< labelset_t > > value_t
Definition: polynomialset.hh:83
value_t & add_here(value_t &v, const value_t &p) const
v += p.
Definition: polynomialset.hh:130
const value_t & zero() const
Definition: polynomialset.hh:353
any_t word_t
Type for words; it is an alias to any_t since the precise type depends on the context (most of the ti...
Definition: typedefs.hh:67
bool is_empty(const Aut &aut) ATTRIBUTE_PURE
Test whether the automaton has no state.
Definition: accessible.hh:365
typename internal::label_t_of_impl< internal::base_t< ValueSet > >::type label_t_of
Helper to retrieve the type of the labels of a value set.
Definition: traits.hh:71
auto get_wordset_context(const context< LS, WS > &ctx) -> context< typename labelset_trait< LS >::wordset_t, WS >
Definition: traits.hh:216
internal::enumerater< Automaton >::polynomial_t shortest(const Automaton &aut, unsigned num)
Computes the weight of the num smallest words accepted by the automaton.
Definition: enumerate.hh:184
typename internal::weight_t_of_impl< internal::base_t< ValueSet > >::type weight_t_of
Helper to retrieve the type of the weights of a value set.
Definition: traits.hh:81
typename internal::context_t_of_impl< internal::base_t< ValueSet > >::type context_t_of
Helper to retrieve the type of the context of a value set.
Definition: traits.hh:66
Aut::element_type::automaton_nocv_t trim(const Aut &aut, bool keep_history=true)
Trim subautomaton.
Definition: accessible.hh:278
typename internal::labelset_t_of_impl< internal::base_t< ValueSet > >::type labelset_t_of
Helper to retrieve the type of the labelset of a value set.
Definition: traits.hh:76
internal::enumerater< Automaton >::polynomial_t enumerate(const Automaton &aut, unsigned max_length)
Gives the weight associated with each word shorter than max_length by aut.
Definition: enumerate.hh:163
typename internal::weightset_t_of_impl< internal::base_t< ValueSet > >::type weightset_t_of
Helper to retrieve the type of the weightset of a value set.
Definition: traits.hh:86
ATTRIBUTE_CONST int max(int a, int b)
Definition: arith.hh:54
Main namespace of Awali.
Definition: ato.hh:22
unsigned state_t
Definition: types.hh:21
L wordset_t
Definition: traits.hh:37