outsplitting.hxx

Go to the documentation of this file.
00001 // outsplitting.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2005 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_OUTSPLITTING_HXX
00018 # define VCSN_ALGORITHMS_OUTSPLITTING_HXX
00019 
00020 
00031 # include <vaucanson/algorithms/internal/outsplitting.hh>
00032 # include <vaucanson/algorithms/accessible.hh>
00033 # include <vaucanson/algebra/implementation/series/series.hh>
00034 # include <vaucanson/algebra/concept/freemonoid_product.hh>
00035 
00036 namespace vcsn {
00037   namespace splitting {
00038 
00042 
00043     template <typename S, typename M1, typename M2, typename Auto_t>
00044     Auto_t
00045     do_outsplitting(const AutomataBase<S>&,
00046                     const algebra::FreeMonoidProduct<M1, M2>&,
00047                     const Auto_t& aut,
00048                     std::set<hstate_t>& m)
00049     {
00050       AUTOMATON_TYPES(Auto_t);
00051 
00052       typedef typename series_set_elt_t::support_t      support_t;
00053 
00054       typedef typename monoid_t::second_monoid_t        second_monoid_t;
00055 
00056       typedef typename monoid_elt_value_t::second_type
00057         second_monoid_elt_value_t;
00058       typedef Element<second_monoid_t, second_monoid_elt_value_t>
00059         second_monoid_elt_t;
00060 
00061       typedef std::set<htransition_t>                   set_of_transitions_t;
00062 
00063 
00064 
00065       second_monoid_elt_t second_identity =
00066         algebra::identity_as<second_monoid_elt_value_t>::
00067 	of(aut.structure().series().monoid().second_monoid());
00068 
00069       Auto_t res(aut);
00070 
00071       const series_set_t&       series   = res.structure().series();
00072       const monoid_t&   monoid   = series.monoid();
00073 
00074 
00075 
00076       for_all_states(s, res)
00077         {
00078           bool eps_out = false;
00079           bool other_out = false;
00080           bool diff = false;
00081 
00082           // Test whether there are different types of outgoing transitions.
00083 
00084           set_of_transitions_t transitions;
00085           res.deltac(transitions, *s, delta_kind::transitions());
00086           for_all_const_(set_of_transitions_t, e, transitions)
00087             {
00088               const series_set_elt_t    series  = res.series_of(*e);
00089               support_t                 supp = series.supp();
00090               const monoid_elt_t                supp_elt (monoid, *(supp.begin()));
00091 
00092               if (supp_elt.value().second == second_identity.value())
00093                 eps_out = true;
00094               else
00095                 other_out = true;
00096               if (eps_out and other_out)
00097                 {
00098                   diff = true;
00099                   break;
00100                 }
00101             }
00102 
00103           if (eps_out and not diff)
00104             m.insert(*s);
00105 
00106           // If there are different types of outgoing transitions.
00107           if (diff)
00108             {
00109               hstate_t s2 = res.add_state();
00110               if (res.is_initial(*s))
00111                 res.set_initial(s2, res.get_initial(*s));
00112 
00113               set_of_transitions_t in_transitions;
00114               res.rdeltac(in_transitions, *s, delta_kind::transitions());
00115 
00116               for_all_(set_of_transitions_t, e, in_transitions)
00117                 res.add_series_transition(res.src_of(*e), s2, res.series_of(*e));
00118 
00119               for_all_const_(set_of_transitions_t, e, transitions)
00120                 {
00121                   const series_set_elt_t        series  = res.series_of(*e);
00122                   support_t             supp = series.supp();
00123                   const monoid_elt_t    supp_elt (monoid, *(supp.begin()));
00124 
00125                   if (supp_elt.value().second == second_identity.value())
00126                     {
00127                       res.add_series_transition(s2, res.dst_of(*e), res.series_of(*e));
00128                       res.del_transition(*e);
00129                     }
00130                 }
00131               m.insert(s2);
00132             }
00133         }
00134       return coaccessible(res);
00135     }
00136 
00137 
00141 
00142     template <typename S, typename M1, typename M2, typename Auto_t>
00143     Auto_t
00144     do_insplitting(const AutomataBase<S>&,
00145                    const algebra::FreeMonoidProduct<M1, M2>&,
00146                    const Auto_t& aut,
00147                    std::set<hstate_t>& m)
00148     {
00149       AUTOMATON_TYPES(Auto_t);
00150 
00151       typedef typename series_set_elt_t::support_t      support_t;
00152 
00153       typedef typename monoid_t::first_monoid_t first_monoid_t;
00154 
00155       typedef typename monoid_elt_value_t::first_type
00156         first_monoid_elt_value_t;
00157       typedef Element<first_monoid_t, first_monoid_elt_value_t>
00158         first_monoid_elt_t;
00159 
00160       typedef std::set<htransition_t>                   set_of_transitions_t;
00161 
00162 
00163 
00164       first_monoid_elt_t first_identity =
00165         algebra::identity_as<first_monoid_elt_value_t>::
00166 	of(aut.structure().series().monoid().first_monoid());
00167 
00168       Auto_t res(aut);
00169 
00170       const series_set_t&       series   = res.structure().series();
00171       const monoid_t&   monoid   = series.monoid();
00172 
00173 
00174 
00175       for_all_states(s, res)
00176         {
00177           bool eps_in = false;
00178           bool other_in = false;
00179           bool diff = false;
00180 
00181           // Test whether there are different types of incoming transitions.
00182 
00183           set_of_transitions_t transitions;
00184           res.rdeltac(transitions, *s, delta_kind::transitions());
00185           for_all_const_(set_of_transitions_t, e, transitions)
00186             {
00187               const series_set_elt_t    series  = res.series_of(*e);
00188               support_t                 supp = series.supp();
00189               const monoid_elt_t                supp_elt (monoid, *(supp.begin()));
00190 
00191               if (supp_elt.value().first == first_identity.value())
00192                 eps_in = true;
00193               else
00194                 other_in = true;
00195               if (eps_in and other_in)
00196                 {
00197                   diff = true;
00198                   break;
00199                 }
00200             }
00201 
00202           if (eps_in and not diff)
00203             m.insert(*s);
00204 
00205           // If there are different types of incoming transitions.
00206           if (diff)
00207             {
00208               hstate_t s2 = res.add_state();
00209               if (res.is_final(*s))
00210                 res.set_final(s2, res.get_final(*s));
00211 
00212               set_of_transitions_t out_transitions;
00213               res.deltac(out_transitions, *s, delta_kind::transitions());
00214 
00215               for_all_(set_of_transitions_t, e, out_transitions)
00216                 res.add_series_transition(s2, res.dst_of(*e), res.series_of(*e));
00217 
00218               for_all_const_(set_of_transitions_t, e, transitions)
00219                 {
00220                   const series_set_elt_t        series  = res.series_of(*e);
00221                   support_t             supp = series.supp();
00222                   const monoid_elt_t    supp_elt (monoid, *(supp.begin()));
00223 
00224                   if (supp_elt.value().first == first_identity.value())
00225                     {
00226                       res.add_series_transition(res.src_of(*e), s2,
00227                                                 res.series_of(*e));
00228                       res.del_transition(*e);
00229                     }
00230                 }
00231               m.insert(s2);
00232             }
00233         }
00234       return res;
00235     }
00236 
00237 
00238     template <typename S, typename T>
00239     Element<S, T>
00240     outsplitting(const Element<S, T>& aut, std::set<hstate_t>& states)
00241     {
00242       return do_outsplitting(aut.structure(),
00243                              aut.structure().series().monoid(),
00244                              aut,
00245                              states);
00246     }
00247 
00248 
00249     template <typename S, typename T>
00250     Element<S, T>
00251     insplitting(const Element<S, T>& aut, std::set<hstate_t>& states)
00252     {
00253       return do_insplitting(aut.structure(),
00254                             aut.structure().series().monoid(),
00255                             aut,
00256                             states);
00257     }
00258 
00259 
00260 
00261     template <typename S, typename T>
00262     Element<S, T>
00263     outsplitting(const Element<S, T>& aut)
00264     {
00265       std::set<hstate_t>                states;
00266       return do_outsplitting(aut.structure(),
00267                              aut.structure().series().monoid(),
00268                              aut,
00269                              states);
00270     }
00271 
00272 
00273     template <typename S, typename T>
00274     Element<S, T>
00275     insplitting(const Element<S, T>& aut)
00276     {
00277       std::set<hstate_t>                states;
00278       return do_insplitting(aut.structure(),
00279                             aut.structure().series().monoid(),
00280                             aut,
00281                             states);
00282     }
00283   }
00284 } // End of namespace vcsn.
00285 
00286 #endif // ! VCSN_ALGORITHMS_OUTSPLITTING_HXX

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