Vaucanson  1.4.1
normalized_composition.hxx
Go to the documentation of this file.
1 // normalized_composition.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2005, 2006, 2011 The Vaucanson Group.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // The complete GNU General Public Licence Notice can be found as the
13 // `COPYING' file in the root directory.
14 //
15 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
16 //
17 #ifndef VCSN_ALGORITHMS_NORMALIZED_COMPOSITION_HXX
18 # define VCSN_ALGORITHMS_NORMALIZED_COMPOSITION_HXX
19 
33 # include <set>
34 # include <queue>
35 # include <vaucanson/algorithms/normalized_composition.hh>
36 # include <vaucanson/algorithms/internal/outsplitting.hh>
37 # include <vaucanson/algebra/concept/freemonoid_product.hh>
38 # include <vaucanson/algebra/implementation/series/series.hh>
39 # include <vaucanson/automata/concept/automata.hh>
40 
41 
42 namespace vcsn {
43 
44  template <typename S, typename M1, typename M2, typename lhs_t,
45  typename rhs_t, typename res_t>
46  struct composer
47  {
48  AUTOMATON_TYPES(res_t);
49  AUTOMATON_TYPES_(lhs_t, lhs_);
50  AUTOMATON_TYPES_(rhs_t, rhs_);
51 
52  #define SPECIFIC_TYPES(Auto) \
53  typedef std::list<typename Auto##_t::htransition_t> Auto##_delta_ret_t; \
54 
55  SPECIFIC_TYPES(lhs);
56  SPECIFIC_TYPES(rhs);
57  SPECIFIC_TYPES(res);
58 
59  #undef SPECIFIC_TYPES
60  typedef std::pair<lhs_hstate_t, rhs_hstate_t> pair_hstate_t;
61  typedef std::map<pair_hstate_t, hstate_t> visited_t;
62  typedef std::map<hstate_t, pair_hstate_t> map_of_states_t;
63  typedef std::queue<pair_hstate_t> to_process_t;
64 
65  typedef std::list<htransition_t> delta_ret_t;
66  typedef typename series_set_elt_t::support_t support_t;
67  typedef typename lhs_series_set_elt_t::support_t lhs_support_t;
68  typedef typename rhs_series_set_elt_t::support_t rhs_support_t;
69 
70  typedef typename lhs_monoid_t::first_monoid_t
71  lhs_first_monoid_t;
72  typedef typename lhs_monoid_elt_value_t::first_type
73  lhs_first_monoid_elt_value_t;
74  typedef Element<lhs_first_monoid_t, lhs_first_monoid_elt_value_t>
75  lhs_first_monoid_elt_t;
76 
77  typedef typename rhs_monoid_t::first_monoid_t
78  rhs_first_monoid_t;
79  typedef typename rhs_monoid_elt_value_t::first_type
80  rhs_first_monoid_elt_value_t;
81  typedef Element<rhs_first_monoid_t, rhs_first_monoid_elt_value_t>
82  rhs_first_monoid_elt_t;
83 
84  typedef typename lhs_monoid_t::second_monoid_t
85  lhs_second_monoid_t;
86  typedef typename lhs_monoid_elt_value_t::second_type
87  lhs_second_monoid_elt_value_t;
88  typedef Element<lhs_second_monoid_t, lhs_second_monoid_elt_value_t>
89  lhs_second_monoid_elt_t;
90 
91  typedef typename rhs_monoid_t::second_monoid_t
92  rhs_second_monoid_t;
93  typedef typename rhs_monoid_elt_value_t::second_type
94  rhs_second_monoid_elt_value_t;
95  typedef Element<rhs_second_monoid_t, rhs_second_monoid_elt_value_t>
96  rhs_second_monoid_elt_t;
97 
98  visited_t visited;
99  to_process_t to_process;
100  map_of_states_t m;
101 
102  const lhs_t& lhs;
103  const rhs_t& rhs;
104  res_t& output;
105  std::set<typename lhs_t::hstate_t>& lhs_black_states;
106  std::set<typename rhs_t::hstate_t>& rhs_black_states;
107 
108  const series_set_t& series;
109  const monoid_t& monoid;
110 
111  const lhs_series_set_t& lhs_series;
112  const lhs_monoid_t& lhs_monoid;
113 
114  const rhs_series_set_t& rhs_series;
115  const rhs_monoid_t& rhs_monoid;
116 
117  lhs_first_monoid_elt_t lhs_first_identity;
118  rhs_first_monoid_elt_t rhs_first_identity;
119  lhs_second_monoid_elt_t lhs_second_identity;
120  rhs_second_monoid_elt_t rhs_second_identity;
121 
122  composer (const AutomataBase<S>&,
123  const algebra::FreeMonoidProduct<M1, M2>&,
124  const lhs_t& aLhs,
125  const rhs_t& aRhs,
126  res_t& aOutput,
127  std::set<typename lhs_t::hstate_t>& aLhs_states,
128  std::set<typename rhs_t::hstate_t>& aRhs_states)
129  : lhs (aLhs),
130  rhs (aRhs),
131  output (aOutput),
132  lhs_black_states (aLhs_states),
133  rhs_black_states (aRhs_states),
134 
135  series (output.structure().series()),
136  monoid (series.monoid()),
137 
138  lhs_series (lhs.structure().series()),
139  lhs_monoid (lhs_series.monoid()),
140 
141  rhs_series (rhs.structure().series()),
142  rhs_monoid (rhs_series.monoid()),
143 
144  lhs_first_identity (algebra::identity_as<lhs_first_monoid_elt_value_t>::
145  of(lhs_monoid.first_monoid())),
146  rhs_first_identity (algebra::identity_as<rhs_first_monoid_elt_value_t>::
147  of(rhs_monoid.first_monoid())),
148  lhs_second_identity (algebra::identity_as<lhs_second_monoid_elt_value_t>::
149  of(lhs_monoid.second_monoid())),
150  rhs_second_identity (algebra::identity_as<rhs_second_monoid_elt_value_t>::
151  of(rhs_monoid.second_monoid()))
152  {
153  }
154 
155  // - Add a transition between current_state and the state
156  // corresponding to the pair (from,to).
157  // - If the state (from,to) does not exist, then it is created.
158  // - The transition is labelled by prod_series.
159  void
160  add_transition(const hstate_t current_state,
161  const hstate_t from,
162  const hstate_t to,
163  typename res_t::series_set_elt_t& prod_series)
164  {
165  if (lhs_black_states.find(from) == lhs_black_states.end()
166  or rhs_black_states.find(to) == rhs_black_states.end())
167  {
168  const pair_hstate_t new_pair (from, to);
169 
170  typename visited_t::const_iterator found =
171  visited.find(new_pair);
172  hstate_t dst;
173  if (found == visited.end())
174  {
175  dst = output.add_state();
176  visited[new_pair] = dst;
177  m[dst] = new_pair;
178  to_process.push(new_pair);
179  }
180  else
181  dst = found->second;
182  output.add_series_transition(current_state, dst, prod_series);
183  }
184  }
185 
186  typename res_t::series_set_elt_t
187  series_product (typename monoid_elt_value_t::first_type l1,
188  typename monoid_elt_value_t::second_type l2,
189  semiring_elt_t w)
190  {
191  typename res_t::series_set_elt_t res (series);
192  const monoid_elt_value_t word (l1, l2);
193  res.assoc(word, w.value());
194  return res;
195  }
196 
197 
198  // Compute the series for an initial or a final state, on the
199  // empty word.
200  typename res_t::series_set_elt_t
201  state_series (lhs_series_set_elt_t l,
202  rhs_series_set_elt_t r)
203  {
204  series_set_elt_t res(series);
205  res.assoc(monoid_elt_t(monoid,
206  algebra::identity_as<monoid_elt_value_t>::
207  of(monoid).value()),
208  l.get(*l.supp().begin()) * r.get(*r.supp().begin()));
209  return res;
210  }
211 
212  void process_one_pair (const hstate_t current_state,
213  const typename lhs_t::hstate_t lhs_s,
214  const hstate_t rhs_s)
215  {
216 
217  if (lhs.is_initial(lhs_s) and rhs.is_initial(rhs_s))
218  output.set_initial(current_state,
219  state_series (lhs.get_initial(lhs_s),
220  rhs.get_initial(rhs_s)));
221 
222  if (lhs.is_final(lhs_s) and rhs.is_final(rhs_s))
223  output.set_final(current_state,
224  state_series (lhs.get_final(lhs_s),
225  rhs.get_final(rhs_s)));
226 
227  for (delta_iterator l(lhs.value(), lhs_s); ! l.done(); l.next())
228  {
229  const lhs_series_set_elt_t left_series = lhs.series_of(*l);
230  for_all_const_(lhs_support_t, left_supp_value,left_series.supp())
231  {
232  const lhs_monoid_elt_t left_supp_elt (lhs_monoid, *left_supp_value);
233  // (i)
234  // If the outgoing transition is of type (*, 1).
235  if (left_supp_elt.value().second == lhs_second_identity.value())
236  {
237  series_set_elt_t s =
238  series_product (left_supp_elt.value().first,
239  rhs_second_identity.value(),
240  left_series.get(left_supp_elt));
241  add_transition (current_state,
242  lhs.dst_of(*l), rhs_s, s);
243  }
244  // (iii')
245  else
246  {
247  for (delta_iterator r(rhs.value(), rhs_s); ! r.done(); r.next())
248  {
249  const rhs_series_set_elt_t right_series =
250  rhs.series_of(*r);
251  for_all_const_(rhs_support_t, right_supp_value, right_series.supp())
252  {
253  const rhs_monoid_elt_t right_supp_elt
254  (rhs_monoid, *right_supp_value);
255 
256  // If the incoming transition is not of type (1, *).
257  if (right_supp_elt.value().first !=
258  rhs_first_identity.value())
259  // we try to connect a transition of lhs and
260  // a transition of rhs.
261  if (left_supp_elt.value().second ==
262  right_supp_elt.value().first)
263  {
264  series_set_elt_t s =
265  series_product (left_supp_elt.value().first,
266  right_supp_elt.value().second,
267  left_series.get(left_supp_elt)
268  * right_series.get(right_supp_elt));
269  add_transition
270  (current_state,
271  lhs.dst_of(*l), rhs.dst_of(*r),
272  s);
273  }
274  }
275  }
276  }
277  }
278  }
279 
280  for (delta_iterator r(rhs.value(), rhs_s); ! r.done(); r.next())
281  {
282  const rhs_series_set_elt_t right_series = rhs.series_of(*r);
283  for_all_const_(rhs_support_t, right_supp_value, right_series.supp())
284  {
285  const rhs_monoid_elt_t right_supp_elt (rhs_monoid,
286  *right_supp_value);
287 
288  // (ii)
289  if (right_supp_elt.value().first == rhs_first_identity.value())
290  {
291  series_set_elt_t s =
292  series_product (lhs_first_identity.value(),
293  right_supp_elt.value().second,
294  right_series.get(right_supp_elt));
295  add_transition (current_state,
296  lhs_s, rhs.dst_of(*r), s);
297  }
298  }
299  }
300 
301  }
302 
303 
304  void operator() ()
305  {
306 
307  /*----------------------------------.
308  | Get initial states of the product |
309  `----------------------------------*/
310  for_all_const_initial_states(lhs_s, lhs)
311  for_all_const_initial_states(rhs_s, rhs)
312  {
313  if (lhs_black_states.find(*lhs_s) == lhs_black_states.end() or
314  rhs_black_states.find(*rhs_s) == rhs_black_states.end())
315  {
316  const hstate_t new_state = output.add_state();
317  const pair_hstate_t new_pair (*lhs_s, *rhs_s);
318 
319  m[new_state] = new_pair;
320  visited[new_pair] = new_state;
321  to_process.push(new_pair);
322  }
323  }
324 
325  /*-----------.
326  | Processing |
327  `-----------*/
328  while (not to_process.empty())
329  {
330  const pair_hstate_t p = to_process.front();
331  to_process.pop();
332  process_one_pair (visited[p], p.first, p.second);
333  }
334  }
335  };
336 
337 
338 
341  template <typename S, typename M1, typename M2, typename lhs_t,
342  typename rhs_t, typename res_t>
343  void
344  do_compose(const AutomataBase<S>&,
345  const algebra::FreeMonoidProduct<M1, M2>&,
346  const lhs_t& lhs,
347  const rhs_t& rhs,
348  res_t& ret)
349  {
350  AUTOMATON_TYPES(res_t);
351 
352  std::set<typename lhs_t::hstate_t> lhs_states;
353  std::set<typename rhs_t::hstate_t> rhs_states;
354 
355  composer<S, M1, M2, lhs_t, rhs_t, res_t>
356  compose (ret.structure(), ret.structure().series().monoid(),
357  lhs, rhs, ret, lhs_states, rhs_states);
358  compose ();
359  eps_removal_here (ret);
360  }
361 
364  template <typename S, typename M1, typename M2, typename lhs_t,
365  typename rhs_t, typename res_t>
366  void
367  do_u_compose(const AutomataBase<S>&,
368  const algebra::FreeMonoidProduct<M1, M2>&,
369  const lhs_t& lhs,
370  const rhs_t& rhs,
371  res_t& ret)
372  {
373  AUTOMATON_TYPES(res_t);
374 
375  std::set<typename lhs_t::hstate_t> lhs_states;
376  std::set<typename rhs_t::hstate_t> rhs_states;
377 
378  lhs_t lhs_cov = splitting::outsplitting(lhs, lhs_states);
379  rhs_t rhs_cov = splitting::insplitting(rhs, rhs_states);
380 
381  composer<S, M1, M2, lhs_t, rhs_t, res_t>
382  compose (ret.structure(), ret.structure().series().monoid(),
383  lhs_cov, rhs_cov, ret, lhs_states, rhs_states);
384  compose ();
385 
386  eps_removal_here (ret);
387  sub_automaton_here (ret, useful_states (ret));
388  }
389 
390 
391 
392  // Compose dispatchers
393  template <typename S, typename M1, typename M2, typename lhs_t,
394  typename rhs_t, typename res_t>
395  void
396  do_compose_dispatcher(const AutomataBase<S>&,
397  const algebra::FreeMonoidProduct<M1, M2>&,
398  SELECTOR(bool),
399  const lhs_t& lhs,
400  const rhs_t& rhs,
401  res_t& ret)
402  {
403  do_compose (ret.structure(),
404  ret.structure().series().monoid(),
405  lhs, rhs, ret);
406  }
407 
408 
409  template <typename S, typename M1, typename M2, typename lhs_t,
410  typename rhs_t, typename res_t, typename weight_t>
411  void
412  do_compose_dispatcher(const AutomataBase<S>&,
413  const algebra::FreeMonoidProduct<M1, M2>&,
414  const weight_t&,
415  const lhs_t& lhs,
416  const rhs_t& rhs,
417  res_t& ret)
418  {
419  do_u_compose (ret.structure(),
420  ret.structure().series().monoid(),
421  lhs, rhs, ret);
422  }
423 
424  // Facade for compose
425 
426  template <typename S, typename T>
427  void
428  compose(const Element<S, T>& lhs,
429  const Element<S, T>& rhs,
430  Element<S, T>& ret)
431  {
432  typedef Element<S, T> auto_t;
433  AUTOMATON_TYPES(auto_t);
434 
435  for_all_states (s, ret)
436  ret.del_state (*s);
437 
438  do_compose_dispatcher (ret.structure(),
439  ret.structure().series().monoid(),
440  SELECT(semiring_elt_value_t),
441  lhs, rhs, ret);
442  }
443 
444 
445 
446  template <typename S, typename T>
447  Element<S, T>
448  compose(const Element<S, T>& lhs,
449  const Element<S, T>& rhs)
450  {
451  typedef Element<S, T> auto_t;
452  AUTOMATON_TYPES(auto_t);
453 
454  typedef algebra::FreeMonoidProduct<
455  typename auto_t::series_set_t::monoid_t::first_monoid_t,
456  typename auto_t::series_set_t::monoid_t::second_monoid_t> res_monoid_t;
457 
458  typedef algebra::Series<typename auto_t::series_set_t::semiring_t,
459  res_monoid_t>
460  res_series_set_t;
461 
462  res_monoid_t monoid(lhs.structure().series().monoid().first_monoid(),
463  rhs.structure().series().monoid().second_monoid());
464 
465 
466  res_series_set_t series(lhs.structure().series().semiring(), monoid);
467 
468  Automata<series_set_t, kind_t> aut_set(series);
469 
470  Element< Automata<series_set_t, kind_t>, T> ret(aut_set);
471  do_compose_dispatcher(ret.structure(),
472  ret.structure().series().monoid(),
473  SELECT(semiring_elt_value_t),
474  lhs, rhs, ret);
475  return ret;
476  }
477 
478 
479  // Facade for unambiguous composition
480  template <typename S, typename T>
481  void
482  u_compose(const Element<S, T>& lhs,
483  const Element<S, T>& rhs,
484  Element<S, T>& ret)
485  {
486  typedef Element<S, T> auto_t;
487  AUTOMATON_TYPES(auto_t);
488 
489  for_all_states (s, ret)
490  ret.del_state (*s);
491 
492  do_u_compose (ret.structure(),
493  ret.structure().series().monoid(),
494  lhs, rhs, ret);
495  }
496 
497  template <typename S, typename T>
498  Element<S, T>
499  u_compose(const Element<S, T>& lhs,
500  const Element<S, T>& rhs)
501  {
502  typedef Element<S, T> auto_t;
503  AUTOMATON_TYPES(auto_t);
504 
505  typedef algebra::FreeMonoidProduct<
506  typename auto_t::series_set_t::monoid_t::first_monoid_t,
507  typename auto_t::series_set_t::monoid_t::second_monoid_t> res_monoid_t;
508 
509  typedef algebra::Series<typename auto_t::series_set_t::semiring_t,
510  res_monoid_t>
511  res_series_set_t;
512 
513  res_monoid_t monoid(lhs.structure().series().monoid().first_monoid(),
514  rhs.structure().series().monoid().second_monoid());
515 
516 
517  res_series_set_t series(lhs.structure().series().semiring(), monoid);
518 
519  Automata<series_set_t, kind_t> aut_set(series);
520 
521  Element< Automata<series_set_t, kind_t>, T> ret(aut_set);
522  do_u_compose(ret.structure(),
523  ret.structure().series().monoid(),
524  lhs, rhs, ret);
525  return ret;
526  }
527 
528 } // vcsn
529 
530 #endif // ! VCSN_ALGORITHMS_NORMALIZED_COMPOSITION_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1