determinize.hxx

00001 // determinize.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 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_DETERMINIZE_HXX
00018 # define VCSN_ALGORITHMS_DETERMINIZE_HXX
00019 
00020 # include <map>
00021 # include <set>
00022 # include <queue>
00023 # include <vaucanson/tools/usual_macros.hh>
00024 # include <vaucanson/automata/concept/automata_base.hh>
00025 # include <vaucanson/algorithms/accessible.hh>
00026 
00027 namespace vcsn {
00028 
00029   /*--------------------.
00030   | subset_construction |
00031   `--------------------*/
00032   // preconditions :
00033   //    - output has been initialized with good series set
00034   //      (alphabet is well initialized) ;
00035   //    - this algorithm is intended to work with realtime automaton
00036   //      over |B<A*> => add concept checking.
00037   //
00038 
00039   template <typename A, typename input_t, typename output_t>
00040   void
00041   do_subset_construction(const AutomataBase<A>& ,
00042                          output_t&              output,
00043                          const input_t&         input,
00044                          std::map<hstate_t, std::set<hstate_t> >& m =
00045                          std::map<hstate_t, std::set<hstate_t> >())
00046   {
00047     AUTOMATON_TYPES(input_t);
00048     AUTOMATON_FREEMONOID_TYPES(input_t);
00049     typedef typename input_t::series_set_t                          series_set_t;
00050     typedef typename std::set<hstate_t>                     subset_t;
00051     typedef typename std::map<subset_t, hstate_t>           subset_set_t;
00052     typedef std::pair<subset_t, hstate_t>                   subset_set_pair_t;
00053     typedef std::vector<hstate_t>                           delta_ret_t;
00054 
00055     hstate_t               qi_hstate = output.add_state();
00056     subset_t               qi;
00057     subset_set_t           subset_set;
00058     const alphabet_t&      alphabet(input.structure().series().monoid().alphabet());
00059     subset_t               q;
00060     subset_t               s;
00061     delta_ret_t            aim;
00062     hstate_t               s_hstate;
00063     typename subset_set_t::const_iterator       current;
00064 
00065     /*---------------.
00066     | Initialization |
00067     `---------------*/
00068     bool is_final = false;
00069     aim.reserve(input.states().size());
00070 
00071     for_each_initial_state(i, input)
00072     {
00073       qi.insert(*i);
00074       is_final |= input.is_final(*i);
00075       output.set_initial(qi_hstate);
00076     }
00077 
00078     if (is_final)
00079       output.set_final(qi_hstate);
00080 
00081     subset_set[qi] = qi_hstate;
00082     m[qi_hstate] = qi;
00083 
00084 
00085     /*----------.
00086     | Main loop |
00087     `----------*/
00088     std::queue<subset_t> path;
00089     path.push(qi);
00090 
00091     do {
00092       s        = path.front();
00093       s_hstate = subset_set[s];
00094       path.pop();
00095 
00096       for_each_letter(e, alphabet)
00097       {
00098         q.clear();
00099         is_final = false;
00100         for (typename subset_t::const_iterator j = s.begin();
00101              j != s.end(); ++j)
00102         {
00103           aim.clear();
00104 
00105           input.letter_deltac(aim, *j, *e, delta_kind::states());
00106           for_all_const_(delta_ret_t, k, aim)
00107           {
00108             hstate_t state = *k;
00109             q.insert(state);
00110             is_final   |= input.is_final(state);
00111           }
00112         }
00113         current = subset_set.find(q);
00114         if (current == subset_set.end())
00115         {
00116           hstate_t qs = output.add_state();
00117           current = (subset_set.insert
00118                      (subset_set_pair_t(q, qs))).first;
00119           m[qs] = q;
00120 
00121 
00122 
00123           if (is_final)
00124             output.set_final(current->second);
00125           path.push(q);
00126         }
00127         output.add_letter_transition(s_hstate, (*current).second, *e);
00128       }
00129     } while (!path.empty());
00130   }
00131 
00132   template<typename A, typename T>
00133   Element<A, T>
00134   subset_construction(const Element<A, T>& a)
00135   {
00136     Element<A, T>    ret(a.structure());
00137     do_subset_construction(ret.structure(), ret, a);
00138     return ret;
00139   }
00140 
00141   /*------------.
00142   | determinize |
00143   `------------*/
00144   template <typename A, typename input_t, typename output_t>
00145   void
00146   do_determinize(const AutomataBase<A>& a_set,
00147                  output_t&                      output,
00148                  const input_t&         input,
00149                  std::map<hstate_t, std::set<hstate_t> >& m)
00150   {
00151     do_subset_construction(a_set, output, input, m);
00152   }
00153 
00154   template<typename A, typename T>
00155   Element<A, T>
00156   determinize(const Element<A, T>& a)
00157   {
00158     std::map<hstate_t, std::set<hstate_t> > m;
00159     return determinize(a, m);
00160   }
00161 
00162   template<typename A, typename T>
00163   Element<A, T>
00164   determinize(const Element<A, T>& a,
00165               std::map<hstate_t, std::set<hstate_t> >& m)
00166   {
00167     Element<A, T> ret(a.structure());
00168     do_determinize(ret.structure(), ret, a, m);
00169     return ret;
00170   }
00171 
00172   template <typename input_t>
00173   static bool
00174   is_state_deterministic (input_t&                                              input,
00175                           typename input_t::state_iterator&                     current_state,
00176                           typename input_t::series_set_elt_t::semiring_elt_t&   zero_semiring)
00177   {
00178     AUTOMATON_TYPES(input_t);
00179 
00180     typedef typename series_set_elt_t::support_t        support_t;
00181     typedef typename std::set<htransition_t>            delta_ret_t;
00182     delta_ret_t delta_ret;
00183 
00184     input.deltac(delta_ret, *current_state, delta_kind::transitions());
00185     // FIXME : O(n^2) => O(nlog(n)) There is maybe an algorithm in O(nlog(n))
00186     for_all_const_(delta_ret_t, j, delta_ret)
00187       {
00188         series_set_elt_t s = input.series_of(*j);
00189         typename delta_ret_t::const_iterator k = j;
00190         ++k;
00191         for (; k != delta_ret.end(); ++k)
00192           {
00193             series_set_elt_t s_ = input.series_of(*k);
00194             for_all_(support_t, supp, s.supp())
00195               if (s_.get(*supp) != zero_semiring)
00196                 return false;
00197           }
00198       }
00199     return true;
00200   }
00201 
00202 
00203 
00204 
00205   /*-----------------.
00206   | is_deterministic |
00207   `-----------------*/
00208   template <typename A, typename input_t>
00209   bool
00210   do_is_deterministic(const AutomataBase<A>&    ,
00211                       const input_t&            input)
00212   {
00213     AUTOMATON_TYPES(input_t);
00214     semiring_elt_t                zero_semiring
00215       = input.structure().series().semiring()
00216       .zero(SELECT(typename semiring_elt_t::value_t));
00217 
00218     // Empty automaton is not deterministic
00219     if (input.states().size() == 0)
00220       return false;
00221 
00222     if (input.initial().size() != 1)
00223       return false;
00224 
00225     for_each_state(i, input)
00226     {
00227       if (not is_state_deterministic (input, i, zero_semiring))
00228         return false;
00229     }
00230     return true;
00231   }
00232 
00233 
00234   template<typename A, typename T>
00235   bool
00236   is_deterministic(const Element<A, T>& a)
00237   {
00238     return do_is_deterministic(a.structure(), a);
00239   }
00240 
00241 } // vcsn
00242 
00243 #endif // ! VCSN_ALGORITHMS_DETERMINIZE_HXX

Generated on Fri Jul 28 12:18:31 2006 for Vaucanson by  doxygen 1.4.6