Vcsn  2.2a
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/expression.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 TAF-Kit 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  aut->new_transition(ini, aut->dst_of(t), aut->label_of(t),
100  ws.mul(wi, aut->weight_of(t)));
101  aut->del_transition(ti);
102 
103  // (iv) Remove the former initial states of A that are the
104  // destination of no incoming transition.
105  if (all_in(aut, i).empty())
106  aut->del_state(i);
107  }
108  // (i.b) Make [state s] initial, with initial multiplicity equal
109  // to the unit of the multiplicity semiring.
110  aut->set_initial(ini);
111  }
112 
113  template <Automaton Aut>
114  auto
115  standard(const Aut& aut)
116  {
117  auto res = copy(aut);
118  standard_here(res);
119  return res;
120  }
121 
122  template <Automaton Aut>
123  auto
124  costandard(const Aut& aut)
125  -> decltype(copy(aut))
126  {
127  return transpose(standard(transpose(aut)));
128  }
129 
130 
131  namespace dyn
132  {
133  namespace detail
134  {
136  template <Automaton Aut>
137  automaton
138  standard(const automaton& aut)
139  {
140  const auto& a = aut->as<Aut>();
141  return make_automaton(::vcsn::standard(a));
142  }
143 
145  template <Automaton Aut>
146  automaton
147  costandard(const automaton& aut)
148  {
149  const auto& a = aut->as<Aut>();
150  return make_automaton(costandard(a));
151  }
152  }
153  }
154 
155 
156  /*------------------------.
157  | standard(expression). |
158  `------------------------*/
159 
160  namespace rat
161  {
166  template <Automaton Aut,
167  typename ExpSet>
169  : public ExpSet::const_visitor
170  {
171  public:
172  using automaton_t = Aut;
173  using expressionset_t = ExpSet;
177 
178  using super_t = typename expressionset_t::const_visitor;
179 
181  constexpr static const char* me() { return "standard"; }
182 
184  : rs_(rs)
186  {}
187 
189  operator()(const typename expressionset_t::value_t& v)
190  {
191  v->accept(*this);
192  res_->set_initial(initial_);
193  return res_;
194  }
195 
196  private:
203  using tuple_t = typename super_t::tuple_t;
204  virtual void visit(const tuple_t&, std::true_type) override
205  {
206  raise(me(), ": tuple is not supported");
207  }
208 
210  {
211  initial_ = res_->new_state();
212  }
213 
215  {
216  auto i = res_->new_state();
217  initial_ = i;
218  res_->set_final(i);
219  }
220 
222  {
223  auto i = res_->new_state();
224  auto f = res_->new_state();
225  initial_ = i;
226  res_->new_transition(i, f, e.value());
227  res_->set_final(f);
228  }
229 
231  using states_t = std::set<state_t>;
232  states_t finals() const
233  {
234  states_t res;
235  for (auto t: final_transitions(res_))
236  res.insert(res_->src_of(t));
237  return res;
238  }
239 
241  {
242  states_t other_finals = finals();
243  e.head()->accept(*this);
244  state_t initial = initial_;
245  for (auto c: e.tail())
246  {
247  c->accept(*this);
248  for (auto t: all_out(res_, initial_))
249  // Not set_transition: for instance 'a*+a*' will make
250  // "initial" go twice to post().
251  res_->add_transition(initial,
252  res_->dst_of(t),
253  res_->label_of(t),
254  res_->weight_of(t));
255  res_->del_state(initial_);
256  }
257  initial_ = initial;
258  }
259 
261  {
262  // The set of the final states that were introduced in pending
263  // parts of the automaton (for instance if we are in the rhs
264  // of "a+bc", recording the final state for "a").
265  states_t other_finals = finals();
266 
267  // Traverse the first part of the product, handle left_weight.
268  e.head()->accept(*this);
269  state_t initial = initial_;
270 
271  // Then the remainder.
272  for (auto c: e.tail())
273  {
274  // The set of the current (left-hand side) final transitions.
276 
277  // Visit the next member of the product.
278  c->accept(*this);
279 
280  // Branch all the previously added final transitions to
281  // the successors of the new initial state.
282  for (auto t1: ftr)
283  if (!has(other_finals, res_->src_of(t1)))
284  {
285  // Remove the previous final transition first, as we
286  // might add a final transition for the same state
287  // later.
288  //
289  // For instance on "<2>a+(<3>\e+<5>a)", the final
290  // state s1 of <2>a will be made final thanks to
291  // <3>\e. So if we compute the new transitions from
292  // s1 and then remove t1, we will have removed the
293  // fact that s1 is final thanks to <3>\e.
294  //
295  // Besides, s1 will become final with weight <3>, which
296  // might interfere with <5>a too.
297  auto s1 = res_->src_of(t1);
298  auto w1 = res_->weight_of(t1);
299  res_->del_transition(t1);
300  for (auto t2: all_out(res_, initial_))
301  res_->set_transition(s1,
302  res_->dst_of(t2),
303  res_->label_of(t2),
304  ws_.mul(w1, res_->weight_of(t2)));
305  }
306  res_->del_state(initial_);
307  }
308  initial_ = initial;
309  }
310 
311  // See star_here().
313  {
314  states_t other_finals = finals();
315  e.sub()->accept(*this);
316  // The "final weight of the initial state", starred.
317  weight_t w = ws_.star(res_->get_final_weight(initial_));
318  // Branch all the final states (but initial) to the successors
319  // of initial.
320  for (auto ti: out(res_, initial_))
321  {
322  res_->lmul_weight(ti, w);
323  for (auto tf: final_transitions(res_))
324  if (res_->src_of(tf) != initial_
325  && !has(other_finals, res_->src_of(tf)))
326  // Note that the weight of ti has already been
327  // multiplied, on the left, by w.
328  //
329  // Not set_transition, as for instance with "a**", the
330  // second star modifies many existing transitions.
331  res_->add_transition
332  (res_->src_of(tf),
333  res_->dst_of(ti),
334  res_->label_of(ti),
335  ws_.mul(res_->weight_of(tf), res_->weight_of(ti)));
336  }
337  for (auto tf: final_transitions(res_))
338  res_->rmul_weight(tf, w);
339  res_->set_final(initial_, w);
340  }
341 
343  {
344  e.sub()->accept(*this);
345  for (auto t: all_out(res_, initial_))
346  res_->lmul_weight(t, e.weight());
347  }
348 
350  {
351  states_t other_finals = finals();
352  e.sub()->accept(*this);
353  for (auto t: final_transitions(res_))
354  if (! has(other_finals, res_->src_of(t)))
355  res_->rmul_weight(t, e.weight());
356  }
357 
358  private:
360  const weightset_t& ws_ = *rs_.weightset();
362  state_t initial_ = automaton_t::element_type::null_state();
363  };
364 
365  } // rat::
366 
367 
372  template <Automaton Aut,
373  typename ExpSet>
374  Aut
375  standard(const ExpSet& rs, const typename ExpSet::value_t& r)
376  {
378  return standard(r);
379  }
380 
381  namespace dyn
382  {
383  namespace detail
384  {
386  template <typename ExpSet>
387  automaton
389  {
390  // FIXME: So far, there is a single implementation of expressions,
391  // but we should actually be parameterized by its type too.
392  using expressionset_t = ExpSet;
393  using automaton_t
395  const auto& e = exp->as<expressionset_t>();
396  return make_automaton(::vcsn::standard<automaton_t>(e.expressionset(),
397  e.expression()));
398  }
399  }
400  }
401 
402 } // vcsn::
bool is_standard(const automaton &aut)
Bridge.
Definition: standard.hh:54
typename super_t::tuple_t tuple_t
Definition: standard.hh:203
auto initial_transitions(const Aut &aut) -> decltype(aut->all_out(aut->pre()))
Indexes of transitions to (visible) initial states.
Definition: automaton.hh:137
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
const weightset_t & ws_
Definition: standard.hh:360
virtual void visit(const tuple_t &, std::true_type) override
Definition: standard.hh:204
const expressionset_t & rs_
Definition: standard.hh:359
A dyn automaton.
Definition: automaton.hh:19
An inner node implementing a weight.
Definition: expression.hh:264
automaton standard(const automaton &aut)
Bridge.
Definition: standard.hh:138
typename expressionset_t::const_visitor super_t
Definition: standard.hh:178
detail::automaton automaton
Definition: automaton.hh:108
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_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:37
std::set< state_t > states_t
The current set of final states.
Definition: standard.hh:231
bool is_costandard(const Aut &a)
Whether a is costandard.
Definition: standard.hh:41
standard_visitor(const expressionset_t &rs)
Definition: standard.hh:183
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:308
automaton_t operator()(const typename expressionset_t::value_t &v)
Definition: standard.hh:189
auto final_transitions(const Aut &aut) -> decltype(aut->all_in(aut->post()))
Indexes of transitions from (visible) final states.
Definition: automaton.hh:148
bool is_standard(const Aut &a)
Whether a is standard.
Definition: standard.hh:28
auto rs
Definition: lift.hh:151
std::vector< typename Cont::value_type > make_vector(const Cont &cont)
The content of cont as a vector.
Definition: vector.hh:20
auto costandard(const Aut &aut) -> decltype(copy(aut))
Definition: standard.hh:124
#define Automaton
Definition: automaton.hh:24
automaton standard_expression(const expression &exp)
Bridge (standard).
Definition: standard.hh:388
#define VCSN_RAT_UNSUPPORTED(Type)
Definition: visitor.hh:74
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:105
automaton costandard(const automaton &aut)
Bridge.
Definition: standard.hh:147
weightset_t_of< expressionset_t > weightset_t
Definition: standard.hh:174
auto all_in(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions entering state s.
Definition: automaton.hh:86
static constexpr const char * me()
Name of this algorithm, for error messages.
Definition: standard.hh:181
void standard_here(Aut &aut)
Turn aut into a standard automaton.
Definition: standard.hh:80
STL namespace.
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:14
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
auto standard(const Aut &aut)
Definition: standard.hh:115
An inner node with multiple children.
Definition: expression.hh:118
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
Definition: automaton.hh:113
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:56
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
state_t_of< automaton_t > state_t
Definition: standard.hh:176
states_t finals() const
Definition: standard.hh:232
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:39
bool is_costandard(const automaton &aut)
Bridge.
Definition: standard.hh:63
std::shared_ptr< detail::expression_base > expression
Definition: expression.hh:92
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:58
Aut transpose(const transpose_automaton< Aut > &aut)
Definition: transpose.hh:227
weight_t_of< expressionset_t > weight_t
Definition: standard.hh:175
Build a standard automaton from an expression.
Definition: standard.hh:168
Definition: a-star.hh:8