gen_random.hxx

00001 // gen_random.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004, 2005 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
00016 //
00017 #ifndef VCSN_TOOLS_GEN_RANDOM_HXX
00018 # define VCSN_TOOLS_GEN_RANDOM_HXX
00019 
00020 # include <vaucanson/tools/gen_random.hh>
00021 # include <vaucanson/tools/usual_macros.hh>
00022 
00023 # include <cstdlib>
00024 
00025 namespace vcsn {
00026 
00027   using namespace algebra;
00028 
00029   /*---------------------.
00030   | GenRandomAutomataSet |
00031   `---------------------*/
00032 
00033   template <class AutoSet>
00034   AutoSet
00035   GenRandomAutomataSet::generate(SELECTOR(AutomataBase<AutoSet>),
00036                                  unsigned nb_letter)
00037   {
00038 
00039     AUTOMATA_SET_TYPES(AutoSet);
00040 
00041     alphabet_t          alpha;
00042     unsigned            nb = alea(nb_letter ? nb_letter :
00043                                   alpha.max_size());
00044     for (unsigned i = 0; i < nb; ++i)
00045       alpha.insert(alpha.random_letter());
00046 
00047     monoid_t            monoid(alpha);
00048     semiring_t          semi;
00049     series_set_t        series(semi, monoid);
00050     automata_set_t      autoset(series);
00051     return autoset;
00052   }
00053 
00054   template <class AutoSet>
00055   AutoSet
00056   GenRandomAutomataSet::generate(SELECTOR(TransducerBase<AutoSet>),
00057                                  unsigned input_nb_letter,
00058                                  unsigned output_nb_letter)
00059   {
00060     AUTOMATA_SET_TYPES(AutoSet);
00061 
00062     alphabet_t                  input_alpha;
00063     alphabet_t                  output_alpha;
00064 
00065     unsigned                    nb = alea(input_nb_letter ? input_nb_letter :
00066                                           input_alpha.max_size());
00067     for (unsigned i = 0; i < nb; ++i)
00068       input_alpha.insert(input_alpha.random_letter());
00069 
00070     nb = alea(output_nb_letter ? output_nb_letter :
00071               output_alpha.max_size());
00072     for (unsigned i = 0; i < nb; ++i)
00073       output_alpha.insert(output_alpha.random_letter());
00074 
00075     monoid_t                    input_monoid(input_alpha);
00076     monoid_t                    output_monoid(output_alpha);
00077 
00078     typename semiring_t::semiring_t     semi;
00079     semiring_t                  output_series(semi, output_monoid);
00080 
00081     series_set_t                series(output_series, input_monoid);
00082 
00083     automata_set_t              auto_set(series);
00084     return auto_set;
00085   }
00086 
00087   unsigned alea(unsigned max)
00088   {
00089     return int (1 + float (max) * rand() / (RAND_MAX + 1.0));
00090   }
00091 
00092   /*------------------.
00093   | GenRandomAutomata |
00094   `------------------*/
00095 
00096   template <class TAutomata, class AutomataSetGenerator>
00097   GenRandomAutomata<TAutomata, AutomataSetGenerator>::GenRandomAutomata()
00098   {}
00099 
00100   template <class TAutomata, class AutomataSetGenerator>
00101   GenRandomAutomata<TAutomata, AutomataSetGenerator>::
00102   GenRandomAutomata(unsigned init)
00103   {
00104     srand(init);
00105   }
00106 
00107   /*------.
00108   | empty |
00109   `------*/
00110 
00111   template <class TAutomata, class AutomataSetGenerator>
00112   TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
00113   empty(unsigned nb_letter)
00114   {
00115     automata_set_t aset =
00116       GenRandomAutomataSet::generate(SELECT(automata_set_t), nb_letter);
00117     TAutomata work(aset);
00118     return work;
00119   }
00120 
00121   template <class TAutomata, class AutomataSetGenerator>
00122   TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
00123   empty(const automata_set_t& set)
00124   {
00125     TAutomata work(set);
00126     return work;
00127   }
00128 
00129   /*---------.
00130   | generate |
00131   `---------*/
00132 
00133   template <class TAutomata, class AutomataSetGenerator>
00134   TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
00135   generate(unsigned nb_state, unsigned nb_transition_,
00136            unsigned istate, unsigned fstate,
00137            unsigned nb_letter)
00138   {
00139     automata_set_t aset =
00140       GenRandomAutomataSet::generate(SELECT(automata_set_t), nb_letter);
00141     return generate(aset, nb_state, nb_transition_, istate, fstate);
00142   }
00143 
00144   template <class TAutomata, class AutomataSetGenerator>
00145   TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
00146   generate(const automata_set_t& set,
00147            unsigned nb_state, unsigned nb_transition_,
00148            unsigned istate, unsigned fstate)
00149   {
00150     AUTOMATON_TYPES(TAutomata);
00151     AUTOMATON_FREEMONOID_TYPES(TAutomata);
00152     int nb_transition = nb_transition_;
00153     // check consistency of automaton
00154     if (nb_transition_ < nb_state - 1)
00155       nb_transition = nb_state - 1;
00156     if (fstate > nb_state) fstate = nb_state;
00157     if (fstate <= 0) fstate = 1;
00158     if (istate > nb_state) istate = nb_state;
00159     if (istate <= 0) istate = 1;
00160 
00161     TAutomata work(set);
00162 
00163     for (unsigned i = 0; i < nb_state; i++)
00164       work.add_state();
00165 
00166     // minimal construction
00167     state_iterator prev = work.states().begin();
00168     state_iterator i = prev;
00169     ++i;
00170     for (; i != work.states().end(); ++i)
00171     {
00172       nb_transition--;
00173       std::set<htransition_t> aim;
00174       letter_t e = set.series().monoid().alphabet().choose();
00175       work.letter_deltac(aim, *prev, e, delta_kind::transitions());
00176       if (aim.size() == 0)
00177         work.add_letter_transition(*prev, *i, e);
00178       prev = i;
00179     }
00180 
00181     for (int i = 0; i < nb_transition; i++)
00182     {
00183       std::set<hstate_t> aim;
00184       letter_t e = set.series().monoid().alphabet().choose();
00185       hstate_t s = work.choose_state();
00186       hstate_t a = work.choose_state();
00187       work.letter_deltac(aim, s, e, delta_kind::states());
00188       if (aim.find(a) == aim.end())
00189         work.add_letter_transition(s, a, e);
00190     }
00191 
00192     work.set_initial(*work.states().begin());
00193     // set initial states
00194     for (unsigned i = 1; i < istate; i++)
00195     {
00196       hstate_t tmp = work.choose_state();
00197       while (work.is_initial(tmp))
00198         tmp = work.choose_state();
00199       work.set_initial(tmp);
00200     }
00201 
00202     work.set_final(*--work.states().end());
00203     // set final states
00204     for (unsigned i = 1; i < fstate; i++)
00205     {
00206       hstate_t tmp = work.choose_state();
00207       while (work.is_final(tmp))
00208         tmp = work.choose_state();
00209       work.set_final(tmp);
00210     }
00211 
00212     return work;
00213   }
00214 
00215   /*---------------.
00216   | useful methods |
00217   `---------------*/
00218 
00219   template <class TAutomata, class AutomataSetGenerator>
00220   unsigned GenRandomAutomata<TAutomata, AutomataSetGenerator>::
00221   nb_transition_circle(TAutomata work, hstate_t state)
00222   {
00223     AUTOMATON_TYPES(TAutomata);
00224     unsigned res = 0;
00225 
00226     for_each_transition(i, work)
00227       if ((work.src_of(*i) == state) && (work.dst_of(*i) == state))
00228         res++;
00229 
00230     return res;
00231   }
00232 
00233   template <class TAutomata, class AutomataSetGenerator>
00234   void GenRandomAutomata<TAutomata, AutomataSetGenerator>::
00235   del_transition_circle(TAutomata& work, hstate_t state)
00236   {
00237     AUTOMATON_TYPES(TAutomata);
00238 
00239     std::list<htransition_t> to_remove;
00240     for_each_transition(i, work)
00241     {
00242       if ((work.src_of(*i) == state) && (work.dst_of(*i) == state))
00243         to_remove.push_back(*i);
00244     }
00245     for_each_const_(std::list<htransition_t>, e, to_remove)
00246       work.del_transition(*e);
00247   }
00248 
00249 
00250   /*----------------------.
00251   | generate with epsilon |
00252   `----------------------*/
00253 
00254   template <class TAutomata, class AutomataSetGenerator>
00255   TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
00256   generate_with_epsilon(unsigned nb_state,
00257                         unsigned nb_transition,
00258                         unsigned nb_epsilon_min,
00259                         unsigned nb_epsilon_max)
00260   {
00261     automata_set_t aset =
00262       GenRandomAutomataSet::generate(SELECT(automata_set_t));
00263     TAutomata a = generate_with_epsilon(aset, nb_state, nb_transition,
00264                                         nb_epsilon_min, nb_epsilon_max);
00265     return a;
00266   }
00267 
00268 
00269 
00270   template <class TAutomata, class AutomataSetGenerator>
00271   TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
00272   generate_with_epsilon(const automata_set_t& set,
00273                         unsigned nb_state,
00274                         unsigned nb_transition,
00275                         unsigned nb_epsilon_min,
00276                         unsigned nb_epsilon_max)
00277   {
00278     TAutomata a = generate(set, nb_state, nb_transition);
00279     unsigned nb_eps = nb_epsilon_min + alea(nb_epsilon_max - nb_epsilon_min);
00280 
00281     for (unsigned i = 0; i < nb_eps; ++i)
00282     {
00283       hstate_t f = a.choose_state();
00284       hstate_t t = a.choose_state();
00285       a.add_spontaneous(f, t);
00286     }
00287     return a;
00288   }
00289 
00290 
00291   /*-------------.
00292   | generate dfa |
00293   `-------------*/
00294 
00295   template <class TAutomata, class AutomataSetGenerator>
00296   TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
00297   generate_dfa(unsigned nb_state,
00298                unsigned size_alphabet,
00299                unsigned fstate)
00300   {
00301     automata_set_t aset =
00302       GenRandomAutomataSet::generate(SELECT(automata_set_t), size_alphabet);
00303     TAutomata a = generate_dfa(aset, nb_state, fstate);
00304     return a;
00305   }
00306 
00307 
00308 
00309   template <class TAutomata, class AutomataSetGenerator>
00310   TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
00311   generate_dfa(const automata_set_t& set,
00312                unsigned nb_state,
00313                unsigned fstate)
00314   {
00315     AUTOMATON_TYPES(TAutomata);
00316     AUTOMATON_FREEMONOID_TYPES(TAutomata);
00317     automaton_t work(set);
00318 
00319     for (unsigned i = 0; i < nb_state; i++)
00320       work.add_state();
00321 
00322     for_each_state(i, work)
00323     {
00324       for_each_letter(j, set.series().monoid().alphabet())
00325         work.add_letter_transition(*i,work.choose_state(),*j);
00326       while (nb_transition_circle(work, *i) == set.series().monoid().alphabet().size())
00327       {
00328         del_transition_circle(work, *i);
00329         for_each_letter(j, set.series().monoid().alphabet())
00330         {
00331           std::set<hstate_t> ret;
00332           work.letter_deltac(ret, *i, *j, delta_kind::states());
00333           if (ret.size() == 0)
00334           {
00335             hstate_t s;
00336             while ((s = work.choose_state()) == *i);
00337             work.add_letter_transition(*i, s, *j);
00338           }
00339         }
00340       }
00341     }
00342 
00343     // set initial states
00344     work.set_initial(work.choose_state());
00345 
00346     // set final states
00347     for (unsigned i = 0; i < fstate; i++)
00348     {
00349       hstate_t tmp = work.choose_state();
00350       while (work.is_final(tmp))
00351         tmp = work.choose_state();
00352       work.set_final(tmp);
00353     }
00354     return work;
00355   }
00356 
00357 
00358   /*--------------------.
00359   | generate normalized |
00360   `--------------------*/
00361 
00362   template <class TAutomata, class AutomataSetGenerator>
00363   TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
00364   generate_normalized(unsigned nb_state, unsigned density)
00365   {
00366     automata_set_t aset =
00367       AutomataSetGenerator::generate(SELECT(automata_set_t));
00368     TAutomata a = generate_normalized(aset, nb_state, density);
00369     return a;
00370   }
00371 
00372   template <class TAutomata, class AutomataSetGenerator>
00373   TAutomata GenRandomAutomata<TAutomata, AutomataSetGenerator>::
00374   generate_normalized(const automata_set_t& set,
00375                       unsigned nb_state,
00376                       unsigned density)
00377   {
00378     typedef typename TAutomata::state_iterator state_iterator;
00379     typedef typename TAutomata::monoid_t::alphabets_elt_t alphabets_elt_t;
00380 
00381     if (density == 0)
00382       density = 1;
00383 
00384     TAutomata work = generate(set, nb_state,
00385                               nb_state + alea(nb_state * density));
00386 
00387     for (state_iterator i = work.states().begin(); i != work.states().end();
00388          i++)
00389     {
00390       if (work.is_initial(*i))
00391         work.unset_initial(*i);
00392       if (work.is_final(*i))
00393         work.unset_final(*i);
00394     }
00395 
00396     hstate_t init = work.add_state();
00397     hstate_t final = work.add_state();
00398 
00399     work.set_initial(init);
00400     work.set_final(final);
00401 
00402     const alphabets_elt_t&
00403       alpha = work.structure().series().monoid().alphabet();
00404 
00405     hstate_t tmp;
00406 
00407     for (unsigned i = 0; i < density; i++)
00408       if (tmp = work.choose_state() != init)
00409         work.add_letter_transition(init, tmp,
00410                                    alpha.choose());
00411 
00412     for (unsigned i =0; i < density; i++)
00413       if (tmp = work.choose_state() != final)
00414         work.add_letter_transition(tmp, final,
00415                                    alpha.choose());
00416 
00417     return work;
00418   }
00419 
00420 } // vcsn
00421 
00422 #endif // ! VCSN_TOOLS_GEN_RANDOM_HXX

Generated on Fri Jul 28 12:18:33 2006 for Vaucanson by  doxygen 1.4.6