Vaucanson: normalized.hxx Source File

00001 // normalized.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 The
00006 // Vaucanson Group.
00007 //
00008 // This program is free software; you can redistribute it and/or
00009 // modify it under the terms of the GNU General Public License
00010 // as published by the Free Software Foundation; either version 2
00011 // of the License, or (at your option) any later version.
00012 //
00013 // The complete GNU General Public Licence Notice can be found as the
00014 // `COPYING' file in the root directory.
00015 //
00016 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
00017 //
00018 #ifndef VCSN_ALGORITHMS_NORMALIZED_HXX
00019 # define VCSN_ALGORITHMS_NORMALIZED_HXX
00020 
00021 # include <vaucanson/algorithms/normalized.hh>
00022 # include <vaucanson/algorithms/internal/has_neighbour.hh>
00023 
00024 # include <vaucanson/automata/concept/automata_base.hh>
00025 # include <vaucanson/misc/usual_macros.hh>
00026 # include <vaucanson/algorithms/sum.hh>
00027 
00028 # include <stack>
00029 
00030 namespace vcsn {
00031 
00032   /*-----------.
00033   | normalized |
00034   `-----------*/
00035   template <typename A, typename AI>
00036   void
00037   do_normalize_here(const AutomataBase<A>&,
00038                     Element<A, AI>& a)
00039   {
00040     BENCH_TASK_SCOPED("normalize");
00041     typedef Element<A, AI> automaton_t;
00042     AUTOMATON_TYPES(automaton_t);
00043 
00044     hstate_t h = a.add_state();
00045 
00046     for_all_const_initial_states(i, a)
00047       a.add_series_transition(h, *i, a.get_initial(*i));
00048 
00049     a.clear_initial();
00050     a.set_initial(h);
00051 
00052     h = a.add_state();
00053 
00054     for_all_const_final_states(i, a)
00055       a.add_series_transition(*i, h, a.get_final(*i));
00056 
00057     a.clear_final();
00058     a.set_final(h);
00059   }
00060 
00061   template <typename A, typename AI>
00062   Element<A, AI>
00063   normalize(const Element<A, AI>& a)
00064   {
00065     Element<A, AI> result(a);
00066     do_normalize_here(result.structure(), result);
00067     return result;
00068   }
00069 
00070   template<typename A, typename AI>
00071   void
00072   normalize_here(Element<A, AI>& a)
00073   {
00074     do_normalize_here(a.structure(), a);
00075   }
00076 
00077 
00078   /*--------------------.
00079   | union_of_normalized |
00080   `--------------------*/
00081 
00082   template <typename A, typename AI1, typename AI2>
00083   void
00084   do_union_of_normalized_here(const AutomataBase<A>&,
00085                               Element<A, AI1>& lhs,
00086                               const Element<A, AI2>& rhs)
00087   {
00088     BENCH_TASK_SCOPED("union_of_normalized");
00089     typedef Element<A, AI1> lhs_t;
00090     typedef Element<A, AI2> rhs_t;
00091     AUTOMATON_TYPES(lhs_t);
00092     monoid_elt_t monoid_identity =
00093       lhs.series().monoid().identity(SELECT(monoid_elt_value_t));
00094     hstate_t new_i = lhs.add_state();
00095     hstate_t new_f = lhs.add_state();
00096 
00097     sum_here(lhs, rhs);
00098 
00099     for_all_const_initial_states(i, lhs)
00100       lhs.add_spontaneous(new_i, *i, lhs.get_initial(*i).get(monoid_identity));
00101     lhs.clear_initial();
00102 
00103     for_all_const_final_states(f, lhs)
00104       lhs.add_spontaneous(*f, new_f, lhs.get_final(*f).get(monoid_identity));
00105     lhs.clear_final();
00106 
00107     lhs.set_final(new_f);
00108     lhs.set_initial(new_i);
00109   }
00110 
00111   template<typename A, typename AI1, typename AI2>
00112   void
00113   union_of_normalized_here(Element<A, AI1>& lhs,
00114                            const Element<A, AI2>& rhs)
00115   {
00116     do_union_of_normalized_here(lhs.structure(), lhs, rhs);
00117   }
00118 
00119   template<typename A, typename AI1, typename AI2>
00120   Element<A, AI1>
00121   union_of_normalized(const Element<A, AI1>& lhs,
00122                       const Element<A, AI2>& rhs)
00123   {
00124     Element<A, AI1> ret(lhs);
00125     do_union_of_normalized_here(ret.structure(), ret, rhs);
00126     return ret;
00127   }
00128 
00129   /*--------------.
00130   | is_normalized |
00131   `--------------*/
00132   template <typename A, typename AI>
00133   bool
00134   do_is_normalized(const AutomataBase<A>&,
00135                    const Element<A, AI>& a)
00136   {
00137     BENCH_TASK_SCOPED("is_normalized");
00138     typedef Element<A, AI> automaton_t;
00139     typedef typename automaton_t::series_set_elt_value_t        series_set_elt_value_t;
00140     typedef typename automaton_t::series_set_elt_t              series_set_elt_t;
00141 
00142     series_set_elt_t series_identity =
00143       a.series().identity(SELECT(series_set_elt_value_t));
00144 
00145     if (a.initial().size() != 1
00146         || a.final().size() != 1
00147         || a.get_initial(*a.initial().begin()) != series_identity
00148         || a.get_final(*a.final().begin()) != series_identity)
00149       return false;
00150 
00151     // Check that there is no input transition on the initial state
00152     // and no output transition on the final state.
00153     return !has_successors(a, *a.final().begin())
00154       && !has_predecessors(a, *a.initial().begin());
00155   }
00156 
00157   template<typename A, typename AI>
00158   bool
00159   is_normalized(const Element<A, AI>& a)
00160   {
00161     return do_is_normalized(a.structure(), a);
00162   }
00163 
00164   /*--------------------------.
00165   | concatenate_of_normalized |
00166   `--------------------------*/
00167   template <typename A, typename AI1, typename AI2>
00168   void
00169   do_concatenate_of_normalized_here(const AutomataBase<A>&,
00170                                     Element<A, AI1>& lhs,
00171                                     const Element<A, AI2>& rhs)
00172   {
00173     BENCH_TASK_SCOPED("concatenate_of_normalized");
00174     typedef Element<A, AI1> lhs_t;
00175     typedef Element<A, AI2> rhs_t;
00176     AUTOMATON_TYPES(rhs_t);
00177     typedef std::map<hstate_t, hstate_t>        map_lhs_rhs_t;
00178     typedef std::list<htransition_t>            delta_ret_t;
00179 
00180     hstate_t    glue_state = *lhs.final().begin();
00181 
00182     /*-----------------.
00183     | Concat of states |
00184     `-----------------*/
00185     map_lhs_rhs_t       map_h;
00186 
00187     // If rhs initial multiplicity is 1 and so is lhs final multiplicity,
00188     // we can merge the lhs final state and the rhs initial state.
00189     bool merge_lhs_final_and_rhs_initial =
00190       (lhs.get_final(*lhs.final().begin()).value() ==
00191        lhs.series().identity(SELECT(series_set_elt_value_t)) &&
00192        rhs.get_initial(*rhs.initial().begin()).value() ==
00193        rhs.series().identity(SELECT(series_set_elt_value_t)));
00194 
00195     for_all_const_states(s, rhs)
00196     {
00197       hstate_t new_state;
00198 
00199       if (merge_lhs_final_and_rhs_initial)
00200       {
00201         if (rhs.is_initial(*s))
00202           new_state = glue_state;
00203         else
00204           new_state = lhs.add_state();
00205       }
00206       else
00207         new_state = lhs.add_state();
00208       map_h[*s] = new_state;
00209       lhs.set_final(new_state, rhs.get_final(*s));
00210     }
00211 
00212     /*------------------------.
00213     | Concat of transitions.  |
00214     `------------------------*/
00215     for_all_const_transitions(t, rhs)
00216       lhs.add_transition(map_h[rhs.src_of(*t)],
00217                          map_h[rhs.dst_of(*t)],
00218                          rhs.label_of(*t));
00219 
00220     // If initial multiplicity of rhs isn't 1, add a spontaneous transition
00221     // between lhs final state and rhs initial state, with lhs final
00222     // multiplicity * rhs initial multiplicity.
00223     if (!merge_lhs_final_and_rhs_initial)
00224     {
00225       monoid_elt_t monoid_identity =
00226         rhs.series().monoid().identity(SELECT(monoid_elt_value_t));
00227       hstate_t i = *rhs.initial().begin();
00228       hstate_t f = *lhs.final().begin();
00229 
00230       lhs.add_spontaneous(f, map_h[i],
00231                           lhs.get_final(f).get(monoid_identity) *
00232                           rhs.get_initial(i).get(monoid_identity));
00233       lhs.unset_final(f);
00234       lhs.unset_initial(map_h[i]);
00235     }
00236   }
00237 
00238   template<typename A, typename AI1, typename AI2>
00239   void
00240   concatenate_of_normalized_here(Element<A, AI1>& lhs, const Element<A, AI2>& rhs)
00241   {
00242     do_concatenate_of_normalized_here(lhs.structure(), lhs, rhs);
00243   }
00244 
00245   template<typename A, typename AI1, typename AI2>
00246   Element<A, AI1>
00247   concatenate_of_normalized(const Element<A, AI1>& lhs, const Element<A, AI2>& rhs)
00248   {
00249     Element<A, AI1> ret(lhs);
00250     do_concatenate_of_normalized_here(ret.structure(), ret, rhs);
00251     return ret;
00252   }
00253 
00254   /*-------------------.
00255   | star_of_normalized |
00256   `-------------------*/
00257   template <typename A, typename AI>
00258   void
00259   do_star_of_normalized_here(const AutomataBase<A>&, Element<A, AI>& a)
00260   {
00261     BENCH_TASK_SCOPED("star_of_normalized");
00262     typedef Element<A, AI> automaton_t;
00263     AUTOMATON_TYPES(automaton_t);
00264     monoid_elt_t monoid_identity =
00265       a.series().monoid().identity(SELECT(monoid_elt_value_t));
00266     hstate_t old_i = *a.initial().begin();
00267     hstate_t old_f = *a.final().begin();
00268     hstate_t new_i = a.add_state();
00269     hstate_t new_f = a.add_state();
00270 
00271     a.add_spontaneous(old_f, old_i, a.get_initial(old_i).get(monoid_identity));
00272     a.add_spontaneous(new_i, old_i, a.get_initial(old_i).get(monoid_identity));
00273     a.add_spontaneous(old_f, new_f, a.get_final(old_f).get(monoid_identity));
00274     a.add_spontaneous(new_i, new_f);
00275     a.set_final(new_f);
00276     a.unset_final(old_f);
00277     a.set_initial(new_i);
00278     a.unset_initial(old_i);
00279   }
00280 
00281   template<typename A, typename AI>
00282   void
00283   star_of_normalized_here(Element<A, AI>& a)
00284   {
00285     do_star_of_normalized_here(a.structure(), a);
00286   }
00287 
00288   template<typename A, typename AI>
00289   Element<A, AI>
00290   star_of_normalized(const Element<A, AI>& a)
00291   {
00292     Element<A, AI> ret(a);
00293     do_star_of_normalized_here(ret.structure(), ret);
00294     return ret;
00295   }
00296 
00297 } // vcsn
00298 
00299 #endif // ! VCSN_ALGORITHMS_NORMALIZED_HXX