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