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

Generated on Wed Jun 13 17:00:21 2007 for Vaucanson by  doxygen 1.5.1