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, 2006, 2007 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/misc/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 
00048     /*--------.
00049     | Typedef |
00050     `--------*/
00051 
00052     AUTOMATON_TYPES(input_t);
00053     AUTOMATON_FREEMONOID_TYPES(input_t);
00054     typedef typename std::set<hstate_t>                     subset_t;
00055     typedef typename std::map<subset_t, hstate_t>           subset_set_t;
00056     typedef std::pair<subset_t, hstate_t>                   subset_set_pair_t;
00057     typedef std::vector<hstate_t>                           delta_ret_t;
00058 
00059 
00060     /*-----------------.
00061     | Initialization.  |
00062     `-----------------*/
00063 
00064     hstate_t qi_hstate = output.add_state();
00065     subset_t qi;
00066     bool is_final = false;
00067     for_all_initial_states(i, input)
00068     {
00069       qi.insert(*i);
00070       is_final |= input.is_final(*i);
00071       output.set_initial(qi_hstate);
00072     }
00073 
00074     if (is_final)
00075       output.set_final(qi_hstate);
00076 
00077     subset_set_t subset_set;
00078     subset_set[qi] = qi_hstate;
00079     m[qi_hstate] = qi;
00080 
00081 
00082     /*------------.
00083     | Main loop.  |
00084     `------------*/
00085 
00086     subset_t q;
00087     const alphabet_t& alphabet(input.structure().series().monoid().alphabet());
00088     delta_ret_t dst;
00089     dst.reserve(input.states().size());
00090     std::queue<subset_t> path;
00091     path.push(qi);
00092     while (!path.empty())
00093     {
00094       subset_t s = path.front();
00095       hstate_t s_hstate = subset_set[s];
00096       path.pop();
00097 
00098       for_all_letters(e, alphabet)
00099       {
00100         q.clear ();
00101         bool is_final = false;
00102         for_all_const_ (subset_t, j, s)
00103         {
00104           dst.clear();
00105           input.letter_deltac(dst, *j, *e, delta_kind::states());
00106           for_all_const_(delta_ret_t, k, dst)
00107           {
00108             q.insert(*k);
00109             is_final |= input.is_final(*k);
00110           }
00111         }
00112         typename subset_set_t::const_iterator current = subset_set.find(q);
00113         if (current == subset_set.end())
00114         {
00115           hstate_t qs = output.add_state();
00116           current = (subset_set.insert(subset_set_pair_t(q, qs))).first;
00117           m[qs] = q;
00118 
00119           if (is_final)
00120             output.set_final(current->second);
00121           path.push(q);
00122         }
00123         output.add_letter_transition(s_hstate, (*current).second, *e);
00124       }
00125     }
00126   }
00127 
00128   template<typename A, typename T>
00129   Element<A, T>
00130   subset_construction(const Element<A, T>& a)
00131   {
00132     Element<A, T> res(a.structure());
00133     do_subset_construction(res.structure(), res, a);
00134     return res;
00135   }
00136 
00137   /*--------------.
00138   | determinize.  |
00139   `--------------*/
00140   template <typename A, typename input_t, typename output_t>
00141   void
00142   do_determinize(const AutomataBase<A>& a_set,
00143                  output_t&              output,
00144                  const input_t&         input,
00145                  std::map<hstate_t, std::set<hstate_t> >& m)
00146   {
00147     TIMER_SCOPED ("determinize");
00148     do_subset_construction(a_set, output, input, m);
00149   }
00150 
00151   template<typename A, typename T>
00152   Element<A, T>
00153   determinize(const Element<A, T>& a,
00154               std::map<hstate_t, std::set<hstate_t> >& m)
00155   {
00156     Element<A, T> ret(a.structure());
00157     do_determinize(ret.structure(), ret, a, m);
00158     return ret;
00159   }
00160 
00161   template<typename A, typename T>
00162   Element<A, T>
00163   determinize(const Element<A, T>& a)
00164   {
00165     std::map<hstate_t, std::set<hstate_t> > m;
00166     return determinize(a, m);
00167   }
00168 
00169 } // vcsn
00170 
00171 #endif // ! VCSN_ALGORITHMS_DETERMINIZE_HXX

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