Vcsn  2.4
Be Rational
standard.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <set>
4 
5 #include <vcsn/algos/copy.hh>
10 #include <vcsn/ctx/fwd.hh>
11 #include <vcsn/ctx/traits.hh>
12 #include <vcsn/dyn/automaton.hh>
13 #include <vcsn/dyn/value.hh>
14 #include <vcsn/misc/memory.hh>
15 #include <vcsn/misc/raise.hh>
16 #include <vcsn/misc/tuple.hh>
17 #include <vcsn/misc/vector.hh> // make_vector
18 
19 namespace vcsn
20 {
21  /*-------------------------.
22  | is_standard(automaton). |
23  `-------------------------*/
24 
26  template <Automaton Aut>
27  bool
28  is_standard(const Aut& a)
29  {
30  auto inis = initial_transitions(a);
31  return
32  inis.size() == 1
33  && a->weightset()->is_one(a->weight_of(inis.front()))
34  // No arrival on the initial state.
35  && in(a, a->dst_of(inis.front())).empty();
36  }
37 
39  template <Automaton Aut>
40  bool
41  is_costandard(const Aut& a)
42  {
43  return is_standard(transpose(a));
44  }
45 
46 
47  namespace dyn
48  {
49  namespace detail
50  {
52  template <Automaton Aut>
53  bool
54  is_standard(const automaton& aut)
55  {
56  const auto& a = aut->as<Aut>();
57  return is_standard(a);
58  }
59 
61  template <Automaton Aut>
62  bool
64  {
65  const auto& a = aut->as<Aut>();
66  return is_costandard(a);
67  }
68  }
69  }
70 
71  /*----------------------.
72  | standard(automaton). |
73  `----------------------*/
74 
78  template <Automaton Aut>
79  void
80  standard_here(Aut& aut)
81  {
82  if (is_standard(aut))
83  return;
84 
85  const auto& ws = *aut->weightset();
86  const auto& inits = initial_transitions(aut);
87  std::vector<transition_t_of<Aut>> initials{begin(inits), end(inits)};
88 
89  // See Tools documentation for the implementation details.
90  //
91  // (i.a) Add a new state s...
92  auto ini = aut->new_state();
93  for (auto ti: initials)
94  {
95  // The initial state.
96  auto i = aut->dst_of(ti);
97  auto wi = aut->weight_of(ti);
98  for (auto t: all_out(aut, i))
99  // Cannot use new_transition.
100  aut->add_transition(ini, aut->dst_of(t), aut->label_of(t),
101  ws.mul(wi, aut->weight_of(t)));
102  aut->del_transition(ti);
103 
104  // (iv) Remove the former initial states of A that are the
105  // destination of no incoming transition.
106  if (all_in(aut, i).empty())
107  aut->del_state(i);
108  }
109  // (i.b) Make [state s] initial, with initial multiplicity equal
110  // to the unit of the multiplicity semiring.
111  aut->set_initial(ini);
112  }
113 
114  template <Automaton Aut>
115  auto
116  standard(const Aut& aut)
117  {
118  auto res = copy(aut);
120  return res;
121  }
122 
123  template <Automaton Aut>
124  auto
125  costandard(const Aut& aut)
126  -> decltype(copy(aut))
127  {
128  return transpose(standard(transpose(aut)));
129  }
130 
131 
132  namespace dyn
133  {
134  namespace detail
135  {
137  template <Automaton Aut>
138  automaton
139  standard(const automaton& aut)
140  {
141  const auto& a = aut->as<Aut>();
143  }
144 
146  template <Automaton Aut>
147  automaton
148  costandard(const automaton& aut)
149  {
150  const auto& a = aut->as<Aut>();
151  return costandard(a);
152  }
153  }
154  }
155 
156 
157  /*------------------------.
158  | standard(expression). |
159  `------------------------*/
160 
161  namespace rat
162  {
167  template <Automaton Aut,
168  typename ExpSet>
170  : public ExpSet::const_visitor
171  {
172  public:
173  using automaton_t = Aut;
174  using expressionset_t = ExpSet;
175  using expression_t = typename expressionset_t::value_t;
179 
180  using super_t = typename expressionset_t::const_visitor;
181 
183  constexpr static const char* me() { return "standard"; }
184 
186  : rs_(rs)
188  {}
189 
192  {
193  try
194  {
195  v->accept(*this);
196  res_->set_initial(initial_);
197  return std::move(res_);
198  }
199  catch (const std::runtime_error& e)
200  {
201  raise(e,
202  " while computing standard automaton of: ",
203  to_string(rs_, v));
204  }
205  }
206 
207  private:
215  using tuple_t = typename super_t::tuple_t;
216  void visit(const tuple_t&, std::true_type) override
217  {
218  raise(me(), ": tuple is not supported");
219  }
220 
222  {
223  initial_ = res_->new_state();
224  }
225 
227  {
228  auto i = res_->new_state();
229  initial_ = i;
230  res_->set_final(i);
231  }
232 
234  {
235  auto i = res_->new_state();
236  auto f = res_->new_state();
237  initial_ = i;
238  res_->new_transition(i, f, e.value());
239  res_->set_final(f);
240  }
241 
243  using states_t = std::set<state_t>;
244  states_t finals() const
245  {
246  states_t res;
247  for (auto t: final_transitions(res_))
248  res.insert(res_->src_of(t));
249  return res;
250  }
251 
253  {
254  states_t other_finals = finals();
255  e.head()->accept(*this);
256  state_t initial = initial_;
257  for (const auto& c: e.tail())
258  {
259  c->accept(*this);
260  for (auto t: all_out(res_, initial_))
261  // Not set_transition: for instance 'a*+a*' will make
262  // "initial" go twice to post().
263  res_->add_transition(initial,
264  res_->dst_of(t),
265  res_->label_of(t),
266  res_->weight_of(t));
267  res_->del_state(initial_);
268  }
269  initial_ = initial;
270  }
271 
273  {
274  // The set of the final states that were introduced in pending
275  // parts of the automaton (for instance if we are in the rhs
276  // of "a+bc", recording the final state for "a").
277  states_t other_finals = finals();
278 
279  // Traverse the first part of the product, handle left_weight.
280  e.head()->accept(*this);
281  state_t initial = initial_;
282 
283  // Then the remainder.
284  for (const auto& c: e.tail())
285  {
286  // The set of the current (left-hand side) final transitions.
288 
289  // Visit the next member of the product.
290  c->accept(*this);
291 
292  // Branch all the previously added final transitions to
293  // the successors of the new initial state.
294  for (auto t1: ftr)
295  if (!has(other_finals, res_->src_of(t1)))
296  {
297  // Remove the previous final transition first, as we
298  // might add a final transition for the same state
299  // later.
300  //
301  // For instance on "<2>a+(<3>\e+<5>a)", the final
302  // state s1 of <2>a will be made final thanks to
303  // <3>\e. So if we compute the new transitions from
304  // s1 and then remove t1, we will have removed the
305  // fact that s1 is final thanks to <3>\e.
306  //
307  // Besides, s1 will become final with weight <3>, which
308  // might interfere with <5>a too.
309  auto s1 = res_->src_of(t1);
310  auto w1 = res_->weight_of(t1);
311  res_->del_transition(t1);
312  for (auto t2: all_out(res_, initial_))
313  res_->set_transition(s1,
314  res_->dst_of(t2),
315  res_->label_of(t2),
316  ws_.mul(w1, res_->weight_of(t2)));
317  }
318  res_->del_state(initial_);
319  }
320  initial_ = initial;
321  }
322 
323  // See star_here().
325  {
326  states_t other_finals = finals();
327  e.sub()->accept(*this);
328  // The "final weight of the initial state", starred.
329  weight_t w = ws_.star(res_->get_final_weight(initial_));
330  // Branch all the final states (but initial) to the successors
331  // of initial.
332  for (auto ti: out(res_, initial_))
333  {
334  res_->lweight(ti, w);
335  for (auto tf: final_transitions(res_))
336  if (res_->src_of(tf) != initial_
337  && !has(other_finals, res_->src_of(tf)))
338  // Note that the weight of ti has already been
339  // multiplied, on the left, by w.
340  //
341  // Not set_transition, as for instance with "a**", the
342  // second star modifies many existing transitions.
343  res_->add_transition
344  (res_->src_of(tf),
345  res_->dst_of(ti),
346  res_->label_of(ti),
347  ws_.mul(res_->weight_of(tf), res_->weight_of(ti)));
348  }
349  for (auto tf: final_transitions(res_))
350  res_->rweight(tf, w);
351  res_->set_final(initial_, w);
352  }
353 
355  {
356  e.sub()->accept(*this);
357  for (auto t: all_out(res_, initial_))
358  res_->lweight(t, e.weight());
359  }
360 
362  {
363  states_t other_finals = finals();
364  e.sub()->accept(*this);
365  for (auto t: final_transitions(res_))
366  if (! has(other_finals, res_->src_of(t)))
367  res_->rweight(t, e.weight());
368  }
369 
370  private:
372  const weightset_t& ws_ = *rs_.weightset();
374  state_t initial_ = automaton_t::element_type::null_state();
375  };
376 
377  } // rat::
378 
379 
384  template <Automaton Aut,
385  typename ExpSet>
386  Aut
387  standard(const ExpSet& rs, const typename ExpSet::value_t& r)
388  {
390  return std(r);
391  }
392 
393  namespace dyn
394  {
395  namespace detail
396  {
398  template <typename ExpSet>
399  automaton
401  {
402  // FIXME: So far, there is a single implementation of expressions,
403  // but we should actually be parameterized by its type too.
404  using expressionset_t = ExpSet;
405  using automaton_t
407  const auto& e = exp->as<expressionset_t>();
408  return ::vcsn::standard<automaton_t>(e.valueset(), e.value());
409  }
410  }
411  }
412 
413 } // vcsn::
std::vector< typename Cont::value_type > make_vector(const Cont &cont)
The content of cont as a vector.
Definition: vector.hh:20
STL namespace.
typename expressionset_t::value_t expression_t
Definition: standard.hh:175
SharedPtr make_shared_ptr(Args &&...args)
Same as std::make_shared, but parameterized by the shared_ptr type, not the (pointed to) element_type...
Definition: memory.hh:13
auto rs
Definition: lift.hh:152
return res
Definition: multiply.hh:398
weight_t_of< expressionset_t > weight_t
Definition: standard.hh:177
void standard_here(Aut &aut)
Turn aut into a standard automaton.
Definition: standard.hh:80
An inner node implementing a weight.
Definition: expression.hh:255
Aut standard(const ExpSet &rs, const typename ExpSet::value_t &r)
Build a standard automaton from an expression.
Definition: standard.hh:387
typename super_t::tuple_t tuple_t
Definition: standard.hh:215
automaton standard_expression(const expression &exp)
Bridge (standard).
Definition: standard.hh:400
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
#define Automaton
Definition: automaton.hh:23
standard_visitor(const expressionset_t &rs)
Definition: standard.hh:185
void visit(const tuple_t &, std::true_type) override
Definition: standard.hh:216
weightset_t_of< expressionset_t > weightset_t
Definition: standard.hh:176
const weightset_t & ws_
Definition: standard.hh:372
auto final_transitions(const Aut &aut) -> decltype(aut->all_in(aut->post()))
Indexes of transitions from (visible) final states.
Definition: automaton.hh:177
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
Build a standard automaton from an expression.
Definition: standard.hh:169
states_t finals() const
Definition: standard.hh:244
auto costandard(const Aut &aut) -> decltype(copy(aut))
Definition: standard.hh:125
automaton costandard(const automaton &aut)
Bridge.
Definition: standard.hh:148
auto initial_transitions(const Aut &aut) -> decltype(aut->all_out(aut->pre()))
Indexes of transitions to (visible) initial states.
Definition: automaton.hh:166
auto standard(const Aut &aut)
Definition: standard.hh:116
Definition: a-star.hh:8
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:85
bool is_costandard(const automaton &aut)
Bridge.
Definition: standard.hh:63
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:134
automaton standard(const automaton &aut)
Bridge.
Definition: standard.hh:139
typename expressionset_t::const_visitor super_t
Definition: standard.hh:180
#define VCSN_RAT_UNSUPPORTED(Type)
Definition: visitor.hh:74
bool is_costandard(const Aut &a)
Whether a is costandard.
Definition: standard.hh:41
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:66
const expressionset_t & rs_
Definition: standard.hh:371
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
A dyn automaton.
Definition: automaton.hh:17
automaton_t operator()(const expression_t &v)
The standard automaton of v.
Definition: standard.hh:191
state_t_of< automaton_t > state_t
Definition: standard.hh:178
An inner node with multiple children.
Definition: expression.hh:118
return v
Definition: multiply.hh:361
bool is_standard(const Aut &a)
Whether a is standard.
Definition: standard.hh:28
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
auto copy(const AutIn &input, KeepState keep_state, KeepTrans keep_trans) -> decltype(keep_state(input->null_state()), keep_trans(input->null_transition()), make_fresh_automaton< AutIn, AutOut >(input))
A copy of input keeping only its states that are accepted by keep_state, and transitions accepted by ...
Definition: copy.hh:322
std::set< state_t > states_t
The current set of final states.
Definition: standard.hh:243
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
Definition: setalpha.hh:25
auto all_in(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions entering state s.
Definition: automaton.hh:115
static constexpr const char * me()
Name of this algorithm, for error messages.
Definition: standard.hh:183
bool is_standard(const automaton &aut)
Bridge.
Definition: standard.hh:54
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
std::string to_string(identities i)
Wrapper around operator<<.
Definition: identities.cc:42
Aut transpose(const transpose_automaton< Aut > &aut)
The transpose of a transpose automaton is the original automaton.
Definition: transpose.hh:253