evaluation.hxx

00001 // evaluation.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, 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_EVALUATION_HXX
00018 # define VCSN_ALGORITHMS_EVALUATION_HXX
00019 
00020 # include <vaucanson/algorithms/evaluation.hh>
00021 
00022 # include <vaucanson/automata/concept/transducer_base.hh>
00023 
00024 # include <vaucanson/algorithms/product.hh>
00025 # include <vaucanson/algorithms/trim.hh>
00026 # include <vaucanson/algorithms/standard.hh>
00027 # include <vaucanson/algorithms/standard_of.hh>
00028 # include <vaucanson/algorithms/aut_to_exp.hh>
00029 # include <vaucanson/algorithms/extension.hh>
00030 # include <vaucanson/algorithms/projection.hh>
00031 # include <vaucanson/algorithms/aut_to_exp.hh>
00032 # include <vaucanson/misc/usual_macros.hh>
00033 
00034 namespace vcsn {
00035 
00036   template <typename SA, typename ST, typename SRET,
00037             typename Auto_t, typename Trans_t, typename Ret_t>
00038   void
00039   do_evaluation(const AutomataBase<SA>&,
00040                 const TransducerBase<ST>&,
00041                 const AutomataBase<SRET>&,
00042                 const Auto_t& a,
00043                 const Trans_t& t,
00044                 Ret_t& ret)
00045   {
00046     output_projection(trim(product(t, extension(a, t))), ret);
00047   }
00048 
00049   template<typename SA, typename TA, typename ST,
00050            typename TT, typename SRET, typename TRET>
00051   void
00052   evaluation(const Element<SA, TA>& a, const Element<ST, TT>& t,
00053              Element<SRET, TRET>& ret)
00054   {
00055     do_evaluation(a.structure(), t.structure(), ret.structure(), a, t, ret);
00056   }
00057 
00058   template<typename E, typename S, typename Trans_t, typename M>
00059   void
00060   do_partial_evaluation(const E& exp,
00061                         const TransducerBase<S>&,
00062                         const Trans_t& t,
00063                         M& state_exp_pair_set)
00064   {
00065     typedef typename Trans_t::value_t T;
00066     typedef typename output_projection_helper<S, T>::ret Auto_t;
00067     typedef typename Auto_t::set_t::series_set_t      Auto_series_set_t;
00068     typename Auto_t::set_t
00069       auto_structure(Auto_series_set_t(t.structure().series().semiring()));
00070     Auto_t tmp_auto(auto_structure);
00071 
00072     AUTOMATON_TYPES(Auto_t);
00073     monoid_elt_t empty = tmp_auto.series().monoid().empty_;
00074     standard_of(tmp_auto, exp.get(empty).value());
00075     partial_1(tmp_auto, t, state_exp_pair_set);
00076   }
00077 
00078   /* Input : an expression, a transducer.
00079      Output : a set of pair (hstate_t, expression)*/
00080   template<typename S1, typename T1,
00081            typename S2, typename T2,
00082            typename M>
00083   void
00084   partial_evaluation(const Element<S1, T1>& exp,
00085                      const Element<S2, T2>& trans,
00086                      M& state_exp_pair_set)
00087   {
00088     do_partial_evaluation(exp, trans.structure(), trans, state_exp_pair_set);
00089   }
00090 
00091   template<typename S, typename Auto_t, typename M, typename Chooser_t>
00092   void
00093   do_partial_elimination(const AutomataBase<S>&,
00094                          const Auto_t& a,
00095                          Chooser_t chooser,
00096                          M& state_exp_pair_set)
00097   {
00098     AUTOMATON_TYPES(Auto_t);
00099     typedef typename std::set<htransition_t>            htransition_set_t;
00100     typedef std::map<hstate_t, series_set_elt_t>        sums_t;
00101 
00102     typename htransition_set_t::const_iterator          i, j;
00103     hstate_t                                            q;
00104     htransition_set_t                                   transitions;
00105 
00106     Auto_t b = a;
00107     standardize(b);
00108 
00109     int num = b.final().size() + 1; // all final states and the initial state.
00110 
00111     while (int(b.states().size()) != num)
00112     {
00113       series_set_elt_t loop_sum(b.series());
00114       sums_t       in_sums, out_sums;
00115       typename sums_t::iterator f;
00116       q = chooser(b);
00117       if (b.is_initial(q) || b.is_final(q))
00118         continue;
00119 
00120       transitions.clear();
00121       // FIXME: use a new version of delta !
00122       b.deltac(transitions, q, delta_kind::transitions());
00123       for (i = transitions.begin(); i != transitions.end(); i = j)
00124       {
00125         j = i; ++j;
00126 
00127         if (b.dst_of(*i) == q)
00128           loop_sum += b.series_of(*i);
00129         else if ((f = out_sums.find(b.dst_of(*i))) !=
00130                  out_sums.end())
00131           f->second += b.series_of(*i);
00132         else
00133           out_sums.insert(std::make_pair(b.dst_of(*i), b.series_of(*i)));
00134         b.del_transition(*i);
00135       }
00136       transitions.clear();
00137       // FIXME: use a new version of delta !
00138       b.rdeltac(transitions, q, delta_kind::transitions());
00139       for (i = transitions.begin(); i != transitions.end(); i = j)
00140       {
00141         j = i; ++j;
00142         // here all loops have already been removed
00143         if ((f = in_sums.find(b.src_of(*i))) !=
00144             in_sums.end())
00145           f->second += b.series_of(*i);
00146         else
00147           in_sums.insert(std::make_pair(b.src_of(*i), b.series_of(*i)));
00148         b.del_transition(*i);
00149       }
00150       loop_sum.star();
00151       for_all_const_(sums_t, in, in_sums)
00152         for_all_const_(sums_t, out, out_sums)
00153       {
00154         series_set_elt_t res = in->second * loop_sum * out->second;
00155         b.add_series_transition(in->first, out->first, res);
00156       }
00157       b.del_state(q);
00158     }
00159 
00160     typedef std::map<hstate_t, series_set_elt_t>   se_map_t;
00161     typedef std::pair<hstate_t, series_set_elt_t>  state_exp_pair_t;
00162     se_map_t se_m;
00163 
00164     // maybe there are more than one transition comming to one final state
00165     // we must sum the labels
00166     for_all_transitions(e, b)
00167     {
00168       hstate_t aim = b.dst_of(*e);
00169       typename se_map_t::iterator i = se_m.find(aim);
00170       if (i == se_m.end())
00171         se_m.insert(std::make_pair(aim,
00172                                    series_set_elt_t (b.structure().series(),
00173                                                      b.label_of(*e))));
00174       else
00175         i->second += b.label_of(*e);
00176     }
00177 
00178     for_all_final_states(p, b)
00179     {
00180       typename se_map_t::iterator i = se_m.find(*p);
00181       if (i != se_m.end())
00182         state_exp_pair_set.insert(std::make_pair(*p, i->second));
00183     }
00184   }
00185 
00186   /*------------.
00187   | elimination |
00188   `------------*/
00189   // preconditions :
00190   //   - hope that automaton's labels are sufficient to support "star"
00191   //     => in fact, generalized automaton are generally expected here.
00192   //
00193 
00194   template<typename A, typename T, typename M>
00195   void
00196   partial_elimination(const Element<A, T>& a,
00197                       M& state_exp_pair_set)
00198   {
00199     do_partial_elimination(a.structure(),
00200                            a,
00201                            DefaultChooser(),
00202                            state_exp_pair_set);
00203   }
00204 
00206   /* partial_1 */
00207   template<typename SA, typename ST,
00208            typename Auto_t, typename Trans_t,
00209            typename M>
00210   void
00211   do_partial_1(const AutomataBase<SA>&,
00212                const TransducerBase<ST>&,
00213                const Auto_t& a,
00214                const Trans_t& t,
00215                M& state_exp_pair_set)
00216   {
00217     typedef typename Trans_t::value_t T;
00218     typedef typename output_projection_helper<ST, T>::ret Auto_ret_t;
00219     typedef typename Auto_ret_t::set_t::series_set_t      Auto_ret_series_set_t;
00220     typename Auto_ret_t::set_t
00221       auto_structure(Auto_ret_series_set_t(t.structure().series().semiring()));
00222 
00223     AUTOMATON_TYPES_(Auto_t, a_);
00224     AUTOMATON_TYPES_(Trans_t, t_);
00225     AUTOMATON_TYPES_(Auto_ret_t, ret_);
00226 
00227     typedef std::map<hstate_t, std::pair<hstate_t, hstate_t> >
00228       state_pair_map_t;
00229     typedef std::map<hstate_t, hstate_t> state_state_map_t;
00230     typedef std::pair<hstate_t, ret_series_set_elt_t> se_pair_t;
00231 
00232     Trans_t tmp_trans(t.structure());
00233     tmp_trans = extension(a, t);
00234 
00235     Trans_t pro(t.structure());
00236     state_pair_map_t sp_m;
00237     pro = product(tmp_trans, t, sp_m);
00238     Auto_ret_t auto_p(auto_structure);
00239     std::map<hstate_t, hstate_t> proj_m;
00240     auto_p = output_projection(pro, proj_m);
00241 
00242     /* unset final all the final states of auto_p */
00243     auto_p.clear_final();
00244 
00245     /* for each state u of t, add one final state to 'auto_p' */
00246     state_state_map_t final_of, is_final_of;
00247     for(t_state_iterator u = t.states().begin(); u != t.states().end(); ++u)
00248     {
00249       hstate_t new_state = auto_p.add_state();
00250       final_of[*u] = new_state;
00251       is_final_of[new_state] = *u;
00252       auto_p.set_final(new_state);
00253     }
00254 
00255     for(a_state_iterator u = auto_p.states().begin();
00256         u != auto_p.states().end(); ++u)
00257     {
00258       if (!auto_p.is_final(*u))
00259       {
00260         hstate_t p = sp_m[proj_m[*u]].first;
00261         hstate_t q = sp_m[proj_m[*u]].second;
00262 
00263         if (tmp_trans.is_final(p))
00264           auto_p.add_spontaneous(*u, final_of[q]);
00265       }
00266     }
00267 
00268     M se;
00269     partial_elimination(auto_p, se);
00270 
00271     state_exp_pair_set.clear();
00272     for_all_(M, p, se)
00273     {
00274       se_pair_t my_pair = std::make_pair(is_final_of[(*p).first],
00275                                          p->second); // checking type compatibility
00276       state_exp_pair_set.insert(my_pair);
00277     }
00278   }
00279 
00280   template<typename SA, typename TA,
00281            typename ST, typename TT,
00282            typename M>
00283   void
00284   partial_1(const Element<SA, TA>& a,
00285             const Element<ST, TT>& t,
00286             M& state_exp_pair_set)
00287   {
00288     do_partial_1(a.structure(), t.structure(), a, t, state_exp_pair_set);
00289   }
00290 
00292   /* partial_2 */
00293   template<typename SA, typename ST,
00294            typename Auto_t, typename Trans_t,
00295            typename Exp>
00296   void
00297   do_partial_2(const AutomataBase<SA>&,
00298                const TransducerBase<ST>&,
00299                const Auto_t& a,
00300                const Trans_t& t,
00301                const hstate_t p,
00302                Exp& exp)
00303   {
00304     typedef typename Trans_t::value_t T;
00305     typedef typename output_projection_helper<ST, T>::ret    Auto_ret_t;
00306     typedef typename Auto_ret_t::set_t::series_set_t      Auto_ret_series_set_t;
00307 
00308     typename Auto_ret_t::set_t
00309       auto_structure(Auto_ret_series_set_t(t.structure().series().semiring()));
00310 
00311     Trans_t tt = t;
00312     tt.clear_initial();
00313     tt.set_initial(p);
00314 
00315     Trans_t tmp_trans(tt.structure());
00316     tmp_trans = extension(a, tt);
00317 
00318     Trans_t pro(t.structure());
00319     pro = trim(product(tmp_trans, tt));
00320     Auto_ret_t auto_p(auto_structure);
00321     auto_p = output_projection(pro);
00322 
00323     exp = aut_to_exp(auto_p);
00324   }
00325 
00326   template<typename SA, typename TA,
00327            typename ST, typename TT,
00328            typename Exp>
00329   void
00330   partial_2(const Element<SA, TA>& a,
00331             const Element<ST, TT>& t,
00332             const hstate_t p, Exp& exp)
00333   {
00334     do_partial_2(a.structure(), t.structure(), a, t, p, exp);
00335   }
00336 
00338 
00339   template<typename SA, typename ST,
00340            typename Auto_t, typename Trans_t,
00341            typename M>
00342   void
00343   do_partial_3(const AutomataBase<SA>&,
00344                const TransducerBase<ST>&,
00345                const Auto_t& a,
00346                const Trans_t& t,
00347                const hstate_t p,
00348                M& state_exp_pair_set)
00349   {
00350     Trans_t tt = t;
00351     tt.clear_initial();
00352     tt.set_initial(p);
00353     trim_here(tt);
00354     partial_1(a, tt, state_exp_pair_set);
00355   }
00356 
00357   template<typename SA, typename TA,
00358            typename ST, typename TT,
00359            typename M>
00360   void
00361   partial_3(const Element<SA, TA>& a,
00362             const Element<ST, TT>& t,
00363             const hstate_t p,
00364             M& state_exp_pair_set)
00365   {
00366     do_partial_3(a.structure(), t.structure(), a, t, p, state_exp_pair_set);
00367   }
00368 
00369 }
00370 
00371 #endif // ! VCSN_ALGORITHMS_EVALUATION_HXX

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