Vaucanson  1.4.1
outsplitting.hxx
Go to the documentation of this file.
1 // outsplitting.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 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_OUTSPLITTING_HXX
18 # define VCSN_ALGORITHMS_OUTSPLITTING_HXX
19 
20 
31 # include <vaucanson/algorithms/internal/outsplitting.hh>
32 # include <vaucanson/algorithms/accessible.hh>
33 # include <vaucanson/algebra/implementation/series/series.hh>
34 # include <vaucanson/algebra/concept/freemonoid_product.hh>
35 
36 namespace vcsn {
37  namespace splitting {
38 
42 
43  template <typename S, typename M1, typename M2, typename Auto_t>
44  Auto_t
45  do_outsplitting(const AutomataBase<S>&,
46  const algebra::FreeMonoidProduct<M1, M2>&,
47  const Auto_t& aut,
48  std::set<typename Auto_t::hstate_t>& m)
49  {
50  AUTOMATON_TYPES(Auto_t);
51 
52  typedef typename series_set_elt_t::support_t support_t;
53 
54  typedef typename monoid_t::second_monoid_t second_monoid_t;
55 
56  typedef typename monoid_elt_value_t::second_type
57  second_monoid_elt_value_t;
58  typedef Element<second_monoid_t, second_monoid_elt_value_t>
59  second_monoid_elt_t;
60 
61  typedef std::list<htransition_t> set_of_transitions_t;
62 
63 
64 
65  second_monoid_elt_t second_identity =
66  algebra::identity_as<second_monoid_elt_value_t>::
67  of(aut.structure().series().monoid().second_monoid());
68 
69  Auto_t res(aut);
70 
71  const series_set_t& series = res.structure().series();
72  const monoid_t& monoid = series.monoid();
73 
74 
75 
76  for_all_states(s, res)
77  {
78  bool eps_out = false;
79  bool other_out = false;
80  bool diff = false;
81 
82  // Test whether there are different types of outgoing transitions.
83 
84  set_of_transitions_t transitions;
85  for (delta_iterator e(res.value(), *s); ! e.done(); e.next())
86  transitions.push_back(*e);
87  for_all_const_(set_of_transitions_t, e, transitions)
88  {
89  const series_set_elt_t series = res.series_of(*e);
90  support_t supp = series.supp();
91  const monoid_elt_t supp_elt (monoid, *(supp.begin()));
92 
93  if (supp_elt.value().second == second_identity.value())
94  eps_out = true;
95  else
96  other_out = true;
97  if (eps_out and other_out)
98  {
99  diff = true;
100  break;
101  }
102  }
103 
104  if (eps_out and not diff)
105  m.insert(*s);
106 
107  // If there are different types of outgoing transitions.
108  if (diff)
109  {
110  hstate_t s2 = res.add_state();
111  if (res.is_initial(*s))
112  res.set_initial(s2, res.get_initial(*s));
113 
114  set_of_transitions_t in_transitions;
115  for (rdelta_iterator e(res.value(), *s); ! e.done(); e.next())
116  in_transitions.push_back(*e);
117 
118  for_all_(set_of_transitions_t, e, in_transitions)
119  res.add_series_transition(res.src_of(*e), s2, res.series_of(*e));
120 
121  for_all_const_(set_of_transitions_t, e, transitions)
122  {
123  const series_set_elt_t series = res.series_of(*e);
124  support_t supp = series.supp();
125  const monoid_elt_t supp_elt (monoid, *(supp.begin()));
126 
127  if (supp_elt.value().second == second_identity.value())
128  {
129  res.add_series_transition(s2, res.dst_of(*e), res.series_of(*e));
130  res.del_transition(*e);
131  }
132  }
133  m.insert(s2);
134  }
135  }
136  return coaccessible(res);
137  }
138 
139 
143 
144  template <typename S, typename M1, typename M2, typename Auto_t>
145  Auto_t
146  do_insplitting(const AutomataBase<S>&,
147  const algebra::FreeMonoidProduct<M1, M2>&,
148  const Auto_t& aut,
149  std::set<typename Auto_t::hstate_t>& m)
150  {
151  AUTOMATON_TYPES(Auto_t);
152 
153  typedef typename series_set_elt_t::support_t support_t;
154 
155  typedef typename monoid_t::first_monoid_t first_monoid_t;
156 
157  typedef typename monoid_elt_value_t::first_type
158  first_monoid_elt_value_t;
159  typedef Element<first_monoid_t, first_monoid_elt_value_t>
160  first_monoid_elt_t;
161 
162  typedef std::list<htransition_t> set_of_transitions_t;
163 
164 
165 
166  first_monoid_elt_t first_identity =
167  algebra::identity_as<first_monoid_elt_value_t>::
168  of(aut.structure().series().monoid().first_monoid());
169 
170  Auto_t res(aut);
171 
172  const series_set_t& series = res.structure().series();
173  const monoid_t& monoid = series.monoid();
174 
175 
176 
177  for_all_states(s, res)
178  {
179  bool eps_in = false;
180  bool other_in = false;
181  bool diff = false;
182 
183  // Test whether there are different types of incoming transitions.
184 
185  set_of_transitions_t transitions;
186  for (rdelta_iterator e(res.value(), *s); ! e.done(); e.next())
187  transitions.push_back(*e);
188  for_all_const_(set_of_transitions_t, e, transitions)
189  {
190  const series_set_elt_t series = res.series_of(*e);
191  support_t supp = series.supp();
192  const monoid_elt_t supp_elt (monoid, *(supp.begin()));
193 
194  if (supp_elt.value().first == first_identity.value())
195  eps_in = true;
196  else
197  other_in = true;
198  if (eps_in and other_in)
199  {
200  diff = true;
201  break;
202  }
203  }
204 
205  if (eps_in and not diff)
206  m.insert(*s);
207 
208  // If there are different types of incoming transitions.
209  if (diff)
210  {
211  hstate_t s2 = res.add_state();
212  if (res.is_final(*s))
213  res.set_final(s2, res.get_final(*s));
214 
215  set_of_transitions_t out_transitions;
216  for (delta_iterator e(res.value(), *s); ! e.done(); e.next())
217  out_transitions.push_back(*e);
218 
219  for_all_(set_of_transitions_t, e, out_transitions)
220  res.add_series_transition(s2, res.dst_of(*e), res.series_of(*e));
221 
222  for_all_const_(set_of_transitions_t, e, transitions)
223  {
224  const series_set_elt_t series = res.series_of(*e);
225  support_t supp = series.supp();
226  const monoid_elt_t supp_elt (monoid, *(supp.begin()));
227 
228  if (supp_elt.value().first == first_identity.value())
229  {
230  res.add_series_transition(res.src_of(*e), s2,
231  res.series_of(*e));
232  res.del_transition(*e);
233  }
234  }
235  m.insert(s2);
236  }
237  }
238  return res;
239  }
240 
241 
242  template <typename S, typename T>
243  Element<S, T>
244  outsplitting(const Element<S, T>& aut,
245  std::set<typename T::hstate_t>& states)
246  {
247  return do_outsplitting(aut.structure(),
248  aut.structure().series().monoid(),
249  aut,
250  states);
251  }
252 
253 
254  template <typename S, typename T>
255  Element<S, T>
256  insplitting(const Element<S, T>& aut,
257  std::set<typename T::hstate_t>& states)
258  {
259  return do_insplitting(aut.structure(),
260  aut.structure().series().monoid(),
261  aut,
262  states);
263  }
264 
265 
266 
267  template <typename S, typename T>
268  Element<S, T>
269  outsplitting(const Element<S, T>& aut)
270  {
271  std::set<typename T::hstate_t> states;
272  return do_outsplitting(aut.structure(),
273  aut.structure().series().monoid(),
274  aut,
275  states);
276  }
277 
278 
279  template <typename S, typename T>
280  Element<S, T>
281  insplitting(const Element<S, T>& aut)
282  {
283  std::set<typename T::hstate_t> states;
284  return do_insplitting(aut.structure(),
285  aut.structure().series().monoid(),
286  aut,
287  states);
288  }
289  }
290 } // End of namespace vcsn.
291 
292 #endif // ! VCSN_ALGORITHMS_OUTSPLITTING_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1