aut_to_exp.hxx

00001 // aut_to_exp.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 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_ALGORITHMS_AUT_TO_EXP_HXX
00018 # define VCSN_ALGORITHMS_AUT_TO_EXP_HXX
00019 
00020 # include <vaucanson/algorithms/aut_to_exp.hh>
00021 
00022 # include <vaucanson/automata/concept/handlers.hh>
00023 # include <vaucanson/algorithms/normalized.hh>
00024 # include <vaucanson/misc/usual_macros.hh>
00025 # include <vaucanson/misc/contract.hh>
00026 # include <vaucanson/misc/limits.hh>
00027 # include <vaucanson/misc/random.hh>
00028 # include <vaucanson/automata/concept/automata_base.hh>
00029 
00030 # include <list>
00031 # include <set>
00032 # include <vector>
00033 
00034 # include <stdlib.h>
00035 # include <time.h>
00036 
00037 namespace vcsn {
00038 
00039   /*---------------.
00040   | DefaultChooser |
00041   `---------------*/
00042 
00049   struct DefaultChooser
00050   {
00051       template <class Auto_>
00052       hstate_t
00053       operator()(const Auto_& a) const
00054       {
00055         assertion(a.states().size() > 0);
00056         typename Auto_::state_iterator s = a.states().begin();
00057         typename Auto_::state_iterator k = s;
00058         while ((k != a.states().end()) &&
00059                ((a.is_initial(*k)) || (a.is_final(*k))))
00060           ++k;
00061         s = k;
00062         return *s;
00063       }
00064   };
00065 
00066 
00067 /*--------------.
00068 | RandomChooser |
00069 `--------------*/
00070 
00077   struct RandomChooser
00078   {
00079       template <class Auto_>
00080       hstate_t
00081       operator()(const Auto_& a) const
00082       {
00083         assertion(a.states().size() > 0);
00084 
00085         int n_init = 0;
00086         int n_final = 0;
00087         for (typename Auto_::state_iterator i = a.states().begin();
00088              i != a.states().end();
00089              ++i)
00090         {
00091           if (a.is_initial(*i))
00092             ++n_init;
00093           if (a.is_final(*i))
00094             ++n_final;
00095         }
00096 
00097         unsigned n = misc::random::generate((unsigned) 0,
00098                                                a.states().size() -
00099                                                (n_init + n_final));
00100 
00101         typename Auto_::state_iterator k = a.states().begin();
00102         unsigned kk = 0;
00103         while (kk <= n || k == a.states().end() ||
00104                ((a.is_initial(*k)) || (a.is_final(*k))))
00105         {
00106           if (k == a.states().end())
00107           {
00108             k = a.states().begin();
00109             continue;
00110           }
00111           ++k;
00112           ++kk;
00113         }
00114         return *k;
00115       }
00116   };
00117 
00118 
00119   /*----------------------------.
00120   |    Heuristic chooser:       |
00121   | Transition Number Heuristic |
00122   `----------------------------*/
00123 
00124   struct HChooser
00125   {
00126       template <class Auto_>
00127       hstate_t
00128       operator()(const Auto_& a) const
00129       {
00130         assertion(a.states().size() > 0);
00131 
00132         std::set<htransition_t> delta_in;
00133         std::set<htransition_t> delta_out;
00134 
00135         typename Auto_::state_iterator s = a.states().begin();
00136         unsigned int d_in = 0;
00137         unsigned int d_out = 0;
00138         unsigned int max = INT_MAX;
00139         bool has_loop = false;
00140         bool has_loop_old = false;
00141 
00142         for (typename Auto_::state_iterator i = a.states().begin();
00143              i != a.states().end();
00144              ++i)
00145         {
00146           if (a.is_final(*i) || a.is_initial(*i))
00147             continue;
00148           has_loop = false;
00149 
00150           a.deltac(delta_out, *i, delta_kind::transitions());
00151           a.rdeltac(delta_in, *i, delta_kind::transitions());
00152           for (typename std::set<htransition_t>::iterator j = delta_out.begin();
00153                j != delta_out.end();
00154                ++j)
00155             if (*i == a.dst_of(*j))
00156               has_loop = true;
00157 
00158           //FIXME : If the state has several loops
00159           if (has_loop)
00160             d_in = delta_in.size() - 1;
00161           else
00162             d_in = delta_in.size();
00163           d_out = delta_out.size();
00164 
00165           //We prefer to delete a state that has no loop transition
00166           if (d_in * d_out < max ||
00167               (d_in * d_out == max &&
00168                has_loop_old && not has_loop))
00169           {
00170             s = i;
00171             max = d_in * d_out;
00172             has_loop_old = has_loop;
00173           }
00174           delta_out.clear();
00175           delta_in.clear();
00176         }
00177         return *s;
00178       }
00179   };
00180 
00181 
00182   /*-------------------------.
00183   | Heuristic chooser:       |
00184   | from Delgado & Morais    |
00185   | (Proposed in CIAA 2004)  |
00186   `-------------------------*/
00187   struct DMChooser
00188   {
00189       template <class Auto_>
00190       hstate_t
00191       operator()(const Auto_& a) const
00192       {
00193         assertion(a.states().size() > 0);
00194 
00195         std::set<htransition_t> delta_in;
00196         std::set<htransition_t> delta_out;
00197         typename Auto_::state_iterator s = a.states().begin();
00198 
00199         unsigned int weight_min = INT_MAX;
00200         for (typename Auto_::state_iterator i = a.states().begin();
00201              i != a.states().end();
00202              ++i)
00203         {
00204           if (a.is_final(*i) || a.is_initial(*i))
00205             continue;
00206           unsigned int n_loops = 0;
00207           unsigned int in = 0;
00208           unsigned int out = 0;
00209 
00210           unsigned int weight = 0;
00211 
00212           delta_in.clear();
00213           delta_out.clear();
00214           a.deltac(delta_out, *i, delta_kind::transitions());
00215           a.rdeltac(delta_in, *i, delta_kind::transitions());
00216 
00217           for (typename std::set<htransition_t>::iterator j = delta_out.begin();
00218                j != delta_out.end();
00219                ++j)
00220             if (*i == a.dst_of(*j))
00221               ++n_loops;
00222 
00223           in = delta_in.size() - n_loops;
00224           out = delta_out.size() - n_loops;
00225 
00226           // Compute SUM(Win(k) * (Out - 1))
00227           for (typename std::set<htransition_t>::iterator j = delta_in.begin();
00228                j != delta_in.end();
00229                ++j)
00230             if (*i != a.dst_of(*j))
00231             {
00232               weight += a.series_value_of(*j).length() * (out - 1);
00233             }
00234 
00235           // Compute SUM(Wout(k) * (In - 1))
00236           for (typename std::set<htransition_t>::iterator j = delta_out.begin();
00237                j != delta_out.end();
00238                ++j)
00239             if (*i != a.dst_of(*j))
00240             {
00241               weight += a.series_value_of(*j).length() * (in - 1);
00242             }
00243 
00244           // Compute Wloop * (In * Out - 1)
00245           for (typename std::set<htransition_t>::iterator j = delta_out.begin();
00246                j != delta_out.end();
00247                ++j)
00248             if (*i == a.dst_of(*j))
00249             {
00250               weight += a.series_value_of(*j).length() * (in  * out - 1);
00251             }
00252 
00253           if (weight < weight_min)
00254           {
00255             s = i;
00256             weight_min = weight;
00257           }
00258         }
00259         return *s;
00260       }
00261   };
00262 
00263 
00264 
00265 
00266   /*------------.
00267   | ListChooser |
00268   `------------*/
00269 
00278   class ListChooser
00279   {
00280     public :
00281       ListChooser(const std::list<hstate_t>& l) :
00282         list_(l),
00283         pos_(l.begin())
00284       {}
00285 
00286       template <class Auto_>
00287       hstate_t operator() (const Auto_&)
00288       {
00289         assertion(pos_ != list_.end());
00290         return *pos_++;
00291       }
00292 
00293     private :
00294       std::list<hstate_t>       list_;
00295       std::list<hstate_t>::const_iterator pos_;
00296   };
00297 
00298   /*-----------.
00299   | aut_to_exp |
00300   `-----------*/
00301 
00302   template <class A_, typename Auto_, typename Chooser_>
00303   typename Auto_::series_set_elt_t
00304   do_in_aut_to_exp(const AutomataBase<A_>&  a_set,
00305                    Auto_&                   a,
00306                    Chooser_                 chooser)
00307   {
00308     AUTOMATON_TYPES(Auto_);
00309     typedef Auto_                                       automaton_t;
00310     typedef typename automaton_t::series_set_t          series_set_t;
00311     typedef typename automaton_t::series_set_elt_t      series_set_elt_t;
00312 
00313     typedef typename std::set<htransition_t>            htransition_set_t;
00314     typedef std::map<hstate_t, series_set_elt_t>        sums_t;
00315 
00316     typename htransition_set_t::const_iterator          i, j;
00317     hstate_t                                            q;
00318     htransition_set_t                                   transitions;
00319     std::list<htransition_t> transitions_to_remove;
00320     normalize_here(a);
00321     precondition(is_normalized(a));
00322 
00323     while (a.states().size() != 2)
00324     {
00325       series_set_elt_t loop_sum(a_set.series());
00326       sums_t       in_sums, out_sums;
00327 
00328       q = chooser(a);
00329       if (a.is_initial(q) || a.is_final(q))
00330         continue;
00331 
00332       transitions.clear();
00333       // FIXME: use a new version of delta!
00334       a.deltac(transitions, q, delta_kind::transitions());
00335       for (i = transitions.begin(); i != transitions.end(); i = j)
00336       {
00337         j = i; ++j;
00338 
00339         if (a.dst_of(*i) == q)
00340           loop_sum += a.series_of(*i);
00341         else
00342         {
00343           typename sums_t::iterator f = out_sums.find(a.dst_of(*i));
00344           if (f == out_sums.end())
00345             f = out_sums.insert
00346               (std::make_pair(a.dst_of(*i),
00347                               series_set_elt_t(a_set.series()))).first;
00348           f->second += a.series_of(*i);
00349         }
00350         a.del_transition(*i);
00351       }
00352       transitions.clear();
00353       // FIXME: use a new version of delta!
00354       a.rdeltac(transitions, q, delta_kind::transitions());
00355       for (i = transitions.begin(); i != transitions.end(); i = j)
00356       {
00357         j = i; ++j;
00358         // Here all loops have already been removed.
00359         typename sums_t::iterator f = in_sums.find(a.src_of(*i));
00360         if (f == in_sums.end())
00361           f = in_sums.insert
00362             (std::make_pair(a.src_of(*i),
00363                             series_set_elt_t(a_set.series()))).first;
00364 
00365         f->second += a.series_of(*i);
00366         a.del_transition(*i);
00367       }
00368       loop_sum.star();
00369       //Slow
00370       for_all_const_(sums_t, in, in_sums)
00371         for_all_const_(sums_t, out, out_sums)
00372       {
00373         series_set_elt_t res = in->second * loop_sum * out->second;
00374         a.add_series_transition(in->first, out->first, res);
00375       }
00376       a.del_state(q);
00377     }
00378     series_set_elt_t final(a_set.series());
00379     for_all_transitions(i, a)
00380       final += a.label_of(*i);
00381     return final;
00382   }
00383 
00384   /*-----------.
00385   | aut_to_exp |
00386   `-----------*/
00387 
00388   template<typename A, typename T, typename Chooser_>
00389   typename Element<A, T>::series_set_elt_t
00390   aut_to_exp(const Element<A, T>& a, const Chooser_& c)
00391   {
00392     Element<A, T> ret(a);
00393     return do_in_aut_to_exp(ret.structure(), ret, c);
00394   }
00395 
00396   template<typename A, typename T>
00397   typename Element<A, T>::series_set_elt_t
00398   aut_to_exp(const Element<A, T>& a)
00399   {
00400     return aut_to_exp(a, DefaultChooser());
00401   }
00402 
00403 } // vcsn
00404 
00405 #endif // ! VCSN_ALGORITHMS_AUT_TO_EXP_HXX

Generated on Sat Jul 29 17:12:58 2006 for Vaucanson by  doxygen 1.4.6