Vcsn  2.4
Be Rational
evaluate.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <vector>
4 #include <queue>
5 
7 #include <vcsn/core/automaton.hh> // out
8 #include <vcsn/ctx/traits.hh>
9 #include <vcsn/dyn/automaton.hh>
10 #include <vcsn/dyn/fwd.hh>
11 #include <vcsn/dyn/value.hh>
14 #include <vcsn/misc/algorithm.hh>
15 #include <vcsn/misc/type_traits.hh>
16 
17 namespace vcsn
18 {
19  namespace detail
20  {
22  template <Automaton Aut>
23  class evaluator
24  {
25  using automaton_t = Aut;
32  using polynomial_t = typename wps_t::value_t;
34  using weight_t = typename weightset_t::value_t;
35 
37  using weights_t = std::vector<weight_t>;
38 
39  public:
41  : aut_(a)
42  {}
43 
45  {
50  {
51  w = w_;
52  l = l_;
53  s = s_;
54  }
55  };
56 
57  template <typename LabelSet = labelset_t>
58  std::enable_if_t<!LabelSet::is_free(),
59  weight_t>
60  operator()(const word_t& word) const
61  {
62  // Initialization.
63  weight_t res = ws_.zero();
64 
65  // A queue of current word states in the automaton.
66  auto q = std::queue<labeled_weight>{};
67  q.emplace(ws_.one(), wordset_.delimit(word), aut_->pre());
68 
69  while (!q.empty())
70  {
71  auto cur = q.front();
72  q.pop();
73 
74  for (auto t : all_out(aut_, cur.s))
75  if (aut_->dst_of(t) == aut_->post() && wordset_.is_special(cur.l))
76  // The word is accepted.
77  {
78  cur.w = ws_.mul(cur.w, aut_->weight_of(t));
79  res = ws_.add(res, cur.w);
80  }
81  else if (auto new_word
82  = wordset_.maybe_ldivide(ls_.word(aut_->label_of(t)), cur.l))
83  q.emplace(
84  ws_.mul(cur.w, aut_->weight_of(t)),
85  std::move(*new_word),
86  aut_->dst_of(t));
87  }
88 
89  return res;
90  }
91 
92  template <typename LabelSet = labelset_t>
93  std::enable_if_t<LabelSet::is_free(),
94  weight_t>
95  operator()(const word_t& word) const
96  {
97  // Initialization.
98  const weight_t zero = ws_.zero();
99 
100  // An array indexed by state numbers.
101  //
102  // Do not use braces (v1{size, zero}): the type of zero might
103  // result in the compiler believing we are building a vector
104  // with two values: size and zero.
105  //
106  // We start with just two states numbered 0 and 1: pre() and
107  // post().
108  weights_t v1(2, zero);
109  v1.reserve(states_size(aut_));
110  v1[aut_->pre()] = ws_.one();
111  weights_t v2{v1};
112  v2.reserve(states_size(aut_));
113 
114  // Computation.
115  auto ls = *aut_->labelset();
116  for (auto l : ls.letters_of(ls.delimit(word)))
117  {
118  v2.assign(v2.size(), zero);
119  for (size_t s = 0; s < v1.size(); ++s)
120  if (!ws_.is_zero(v1[s])) // delete if bench >
121  for (auto t : out(aut_, s, l))
122  {
123  // Make sure the vectors are large enough for dst.
124  // Exponential growth on the capacity, but keep
125  // the actual size as small as possible.
126  auto dst = aut_->dst_of(t);
127  if (v2.size() <= dst)
128  {
129  auto capacity = v2.capacity();
130  while (capacity <= dst)
131  capacity *= 2;
132  v1.reserve(capacity);
133  v2.reserve(capacity);
134  v1.resize(dst + 1, zero);
135  v2.resize(dst + 1, zero);
136  }
137  // Introducing a reference to v2[aut_->dst_of(tr)] is
138  // tempting, but won't work for std::vector<bool>.
139  // FIXME: Specialize for Boolean?
140  v2[dst] =
141  ws_.add(v2[dst],
142  ws_.mul(v1[s], aut_->weight_of(t)));
143  }
144  std::swap(v1, v2);
145  }
146  return v1[aut_->post()];
147  }
148 
150  weight_t operator()(const polynomial_t& poly) const
151  {
152  weight_t res = ws_.zero();
153  for (const auto& m: poly)
154  res = ws_.add(res, ws_.mul(weight_of(m), (*this)(label_of(m))));
155 
156  return res;
157  }
158 
159  private:
161  const weightset_t& ws_ = *aut_->weightset();
162  const labelset_t& ls_ = *aut_->labelset();
163  const wordset_t wordset_ = make_wordset(*aut_->labelset());
164  const wps_t wps_ = make_word_polynomialset(aut_->context());
165  };
166 
167  } // namespace detail
168 
170  template <Automaton Aut>
171  auto
172  evaluate(const Aut& a, const word_t_of<Aut>& w)
173  -> std::enable_if_t<!context_t_of<Aut>::is_lao, weight_t_of<Aut>>
174  {
175  auto e = detail::evaluator<Aut>{a};
176  return e(w);
177  }
178 
184  template <Automaton Aut>
185  auto
186  evaluate(const Aut& a)
187  -> std::enable_if_t<context_t_of<Aut>::is_lao, weight_t_of<Aut>>
188  {
189  require(is_proper(a), "evaluate: cannot evaluate with spontaneous transitions");
190  const auto& ws = *a->weightset();
191  auto res = ws.zero();
192  for (auto init_tr: initial_transitions(a))
193  {
194  auto s = a->dst_of(init_tr);
195  auto w = a->weight_of(init_tr);
196  for (auto out: all_out(a, s))
197  {
198  assert(a->dst_of(out) == a->post());
199  res = ws.add(res, ws.mul(w, a->weight_of(out)));
200  }
201  }
202  return res;
203  }
204 
205  namespace dyn
206  {
207  namespace detail
208  {
210  template <Automaton Aut, typename LabelSet>
211  weight
212  evaluate(const automaton& aut, const label& lbl)
213  {
214  const auto& a = aut->as<Aut>();
215  const auto& l = lbl->as<LabelSet>().value();
216  auto res = ::vcsn::evaluate(a, l);
217  return {*a->weightset(), res};
218  }
219  }
220  }
221 
223  template <Automaton Aut>
224  auto
225  evaluate(const Aut& a,
226  const typename detail::word_polynomialset_t<context_t_of<Aut>>::value_t& p)
228  {
229  auto e = detail::evaluator<Aut>{a};
230  return e(p);
231  }
232 
233 
234  namespace dyn
235  {
236  namespace detail
237  {
239  template <Automaton Aut, typename PolynomialSet>
240  weight
241  eval_polynomial(const automaton& aut, const polynomial& poly)
242  {
243  const auto& a = aut->as<Aut>();
244  const auto& p = poly->as<PolynomialSet>().value();
245  auto res = ::vcsn::evaluate(a, p);
246  return {*a->weightset(), res};
247  }
248  }
249  }
250 } // namespace vcsn
std::vector< weight_t > weights_t
state -> weight.
Definition: evaluate.hh:37
return res
Definition: multiply.hh:398
value_impl< detail::weight_tag > weight
Definition: fwd.hh:28
labeled_weight(weight_t w_, word_t l_, state_t s_)
Definition: evaluate.hh:49
auto weight_of(const welement< Label, Weight > &m) -> decltype(m.weight())
The weight of a welement.
Definition: wet.hh:154
const weightset_t & ws_
Definition: evaluate.hh:161
auto make_word_polynomialset(const Ctx &ctx) -> word_polynomialset_t< Ctx >
The polynomialset of words of a labelset (not necessarily on words itself).
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
labelset_t_of< automaton_t > labelset_t
Definition: evaluate.hh:26
Evaluate a word on an automaton.
Definition: evaluate.hh:23
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
size_t states_size(const Aut &aut)
The largest state number, plus one.
Definition: automaton.hh:40
bool is_proper(const Aut &aut)
Test whether an automaton is proper.
Definition: is-proper.hh:47
auto initial_transitions(const Aut &aut) -> decltype(aut->all_out(aut->pre()))
Indexes of transitions to (visible) initial states.
Definition: automaton.hh:166
typename wps_t::value_t polynomial_t
Definition: evaluate.hh:32
Definition: a-star.hh:8
std::enable_if_t<!LabelSet::is_free(), weight_t > operator()(const word_t &word) const
Definition: evaluate.hh:60
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:85
evaluator(const automaton_t &a)
Definition: evaluate.hh:40
context_t_of< automaton_t > context_t
Definition: evaluate.hh:30
weight_t operator()(const polynomial_t &poly) const
Polynomial implementation.
Definition: evaluate.hh:150
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:66
typename law_traits< LabelSet >::type law_t
The smallest wordset that includes LabelSet.
Definition: labelset.hh:255
const wordset_t wordset_
Definition: evaluate.hh:163
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
typename labelset_t_of< base_t< ValueSet >>::word_t word_t_of
Definition: traits.hh:90
A dyn automaton.
Definition: automaton.hh:17
law_t< labelset_t > wordset_t
Definition: evaluate.hh:29
std::enable_if_t< LabelSet::is_free(), weight_t > operator()(const word_t &word) const
Definition: evaluate.hh:95
typename weightset_t::value_t weight_t
Definition: evaluate.hh:34
auto & as()
Extract wrapped typed value.
Definition: value.hh:53
state_t_of< automaton_t > state_t
Definition: evaluate.hh:27
auto evaluate(const Aut &a, const typename detail::word_polynomialset_t< context_t_of< Aut >>::value_t &p) -> weight_t_of< Aut >
Evaluation of a polynomial.
Definition: evaluate.hh:225
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
weight evaluate(const automaton &aut, const label &lbl)
Bridge.
Definition: evaluate.hh:212
const labelset_t & ls_
Definition: evaluate.hh:162
A dyn Value/ValueSet.
Definition: fwd.hh:23
auto evaluate(const Aut &a, const word_t_of< Aut > &w) -> std::enable_if_t<!context_t_of< Aut >::is_lao, weight_t_of< Aut >>
General case of evaluation.
Definition: evaluate.hh:172
weightset_t_of< automaton_t > weightset_t
Definition: evaluate.hh:33
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
weight eval_polynomial(const automaton &aut, const polynomial &poly)
Bridge (evaluate).
Definition: evaluate.hh:241
word_t_of< automaton_t > word_t
Definition: evaluate.hh:28
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
auto label_of(const welement< Label, Weight > &m) -> decltype(m.label())
The label of a welement.
Definition: wet.hh:146
law_t< LabelSet > make_wordset(const LabelSet &ls)
The wordset of a labelset.
Definition: labelset.hh:260