Vaucanson  1.4.1
aut_to_exp.hxx
1 // aut_to_exp.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2004, 2005, 2006, 2008 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_AUT_TO_EXP_HXX
18 # define VCSN_ALGORITHMS_AUT_TO_EXP_HXX
19 
20 # include <vaucanson/algorithms/aut_to_exp.hh>
21 
22 # include <vaucanson/automata/concept/handlers.hh>
23 # include <vaucanson/algorithms/normalized.hh>
24 # include <vaucanson/misc/usual_macros.hh>
25 # include <vaucanson/misc/contract.hh>
26 # include <vaucanson/misc/limits.hh>
27 # include <vaucanson/misc/random.hh>
28 # include <vaucanson/automata/concept/automata_base.hh>
29 
30 # include <list>
31 # include <set>
32 # include <vector>
33 
34 # include <stdlib.h>
35 # include <time.h>
36 
37 namespace vcsn {
38 
39  /*---------------.
40  | DefaultChooser |
41  `---------------*/
42 
43  template <class Auto_>
44  typename Auto_::hstate_t
45  DefaultChooser::operator()(const Auto_& a) const
46  {
47  assertion(a.states().size() > 0);
48  typename Auto_::state_iterator s = a.states().begin();
49  typename Auto_::state_iterator k = s;
50  while ((k != a.states().end()) &&
51  ((a.is_initial(*k)) || (a.is_final(*k))))
52  ++k;
53  s = k;
54  return *s;
55  }
56 
57  /*--------------.
58  | RandomChooser |
59  `--------------*/
60 
61  template <class Auto_>
62  typename Auto_::hstate_t
63  RandomChooser::operator()(const Auto_& a) const
64  {
65  assertion(a.states().size() > 0);
66 
67  int n_init = 0;
68  int n_final = 0;
69  for (typename Auto_::state_iterator i = a.states().begin();
70  i != a.states().end();
71  ++i)
72  {
73  if (a.is_initial(*i))
74  ++n_init;
75  if (a.is_final(*i))
76  ++n_final;
77  }
78 
79  unsigned n = misc::random::generate((unsigned) 0,
80  a.states().size() -
81  (n_init + n_final));
82 
83  typename Auto_::state_iterator k = a.states().begin();
84  unsigned kk = 0;
85  while (kk <= n || k == a.states().end() ||
86  ((a.is_initial(*k)) || (a.is_final(*k))))
87  {
88  if (k == a.states().end())
89  {
90  k = a.states().begin();
91  continue;
92  }
93  ++k;
94  ++kk;
95  }
96  return *k;
97  }
98 
99  /*----------------------------.
100  | Heuristic chooser: |
101  | Transition Number Heuristic |
102  `----------------------------*/
103 
104  template <class Auto_>
105  typename Auto_::hstate_t
106  HChooser::operator()(const Auto_& a) const
107  {
108  assertion(a.states().size() > 0);
109 
110  std::list<typename Auto_::htransition_t> delta_in;
111  std::list<typename Auto_::htransition_t> delta_out;
112 
113  typename Auto_::state_iterator s = a.states().begin();
114  unsigned int d_in = 0;
115  unsigned int d_out = 0;
116  unsigned int max = misc::limits<unsigned int>::max();
117  bool has_loop = false;
118  bool has_loop_old = false;
119 
120  for (typename Auto_::state_iterator i = a.states().begin();
121  i != a.states().end();
122  ++i)
123  {
124  if (a.is_final(*i) || a.is_initial(*i))
125  continue;
126  has_loop = false;
127 
128  for (typename Auto_::delta_iterator j(a.value(), *i);
129  ! j.done();
130  j.next())
131  delta_out.push_back(*j);
132  for (typename Auto_::rdelta_iterator j(a.value(), *i);
133  ! j.done();
134  j.next())
135  delta_in.push_back(*j);
136  for (typename std::list<typename Auto_::htransition_t>::iterator j = delta_out.begin();
137  j != delta_out.end();
138  ++j)
139  if (*i == a.dst_of(*j))
140  has_loop = true;
141 
142  //FIXME : If the state has several loops
143  if (has_loop)
144  d_in = delta_in.size() - 1;
145  else
146  d_in = delta_in.size();
147  d_out = delta_out.size();
148 
149  //We prefer to delete a state that has no loop transition
150  if (d_in * d_out < max ||
151  (d_in * d_out == max &&
152  has_loop_old && not has_loop))
153  {
154  s = i;
155  max = d_in * d_out;
156  has_loop_old = has_loop;
157  }
158  delta_out.clear();
159  delta_in.clear();
160  }
161  return *s;
162  }
163 
164  /*-------------------------.
165  | Heuristic chooser: |
166  | from Delgado & Morais |
167  | (Proposed in CIAA 2004) |
168  `-------------------------*/
169 
170  template <class Auto_>
171  typename Auto_::hstate_t
172  DMChooser::operator()(const Auto_& a) const
173  {
174  assertion(a.states().size() > 0);
175 
176  std::list<typename Auto_::htransition_t> delta_in;
177  std::list<typename Auto_::htransition_t> delta_out;
178  typename Auto_::state_iterator s = a.states().begin();
179 
180  int weight_min = misc::limits<int>::max();
181  for (typename Auto_::state_iterator i = a.states().begin();
182  i != a.states().end();
183  ++i)
184  {
185  if (a.is_final(*i) || a.is_initial(*i))
186  continue;
187  unsigned int n_loops = 0;
188  unsigned int in = 0;
189  unsigned int out = 0;
190 
191  int weight = 0;
192 
193  delta_in.clear();
194  delta_out.clear();
195  for (typename Auto_::delta_iterator j(a.value(), *i);
196  ! j.done();
197  j.next())
198  delta_out.push_back(*j);
199  for (typename Auto_::rdelta_iterator j(a.value(), *i);
200  ! j.done();
201  j.next())
202  delta_in.push_back(*j);
203 
204  for (typename std::list<typename Auto_::htransition_t>::iterator j = delta_out.begin();
205  j != delta_out.end();
206  ++j)
207  if (*i == a.dst_of(*j))
208  ++n_loops;
209 
210  in = delta_in.size() - n_loops;
211  out = delta_out.size() - n_loops;
212 
213  // Compute SUM(Win(k) * (Out - 1))
214  for (typename std::list<typename Auto_::htransition_t>::iterator j = delta_in.begin();
215  j != delta_in.end();
216  ++j)
217  if (*i != a.dst_of(*j))
218  {
219  weight += a.series_value_of(*j).length() * (out - 1);
220  }
221 
222  // Compute SUM(Wout(k) * (In - 1))
223  for (typename std::list<typename Auto_::htransition_t>::iterator j = delta_out.begin();
224  j != delta_out.end();
225  ++j)
226  if (*i != a.dst_of(*j))
227  {
228  weight += a.series_value_of(*j).length() * (in - 1);
229  }
230 
231  // Compute Wloop * (In * Out - 1)
232  for (typename std::list<typename Auto_::htransition_t>::iterator j = delta_out.begin();
233  j != delta_out.end();
234  ++j)
235  if (*i == a.dst_of(*j))
236  {
237  weight += a.series_value_of(*j).length() * (in * out - 1);
238  }
239 
240  if (weight < weight_min)
241  {
242  s = i;
243  weight_min = weight;
244  }
245  }
246  return *s;
247  }
248 
249  /*------------.
250  | ListChooser |
251  `------------*/
252 
253  inline ListChooser::ListChooser(const std::list<unsigned int>& l) :
254  list_(l),
255  pos_(l.begin())
256  {
257  }
258 
259  template <class Auto_>
260  typename Auto_::hstate_t
261  ListChooser::operator() (const Auto_& a)
262  {
263  assertion(pos_ != list_.end());
264  return a.get_state(*pos_++);
265  }
266 
267  /*-----------.
268  | aut_to_exp |
269  `-----------*/
270 
271  template <class A, typename AI, typename Chooser>
272  typename Element<A, AI>::series_set_elt_t
273  do_in_aut_to_exp(const AutomataBase<A>& a_set,
274  Element<A, AI>& a,
275  Chooser chooser)
276  {
277  typedef Element<A, AI> automaton_t;
278  AUTOMATON_TYPES(automaton_t);
279  typedef typename automaton_t::series_set_t series_set_t;
280  typedef typename automaton_t::series_set_elt_t series_set_elt_t;
281 
282  typedef typename std::list<htransition_t> htransition_set_t;
283  typedef std::map<hstate_t, series_set_elt_t> sums_t;
284 
285  typename htransition_set_t::const_iterator i, j;
286  hstate_t q;
287  htransition_set_t transitions;
288  std::list<htransition_t> transitions_to_remove;
289  normalize_here(a);
290  // assertion(is_normalized(a)); // FIXME To remove
291 
292  while (a.states().size() != 2)
293  {
294  series_set_elt_t loop_sum(a_set.series());
295  sums_t in_sums, out_sums;
296 
297  q = chooser(a);
298  if (a.is_initial(q) || a.is_final(q))
299  continue;
300 
301  transitions.clear();
302  for (delta_iterator e(a.value(), q); ! e.done(); e.next())
303  transitions.push_back(*e);
304  for (i = transitions.begin(); i != transitions.end(); i = j)
305  {
306  j = i; ++j;
307 
308  if (a.dst_of(*i) == q)
309  loop_sum += a.series_of(*i);
310  else
311  {
312  typename sums_t::iterator f = out_sums.find(a.dst_of(*i));
313  if (f == out_sums.end())
314  f = out_sums.insert
315  (std::make_pair(a.dst_of(*i),
316  series_set_elt_t(a_set.series()))).first;
317  f->second += a.series_of(*i);
318  }
319  a.del_transition(*i);
320  }
321  transitions.clear();
322  for (rdelta_iterator e(a.value(), q); ! e.done(); e.next())
323  transitions.push_back(*e);
324  for (i = transitions.begin(); i != transitions.end(); i = j)
325  {
326  j = i; ++j;
327  // Here all loops have already been removed.
328  typename sums_t::iterator f = in_sums.find(a.src_of(*i));
329  if (f == in_sums.end())
330  f = in_sums.insert
331  (std::make_pair(a.src_of(*i),
332  series_set_elt_t(a_set.series()))).first;
333 
334  f->second += a.series_of(*i);
335  a.del_transition(*i);
336  }
337  loop_sum.star();
338  //Slow
339  for_all_const_(sums_t, in, in_sums)
340  for_all_const_(sums_t, out, out_sums)
341  {
342  series_set_elt_t res = in->second * loop_sum * out->second;
343  a.add_series_transition(in->first, out->first, res);
344  }
345  a.del_state(q);
346  }
347  series_set_elt_t final(a_set.series());
348  for_all_const_transitions(i, a)
349  final += a.label_of(*i);
350  return final;
351  }
352 
353  /*-----------.
354  | aut_to_exp |
355  `-----------*/
356 
357  template<typename A, typename AI, typename Chooser>
358  typename Element<A, AI>::series_set_elt_t
359  aut_to_exp(const Element<A, AI>& a, const Chooser& c)
360  {
361  BENCH_TASK_SCOPED("aut_to_exp");
362  Element<A, AI> ret(a);
363  return do_in_aut_to_exp(ret.structure(), ret, c);
364  }
365 
366  template<typename A, typename AI>
367  typename Element<A, AI>::series_set_elt_t
368  aut_to_exp(const Element<A, AI>& a)
369  {
370  return aut_to_exp(a, DefaultChooser());
371  }
372 
373 } // vcsn
374 
375 #endif // ! VCSN_ALGORITHMS_AUT_TO_EXP_HXX
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1