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

Generated on Sun Jul 29 19:35:17 2007 for Vaucanson by  doxygen 1.5.2