Vaucanson  1.4.1
gen_random.hxx
1 // gen_random.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, 2008 The
6 // 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_TOOLS_GEN_RANDOM_HXX
19 # define VCSN_TOOLS_GEN_RANDOM_HXX
20 
21 # include <vaucanson/tools/gen_random.hh>
22 # include <vaucanson/misc/usual_macros.hh>
23 
24 # include <cstdlib>
25 
26 namespace vcsn {
27 
28  namespace tools {
29 
30  using namespace algebra;
31 
32  /*---------------------.
33  | GenRandomAutomataSet |
34  `---------------------*/
35 
36  template <class AutoSet>
37  AutoSet
38  GenRandomAutomataSet::generate(SELECTOR(AutomataBase<AutoSet>),
39  unsigned nb_letter)
40  {
41 
42  AUTOMATA_SET_TYPES(AutoSet);
43 
44  alphabet_t alpha;
45  unsigned max = (alpha.max_size() > ALPHABET_MAX_SIZE ?
46  ALPHABET_MAX_SIZE :
47  alpha.max_size());
48  unsigned nb = alea(nb_letter ? nb_letter : max);
49  for (unsigned i = 0; i < nb; ++i)
50  alpha.insert(alpha.random_letter());
51 
52  monoid_t monoid(alpha);
53  semiring_t semi;
54  series_set_t series(semi, monoid);
55  automata_set_t autoset(series);
56  return autoset;
57  }
58 
59  template <class AutoSet>
60  AutoSet
61  GenRandomAutomataSet::generate(SELECTOR(TransducerBase<AutoSet>),
62  unsigned input_nb_letter,
63  unsigned output_nb_letter)
64  {
65  AUTOMATA_SET_TYPES(AutoSet);
66 
67  alphabet_t input_alpha;
68  alphabet_t output_alpha;
69 
70  unsigned max = (input_alpha.max_size() > ALPHABET_MAX_SIZE ?
71  ALPHABET_MAX_SIZE :
72  input_alpha.max_size());
73  unsigned nb = alea(input_nb_letter ? input_nb_letter : max);
74  for (unsigned i = 0; i < nb; ++i)
75  input_alpha.insert(input_alpha.random_letter());
76 
77  max = (output_alpha.max_size() > ALPHABET_MAX_SIZE ?
78  ALPHABET_MAX_SIZE :
79  output_alpha.max_size());
80  nb = alea(output_nb_letter ? output_nb_letter : max);
81  for (unsigned i = 0; i < nb; ++i)
82  output_alpha.insert(output_alpha.random_letter());
83 
84  monoid_t input_monoid(input_alpha);
85  monoid_t output_monoid(output_alpha);
86 
87  typename semiring_t::semiring_t semi;
88  semiring_t output_series(semi, output_monoid);
89 
90  series_set_t series(output_series, input_monoid);
91 
92  automata_set_t auto_set(series);
93  return auto_set;
94  }
95 
96  unsigned alea(unsigned max)
97  {
98  return int (1 + float (max) * rand() / (RAND_MAX + 1.0));
99  }
100 
101  /*------------------.
102  | GenRandomAutomata |
103  `------------------*/
104 
105  template <class TAutomata, class AutomataSetGenerator>
106  GenRandomAutomata<TAutomata, AutomataSetGenerator>::GenRandomAutomata()
107  {}
108 
109 
110  /*------.
111  | empty |
112  `------*/
113 
114  template <class TAutomata, class AutomataSetGenerator>
115  TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
116  empty(unsigned nb_letter)
117  {
118  automata_set_t aset =
119  GenRandomAutomataSet::generate(SELECT(automata_set_t), nb_letter);
120  TAutomata work(aset);
121  return work;
122  }
123 
124  template <class TAutomata, class AutomataSetGenerator>
125  TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
126  empty(const automata_set_t& set)
127  {
128  TAutomata work(set);
129  return work;
130  }
131 
132  /*---------.
133  | generate |
134  `---------*/
135 
136  template <class TAutomata, class AutomataSetGenerator>
137  TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
138  generate(unsigned nb_state, unsigned nb_transition_,
139  unsigned istate, unsigned fstate,
140  unsigned nb_letter)
141  {
142  automata_set_t aset =
143  GenRandomAutomataSet::generate(SELECT(automata_set_t), nb_letter);
144  return generate(aset, nb_state, nb_transition_, istate, fstate);
145  }
146 
147  template <class TAutomata, class AutomataSetGenerator>
148  TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
149  generate(const automata_set_t& set,
150  unsigned nb_state, unsigned nb_transition_,
151  unsigned istate, unsigned fstate)
152  {
153  AUTOMATON_TYPES(TAutomata);
154  AUTOMATON_FREEMONOID_TYPES(TAutomata);
155  int nb_transition = nb_transition_;
156  // check consistency of automaton
157  if (nb_transition_ < nb_state - 1)
158  nb_transition = nb_state - 1;
159  if (fstate > nb_state) fstate = nb_state;
160  if (fstate <= 0) fstate = 1;
161  if (istate > nb_state) istate = nb_state;
162  if (istate <= 0) istate = 1;
163 
164  TAutomata work(set);
165 
166  for (unsigned i = 0; i < nb_state; i++)
167  work.add_state();
168 
169  // minimal construction
170  state_iterator prev = work.states().begin();
171  state_iterator i = prev;
172  ++i;
173  for (; i != work.states().end(); ++i)
174  {
175  nb_transition--;
176  letter_t e = set.series().monoid().alphabet().choose();
177  bool empty = true;
178  for (delta_iterator t(work.value(), *prev);
179  ! t.done() && empty;
180  t.next())
181  {
182  monoid_elt_t w(work.series_of(*t).structure().monoid(), e);
183  if (work.series_of(*t).get(w) != work.series().semiring().wzero_)
184  {
185  empty = false;
186  break;
187  }
188  }
189 
190  if (empty &&
191  algebra::letter_traits<letter_t>::letter_to_literal(e) != work.structure().series().monoid().representation()->empty)
192  work.add_letter_transition(*prev, *i, e);
193  prev = i;
194  }
195 
196  for (int i = 0; i < nb_transition; i++)
197  {
198  std::set<hstate_t> dst;
199  letter_t e = set.series().monoid().alphabet().choose();
200  hstate_t s = work.choose_state();
201  hstate_t a = work.choose_state();
202  for (delta_iterator t(work.value(), s);
203  ! t.done();
204  t.next())
205  {
206  monoid_elt_t w(work.series_of(*t).structure().monoid(), e);
207  if (work.series_of(*t).get(w) != work.series().semiring().wzero_)
208  dst.insert(work.dst_of(*t));
209  }
210  if (dst.find(a) == dst.end() &&
211  algebra::letter_traits<letter_t>::letter_to_literal(e) != work.structure().series().monoid().representation()->empty)
212  work.add_letter_transition(s, a, e);
213  }
214 
215  work.set_initial(*work.states().begin());
216  // set initial states
217  for (unsigned i = 1; i < istate; i++)
218  {
219  hstate_t tmp = work.choose_state();
220  while (work.is_initial(tmp))
221  tmp = work.choose_state();
222  work.set_initial(tmp);
223  }
224 
225  work.set_final(*--work.states().end());
226  // set final states
227  for (unsigned i = 1; i < fstate; i++)
228  {
229  hstate_t tmp = work.choose_state();
230  while (work.is_final(tmp))
231  tmp = work.choose_state();
232  work.set_final(tmp);
233  }
234 
235  return work;
236  }
237 
238  /*---------------.
239  | useful methods |
240  `---------------*/
241 
242  template <class TAutomata, class AutomataSetGenerator>
243  unsigned GenRandomAutomata<TAutomata, AutomataSetGenerator>::
244  nb_transition_circle(TAutomata work, hstate_t state)
245  {
246  AUTOMATON_TYPES(TAutomata);
247  unsigned res = 0;
248 
249  for_all_transitions(i, work)
250  if ((work.src_of(*i) == state) && (work.dst_of(*i) == state))
251  res++;
252 
253  return res;
254  }
255 
256  template <class TAutomata, class AutomataSetGenerator>
257  void GenRandomAutomata<TAutomata, AutomataSetGenerator>::
258  del_transition_circle(TAutomata& work, hstate_t state)
259  {
260  AUTOMATON_TYPES(TAutomata);
261 
262  std::list<htransition_t> to_remove;
263  for_all_transitions(i, work)
264  {
265  if ((work.src_of(*i) == state) && (work.dst_of(*i) == state))
266  to_remove.push_back(*i);
267  }
268  for_all_const_(std::list<htransition_t>, e, to_remove)
269  work.del_transition(*e);
270  }
271 
272 
273  /*----------------------.
274  | generate with epsilon |
275  `----------------------*/
276 
277  template <class TAutomata, class AutomataSetGenerator>
278  TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
279  generate_with_epsilon(unsigned nb_state,
280  unsigned nb_transition,
281  unsigned nb_epsilon_min,
282  unsigned nb_epsilon_max)
283  {
284  automata_set_t aset =
285  GenRandomAutomataSet::generate(SELECT(automata_set_t));
286  TAutomata a = generate_with_epsilon(aset, nb_state, nb_transition,
287  nb_epsilon_min, nb_epsilon_max);
288  return a;
289  }
290 
291 
292 
293  template <class TAutomata, class AutomataSetGenerator>
294  TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
295  generate_with_epsilon(const automata_set_t& set,
296  unsigned nb_state,
297  unsigned nb_transition,
298  unsigned nb_epsilon_min,
299  unsigned nb_epsilon_max)
300  {
301  TAutomata a = generate(set, nb_state, nb_transition);
302  unsigned nb_eps = nb_epsilon_min + alea(nb_epsilon_max - nb_epsilon_min);
303 
304  for (unsigned i = 0; i < nb_eps; ++i)
305  {
306  hstate_t f = a.choose_state();
307  hstate_t t = a.choose_state();
308  a.add_spontaneous(f, t);
309  }
310  return a;
311  }
312 
313 
314  /*-------------.
315  | generate dfa |
316  `-------------*/
317 
318  template <class TAutomata, class AutomataSetGenerator>
319  TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
320  generate_dfa(unsigned nb_state,
321  unsigned size_alphabet,
322  unsigned fstate)
323  {
324  automata_set_t aset =
325  GenRandomAutomataSet::generate(SELECT(automata_set_t), size_alphabet);
326  TAutomata a = generate_dfa(aset, nb_state, fstate);
327  return a;
328  }
329 
330 
331 
332  template <class TAutomata, class AutomataSetGenerator>
333  TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
334  generate_dfa(const automata_set_t& set,
335  unsigned nb_state,
336  unsigned fstate)
337  {
338  AUTOMATON_TYPES(TAutomata);
339  AUTOMATON_FREEMONOID_TYPES(TAutomata);
340  automaton_t work(set);
341 
342  for (unsigned i = 0; i < nb_state; i++)
343  work.add_state();
344 
345  for_all_states(i, work)
346  {
347  for_all_letters(j, set.series().monoid().alphabet())
348  work.add_letter_transition(*i,work.choose_state(),*j);
349  while (nb_transition_circle(work, *i) == set.series().monoid().alphabet().size())
350  {
351  del_transition_circle(work, *i);
352  for_all_letters(j, set.series().monoid().alphabet())
353  {
354  bool empty = true;
355  for (delta_iterator t(work.value(), *i);
356  ! t.done() && empty;
357  t.next())
358  {
359  monoid_elt_t w(work.series_of(*t).structure().monoid(), *j);
360  if (work.series_of(*t).get(w) != work.series().semiring().wzero_)
361  {
362  empty = false;
363  break;
364  }
365  }
366  if (empty)
367  {
368  hstate_t s;
369  while ((s = work.choose_state()) == *i) ;
370  work.add_letter_transition(*i, s, *j);
371  }
372  }
373  }
374  }
375 
376  // set initial states
377  work.set_initial(work.choose_state());
378 
379  // set final states
380  for (unsigned i = 0; i < fstate; i++)
381  {
382  hstate_t tmp = work.choose_state();
383  while (work.is_final(tmp))
384  tmp = work.choose_state();
385  work.set_final(tmp);
386  }
387  return work;
388  }
389 
390 
391  /*--------------------.
392  | generate normalized |
393  `--------------------*/
394 
395  template <class TAutomata, class AutomataSetGenerator>
396  TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
397  generate_normalized(unsigned nb_state, unsigned density)
398  {
399  automata_set_t aset =
400  AutomataSetGenerator::generate(SELECT(automata_set_t));
401  TAutomata a = generate_normalized(aset, nb_state, density);
402  return a;
403  }
404 
405  template <class TAutomata, class AutomataSetGenerator>
406  TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
407  generate_normalized(const automata_set_t& set,
408  unsigned nb_state,
409  unsigned density)
410  {
411  typedef typename TAutomata::state_iterator state_iterator;
412  typedef typename TAutomata::monoid_t::alphabets_elt_t alphabets_elt_t;
413 
414  if (density == 0)
415  density = 1;
416 
417  TAutomata work = generate(set, nb_state,
418  nb_state + alea(nb_state * density));
419 
420  for (state_iterator i = work.states().begin(); i != work.states().end();
421  i++)
422  {
423  if (work.is_initial(*i))
424  work.unset_initial(*i);
425  if (work.is_final(*i))
426  work.unset_final(*i);
427  }
428 
429  hstate_t init = work.add_state();
430  hstate_t final = work.add_state();
431 
432  work.set_initial(init);
433  work.set_final(final);
434 
435  const alphabets_elt_t&
436  alpha = work.structure().series().monoid().alphabet();
437 
438  hstate_t tmp;
439 
440  for (unsigned i = 0; i < density; i++)
441  if ((tmp = work.choose_state()) != init)
442  work.add_letter_transition(init, tmp,
443  alpha.choose());
444 
445  for (unsigned i =0; i < density; i++)
446  if ((tmp = work.choose_state()) != final)
447  work.add_letter_transition(tmp, final,
448  alpha.choose());
449 
450  return work;
451  }
452 
453  } // ! tools
454 
455 } // ! vcsn
456 
457 #endif // ! VCSN_TOOLS_GEN_RANDOM_HXX
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1