minimization_moore.hxx

00001 // minimization_moore.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 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_MINIMIZATION_MOORE_HXX
00018 # define VCSN_ALGORITHMS_MINIMIZATION_MOORE_HXX
00019 
00020 # include <vaucanson/algorithms/minimization_moore.hh>
00021 
00022 # include <vaucanson/automata/concept/handlers.hh>
00023 # include <vaucanson/automata/concept/delta_kind.hh>
00024 # include <vaucanson/misc/usual_macros.hh>
00025 # include <vaucanson/misc/contract.hh>
00026 
00027 # include <map>
00028 # include <set>
00029 # include <vector>
00030 
00031 // Useful macros for Moore's minimization.
00032 
00033 // Iterator on a list of groups.
00034 # define for_all_groups(I, P)                                           \
00035   for (groupid_to_group_t::iterator I = ((P).begin()); I != (P).end(); ++I)
00036 
00037 // Iterator on state in a group. We don't iterate on the first not
00038 // processed state.
00039 # define for_all_state_in_groups(I, P)                                  \
00040   for (group_t::iterator I = ++((P).begin()); I != (P).end(); ++I)
00041 
00042 namespace vcsn {
00043 
00044   /*-------------------.
00045   | minimization_moore |
00046   `-------------------*/
00047   // preconditions :
00048   // - the input automaton is deterministic or co-deterministic
00049   //   according to Transposed;
00050   // - the output automaton is well initialized with good sets ;
00051   //
00052 
00053   template<typename A, typename T, bool Transposed>
00054   void
00055   do_minimization_moore(const Element<A, T>& input, Element<A, T>& output)
00056   {
00057     TIMER_SCOPED("minimization_moore");
00058     typedef Element<A, T> automata_type;
00059     AUTOMATON_TYPES(automata_type);
00060     AUTOMATON_FREEMONOID_TYPES(automata_type);
00061     using std::map;
00062     using std::vector;
00063     using std::set;
00064 
00065     // Consts.
00066 
00067     const hstate_t      NullState = -1;
00068     const hstate_t      NullGroup = -1;
00069     const alphabet_t&   alphabet (input.series().monoid().alphabet());
00070 
00071     // Typedefs.
00072 
00073     typedef int                                 letterid_t;
00074     typedef int                                 groupid_t;
00075 
00076     typedef set<hstate_t>                       group_t;
00077     typedef vector<group_t>                     groupid_to_group_t;
00078 
00079     typedef vector<hstate_t>                    letterid_to_state_t;
00080 
00081     typedef map<hstate_t, letterid_to_state_t>  state_to_letterid_to_state_t;
00082 
00083     typedef map<hstate_t, groupid_t>            state_to_groupid_t;
00084     typedef map<letter_t,  letterid_t>          letter_to_letterid_t;
00085 
00086     /*---------------.
00087     | Initialization |
00088     `---------------*/
00089 
00090     precondition(input.exists());
00091 
00092     groupid_to_group_t  groupid_to_group(input.states().size());
00093 
00094     state_to_groupid_t state_to_groupid;
00095     state_to_groupid[NullState] = NullGroup;
00096 
00097     letter_to_letterid_t letter_to_letterid;
00098     int letter_count = 0;
00099     for_all_letters(iletter, alphabet)
00100       letter_to_letterid[*iletter] = letter_count++;
00101 
00102     state_to_letterid_to_state_t aut_view;
00103     for_all_states(istate, input)
00104     {
00105       aut_view[*istate] = letterid_to_state_t(letter_count, NullState);
00106       if ((not Transposed and input.is_final(*istate)) or
00107           (Transposed and input.is_initial(*istate)))
00108       {
00109         groupid_to_group[0].insert(*istate);
00110         state_to_groupid[*istate] = 0;
00111       }
00112       else
00113       {
00114         groupid_to_group[1].insert(*istate);
00115         state_to_groupid[*istate] = 1;
00116       }
00117     }
00118 
00119     group_t delta_ret;
00120     for_all_states(istate, input)
00121     {
00122       for_all_const_(letter_to_letterid_t, iletter, letter_to_letterid)
00123       {
00124         delta_ret.clear ();
00125         if (not Transposed)
00126           input.letter_deltac(delta_ret, *istate, iletter->first,
00127                               delta_kind::states());
00128         else
00129           input.letter_rdeltac(delta_ret, *istate, iletter->first,
00130                                delta_kind::states());
00131         if (not delta_ret.empty())
00132           aut_view[*istate][iletter->second] = *delta_ret.begin();
00133       }
00134     }
00135 
00136 
00137     /*-----.
00138     | Loop |
00139     `-----*/
00140 
00141     int  last_group = 1;
00142     for (bool group_modified = true; group_modified;)
00143     {
00144       group_modified = false;
00145       for_all_groups(igroup, groupid_to_group)
00146       {
00147         if (igroup->empty())
00148           break;
00149 
00150         hstate_t first_state = *(igroup->begin());
00151         bool     group_created = false;
00152 
00153         for_all_state_in_groups(istate, *igroup)
00154         {
00155           int i;
00156           for (i = 0; i < letter_count; ++i)
00157             if (state_to_groupid[aut_view[first_state][i]] !=
00158                 state_to_groupid[aut_view[*istate][i]])
00159               break;
00160           if (i != letter_count)
00161           {
00162             group_t::iterator istate_save = istate;
00163 
00164             istate_save--;
00165             if (group_created == false)
00166             {
00167               last_group++;
00168               group_created = true;
00169               group_modified = true;
00170             }
00171             groupid_to_group[last_group].insert(*istate);
00172             state_to_groupid[*istate] = last_group;
00173             igroup->erase(*istate);
00174             istate = istate_save;
00175           }
00176         }
00177       }
00178     }
00179 
00180 
00181     /*-----------------------.
00182     | Automaton construction |
00183     `-----------------------*/
00184 
00185     std::vector<hstate_t> new_states(last_group + 1);
00186 
00187     // Create all states.
00188     for (int i = 0; i <= last_group; ++i)
00189       new_states[i] = output.add_state();
00190 
00191     // Create all transitions.
00192     for (int i = 0; i <= last_group; ++i)
00193     {
00194       hstate_t repres = *(groupid_to_group[i].begin());
00195 
00196       for_all_const_(letter_to_letterid_t, iletter, letter_to_letterid)
00197         if (aut_view[repres][iletter->second] != NullState)
00198         {
00199           if (not Transposed)
00200             output.add_letter_transition(new_states[i],
00201                                          new_states[state_to_groupid
00202                                                     [aut_view[repres]
00203                                                      [iletter->second]]],
00204                                          iletter->first);
00205           else
00206             output.add_letter_transition(new_states[state_to_groupid
00207                                                     [aut_view[repres]
00208                                                      [iletter->second]]],
00209                                          new_states[i],
00210                                          iletter->first);
00211         }
00212     }
00213 
00214     // Setting initial and final states.
00215     if (not Transposed)
00216     {
00217       output.set_final(new_states[0]);
00218       output.set_initial(new_states[state_to_groupid[*input.initial().begin()]]);
00219     }
00220     else
00221     {
00222       output.set_initial(new_states[0]);
00223       output.set_final(new_states[state_to_groupid[*input.final().begin()]]);
00224     }
00225 
00226   }
00227 
00228 
00229   template<typename A, typename T>
00230   void
00231   minimization_moore_here(Element<A, T>& a)
00232   {
00233     Element<A, T> output(a.structure());
00234     do_minimization_moore<A, T, false>(a, output);
00235     a = output;
00236   }
00237 
00238 
00239   template<typename A, typename T>
00240   Element<A, T>
00241   minimization_moore(const Element<A, T>& a)
00242   {
00243     Element<A, T> output(a.structure());
00244     do_minimization_moore<A, T, false>(a, output);
00245     return output;
00246   }
00247 
00248   template<typename A, typename T>
00249   void
00250   co_minimization_moore_here(Element<A, T>& a)
00251   {
00252     Element<A, T> output(a.structure());
00253     do_minimization_moore<A, T, true>(a, output);
00254     a = output;
00255   }
00256 
00257 
00258   template<typename A, typename T>
00259   Element<A, T>
00260   co_minimization_moore(const Element<A, T>& a)
00261   {
00262     Element<A, T> output(a.structure());
00263     do_minimization_moore<A, T, true>(a, output);
00264     return output;
00265   }
00266 
00267 } // vcsn
00268 
00269 // Prevent potential conflicts.
00270 # undef for_all_groups
00271 # undef for_all_state_in_groups
00272 
00273 
00274 #endif // ! VCSN_ALGORITHMS_MINIMIZATION_MOORE_HXX

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