Vaucanson: rw_to_fmp.hxx Source File

00001 // rw_to_fmp.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, 2008 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_RW_TO_FMP_HXX
00018 # define VCSN_ALGORITHMS_RW_TO_FMP_HXX
00019 
00020 # include <vaucanson/algebra/concept/freemonoid_product.hh>
00021 # include <vaucanson/automata/concept/transducer.hh>
00022 # include <vaucanson/automata/concept/automata.hh>
00023 # include <map>
00024 
00025 namespace vcsn
00026 {
00027   template<typename S, typename T,
00028            typename SS, typename TT,
00029            typename Self>
00030   void
00031   do_rw_to_fmp(const vcsn::TransducerBase<S>&,
00032                const vcsn::AutomataBase<SS>&,
00033                const vcsn::algebra::FreeMonoidProductBase<Self>&,
00034                const vcsn::Element<S, T>& trans,
00035                vcsn::Element<SS, TT>& res)
00036   {
00037     typedef typename T::hstate_t hstate_t;
00038     //Map source states with result states
00039     std::map<hstate_t, hstate_t> m;
00040 
00041     //Input transducer type
00042     typedef vcsn::Element<S, T> Trans_t;
00043 
00044     //Output FMP Automaton type
00045     typedef vcsn::Element<SS, TT> FMP_t;
00046 
00047     typename FMP_t::monoid_t fmp(trans.structure().series().monoid(),
00048                                  trans.structure().series().monoid());
00049     typename FMP_t::semiring_t sg;
00050     typename FMP_t::series_set_t ss(sg, fmp);
00051 
00052     typedef vcsn::Element<typename FMP_t::monoid_t::first_monoid_t,
00053       typename FMP_t::monoid_elt_value_t::first_type>
00054       first_monoid_elt_t;
00055     typedef vcsn::Element<typename FMP_t::monoid_t::second_monoid_t,
00056       typename FMP_t::monoid_elt_value_t::second_type>
00057       second_monoid_elt_t;
00058     typedef vcsn::Element<typename Trans_t::series_set_t,
00059       typename Trans_t::series_set_elt_value_t>
00060       mult_elt_t;
00061 
00062 
00063     /*----------------------------.
00064     | Creating the FMP automaton. |
00065     `----------------------------*/
00066 
00067     // Adding states
00068     for (typename Trans_t::state_iterator St = trans.states().begin();
00069          St != trans.states().end();
00070          ++St)
00071       m[*St] = res.add_state();
00072 
00073     typename Trans_t::series_set_elt_t id_series(trans.structure().series());
00074     id_series = vcsn::algebra::
00075       identity_as<typename Trans_t::series_set_elt_value_t>::
00076       of(trans.structure().series());
00077 
00078 
00079     /*------------------------.
00080     | Setting initial states. |
00081     `------------------------*/
00082 
00083     for (typename Trans_t::initial_iterator St, next = trans.initial().begin();
00084          next != trans.initial().end();)
00085     {
00086       //We need to store the next iterator before using the current one
00087       //to avoid an invalid iterator after having called set_final.
00088       //Indeed, set_final can delete the iterator if its second parameter
00089       //is the zero of the serie.
00090       St = next;
00091       next++;
00092 
00093       typename FMP_t::series_set_elt_t s(ss);
00094       typename FMP_t::monoid_elt_t mon(res.structure().series().monoid());
00095       first_monoid_elt_t
00096         first(res.structure().series().monoid().first_monoid());
00097       second_monoid_elt_t
00098         second(res.structure().series().monoid().second_monoid());
00099       typename FMP_t::semiring_elt_t
00100         weight(res.structure().series().semiring());
00101 
00102       mult_elt_t mult = trans.get_initial(*St);
00103       if (mult != id_series)
00104       {
00105         hstate_t tmp = res.add_state();
00106         typename mult_elt_t::support_t mult_supp = mult.supp();
00107         for_all_const_(mult_elt_t::support_t, i, mult_supp)
00108         {
00109           first = *i;
00110 
00111           typename Trans_t::semiring_elt_t
00112             output(trans.structure().series().semiring(), mult.get(*i));
00113           typename Trans_t::semiring_elt_t::support_t
00114             output_supp = output.supp();
00115           for_all_const_(Trans_t::semiring_elt_t::support_t,
00116                          j,
00117                          output_supp)
00118           {
00119             second = *j;
00120             weight = output.get(*j);
00121             mon = typename FMP_t::monoid_elt_value_t(first.value(),
00122                                                      second.value());
00123             s.assoc(mon, weight);
00124           }
00125         }
00126         res.add_series_transition(tmp, m[*St], s);
00127         res.set_initial(tmp);
00128       }
00129       else
00130         res.set_initial(m[*St]);
00131     }
00132 
00133 
00134     /*----------------------.
00135     | Setting final states. |
00136     `----------------------*/
00137 
00138     for (typename Trans_t::final_iterator St, next = trans.final().begin();
00139          next != trans.final().end();)
00140     {
00141       //We need to store the next iterator before using the current one
00142       //to avoid an invalid iterator after having called set_final.
00143       //Indeed, set_final can delete the iterator if its second parameter
00144       //is the zero of the serie.
00145       St = next;
00146       next++;
00147 
00148       typename FMP_t::series_set_elt_t s(ss);
00149       typename FMP_t::monoid_elt_t mon(res.structure().series().monoid());
00150       first_monoid_elt_t
00151         first(res.structure().series().monoid().first_monoid());
00152       second_monoid_elt_t
00153         second(res.structure().series().monoid().second_monoid());
00154       typename FMP_t::semiring_elt_t
00155         weight(res.structure().series().semiring());
00156 
00157       mult_elt_t mult = trans.get_final(*St);
00158       if (mult != id_series)
00159       {
00160         hstate_t tmp = res.add_state();
00161 
00162         typename mult_elt_t::support_t mult_supp = mult.supp();
00163         for_all_const_(mult_elt_t::support_t, i, mult_supp)
00164         {
00165           first = *i;
00166 
00167           typename Trans_t::semiring_elt_t
00168             output(trans.structure().series().semiring(), mult.get(*i));
00169           typename Trans_t::semiring_elt_t::support_t
00170             output_supp = output.supp();
00171           for_all_const_(Trans_t::semiring_elt_t::support_t,
00172                          j,
00173                          output_supp)
00174           {
00175             second = *j;
00176             weight = output.get(*j);
00177             mon = typename FMP_t::monoid_elt_value_t(first.value(),
00178                                                      second.value());
00179             s.assoc(mon, weight);
00180           }
00181         }
00182         res.add_series_transition(m[*St], tmp, s);
00183         res.set_final(tmp);
00184       }
00185       else
00186         res.set_final(m[*St]);
00187     }
00188 
00189 
00190     /*-----------------------.
00191     | Creating transitions.  |
00192     `-----------------------*/
00193 
00194     for (typename Trans_t::transition_iterator Ed = trans.transitions().begin();
00195          Ed != trans.transitions().end();
00196          ++Ed)
00197     {
00198       typename FMP_t::series_set_elt_t s(ss);
00199 
00200       first_monoid_elt_t first(trans.structure().series().monoid());
00201       second_monoid_elt_t
00202         second(trans.structure().series().semiring().monoid());
00203       typename FMP_t::monoid_elt_t
00204         mon(res.structure().series().monoid());
00205 
00206       typename Trans_t::series_set_elt_t
00207         series_elt(trans.structure().series());
00208       series_elt = trans.series_of(*Ed);
00209 
00210       for (typename Trans_t::series_set_elt_t::support_t::const_iterator
00211              i = series_elt.supp().begin();
00212            i != series_elt.supp().end();
00213            ++i)
00214       {
00215         first = *i;
00216 
00217         typename Trans_t::semiring_elt_t
00218           mult(trans.structure().series().semiring());
00219         mult = series_elt.get(first);
00220 
00221         //FIXME
00222         //If we don't use a copy of the support we don't get ALL the
00223         //element of the series when card(mult) > 1.
00224         typename Trans_t::semiring_elt_t::support_t
00225           mult_supp = mult.supp();
00226         for (typename Trans_t::semiring_elt_t::support_t::const_iterator
00227                j = mult_supp.begin();
00228              j != mult_supp.end();
00229              ++j)
00230         {
00231           second = *j;
00232 
00233           mon = typename FMP_t::monoid_elt_value_t(first.value(),
00234                                                    second.value());
00235           s.assoc(mon, trans.output_of(*Ed).get(second));
00236         }
00237       }
00238       res.add_series_transition(m[trans.src_of(*Ed)],
00239                                 m[trans.dst_of(*Ed)],
00240                                 s);
00241     }
00242   }
00243 
00244   template<typename S, typename T,
00245            typename SS, typename TT>
00246   vcsn::Element<SS, TT>&
00247   rw_to_fmp(const vcsn::Element<S, T>& trans, vcsn::Element<SS, TT>& res)
00248   {
00249     do_rw_to_fmp(trans.structure(), res.structure(),
00250                  res.structure().series().monoid(),
00251                  trans, res);
00252     return res;
00253   }
00254 }
00255 
00256 #endif // ! VCSN_ALGORITHMS_RW_TO_FMP_HXX