Vaucanson  1.4.1
standard.hxx
1 // standard.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
6 // 2010, 2011 The Vaucanson Group.
7 //
8 // This program is free software; you can redistribute it and/or
9 // modify it under the terms of the GNU General Public License
10 // as published by the Free Software Foundation; either version 2
11 // of the License, or (at your option) any later version.
12 //
13 // The complete GNU General Public Licence Notice can be found as the
14 // `COPYING' file in the root directory.
15 //
16 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
17 //
18 #ifndef VCSN_ALGORITHMS_STANDARD_HXX
19 # define VCSN_ALGORITHMS_STANDARD_HXX
20 
21 # include <vaucanson/algorithms/standard.hh>
22 # include <vaucanson/algorithms/one_eps_closure.hh>
23 # include <vaucanson/algorithms/internal/has_neighbour.hh>
24 # include <vaucanson/algorithms/internal/build_pattern.hh>
25 
26 # include <vaucanson/algorithms/accessible.hh>
27 # include <vaucanson/automata/concept/automata_base.hh>
28 # include <vaucanson/automata/concept/automata.hh>
29 # include <vaucanson/misc/usual_macros.hh>
30 
31 # include <set>
32 
33 namespace vcsn {
34 
35  /*------------.
36  | basic_sptr |
37  `------------*/
38 
39  template<typename HSTATE, typename WEIGHT>
40  struct basic_sptr
41  {
42  private:
43  const HSTATE& src_;
44  const HSTATE& dst_;
45  const WEIGHT& weight_;
46 
47  public:
48  basic_sptr(const HSTATE& src, const HSTATE& dst, const WEIGHT& weight) :
49  src_(src), dst_(dst), weight_(weight) {}
50 
51  HSTATE src() const {
52  return src_;
53  }
54 
55  HSTATE dst() const {
56  return dst_;
57  }
58 
59  WEIGHT weight() const {
60  return weight_;
61  }
62  };
63 
64 
65  /*--------.
66  | union |
67  `--------*/
68 
69  template <typename A, typename AI1, typename AI2>
70  void
71  do_union_here(const AutomataBase<A>&,
72  Element<A, AI1>& lhs,
73  const Element<A, AI2>& rhs)
74  {
75  typedef Element<A, AI1> lhs_t;
76  AUTOMATON_TYPES(lhs_t);
77  typedef Element<A, AI2> rhs_t;
78  typedef typename rhs_t::hstate_t r_hstate_t;
79 
80  std::map<r_hstate_t, hstate_t> states_map;
81 
82  // union of states
83  for_all_states(it, rhs)
84  {
85  hstate_t new_state = lhs.add_state();
86  states_map[*it] = new_state;
87 
88  lhs.set_initial(new_state, rhs.get_initial(*it));
89  lhs.set_final(new_state, rhs.get_final(*it));
90  }
91 
92  // union of transitions.
93  for_all_transitions(it, rhs)
94  {
95  lhs.add_transition(states_map[rhs.src_of(*it)],
96  states_map[rhs.dst_of(*it)],
97  rhs.label_of(*it));
98  }
99  }
100 
101  // wrappers for union
102  template<typename A, typename AI1, typename AI2>
103  void
104  union_here(Element<A, AI1>& lhs, const Element<A, AI2>& rhs)
105  {
106  do_union_here(lhs.structure(), lhs, rhs);
107  }
108 
109 
110  template<typename A, typename AI1, typename AI2>
111  Element<A, AI1>
112  union_(const Element<A, AI1>& lhs, const Element<A, AI2>& rhs)
113  {
114  Element<A, AI1> ret(lhs);
115  do_union_here(ret.structure(), ret, rhs);
116  return ret;
117  }
118 
119  // same as union, but keeps track of two states in the union
120  // (will be used for initial states)
121  template <typename A, typename AI1, typename AI2>
122  void
123  marked_union_here(const AutomataBase<A>&,
124  Element<A, AI1>& lhs,
125  const Element<A, AI2>& rhs,
126  const typename Element<A, AI1>::hstate_t& lhs_stt,
127  typename Element<A, AI1>::hstate_t& mrk_stt,
128  const typename Element<A, AI2>::hstate_t& rhs_stt)
129  {
130  typedef Element<A, AI1> lhs_t;
131  AUTOMATON_TYPES(lhs_t);
132  typedef Element<A, AI2> rhs_t;
133  typedef typename rhs_t::hstate_t r_hstate_t;
134  std::map<r_hstate_t, hstate_t> states_map;
135 
136  // copy of rhs states into lhs
137  for_all_states(it, rhs)
138  {
139  hstate_t new_state = lhs.add_state();
140  states_map[*it] = new_state;
141 
142  lhs.set_initial(new_state, rhs.get_initial(*it));
143  lhs.set_final(new_state, rhs.get_final(*it));
144  }
145  mrk_stt = states_map[rhs_stt]; // mark copy of rhs_stt
146 
147  // copy of rhs transitions into lhs
148  for_all_transitions(it, rhs)
149  {
150  lhs.add_transition(states_map[rhs.src_of(*it)],
151  states_map[rhs.dst_of(*it)],
152  rhs.label_of(*it));
153  }
154  }
155 
156  /*--------------.
157  | is_standard. |
158  `--------------*/
159  template<typename A, typename AI>
160  bool
161  do_is_standard(const AutomataBase<A>&, const Element<A, AI>& a)
162  {
163  BENCH_TASK_SCOPED("is_standard");
164  typedef Element<A, AI> automaton_t;
165  typedef typename automaton_t::series_set_elt_value_t series_set_elt_value_t;
166 
167  // Check there is only one initial state.
168  if (a.initial().size() != 1)
169  return false;
170 
171  // Check the multiplicity of the initial state.
172  typename automaton_t::hstate_t s = *a.initial().begin();
173  if (a.get_initial(s)
174  != a.series().identity(SELECT(series_set_elt_value_t)))
175  return false;
176 
177  // Check that there is no input transition on the initial state.
178  return !has_predecessors(a, s);
179  }
180 
181  template<typename A, typename AI>
182  bool
183  is_standard(const Element<A, AI>& a)
184  {
185  return do_is_standard(a.structure(), a);
186  }
187 
188  /*------------.
189  | standardize |
190  `------------*/
191 
192  template<typename S, typename AI>
193  void
194  do_standardize(const AutomataBase<S>&, Element<S, AI>& a)
195  {
196  BENCH_TASK_SCOPED("standardize");
197  typedef Element<S, AI> automaton_t;
198  AUTOMATON_TYPES(automaton_t);
199  typedef basic_sptr<hstate_t, series_set_elt_t> sptr_t;
200  typedef typename std::list<hstate_t> stt_lst_t;
201 
202  stt_lst_t stt_list;
203  series_set_elt_t fin_wgt =
204  algebra::zero_as<series_set_elt_value_t>::of(a.series());
205 
206  if (is_standard(a)) return;
207 
208  hstate_t i = a.add_state(); // add a new state that will be the
209  // initial state
210  // put all initial states of a in a list
211  for_all_initial_states(it, a) stt_list.push_back(*it);
212 
213  for_all(typename stt_lst_t, it, stt_list)
214  {
215  hstate_t ini_stt = *it;
216  series_set_elt_t ini_wgt = a.get_initial(ini_stt);
217 
218  // emulates closure with respect of a spt transition between i and ini_stt
219  sptr_t t(i, ini_stt, ini_wgt);
220  one_eps_closure(a, t, misc::backward);
221  // computes the final weight of the new initial state
222  a.unset_initial(ini_stt);
223  // delete state if there is zero incoming transitions
224  if (!has_predecessors(a, ini_stt))
225  a.del_state(ini_stt);
226  }
227 
228  a.set_initial(i);
229 
230  return;
231  }
232 
233  // standardize is always 'here'
234  template<typename A, typename AI>
235  void
236  standardize(Element<A, AI>& a)
237  {
238  do_standardize(a.structure(), a);
239  }
240 
241  /*-----------------.
242  | sum_of_standard |
243  `-----------------*/
244 
245  template <typename A, typename AI>
246  void
247  sum_of_standard_inside(const AutomataBase<A>&, Element<A, AI>& aut,
248  const typename Element<A, AI>::hstate_t& aut_stt,
249  typename Element<A, AI>::hstate_t& mrk_stt)
250  {
251  typedef Element<A, AI> automaton_t; AUTOMATON_TYPES(automaton_t);
252  typedef series_set_elt_t weight_t;
253  typedef basic_sptr<hstate_t, weight_t> sptr_t;
254 
255  weight_t unit = aut.series().identity(SELECT(series_set_elt_value_t));
256 
257  sptr_t t(aut_stt, mrk_stt, unit);
258  one_eps_closure(aut, t, misc::backward);
259  aut.del_state(mrk_stt);
260  }
261 
262 
263  template <typename A, typename AI1, typename AI2>
264  void
265  do_sum_of_standard_here(const AutomataBase<A>&,
266  Element<A, AI1>& lhs,
267  const Element<A, AI2>& rhs)
268  {
269  BENCH_TASK_SCOPED("sum_of_standard");
270 
271  typedef Element<A, AI1> lhs_t;
272  AUTOMATON_TYPES(lhs_t);
273  typedef Element<A, AI2> rhs_t;
274  typedef typename rhs_t::hstate_t r_hstate_t;
275 
276  hstate_t mrk_stt;
277 
278  // Mark the initial states
279  hstate_t lhs_stt = *lhs.initial().begin();
280  r_hstate_t rhs_stt = *rhs.initial().begin();
281 
282  marked_union_here(lhs.structure(), lhs, rhs, lhs_stt, mrk_stt, rhs_stt);
283 
284  sum_of_standard_inside(lhs.structure(), lhs, lhs_stt, mrk_stt);
285  }
286 
287 
288  template<typename A, typename AI1, typename AI2>
289  void
290  sum_of_standard_here(Element<A, AI1>& lhs, const Element<A, AI2>& rhs)
291  {
292  precondition(is_standard(lhs));
293  precondition(is_standard(rhs));
294  do_sum_of_standard_here(lhs.structure(), lhs, rhs);
295  }
296 
297  template<typename A, typename AI1, typename AI2>
298  Element<A, AI1>
299  sum_of_standard(const Element<A, AI1>& lhs, const Element<A, AI2>& rhs)
300  {
301  precondition(is_standard(lhs));
302  precondition(is_standard(rhs));
303  Element<A, AI1> ret(lhs);
304  sum_of_standard_here(ret, rhs);
305  return ret;
306  }
307 
308  /*---------------------.
309  | concat_of_standard. |
310  `---------------------*/
311 
312 
313  template <typename A, typename AI>
314  void
315  concat_of_standard_inside(const AutomataBase<A>&, Element<A, AI>& aut,
316  typename std::list<typename Element<A, AI>::hstate_t>& stt_list,
317  typename Element<A, AI>::hstate_t& mrk_stt)
318  {
319  typedef Element<A, AI> aut_t;
320  AUTOMATON_TYPES(aut_t);
321  typedef series_set_elt_t weight_t;
322  typedef typename std::list<hstate_t> stt_lst_t;
323  typedef basic_sptr<hstate_t, weight_t> sptr_t;
324 
325  weight_t mrk_wgt = aut.get_final(mrk_stt);
326 
327  for_all(typename stt_lst_t, it, stt_list)
328  {
329  hstate_t fin_stt = *it;
330  weight_t fin_wgt = aut.get_final(fin_stt);
331  aut.unset_final(fin_stt);
332  sptr_t t(fin_stt, mrk_stt, fin_wgt);
333  one_eps_closure(aut, t, misc::backward);
334  }
335  aut.del_state(mrk_stt);
336  }
337 
338 
339  template <typename A, typename AI1, typename AI2>
340  void
341  do_concat_of_standard_here(const AutomataBase<A>&,
342  Element<A, AI1>& lhs,
343  const Element<A, AI2>& rhs)
344  {
345  BENCH_TASK_SCOPED("concat_of_standard");
346 
347  typedef Element<A, AI1> lhs_t;
348  AUTOMATON_TYPES(lhs_t);
349  typedef std::list<hstate_t> stt_lst_t;
350  typedef Element<A, AI2> rhs_t;
351  typedef typename rhs_t::hstate_t r_hstate_t;
352 
353  // Remember list of final states in lhs
354  stt_lst_t stt_list;
355  for_all_final_states(it, lhs) stt_list.push_back(*it);
356 
357  // Mark the initial states and perform marked union of states
358  hstate_t mrk_stt;
359  hstate_t lhs_stt = *lhs.initial().begin();
360  r_hstate_t rhs_stt = *rhs.initial().begin();
361  marked_union_here(lhs.structure(), lhs, rhs, lhs_stt, mrk_stt, rhs_stt);
362 
363  concat_of_standard_inside(lhs.structure(), lhs, stt_list, mrk_stt);
364  }
365 
366 
367  template<typename A, typename AI1, typename AI2>
368  void
369  concat_of_standard_here(Element<A, AI1>& lhs, const Element<A, AI2>& rhs)
370  {
371  precondition(is_standard(lhs));
372  precondition(is_standard(rhs));
373  do_concat_of_standard_here(lhs.structure(), lhs, rhs);
374  }
375 
376  template<typename A, typename AI1, typename AI2>
377  Element<A, AI1>
378  concat_of_standard(const Element<A, AI1>& lhs,
379  const Element<A, AI2>& rhs)
380  {
381  precondition(is_standard(lhs));
382  precondition(is_standard(rhs));
383  Element<A, AI1> ret(lhs);
384  do_concat_of_standard_here(ret.structure(), ret, rhs);
385  return ret;
386  }
387 
388 
389  /*----------------------------------.
390  | left_ext_mult_of_standard_inside |
391  `----------------------------------*/
392 
393  template <typename A, typename AI>
394  void
395  left_ext_mult_of_standard_inside(const AutomataBase<A>&,
396  Element<A, AI>& aut,
397  const typename Element<A, AI>::hstate_t& ini_stt,
398  const typename Element<A, AI>::series_set_elt_t& k)
399  {
400  typedef Element<A, AI> automaton_t; AUTOMATON_TYPES(automaton_t);
401  typedef series_set_elt_t weight_t;
402  typedef typename std::list<htransition_t> trn_lst_t;
403 
404  weight_t zero(aut.series().zero_);
405  trn_lst_t ini_out_list;
406 
407  // Build the list of outgoing transitions from ini_stt
408  for (delta_iterator it(aut.value(), ini_stt); !it.done(); it.next())
409  ini_out_list.push_back(*it);
410 
411  // In case of multiplication by zero (this cannot happen if we are
412  // working from a rational expression, but we check it nonetheless
413  // in case one day this function is used with a used-supplied
414  // weight).
415  if (k == zero)
416  {
417  // erase all outgoing transitions from ini_stt
418  for_all(typename trn_lst_t, it, ini_out_list)
419  aut.del_transition(*it);
420  // make ini_stt non final
421  aut.unset_final(ini_stt);
422  }
423  // In all other cases
424  else
425  {
426  for_all(typename trn_lst_t, it, ini_out_list)
427  { // multiply by k the series of all outgoing transitions from ini_stt
428  hstate_t dest = aut.dst_of(*it);
429  weight_t wgt = k * aut.series_of(*it);
430  aut.del_transition(*it);
431  aut.add_series_transition(ini_stt, dest, wgt);
432  }
433  // multiply by k the final weight of ini_stt
434  aut.set_final(ini_stt, k * aut.get_final(ini_stt));
435  }
436  }
437 
438  template <typename A, typename AI>
439  void
440  left_mult_of_standard_here(Element<A, AI>& aut,
441  const typename Element<A, AI>::series_set_elt_t& k)
442  {
443  precondition(is_standard(aut));
444  left_ext_mult_of_standard_inside(aut.structure(), aut,
445  *aut.initial().begin(), k);
446  }
447 
448  /*----------------------------------.
449  | right_ext_mult_of_standard_inside |
450  `----------------------------------*/
451 
452  template <typename A, typename AI>
453  void
454  right_ext_mult_of_standard_inside
455  (const AutomataBase<A>&, Element<A, AI>& aut,
456  typename std::list<typename Element<A, AI>::hstate_t>& stt_list,
457  const typename Element<A, AI>::series_set_elt_t& k)
458  {
459  typedef Element<A, AI> automaton_t; AUTOMATON_TYPES(automaton_t);
460  typedef typename std::list<hstate_t> stt_lst_t;
461 
462  // multiply by k (on the right) the final weight of of every state
463  // in stt_list
464  for_all(typename stt_lst_t, it, stt_list)
465  aut.set_final(*it, aut.get_final(*it) * k);
466  }
467 
468  template <typename A, typename AI>
469  void
470  right_mult_of_standard_here(Element<A, AI>& aut,
471  const typename Element<A, AI>::series_set_elt_t& k)
472  {
473  typedef Element<A, AI> automaton_t;
474  AUTOMATON_TYPES(automaton_t);
475 
476  precondition(is_standard(aut));
477  std::list<hstate_t> finals;
478  for_all_final_states(it, aut) finals.push_back(*it);
479 
480  right_ext_mult_of_standard_inside(aut.structure(), aut,
481  finals, k);
482  }
483 
484  /*------------------.
485  | star_of_standard |
486  `------------------*/
487 
488  template <typename A, typename AI>
489  void
490  star_of_standard_inside(const AutomataBase<A>&, Element<A, AI>& aut,
491  const typename Element<A, AI>::hstate_t& ini_stt,
492  typename std::list<typename Element<A, AI>::hstate_t>& stt_list)
493  {
494  typedef Element<A, AI> automaton_t; AUTOMATON_TYPES(automaton_t);
495  typedef series_set_elt_t weight_t;
496  typedef typename std::list<hstate_t> stt_lst_t;
497  typedef basic_sptr<hstate_t, weight_t> sptr_t;
498  weight_t unit = aut.series().identity(SELECT(series_set_elt_value_t));
499 
500  // compute the star of the final weight of ini_stt (starable has
501  // already been called)
502  weight_t fin_wgt = aut.get_final(ini_stt); fin_wgt.star();
503 
504  // multiply on the left by that coefficient
505  aut.set_final(ini_stt, unit);
506  left_ext_mult_of_standard_inside(aut.structure(), aut, ini_stt, fin_wgt);
507 
508  // emulates closure of spt transition from every
509  // state in stt_list to ini_stt
510  for_all(typename stt_lst_t, it, stt_list)
511  {
512  hstate_t crn_stt = *it;
513  weight_t crn_fin_wgt = aut.get_final(crn_stt);
514  aut.unset_final(crn_stt);
515 
516  sptr_t t(crn_stt, ini_stt, crn_fin_wgt);
517  one_eps_closure(aut, t, misc::backward);
518  }
519  }
520 
521 
522  template <typename A, typename AI>
523  void
524  do_star_of_standard_here(const AutomataBase<A>&, Element<A, AI>& a)
525  {
526  BENCH_TASK_SCOPED("star_of_standard");
527  typedef Element<A, AI> automaton_t; AUTOMATON_TYPES(automaton_t);
528  typedef series_set_elt_t weight_t;
529  typedef std::list<hstate_t> stt_lst_t;
530 
531  hstate_t ini_stt = *a.initial().begin();
532  weight_t fin_wgt = a.get_final(ini_stt);
533 
534  precondition(fin_wgt.starable());
535 
536  stt_lst_t stt_list;
537  for_all_final_states(it, a)
538  if (*it != ini_stt)
539  stt_list.push_back(*it);
540 
541  star_of_standard_inside(a.structure(), a, ini_stt, stt_list);
542  }
543 
544  template<typename A, typename AI>
545  void
546  star_of_standard_here(Element<A, AI>& a)
547  {
548  precondition(is_standard(a));
549  do_star_of_standard_here(a.structure(), a);
550  }
551 
552  template<typename A, typename AI>
553  Element<A, AI>
554  star_of_standard(const Element<A, AI>& a)
555  {
556  precondition(is_standard(a));
557  Element<A, AI> ret(a);
558  do_star_of_standard_here(ret.structure(), ret);
559  return ret;
560  }
561 
562 } // vcsn
563 
564 #endif // ! VCSN_ALGORITHMS_STANDARD_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1