eps_removal_sp.hxx

00001 // eps_removal.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_EPS_REMOVAL_SP_HXX
00018 # define VCSN_ALGORITHMS_EPS_REMOVAL_SP_HXX
00019 
00020 # include <vaucanson/algorithms/eps_removal.hh>
00021 
00022 # include <vaucanson/automata/concept/automata_base.hh>
00023 # include <vaucanson/misc/usual_macros.hh>
00024 
00025 # include <boost/multi_index_container.hpp>
00026 # include <boost/multi_index/member.hpp>
00027 # include <boost/multi_index/hashed_index.hpp>
00028 # include <boost/multi_index/composite_key.hpp>
00029 # include <boost/functional/hash/hash.hpp>
00030 # include <boost/tuple/tuple.hpp>
00031 # include <vector>
00032 # include <queue>
00033 # include <map>
00034 # include <utility>
00035 # include <set>
00036 # include <stack>
00037 
00038 namespace vcsn {
00039 
00040   /*----------------------------------------.
00041   | EpsilonRemoverSp for weighted automaton |
00042   `----------------------------------------*/
00043 
00044   template
00045   <class A_, typename Auto, typename Weight>
00046   class EpsilonRemoverSp
00047   {
00048     AUTOMATON_TYPES(Auto);
00049   public:
00050     struct tr_t
00051     {
00052       tr_t(hstate_t src_, hstate_t dst_, series_set_elt_t series_)
00053           : src(src_),
00054             dst(dst_),
00055             series(series_)
00056       {}
00057 
00058       hstate_t src;
00059       hstate_t dst;
00060       series_set_elt_t series;
00061     };
00062 
00063     struct s_shortest
00064     {
00065       s_shortest(const hstate_t src_, const hstate_t dst_, semiring_elt_t& d_, semiring_elt_t& r_)
00066         : src(src_),
00067           dst(dst_),
00068           dist(d_),
00069           rel(r_)
00070       {}
00071 
00072       const hstate_t src;
00073       const hstate_t dst;
00074       semiring_elt_t dist;
00075       semiring_elt_t rel;
00076     };
00077 
00078     struct change_rel
00079     {
00080       change_rel(const semiring_elt_t& new_rel)
00081         : new_rel(new_rel)
00082       {}
00083 
00084       void operator() (s_shortest& s)
00085       {
00086         s.rel = new_rel;
00087       }
00088       private:
00089       semiring_elt_t new_rel;
00090     };
00091 
00092     struct change_dist
00093     {
00094       change_dist(const semiring_elt_t& new_dist)
00095         : new_dist(new_dist)
00096       {}
00097 
00098       void operator() (s_shortest& s)
00099       {
00100         s.dist = new_dist;
00101       }
00102       private:
00103       semiring_elt_t new_dist;
00104     };
00105 
00106     struct add_dr
00107     {
00108       add_dr(const semiring_elt_t& new_dist, const semiring_elt_t& new_rel)
00109         : new_dist(new_dist),
00110           new_rel(new_rel)
00111       {}
00112 
00113       void operator() (s_shortest& s)
00114       {
00115         s.dist += new_dist;
00116         s.rel += new_rel;
00117       }
00118       private:
00119       semiring_elt_t new_dist;
00120       semiring_elt_t new_rel;
00121     };
00122 
00123     typedef boost::multi_index_container
00124     <
00125       s_shortest,
00126       boost::multi_index::indexed_by
00127       <
00128         boost::multi_index::hashed_unique
00129         <
00130           boost::multi_index::composite_key
00131           <
00132             s_shortest,
00133             BOOST_MULTI_INDEX_MEMBER(s_shortest, const hstate_t, src),
00134             BOOST_MULTI_INDEX_MEMBER(s_shortest, const hstate_t, dst)
00135           >
00136         >
00137       >
00138     > s_shortest_hash;
00139 
00140     EpsilonRemoverSp(const AutomataBase<A_>&,
00141                      Auto& aut)
00142       : a(aut),
00143         null_series(aut.series().zero_),
00144         semiring_elt_zero(aut.series().semiring().wzero_),
00145         semiring_elt_one(aut.series().semiring().wone_),
00146         monoid_identity(aut.series().monoid().vcsn_empty)
00147     {
00148       shortest_eps_distance();
00149     }
00150 
00151     void operator() (misc::direction_type dir)
00152     {
00153       // Remove epsilon-transitions
00154       for_all_transitions(e,a)
00155       {
00156         series_set_elt_t t = a.series_of(*e);
00157         if (t.get(monoid_identity) != semiring_elt_zero)
00158         {
00159           t.assoc(monoid_identity.value(), semiring_elt_zero.value());
00160           if (t != null_series)
00161             a.add_series_transition(a.src_of(*e), a.dst_of(*e), t);
00162           a.del_transition(*e);
00163         }
00164       }
00165 
00166       if (dir == misc::backward)
00167         backward_remove();
00168       else
00169         forward_remove();
00170     }
00171 
00172   private:
00173     void shortest_eps_distance()
00174     {
00175       for_all_states(s, a)
00176       {
00177         typename s_shortest_hash::iterator it;
00178         shortest_hash.insert(s_shortest(*s, *s, semiring_elt_one, semiring_elt_one));
00179         squeue.insert(*s);
00180         while (!squeue.empty())
00181         {
00182           hstate_t curr = *squeue.begin();
00183           squeue.erase(squeue.begin());
00184           semiring_elt_t R = semiring_elt_zero;
00185           it = shortest_hash.find(boost::make_tuple(*s, curr));
00186           if (it != shortest_hash.end())
00187           {
00188             R = it->rel;
00189             shortest_hash.modify(it, change_rel(semiring_elt_zero));
00190           }
00191 
00192           std::list<htransition_t> transition_list;
00193           a.spontaneous_deltac(transition_list, curr, delta_kind::transitions());
00194           for_all_const_(std::list<htransition_t>, e, transition_list)
00195           {
00196             semiring_elt_t dist = semiring_elt_zero;
00197             it = shortest_hash.find(boost::make_tuple(*s, a.dst_of(*e)));
00198             if (it != shortest_hash.end())
00199               dist = it->dist;
00200             semiring_elt_t we = a.series_of(*e).get(monoid_identity);
00201             we = R * we;
00202             if (dist != dist +  we)
00203               if (it != shortest_hash.end())
00204               {
00205                 shortest_hash.modify(it, add_dr(we, we));
00206                 squeue.insert(a.dst_of(*e));
00207               }
00208               else
00209               {
00210                 shortest_hash.insert(s_shortest(*s, a.dst_of(*e), we, we));
00211                 squeue.insert(a.dst_of(*e));
00212               }
00213           }
00214          //it = shortest_hash.find(boost::make_tuple(*s, *s));
00215          //result_not_computable_if(!it->rel.starable());
00216         }
00217       }
00218     }
00219 
00220     void backward_remove()
00221     {
00222       std::stack<tr_t> tr_st;
00223       std::stack<std::pair<hstate_t, series_set_elt_t> > fin_st;
00224 
00225       std::list<htransition_t> transition_list;
00226       for_all_(s_shortest_hash, it, shortest_hash)
00227       {
00228         transition_list.clear();
00229         a.deltac(transition_list, it->dst, delta_kind::transitions());
00230         for_all_const_(std::list<htransition_t>, e, transition_list)
00231           tr_st.push(tr_t(it->src, a.dst_of(*e), it->dist * a.series_of(*e)));
00232         if (a.is_final(it->dst))
00233           fin_st.push(make_pair(it->src, it->dist * a.get_final(it->dst)));
00234       }
00235 
00236       while (!tr_st.empty())
00237       {
00238         a.add_series_transition(tr_st.top().src, tr_st.top().dst, tr_st.top().series);
00239         tr_st.pop();
00240       }
00241 
00242       while (!fin_st.empty())
00243       {
00244         a.set_final(fin_st.top().first, a.get_final(fin_st.top().first) +
00245                                              fin_st.top().second);
00246         fin_st.pop();
00247       }
00248     }
00249 
00250     void forward_remove()
00251     {
00252       std::stack<tr_t> tr_st;
00253       std::stack<std::pair<hstate_t, series_set_elt_t> > init_st;
00254 
00255       std::list<htransition_t> transition_list;
00256       for_all_(s_shortest_hash, it, shortest_hash)
00257       {
00258         transition_list.clear();
00259         a.rdeltac(transition_list, it->src, delta_kind::transitions());
00260         for_all_const_(std::list<htransition_t>, e, transition_list)
00261           tr_st.push(tr_t(a.src_of(*e), it->dst, a.series_of(*e) * it->dist));
00262         if (a.is_initial(it->src))
00263           init_st.push(make_pair(it->dst, a.get_initial(it->src) * it->dist));
00264       }
00265 
00266       while (!tr_st.empty())
00267       {
00268         a.add_series_transition(tr_st.top().src, tr_st.top().dst, tr_st.top().series);
00269         tr_st.pop();
00270       }
00271 
00272       while (!init_st.empty())
00273       {
00274         a.set_initial(init_st.top().first, a.get_initial(init_st.top().first) +
00275                                              init_st.top().second);
00276         init_st.pop();
00277       }
00278     }
00279 
00280     automaton_t&        a;
00281 
00282     // zero and identity of used algebraic structure.
00283     series_set_elt_t    null_series;
00284     semiring_elt_t      semiring_elt_zero;
00285     semiring_elt_t      semiring_elt_one;
00286     monoid_elt_t        monoid_identity;
00287 
00288     // Shortest distance structures
00289     s_shortest_hash     shortest_hash;
00290     std::set<hstate_t>  squeue;
00291   };
00292 
00293   /*--------------.
00294   | eps_removal.  |
00295   `--------------*/
00296 
00297   template<class A_, typename Auto, typename Weight>
00298   void
00299   do_eps_removal_here_sp(const AutomataBase<A_>& a_set,
00300                       const Weight&,
00301                       Auto& a,
00302                       misc::direction_type dir)
00303   {
00304     TIMER_SCOPED("eps_removal");
00305 
00306     EpsilonRemoverSp<A_, Auto, Weight> algo(a_set, a);
00307     algo(dir);
00308   }
00309 
00310   template<typename  A, typename  T>
00311   void
00312   eps_removal_here_sp(Element<A, T>& a, misc::direction_type dir)
00313   {
00314     typedef Element<A, T> auto_t;
00315     AUTOMATON_TYPES(auto_t);
00316 
00317     do_eps_removal_here_sp(a.structure(),
00318                            SELECT(semiring_elt_value_t),
00319                            a, dir);
00320   }
00321 
00322   template<typename  A, typename  T>
00323   Element<A, T>
00324   eps_removal_sp(const Element<A, T>& a, misc::direction_type dir)
00325   {
00326     typedef Element<A, T> auto_t;
00327     AUTOMATON_TYPES(auto_t);
00328 
00329     Element<A, T> ret(a);
00330     do_eps_removal_here_sp(ret.structure(),
00331                            SELECT(semiring_elt_value_t),
00332                            ret, dir);
00333     return ret;
00334   }
00335 
00336   template<typename  A, typename  T>
00337   void
00338   backward_eps_removal_here_sp(Element<A, T>& a)
00339   {
00340     typedef Element<A, T> auto_t;
00341     AUTOMATON_TYPES(auto_t);
00342 
00343     do_eps_removal_here_sp(a.structure(),
00344                            SELECT(semiring_elt_value_t),
00345                            a, misc::backward);
00346   }
00347 
00348   template<typename  A, typename  T>
00349   Element<A, T>
00350   backward_eps_removal_sp(const Element<A, T>& a)
00351   {
00352     typedef Element<A, T> auto_t;
00353     AUTOMATON_TYPES(auto_t);
00354 
00355     Element<A, T> ret(a);
00356     do_eps_removal_here_sp(ret.structure(),
00357                            SELECT(semiring_elt_value_t),
00358                            ret, misc::backward);
00359     return ret;
00360   }
00361 
00362   template<typename  A, typename  T>
00363   void
00364   forward_eps_removal_here_sp(Element<A, T>& a)
00365   {
00366     typedef Element<A, T> auto_t;
00367     AUTOMATON_TYPES(auto_t);
00368 
00369     do_eps_removal_here_sp(a.structure(),
00370                            SELECT(semiring_elt_value_t),
00371                            a, misc::forward);
00372   }
00373 
00374   template<typename  A, typename  T>
00375   Element<A, T>
00376   forward_eps_removal_sp(const Element<A, T>& a)
00377   {
00378     typedef Element<A, T> auto_t;
00379     AUTOMATON_TYPES(auto_t);
00380 
00381     Element<A, T> ret(a);
00382     do_eps_removal_here_sp(ret.structure(),
00383                            SELECT(semiring_elt_value_t),
00384                            ret, misc::forward);
00385     return ret;
00386   }
00387 
00388 } // vcsn
00389 
00390 #endif // ! VCSN_ALGORITHMS_EPS_REMOVAL_HXX

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