normalized_composition.hxx

Go to the documentation of this file.
00001 // normalized_composition.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 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_NORMALIZED_COMPOSITION_HXX
00018 # define VCSN_ALGORITHMS_NORMALIZED_COMPOSITION_HXX
00019 
00033 # include <set>
00034 # include <queue>
00035 # include <vaucanson/algorithms/normalized_composition.hh>
00036 # include <vaucanson/algorithms/internal/outsplitting.hh>
00037 # include <vaucanson/algebra/concept/freemonoid_product.hh>
00038 # include <vaucanson/algebra/implementation/series/series.hh>
00039 # include <vaucanson/automata/concept/automata.hh>
00040 
00041 
00042 namespace vcsn {
00043 
00044   template <typename S, typename M1, typename M2, typename lhs_t,
00045             typename rhs_t, typename res_t>
00046   struct composer
00047   {
00049     typedef std::pair<hstate_t, hstate_t>       pair_hstate_t;
00051     typedef std::map<pair_hstate_t, hstate_t>   visited_t;
00053     typedef std::map<hstate_t, pair_hstate_t >  map_of_states_t;
00055     typedef std::queue<pair_hstate_t>           to_process_t;
00056 
00057     AUTOMATON_TYPES(res_t);
00058     AUTOMATON_TYPES_(lhs_t, lhs_);
00059     AUTOMATON_TYPES_(rhs_t, rhs_);
00060 
00061     typedef std::set<htransition_t>                     delta_ret_t;
00062     typedef typename series_set_elt_t::support_t        support_t;
00063     typedef typename lhs_series_set_elt_t::support_t    lhs_support_t;
00064     typedef typename rhs_series_set_elt_t::support_t    rhs_support_t;
00065 
00066     typedef typename lhs_monoid_t::first_monoid_t
00067     lhs_first_monoid_t;
00068     typedef typename lhs_monoid_elt_value_t::first_type
00069     lhs_first_monoid_elt_value_t;
00070     typedef Element<lhs_first_monoid_t, lhs_first_monoid_elt_value_t>
00071     lhs_first_monoid_elt_t;
00072 
00073     typedef typename rhs_monoid_t::first_monoid_t
00074     rhs_first_monoid_t;
00075     typedef typename rhs_monoid_elt_value_t::first_type
00076     rhs_first_monoid_elt_value_t;
00077     typedef Element<rhs_first_monoid_t, rhs_first_monoid_elt_value_t>
00078     rhs_first_monoid_elt_t;
00079 
00080     typedef typename lhs_monoid_t::second_monoid_t
00081     lhs_second_monoid_t;
00082     typedef typename lhs_monoid_elt_value_t::second_type
00083     lhs_second_monoid_elt_value_t;
00084     typedef Element<lhs_second_monoid_t, lhs_second_monoid_elt_value_t>
00085     lhs_second_monoid_elt_t;
00086 
00087     typedef typename rhs_monoid_t::second_monoid_t
00088     rhs_second_monoid_t;
00089     typedef typename rhs_monoid_elt_value_t::second_type
00090     rhs_second_monoid_elt_value_t;
00091     typedef Element<rhs_second_monoid_t, rhs_second_monoid_elt_value_t>
00092     rhs_second_monoid_elt_t;
00093 
00094     visited_t visited;
00095     to_process_t to_process;
00096     map_of_states_t m;
00097 
00098     const lhs_t&                 lhs;
00099     const rhs_t&                 rhs;
00100     res_t&                       output;
00101     std::set<hstate_t>&          lhs_black_states;
00102     std::set<hstate_t>&          rhs_black_states;
00103 
00104     const series_set_t& series;
00105     const monoid_t&     monoid;
00106 
00107     const lhs_series_set_t&     lhs_series;
00108     const lhs_monoid_t&         lhs_monoid;
00109 
00110     const rhs_series_set_t&     rhs_series;
00111     const rhs_monoid_t&         rhs_monoid;
00112 
00113     lhs_first_monoid_elt_t lhs_first_identity;
00114     rhs_first_monoid_elt_t rhs_first_identity;
00115     lhs_second_monoid_elt_t lhs_second_identity;
00116     rhs_second_monoid_elt_t rhs_second_identity;
00117 
00118     composer (const AutomataBase<S>&,
00119               const algebra::FreeMonoidProduct<M1, M2>&,
00120               const lhs_t&                 aLhs,
00121               const rhs_t&                 aRhs,
00122               res_t&                       aOutput,
00123               std::set<hstate_t>&          aLhs_states,
00124               std::set<hstate_t>&          aRhs_states)
00125       : lhs (aLhs),
00126         rhs (aRhs),
00127         output (aOutput),
00128         lhs_black_states (aLhs_states),
00129         rhs_black_states (aRhs_states),
00130 
00131         series (output.structure().series()),
00132         monoid (series.monoid()),
00133 
00134         lhs_series (lhs.structure().series()),
00135         lhs_monoid (lhs_series.monoid()),
00136 
00137         rhs_series (rhs.structure().series()),
00138         rhs_monoid (rhs_series.monoid()),
00139 
00140         lhs_first_identity (algebra::identity_as<lhs_first_monoid_elt_value_t>::
00141                             of(lhs_monoid.first_monoid())),
00142         rhs_first_identity (algebra::identity_as<rhs_first_monoid_elt_value_t>::
00143                             of(rhs_monoid.first_monoid())),
00144         lhs_second_identity (algebra::identity_as<lhs_second_monoid_elt_value_t>::
00145                              of(lhs_monoid.second_monoid())),
00146         rhs_second_identity (algebra::identity_as<rhs_second_monoid_elt_value_t>::
00147                              of(rhs_monoid.second_monoid()))
00148     {
00149     }
00150 
00151     // - Add a transition between current_state and the state
00152     //   corresponding to the pair (from,to).
00153     // - If the state (from,to) does not exist, then it is created.
00154     // - The transition is labelled by prod_series.
00155     void
00156     add_transition(const hstate_t current_state,
00157                    const hstate_t from,
00158                    const hstate_t to,
00159                    typename res_t::series_set_elt_t& prod_series)
00160     {
00161       if (lhs_black_states.find(from) == lhs_black_states.end()
00162           or rhs_black_states.find(to) == rhs_black_states.end())
00163         {
00164           const pair_hstate_t new_pair (from, to);
00165 
00166           typename visited_t::const_iterator found =
00167             visited.find(new_pair);
00168           hstate_t dst;
00169           if (found == visited.end())
00170             {
00171               dst = output.add_state();
00172               visited[new_pair] = dst;
00173               m[dst] = new_pair;
00174               to_process.push(new_pair);
00175             }
00176           else
00177             dst = found->second;
00178           output.add_series_transition(current_state, dst, prod_series);
00179         }
00180     }
00181 
00182     typename res_t::series_set_elt_t
00183     series_product (typename monoid_elt_value_t::first_type l1,
00184                     typename monoid_elt_value_t::second_type l2,
00185                     semiring_elt_t w)
00186     {
00187       typename res_t::series_set_elt_t res (series);
00188       const monoid_elt_value_t word (l1, l2);
00189       res.assoc(word, w.value());
00190       return res;
00191     }
00192 
00193 
00194     // Compute the series for an initial or a final state, on the
00195     // empty word.
00196     typename res_t::series_set_elt_t
00197     state_series (lhs_series_set_elt_t l,
00198                   rhs_series_set_elt_t r)
00199     {
00200       series_set_elt_t res(series);
00201       res.assoc(monoid_elt_t(monoid,
00202                              algebra::identity_as<monoid_elt_value_t>::
00203                              of(monoid).value()),
00204                 l.get(*l.supp().begin()) * r.get(*r.supp().begin()));
00205       return res;
00206     }
00207 
00208     void process_one_pair (const hstate_t current_state,
00209                            const hstate_t lhs_s, const hstate_t rhs_s)
00210     {
00211 
00212       if (lhs.is_initial(lhs_s) and rhs.is_initial(rhs_s))
00213         output.set_initial(current_state,
00214                            state_series (lhs.get_initial(lhs_s),
00215                                          rhs.get_initial(rhs_s)));
00216 
00217       if (lhs.is_final(lhs_s) and rhs.is_final(rhs_s))
00218         output.set_final(current_state,
00219                          state_series (lhs.get_final(lhs_s),
00220                                        rhs.get_final(rhs_s)));
00221 
00222       delta_ret_t transition_lhs;
00223       delta_ret_t transition_rhs;
00224       lhs.deltac(transition_lhs, lhs_s, delta_kind::transitions());
00225       rhs.deltac(transition_rhs, rhs_s, delta_kind::transitions());
00226 
00227       for_all_const_(delta_ret_t, l, transition_lhs)
00228         {
00229           const lhs_series_set_elt_t left_series = lhs.series_of(*l);
00230           const lhs_monoid_elt_t left_supp_elt (lhs_monoid,
00231                                                 *left_series.supp().begin());
00232 
00233           // (i)
00234           // If the outgoing transition is of type (*, 1).
00235           if (left_supp_elt.value().second == lhs_second_identity.value())
00236             {
00237               series_set_elt_t s =
00238                 series_product (left_supp_elt.value().first,
00239                                 rhs_second_identity.value(),
00240                                 left_series.get(left_supp_elt));
00241               add_transition (current_state,
00242                               lhs.dst_of(*l), rhs_s, s);
00243             }
00244           // (iii')
00245           else
00246             {
00247               for_all_const_(delta_ret_t, r, transition_rhs)
00248                 {
00249                   const rhs_series_set_elt_t right_series =
00250                     rhs.series_of(*r);
00251                   const rhs_monoid_elt_t right_supp_elt
00252                     (rhs_monoid, *right_series.supp().begin());
00253 
00254                   // If the incoming transition is not of type (1, *).
00255                   if (right_supp_elt.value().first !=
00256                       rhs_first_identity.value())
00257                     //  we try to connect a transition of lhs and
00258                     // a transition of rhs.
00259                     if (left_supp_elt.value().second ==
00260                         right_supp_elt.value().first)
00261                       {
00262                         series_set_elt_t s =
00263                           series_product (left_supp_elt.value().first,
00264                                           right_supp_elt.value().second,
00265                                           left_series.get(left_supp_elt)
00266                                           * right_series.get(right_supp_elt));
00267                         add_transition
00268                           (current_state,
00269                            lhs.dst_of(*l), rhs.dst_of(*r),
00270                            s);
00271                       }
00272                 }
00273             }
00274         }
00275 
00276       for_all_const_(delta_ret_t, r, transition_rhs)
00277         {
00278           const rhs_series_set_elt_t right_series = rhs.series_of(*r);
00279           const rhs_monoid_elt_t right_supp_elt (rhs_monoid,
00280                                                  *right_series.supp().begin());
00281 
00282           // (ii)
00283           if (right_supp_elt.value().first == rhs_first_identity.value())
00284             {
00285               series_set_elt_t s =
00286                 series_product (lhs_first_identity.value(),
00287                                 right_supp_elt.value().second,
00288                                 right_series.get(right_supp_elt));
00289               add_transition (current_state,
00290                               lhs_s, rhs.dst_of(*r), s);
00291             }
00292         }
00293 
00294     }
00295 
00296 
00297     void operator() ()
00298     {
00299 
00300       /*----------------------------------.
00301       | Get initial states of the product |
00302       `----------------------------------*/
00303       for_all_initial_states(lhs_s, lhs)
00304         for_all_initial_states(rhs_s, rhs)
00305         {
00306           if (lhs_black_states.find(*lhs_s) == lhs_black_states.end() or
00307               rhs_black_states.find(*rhs_s) == rhs_black_states.end())
00308             {
00309               const hstate_t    new_state = output.add_state();
00310               const pair_hstate_t       new_pair (*lhs_s, *rhs_s);
00311 
00312               m[new_state] = new_pair;
00313               visited[new_pair] = new_state;
00314               to_process.push(new_pair);
00315             }
00316         }
00317 
00318       /*-----------.
00319       | Processing |
00320       `-----------*/
00321       while (not to_process.empty())
00322         {
00323           const pair_hstate_t p = to_process.front();
00324           to_process.pop();
00325           process_one_pair (visited[p], p.first, p.second);
00326         }
00327     }
00328   };
00329 
00330 
00331 
00334   template <typename S, typename M1, typename M2, typename lhs_t,
00335             typename rhs_t, typename res_t>
00336   void
00337   do_compose(const AutomataBase<S>&,
00338              const algebra::FreeMonoidProduct<M1, M2>&,
00339              const lhs_t& lhs,
00340              const rhs_t& rhs,
00341              res_t& ret)
00342   {
00343     AUTOMATON_TYPES(res_t);
00344 
00345     typedef std::set<hstate_t>                  set_of_states_t;
00346     set_of_states_t lhs_states;
00347     set_of_states_t rhs_states;
00348 
00349     composer<S, M1, M2, lhs_t, rhs_t, res_t>
00350       compose (ret.structure(), ret.structure().series().monoid(),
00351                lhs, rhs, ret, lhs_states, rhs_states);
00352     compose ();
00353   }
00354 
00357   template <typename S, typename M1, typename M2, typename lhs_t,
00358             typename rhs_t, typename res_t>
00359   void
00360   do_u_compose(const AutomataBase<S>&,
00361                const algebra::FreeMonoidProduct<M1, M2>&,
00362                const lhs_t& lhs,
00363                const rhs_t& rhs,
00364                res_t& ret)
00365   {
00366     AUTOMATON_TYPES(res_t);
00367 
00368     typedef std::set<hstate_t>                  set_of_states_t;
00369     set_of_states_t lhs_states;
00370     set_of_states_t rhs_states;
00371 
00372     lhs_t lhs_cov = splitting::outsplitting(lhs, lhs_states);
00373     rhs_t rhs_cov = splitting::insplitting(rhs, rhs_states);
00374 
00375     composer<S, M1, M2, lhs_t, rhs_t, res_t>
00376       compose (ret.structure(), ret.structure().series().monoid(),
00377                lhs_cov, rhs_cov, ret, lhs_states, rhs_states);
00378     compose ();
00379 
00380     eps_removal_here (ret);
00381     sub_automaton_here (ret, useful_states (ret));
00382   }
00383 
00384 
00385 
00386   // Compose dispatchers
00387   template <typename S, typename M1, typename M2, typename lhs_t,
00388             typename rhs_t, typename res_t>
00389   void
00390   do_compose_dispatcher(const AutomataBase<S>&,
00391                         const algebra::FreeMonoidProduct<M1, M2>&,
00392                         SELECTOR(bool),
00393                         const lhs_t& lhs,
00394                         const rhs_t& rhs,
00395                         res_t& ret)
00396   {
00397     do_compose (ret.structure(),
00398                 ret.structure().series().monoid(),
00399                 lhs, rhs, ret);
00400   }
00401 
00402 
00403   template <typename S, typename M1, typename M2, typename lhs_t,
00404             typename rhs_t, typename res_t, typename weight_t>
00405   void
00406   do_compose_dispatcher(const AutomataBase<S>&,
00407                         const algebra::FreeMonoidProduct<M1, M2>&,
00408                         const weight_t&,
00409                         const lhs_t& lhs,
00410                         const rhs_t& rhs,
00411                         res_t& ret)
00412   {
00413     do_u_compose (ret.structure(),
00414                   ret.structure().series().monoid(),
00415                   lhs, rhs, ret);
00416   }
00417 
00418   // Facade for compose
00419 
00420   template <typename S, typename T>
00421   void
00422   compose(const Element<S, T>& lhs,
00423           const Element<S, T>& rhs,
00424           Element<S, T>& ret)
00425   {
00426     typedef Element<S, T> auto_t;
00427     AUTOMATON_TYPES(auto_t);
00428 
00429     for_all_states (s, ret)
00430       ret.del_state (*s);
00431 
00432     do_compose_dispatcher (ret.structure(),
00433                            ret.structure().series().monoid(),
00434                            SELECT(semiring_elt_value_t),
00435                            lhs, rhs, ret);
00436   }
00437 
00438 
00439 
00440   template <typename S, typename T>
00441   Element<S, T>
00442   compose(const Element<S, T>& lhs,
00443           const Element<S, T>& rhs)
00444   {
00445     typedef Element<S, T> auto_t;
00446     AUTOMATON_TYPES(auto_t);
00447 
00448     typedef algebra::FreeMonoidProduct<
00449     typename auto_t::series_set_t::monoid_t::first_monoid_t,
00450       typename auto_t::series_set_t::monoid_t::second_monoid_t> res_monoid_t;
00451 
00452     typedef algebra::Series<typename auto_t::series_set_t::semiring_t,
00453       res_monoid_t>
00454       res_series_set_t;
00455 
00456     res_monoid_t monoid(lhs.structure().series().monoid().first_monoid(),
00457                         rhs.structure().series().monoid().second_monoid());
00458 
00459 
00460     res_series_set_t series(lhs.structure().series().semiring(), monoid);
00461 
00462     Automata<series_set_t> aut_set(series);
00463 
00464     Element< Automata<series_set_t>, T> ret(aut_set);
00465     do_compose_dispatcher(ret.structure(),
00466                           ret.structure().series().monoid(),
00467                           SELECT(semiring_elt_value_t),
00468                           lhs, rhs, ret);
00469     return ret;
00470   }
00471 
00472 
00473   // Facade for unambiguous composition
00474   template <typename S, typename T>
00475   void
00476   u_compose(const Element<S, T>& lhs,
00477             const Element<S, T>& rhs,
00478             Element<S, T>& ret)
00479   {
00480     typedef Element<S, T> auto_t;
00481     AUTOMATON_TYPES(auto_t);
00482 
00483     for_all_states (s, ret)
00484       ret.del_state (*s);
00485 
00486     do_u_compose (ret.structure(),
00487                   ret.structure().series().monoid(),
00488                   lhs, rhs, ret);
00489   }
00490 
00491   template <typename S, typename T>
00492   Element<S, T>
00493   u_compose(const Element<S, T>& lhs,
00494             const Element<S, T>& rhs)
00495   {
00496     typedef Element<S, T> auto_t;
00497     AUTOMATON_TYPES(auto_t);
00498 
00499     typedef algebra::FreeMonoidProduct<
00500     typename auto_t::series_set_t::monoid_t::first_monoid_t,
00501       typename auto_t::series_set_t::monoid_t::second_monoid_t> res_monoid_t;
00502 
00503     typedef algebra::Series<typename auto_t::series_set_t::semiring_t,
00504       res_monoid_t>
00505       res_series_set_t;
00506 
00507     res_monoid_t monoid(lhs.structure().series().monoid().first_monoid(),
00508                         rhs.structure().series().monoid().second_monoid());
00509 
00510 
00511     res_series_set_t series(lhs.structure().series().semiring(), monoid);
00512 
00513     Automata<series_set_t> aut_set(series);
00514 
00515     Element< Automata<series_set_t>, T> ret(aut_set);
00516     do_u_compose(ret.structure(),
00517                  ret.structure().series().monoid(),
00518                  lhs, rhs, ret);
00519     return ret;
00520   }
00521 
00522 } // vcsn
00523 
00524 #endif // ! VCSN_ALGORITHMS_NORMALIZED_COMPOSITION_HXX

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