00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
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
00026 # ifndef VCSN_NDEBUG
00027 # include <vaucanson/algorithms/realtime.hh>
00028 # endif // ! VCSN_NDEBUG
00029
00030 namespace vcsn {
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042 template <typename A, typename input_t, typename output_t>
00043 void
00044 do_subset_construction(const AutomataBase<A>& ,
00045 output_t& output,
00046 const input_t& input,
00047 std::map<typename output_t::hstate_t,
00048 std::set<typename input_t::hstate_t> >& m =
00049 std::map<typename output_t::hstate_t,
00050 std::set<typename input_t::hstate_t> >())
00051 {
00052
00053
00054
00055
00056
00057 AUTOMATON_TYPES(input_t);
00058 AUTOMATON_FREEMONOID_TYPES(input_t);
00059 typedef typename std::set<typename input_t::hstate_t> subset_t;
00060 typedef typename std::map<subset_t, typename output_t::hstate_t>
00061 subset_set_t;
00062 typedef std::pair<subset_t, typename output_t::hstate_t> subset_set_pair_t;
00063 typedef std::vector<typename input_t::hstate_t> delta_ret_t;
00064
00065
00066
00067
00068
00069
00070 typename output_t::hstate_t qi_hstate = output.add_state();
00071 subset_t qi;
00072 bool is_final = false;
00073 for_all_const_initial_states(i, input)
00074 {
00075 qi.insert(*i);
00076 is_final |= input.is_final(*i);
00077 }
00078 output.set_initial(qi_hstate);
00079
00080 if (is_final)
00081 output.set_final(qi_hstate);
00082
00083 subset_set_t subset_set;
00084 subset_set[qi] = qi_hstate;
00085 m[qi_hstate] = qi;
00086
00087
00088
00089
00090
00091
00092 subset_t q;
00093 const alphabet_t& alphabet(input.structure().series().monoid().alphabet());
00094 delta_ret_t dst;
00095 dst.reserve(input.states().size());
00096 std::queue<subset_t> path;
00097 path.push(qi);
00098 while (!path.empty())
00099 {
00100 subset_t s = path.front();
00101 typename input_t::hstate_t s_hstate = subset_set[s];
00102 path.pop();
00103
00104 for_all_const_letters(e, alphabet)
00105 {
00106 q.clear ();
00107 bool is_final = false;
00108 for_all_const_ (subset_t, j, s)
00109 {
00110 for (delta_iterator t(input.value(), *j); ! t.done(); t.next())
00111 {
00112 monoid_elt_t w(input.series_of(*t).structure().monoid(), *e);
00113 if (input.series_of(*t).get(w) != input.series().semiring().wzero_)
00114 {
00115 hstate_t s = input.dst_of(*t);
00116 q.insert(s);
00117 is_final |= input.is_final(s);
00118 }
00119 }
00120 }
00121 typename subset_set_t::const_iterator current = subset_set.find(q);
00122 if (current == subset_set.end())
00123 {
00124 typename output_t::hstate_t qs = output.add_state();
00125 current = (subset_set.insert(subset_set_pair_t(q, qs))).first;
00126 m[qs] = q;
00127
00128 if (is_final)
00129 output.set_final(current->second);
00130 path.push(q);
00131 }
00132 output.add_letter_transition(s_hstate, (*current).second, *e);
00133 }
00134 }
00135 }
00136
00137 template<typename A, typename AI>
00138 Element<A, AI>
00139 subset_construction(const Element<A, AI>& a)
00140 {
00141 Element<A, AI> res(a.structure());
00142 do_subset_construction(res.structure(), res, a);
00143 return res;
00144 }
00145
00146
00147
00148
00149 template <typename A, typename AI>
00150 void
00151 do_determinize(const AutomataBase<A>& a_set,
00152 Element<A, AI>& output,
00153 const Element<A, AI>& input,
00154 std::map<typename Element<A, AI>::hstate_t,
00155 std::set<typename Element<A, AI>::hstate_t> >& m)
00156 {
00157 TIMER_SCOPED ("determinize");
00158 precondition(is_realtime(input));
00159 do_subset_construction(a_set, output, input, m);
00160 }
00161
00162 template<typename A, typename AI>
00163 Element<A, AI>
00164 determinize(const Element<A, AI>& a,
00165 std::map<typename Element<A, AI>::hstate_t,
00166 std::set<typename Element<A, AI>::hstate_t> >& m)
00167 {
00168 Element<A, AI> ret(a.structure());
00169 do_determinize(ret.structure(), ret, a, m);
00170 return ret;
00171 }
00172
00173 template<typename A, typename AI>
00174 Element<A, AI>
00175 determinize(const Element<A, AI>& a)
00176 {
00177 std::map<typename Element<A, AI>::hstate_t,
00178 std::set<typename Element<A, AI>::hstate_t> > m;
00179 return determinize(a, m);
00180 }
00181
00182 }
00183
00184 #endif // ! VCSN_ALGORITHMS_DETERMINIZE_HXX