closure.hxx

00001 // closure.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2004 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_CLOSURE_HXX
00018 # define VCSN_ALGORITHMS_CLOSURE_HXX
00019 
00020 # include <vaucanson/algorithms/closure.hh>
00021 
00022 # include <vaucanson/automata/concept/automata_base.hh>
00023 # include <vaucanson/tools/usual_macros.hh>
00024 
00025 # include <vector>
00026 
00027 namespace vcsn {
00028 
00029   /*--------.
00030   | closure |
00031   `--------*/
00032   template <class A_, typename Auto>
00033   void
00034   do_closure_here(const AutomataBase<A_>&, Auto& a, bool bck_fwd)
00035   {
00036     // bck_fwd : true -> backward closure , false -> forward closure
00037     AUTOMATON_TYPES(Auto);
00038     typedef std::vector<std::vector<semiring_elt_t> >   matrix_semiring_elt_t;
00039     typedef std::vector<series_set_elt_t>               vector_series_t;
00040 
00041     series_set_elt_t    series_identity = a.series().zero_;
00042     semiring_elt_t      semiring_elt_zero = a.series().semiring().wzero_;
00043     monoid_elt_t        monoid_identity = a.series().monoid().empty_;
00044 
00045     int                   i, j, k, size = a.states().size();
00046 
00047     matrix_semiring_elt_t       m_semiring_elt (size);
00048 
00049     for (i = 0; i < size; i++)
00050       m_semiring_elt[i].resize(size, semiring_elt_zero);
00051 
00053     // Initialize converters between matrix index and states.
00054     std::vector<hstate_t>       index_to_state (size);
00055     std::map<hstate_t, int>     state_to_index;
00056     i = 0;
00057     for_each_state(s, a)
00058     {
00059       index_to_state[i] = *s;
00060       state_to_index[*s] = i++;
00061     }
00062 
00063     // Initialize the matrix m_semiring_elt
00064     // with the original automaton and delete epsilon-transitions
00065     for_each_state(s, a)
00066     {
00067       std::list<htransition_t>  transition_list;
00068       a.deltac(transition_list, *s, delta_kind::transitions());
00069 
00070       int origin = state_to_index[*s];
00071 
00072       for_each_const_(std::list<htransition_t>, e, transition_list)
00073       {
00074         int aim = state_to_index[a.dst_of(*e)];
00075         series_set_elt_t t = a.series_of(*e);
00076         m_semiring_elt[origin][aim] += t.get(monoid_identity);
00077         t.assoc(monoid_identity.value(), semiring_elt_zero.value());
00078         if(t != series_identity)
00079           a.add_series_transition(*s, a.dst_of(*e), t);
00080         a.del_transition(*e);
00081       }
00082     }
00083 
00084     // Compute star(m_semiring_elt) <--> epsilon-closure
00085     for (int r = 0; r < size; r++)
00086     {
00087       result_not_computable_if(!m_semiring_elt[r][r].starable());
00088 
00089       semiring_elt_t w = m_semiring_elt[r][r].star();
00090       m_semiring_elt[r][r] = w;
00091       for (i = 0; i < size; i++)
00092         if (i != r)
00093         {
00094           semiring_elt_t z = m_semiring_elt[i][r] * w;
00095           m_semiring_elt[i][r] = z;
00096           if(z != semiring_elt_zero)
00097             for (j = 0; j < size; j++)
00098               if(j != r)
00099                 m_semiring_elt[i][j] += z * m_semiring_elt[r][j];
00100         }
00101       for (j = 0; j < size; j++)
00102         if (j != r)
00103           m_semiring_elt[r][j] = w * m_semiring_elt[r][j];
00104     }
00105 
00106     if (bck_fwd)
00107     {
00108       // Backward_closure
00109       // Initialize the m_wfinal
00110       vector_series_t   m_wfinal (size, series_identity);
00111       for_each_final_state(p, a)
00112         m_wfinal[state_to_index[*p]] = a.get_final(*p);
00113       a.clear_final();
00114 
00115       // Compute the backward_closure
00116       for_each_state(s, a)
00117       {
00118         std::list<htransition_t> transition_list;
00119         a.rdeltac(transition_list, *s, delta_kind::transitions());
00120         int aim = state_to_index[*s];
00121         for_each_const_(std::list<htransition_t>, e, transition_list)
00122         {
00123           int origin = state_to_index[a.src_of(*e)];
00124           series_set_elt_t t = a.series_of(*e);
00125           for (k = 0; k < size; k++)
00126           {
00127             semiring_elt_t w = m_semiring_elt[k][origin];
00128             if (w != semiring_elt_zero)
00129               a.add_series_transition(index_to_state[k], *s, w * t);
00130           }
00131           a.del_transition(*e);
00132         }
00133         series_set_elt_t tw = series_identity;
00134         for (k = 0; k < size; k++)
00135           tw += m_semiring_elt[aim][k] * m_wfinal[k];
00136         if (tw != series_identity)
00137           a.set_final(*s, tw);
00138       }
00139     }
00140     else
00141     {
00142       // Forward closure
00143       // Initialize the m_wfinal
00144       vector_series_t   m_winitial (size, series_identity);
00145       for_each_initial_state(p, a)
00146         m_winitial[state_to_index[*p]] = a.get_initial(*p);
00147       a.clear_initial();
00148 
00149       // Compute the forward_closure
00150       for_each_state(s, a)
00151       {
00152         std::list<htransition_t> transition_list;
00153         a.deltac(transition_list, *s, delta_kind::transitions());
00154         int origin = state_to_index[*s];
00155         for_each_const_(std::list<htransition_t>, e, transition_list)
00156         {
00157           int aim = state_to_index[a.dst_of(*e)];
00158           series_set_elt_t t = a.series_of(*e);
00159           for (k = 0; k < size; k++)
00160           {
00161             semiring_elt_t w = m_semiring_elt[aim][k];
00162             if (w != semiring_elt_zero)
00163               a.add_series_transition(*s, index_to_state[k], t * w);
00164           }
00165           a.del_transition(*e);
00166         }
00167         series_set_elt_t tw = series_identity;
00168         for (k = 0; k < size; k++)
00169           tw += m_winitial[k] * m_semiring_elt[k][origin];
00170         if (tw != series_identity)
00171           a.set_initial(*s, tw);
00172       }
00173     }
00174   }
00175 
00176   template<typename  A, typename  T>
00177   void
00178   closure_here(Element<A, T>& a, bool bck)
00179   {
00180     do_closure_here(a.structure(), a, bck);
00181   }
00182 
00183   template<typename  A, typename  T>
00184   Element<A, T>
00185   closure(const Element<A, T>& a, bool bck)
00186   {
00187     Element<A, T> ret(a);
00188     do_closure_here(ret.structure(), ret, bck);
00189     return ret;
00190   }
00191 
00192   template<typename  A, typename  T>
00193   void
00194   backward_closure_here(Element<A, T>& a)
00195   {
00196     do_closure_here(a.structure(), a, true);
00197   }
00198 
00199   template<typename  A, typename  T>
00200   Element<A, T>
00201   backward_closure(const Element<A, T>& a)
00202   {
00203     Element<A, T> ret(a);
00204     do_closure_here(ret.structure(), ret, true);
00205     return ret;
00206   }
00207 
00208   template<typename  A, typename  T>
00209   void
00210   forward_closure_here(Element<A, T>& a)
00211   {
00212     do_closure_here(a.structure(), a, false);
00213   }
00214 
00215   template<typename  A, typename  T>
00216   Element<A, T>
00217   forward_closure(const Element<A, T>& a)
00218   {
00219     Element<A, T> ret(a);
00220     do_closure_here(ret.structure(), ret, false);
00221     return ret;
00222   }
00223 
00224 } // vcsn
00225 
00226 #endif // ! VCSN_ALGORITHMS_CLOSURE_HXX

Generated on Fri Jul 28 12:18:30 2006 for Vaucanson by  doxygen 1.4.6