eps_removal.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_HXX
00018 # define VCSN_ALGORITHMS_EPS_REMOVAL_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 <vector>
00026 # include <queue>
00027 # include <map>
00028 # include <utility>
00029 
00030 namespace vcsn {
00031 
00032   /*--------------------------------------.
00033   | EpsilonRemover for weighted automaton |
00034   `--------------------------------------*/
00035 
00036   template
00037   <class A_, typename Auto, typename Weight>
00038   class EpsilonRemover
00039   {
00040     AUTOMATON_TYPES(Auto);
00041     typedef std::vector<std::vector<semiring_elt_t> >   matrix_semiring_elt_t;
00042     typedef std::vector<series_set_elt_t>               vector_series_t;
00043 
00044   public:
00045     EpsilonRemover(const AutomataBase<A_>&,
00046                    Auto& aut)
00047       : a(aut),
00048         size(aut.states().size()),
00049         null_series(aut.series().zero_),
00050         semiring_elt_zero(aut.series().semiring().wzero_),
00051         monoid_identity(aut.series().monoid().vcsn_empty)
00052     {
00053 
00055       // Initialize converters between matrix index and states.
00056       index_to_state.resize(size);
00057       int i = 0;
00058       for_all_states(s, a)
00059       {
00060         index_to_state[i] = *s;
00061         state_to_index[*s] = i++;
00062       }
00063 
00064       // Initialize m_semiring_elt matrix with epsilon transitions,
00065       // and suppress them.
00066       m_semiring_elt.resize(size);
00067       for (int i = 0; i < size; i++)
00068         m_semiring_elt[i].resize(size, semiring_elt_zero);
00069 
00070       for_all_states(s, a)
00071       {
00072         std::list<htransition_t>        transition_list;
00073         int src = state_to_index[*s];
00074 
00075         a.deltac(transition_list, *s, delta_kind::transitions());
00076         for_all_const_(std::list<htransition_t>, e, transition_list)
00077         {
00078           int dst = state_to_index[a.dst_of(*e)];
00079           series_set_elt_t t = a.series_of(*e);
00080 
00081           m_semiring_elt[src][dst] += t.get(monoid_identity);
00082           t.assoc(monoid_identity.value(), semiring_elt_zero.value());
00083           if(t != null_series)
00084             a.add_series_transition(*s, a.dst_of(*e), t);
00085           a.del_transition(*e);
00086         }
00087       }
00088     }
00089 
00090     void operator() (misc::direction_type dir)
00091     {
00092       star_matrix();
00093       if (dir == misc::backward)
00094         backward_remove();
00095       else
00096         forward_remove();
00097     }
00098 
00099   private:
00100     // Compute the star of the matrix,
00101     // it's equivalent to a transitive closure.
00102     void star_matrix()
00103     {
00104       for (int r = 0; r < size; r++)
00105       {
00106         result_not_computable_if(!m_semiring_elt[r][r].starable());
00107 
00108         semiring_elt_t w = m_semiring_elt[r][r].star();
00109         m_semiring_elt[r][r] = w;
00110         for (int i = 0; i < size; i++)
00111           if (i != r)
00112           {
00113             semiring_elt_t z = m_semiring_elt[i][r] * w;
00114             m_semiring_elt[i][r] = z;
00115             if(z != semiring_elt_zero)
00116               for (int j = 0; j < size; j++)
00117                 if (j != r)
00118                   m_semiring_elt[i][j] += z * m_semiring_elt[r][j];
00119           }
00120         for (int j = 0; j < size; j++)
00121           if (j != r)
00122             m_semiring_elt[r][j] = w * m_semiring_elt[r][j];
00123       }
00124     }
00125 
00126     void backward_remove()
00127     {
00128       // Backward_eps_removal
00129       // Initialize the m_wfinal
00130       vector_series_t   m_wfinal (size, null_series);
00131       for_all_final_states(p, a)
00132         m_wfinal[state_to_index[*p]] = a.get_final(*p);
00133       a.clear_final();
00134 
00135       // Compute the backward_eps_removal
00136       for_all_states(s, a)
00137       {
00138         std::list<htransition_t> transition_list;
00139         a.rdeltac(transition_list, *s, delta_kind::transitions());
00140         int dst = state_to_index[*s];
00141         for_all_const_(std::list<htransition_t>, e, transition_list)
00142         {
00143           int src = state_to_index[a.src_of(*e)];
00144           series_set_elt_t t = a.series_of(*e);
00145           for (int k = 0; k < size; k++)
00146           {
00147             semiring_elt_t w = m_semiring_elt[k][src];
00148             if (w != semiring_elt_zero)
00149               a.add_series_transition(index_to_state[k], *s, w * t);
00150           }
00151           a.del_transition(*e);
00152         }
00153         series_set_elt_t tw = null_series;
00154         for (int k = 0; k < size; k++)
00155           tw += m_semiring_elt[dst][k] * m_wfinal[k];
00156         if (tw != null_series)
00157           a.set_final(*s, tw);
00158       }
00159     }
00160 
00161     void forward_remove()
00162     {
00163       // Forward eps_removal
00164       // Initialize the m_wfinal
00165       vector_series_t   m_winitial (size, null_series);
00166       for_all_initial_states(p, a)
00167         m_winitial[state_to_index[*p]] = a.get_initial(*p);
00168       a.clear_initial();
00169 
00170       // Compute the forward_eps_removal
00171       for_all_states(s, a)
00172       {
00173         std::list<htransition_t> transition_list;
00174         a.deltac(transition_list, *s, delta_kind::transitions());
00175         int src = state_to_index[*s];
00176         for_all_const_(std::list<htransition_t>, e, transition_list)
00177         {
00178           int dst = state_to_index[a.dst_of(*e)];
00179           series_set_elt_t t = a.series_of(*e);
00180           for (int k = 0; k < size; k++)
00181           {
00182             semiring_elt_t w = m_semiring_elt[dst][k];
00183             if (w != semiring_elt_zero)
00184               a.add_series_transition(*s, index_to_state[k], t * w);
00185           }
00186           a.del_transition(*e);
00187         }
00188         series_set_elt_t tw = null_series;
00189         for (int k = 0; k < size; k++)
00190           tw += m_winitial[k] * m_semiring_elt[k][src];
00191         if (tw != null_series)
00192           a.set_initial(*s, tw);
00193       }
00194     }
00195 
00196 
00197     automaton_t&        a;
00198     // Number of states in a.
00199     // Use as the dimension of the matrix m_semiring_elt.
00200     int                 size;
00201 
00202     // zero and identity of used algebraic structure.
00203     series_set_elt_t    null_series;
00204     semiring_elt_t      semiring_elt_zero;
00205     monoid_elt_t        monoid_identity;
00206 
00207     // Matrix of epsilon transition.
00208     matrix_semiring_elt_t       m_semiring_elt;
00209 
00210     // Maps between states and matrix indexes.
00211     std::vector<hstate_t>       index_to_state;
00212     std::map<hstate_t, int>     state_to_index;
00213   };
00214 
00215 
00216   /*----------------------------------------------------.
00217   | Find a transition (src, label, dst), using deltaf.  |
00218   `----------------------------------------------------*/
00219 
00220   template <typename Auto>
00221   class Finder
00222   {
00223     AUTOMATON_TYPES(Auto);
00224 
00225   public:
00226     Finder (const automaton_t& aut)
00227       : a_(aut)
00228     {
00229       for_all_transitions(t, a_)
00230         map_[make_pair(a_.src_of(*t), make_pair(a_.label_of(*t),
00231                                                 a_.dst_of(*t)))] = true;
00232     }
00233 
00234     void insert(const hstate_t src, const label_t l, const hstate_t dst)
00235     {
00236       map_[make_pair(src, make_pair(l, dst))] = true;
00237     }
00238 
00239     bool operator() (const hstate_t src, const label_t l, const hstate_t dst)
00240     {
00241       return map_[make_pair(src, make_pair(l, dst))];
00242     }
00243 
00244   private:
00245     const automaton_t& a_;
00246     std::map<std::pair<hstate_t, std::pair<label_t, hstate_t> >, bool> map_;
00247   };
00248 
00249 
00250 
00251   /*------------------------------------------------------.
00252   | EpsilonRemover for automaton with multiplicity in B.  |
00253   `------------------------------------------------------*/
00254 
00255   template <class A_, typename Auto>
00256   class EpsilonRemover<A_, Auto, bool>
00257   {
00258     AUTOMATON_TYPES(Auto);
00259     typedef std::vector<std::vector<semiring_elt_t> >   matrix_semiring_elt_t;
00260     typedef std::vector<series_set_elt_t>               vector_series_t;
00261     typedef std::queue<htransition_t>                   tr_queue_t;
00262     typedef std::queue<hstate_t>                        state_queue_t;
00263     typedef std::vector<htransition_t>                  ctransitions_t;
00264     typedef std::vector<hstate_t>                       cstates_t;
00265 
00266   public:
00267     EpsilonRemover(const AutomataBase<A_>&,
00268                    Auto& aut)
00269       : a(aut),
00270         null_series(aut.series().zero_),
00271         semiring_elt_zero(aut.series().semiring().wzero_),
00272         monoid_identity(aut.series().monoid().vcsn_empty)
00273     {
00274       for_all_transitions(t, a)
00275         tr_q.push(*t);
00276     }
00277 
00278     void operator() (misc::direction_type dir)
00279     {
00280       if (dir == misc::forward)
00281         forward_closure();
00282       else
00283         backward_closure();
00284       suppress_epsilon_transitions();
00285     }
00286 
00287     void suppress_epsilon_transitions ()
00288     {
00289       for_all_transitions(t, a)
00290       {
00291         series_set_elt_t s = a.series_of(*t);
00292         if (s.get(monoid_identity) == semiring_elt_zero)
00293           continue;
00294 
00295         s.assoc(monoid_identity.value(), semiring_elt_zero.value());
00296         if (s != null_series)
00297           a.add_series_transition(a.src_of(*t), a.dst_of(*t), s);
00298         a.del_transition(*t);
00299       }
00300     }
00301 
00302     void forward_closure ()
00303     {
00304       // Closure.
00305       Finder<automaton_t> find(a);
00306       cstates_t st_out;
00307 
00308       while (!tr_q.empty())
00309       {
00310         htransition_t t = tr_q.front();
00311         hstate_t src = a.src_of(t);
00312         hstate_t mid = a.dst_of(t);
00313         label_t l = a.label_of(t);
00314 
00315         st_out.clear();
00316         a.spontaneous_deltac(st_out, mid, delta_kind::states());
00317         for_all_const(cstates_t, dst, st_out)
00318         {
00319           if (!find(src, l, *dst))
00320           {
00321             htransition_t new_tr = a.add_transition(src, *dst, l);
00322             tr_q.push(new_tr);
00323             find.insert(src, l, *dst);
00324           }
00325         }
00326         tr_q.pop();
00327       }
00328       // Set initial state.
00329       state_queue_t sq;
00330 
00331       for_all_initial_states(s, a)
00332         sq.push(*s);
00333       while (!sq.empty())
00334       {
00335         hstate_t i = sq.front();
00336 
00337         st_out.clear();
00338         a.spontaneous_deltac(st_out, i, delta_kind::states());
00339         for_all_const(cstates_t, s, st_out)
00340         {
00341           if (!a.is_initial(*s))
00342           {
00343             a.set_initial(*s);
00344             sq.push(*s);
00345           }
00346         }
00347         sq.pop();
00348       }
00349     }
00350 
00351     void backward_closure ()
00352     {
00353       // Closure.
00354       Finder<automaton_t> find(a);
00355       cstates_t st_in;
00356 
00357       while (!tr_q.empty())
00358       {
00359         htransition_t t = tr_q.front();
00360         hstate_t mid = a.src_of(t);
00361         hstate_t dst = a.dst_of(t);
00362         label_t l = a.label_of(t);
00363 
00364         st_in.clear();
00365         a.spontaneous_rdeltac(st_in, mid, delta_kind::states());
00366         for_all_const(cstates_t, src, st_in)
00367         {
00368           if (!find(*src, l, dst))
00369           {
00370             htransition_t new_tr = a.add_transition(*src, dst, l);
00371             tr_q.push(new_tr);
00372             find.insert(*src, l, dst);
00373           }
00374         }
00375         tr_q.pop();
00376       }
00377       // Set final state.
00378       state_queue_t sq;
00379 
00380       for_all_final_states(s, a)
00381         sq.push(*s);
00382       while (!sq.empty())
00383       {
00384         hstate_t i = sq.front();
00385 
00386         st_in.clear();
00387         a.spontaneous_rdeltac(st_in, i, delta_kind::states());
00388         for_all_const(cstates_t, s, st_in)
00389         {
00390           if (!a.is_final(*s))
00391           {
00392             a.set_final(*s);
00393             sq.push(*s);
00394           }
00395         }
00396         sq.pop();
00397       }
00398     }
00399 
00400   private:
00401     automaton_t&        a;
00402 
00403     // zero and identity of used algebraic structure.
00404     const series_set_elt_t      null_series;
00405     const semiring_elt_t        semiring_elt_zero;
00406     const monoid_elt_t          monoid_identity;
00407 
00408     // Queue of transitions.
00409     tr_queue_t          tr_q;
00410   };
00411 
00412 
00413   /*--------------.
00414   | eps_removal.  |
00415   `--------------*/
00416 
00417   template<class A_, typename Auto, typename Weight>
00418   void
00419   do_eps_removal_here(const AutomataBase<A_>& a_set,
00420                       const Weight&,
00421                       Auto& a,
00422                       misc::direction_type dir)
00423   {
00424     TIMER_SCOPED("eps_removal");
00425 
00426     EpsilonRemover<A_, Auto, Weight> algo(a_set, a);
00427     algo(dir);
00428   }
00429 
00430   template<typename  A, typename  T>
00431   void
00432   eps_removal_here(Element<A, T>& a, misc::direction_type dir)
00433   {
00434     typedef Element<A, T> auto_t;
00435     AUTOMATON_TYPES(auto_t);
00436 
00437     do_eps_removal_here(a.structure(),
00438                         SELECT(semiring_elt_value_t),
00439                         a, dir);
00440   }
00441 
00442   template<typename  A, typename  T>
00443   Element<A, T>
00444   eps_removal(const Element<A, T>& a, misc::direction_type dir)
00445   {
00446     typedef Element<A, T> auto_t;
00447     AUTOMATON_TYPES(auto_t);
00448 
00449     Element<A, T> ret(a);
00450     do_eps_removal_here(ret.structure(),
00451                         SELECT(semiring_elt_value_t),
00452                         ret, dir);
00453     return ret;
00454   }
00455 
00456   template<typename  A, typename  T>
00457   void
00458   backward_eps_removal_here(Element<A, T>& a)
00459   {
00460     typedef Element<A, T> auto_t;
00461     AUTOMATON_TYPES(auto_t);
00462 
00463     do_eps_removal_here(a.structure(),
00464                         SELECT(semiring_elt_value_t),
00465                         a, misc::backward);
00466   }
00467 
00468   template<typename  A, typename  T>
00469   Element<A, T>
00470   backward_eps_removal(const Element<A, T>& a)
00471   {
00472     typedef Element<A, T> auto_t;
00473     AUTOMATON_TYPES(auto_t);
00474 
00475     Element<A, T> ret(a);
00476     do_eps_removal_here(ret.structure(),
00477                         SELECT(semiring_elt_value_t),
00478                         ret, misc::backward);
00479     return ret;
00480   }
00481 
00482   template<typename  A, typename  T>
00483   void
00484   forward_eps_removal_here(Element<A, T>& a)
00485   {
00486     typedef Element<A, T> auto_t;
00487     AUTOMATON_TYPES(auto_t);
00488 
00489     do_eps_removal_here(a.structure(),
00490                         SELECT(semiring_elt_value_t),
00491                         a, misc::forward);
00492   }
00493 
00494   template<typename  A, typename  T>
00495   Element<A, T>
00496   forward_eps_removal(const Element<A, T>& a)
00497   {
00498     typedef Element<A, T> auto_t;
00499     AUTOMATON_TYPES(auto_t);
00500 
00501     Element<A, T> ret(a);
00502     do_eps_removal_here(ret.structure(),
00503                         SELECT(semiring_elt_value_t),
00504                         ret, misc::forward);
00505     return ret;
00506   }
00507 
00508 } // vcsn
00509 
00510 #endif // ! VCSN_ALGORITHMS_EPS_REMOVAL_HXX

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