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

Generated on Sat Jul 29 17:13:09 2006 for Vaucanson by  doxygen 1.4.6