00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef VCSN_ALGORITHMS_EPS_REMOVAL_SP_HXX
00018 # define VCSN_ALGORITHMS_EPS_REMOVAL_SP_HXX
00019
00020 # include <vaucanson/algorithms/eps_removal.hh>
00021
00022 # include <vaucanson/automata/concept/automata_base.hh>
00023 # include <vaucanson/misc/usual_macros.hh>
00024
00025 # include <boost/multi_index_container.hpp>
00026 # include <boost/multi_index/member.hpp>
00027 # include <boost/multi_index/hashed_index.hpp>
00028 # include <boost/multi_index/composite_key.hpp>
00029 # include <boost/functional/hash/hash.hpp>
00030 # include <boost/tuple/tuple.hpp>
00031 # include <vector>
00032 # include <list>
00033 # include <queue>
00034 # include <map>
00035 # include <utility>
00036 # include <set>
00037 # include <stack>
00038
00039 namespace vcsn {
00040
00041
00042
00043
00044
00045 template
00046 <class A_, typename Auto, typename Weight>
00047 class EpsilonRemoverSp
00048 {
00049 AUTOMATON_TYPES(Auto);
00050 public:
00051 struct tr_t
00052 {
00053 tr_t(hstate_t src_, hstate_t dst_, series_set_elt_t series_)
00054 : src(src_),
00055 dst(dst_),
00056 series(series_)
00057 {}
00058
00059 hstate_t src;
00060 hstate_t dst;
00061 series_set_elt_t series;
00062 };
00063
00064 struct s_shortest
00065 {
00066 s_shortest(const hstate_t src_, const hstate_t dst_, semiring_elt_t& d_, semiring_elt_t& r_)
00067 : src(src_),
00068 dst(dst_),
00069 dist(d_),
00070 rel(r_)
00071 {}
00072
00073 const hstate_t src;
00074 const hstate_t dst;
00075 semiring_elt_t dist;
00076 semiring_elt_t rel;
00077 };
00078
00079 struct change_rel
00080 {
00081 change_rel(const semiring_elt_t& new_rel)
00082 : new_rel(new_rel)
00083 {}
00084
00085 void operator() (s_shortest& s)
00086 {
00087 s.rel = new_rel;
00088 }
00089 private:
00090 semiring_elt_t new_rel;
00091 };
00092
00093 struct change_dist
00094 {
00095 change_dist(const semiring_elt_t& new_dist)
00096 : new_dist(new_dist)
00097 {}
00098
00099 void operator() (s_shortest& s)
00100 {
00101 s.dist = new_dist;
00102 }
00103 private:
00104 semiring_elt_t new_dist;
00105 };
00106
00107 struct add_dr
00108 {
00109 add_dr(const semiring_elt_t& new_dist, const semiring_elt_t& new_rel)
00110 : new_dist(new_dist),
00111 new_rel(new_rel)
00112 {}
00113
00114 void operator() (s_shortest& s)
00115 {
00116 s.dist += new_dist;
00117 s.rel += new_rel;
00118 }
00119 private:
00120 semiring_elt_t new_dist;
00121 semiring_elt_t new_rel;
00122 };
00123
00124 typedef boost::multi_index_container
00125 <
00126 s_shortest,
00127 boost::multi_index::indexed_by
00128 <
00129 boost::multi_index::hashed_unique
00130 <
00131 boost::multi_index::composite_key
00132 <
00133 s_shortest,
00134 BOOST_MULTI_INDEX_MEMBER(s_shortest, const hstate_t, src),
00135 BOOST_MULTI_INDEX_MEMBER(s_shortest, const hstate_t, dst)
00136 >
00137 >
00138 >
00139 > s_shortest_hash;
00140
00141 EpsilonRemoverSp(const AutomataBase<A_>&,
00142 Auto& aut)
00143 : a(aut),
00144 null_series(aut.series().zero_),
00145 semiring_elt_zero(aut.series().semiring().wzero_),
00146 semiring_elt_one(aut.series().semiring().wone_),
00147 monoid_identity(aut.series().monoid().VCSN_EMPTY_)
00148 {
00149 shortest_eps_distance();
00150 }
00151
00152 void operator() (misc::direction_type dir)
00153 {
00154
00155 for_all_transitions(e,a)
00156 {
00157 series_set_elt_t t = a.series_of(*e);
00158 if (t.get(monoid_identity) != semiring_elt_zero)
00159 {
00160 t.assoc(monoid_identity.value(), semiring_elt_zero.value());
00161 if (t != null_series)
00162 a.add_series_transition(a.src_of(*e), a.dst_of(*e), t);
00163 a.del_transition(*e);
00164 }
00165 }
00166
00167 if (dir == misc::backward)
00168 backward_remove();
00169 else
00170 forward_remove();
00171 }
00172
00173 private:
00174 void shortest_eps_distance()
00175 {
00176 for_all_const_states(s, a)
00177 {
00178 typename s_shortest_hash::iterator it;
00179 shortest_hash.insert(s_shortest(*s, *s, semiring_elt_one, semiring_elt_one));
00180 squeue.insert(*s);
00181 while (!squeue.empty())
00182 {
00183 hstate_t curr = *squeue.begin();
00184 squeue.erase(squeue.begin());
00185 semiring_elt_t R = semiring_elt_zero;
00186 it = shortest_hash.find(boost::make_tuple(*s, curr));
00187 if (it != shortest_hash.end())
00188 {
00189 R = it->rel;
00190 shortest_hash.modify(it, change_rel(semiring_elt_zero));
00191 }
00192
00193 std::list<htransition_t> transition_list;
00194 a.spontaneous_deltac(transition_list, curr, delta_kind::transitions());
00195 for_all_const_(std::list<htransition_t>, e, transition_list)
00196 {
00197 semiring_elt_t dist = semiring_elt_zero;
00198 it = shortest_hash.find(boost::make_tuple(*s, a.dst_of(*e)));
00199 if (it != shortest_hash.end())
00200 dist = it->dist;
00201 semiring_elt_t we = a.series_of(*e).get(monoid_identity);
00202 we = R * we;
00203 if (dist != dist + we)
00204 {
00205 if (it != shortest_hash.end())
00206 {
00207 shortest_hash.modify(it, add_dr(we, we));
00208 squeue.insert(a.dst_of(*e));
00209 }
00210 else
00211 {
00212 shortest_hash.insert(s_shortest(*s, a.dst_of(*e), we, we));
00213 squeue.insert(a.dst_of(*e));
00214 }
00215 }
00216 }
00217 }
00218 }
00219 }
00220
00221 void backward_remove()
00222 {
00223 std::list<std::pair<htransition_t, semiring_elt_t> > tr_l;
00224 std::list<std::pair<hstate_t, semiring_elt_t> > fin_l;
00225 std::stack<tr_t> tr_st;
00226 std::stack<std::pair<hstate_t, series_set_elt_t> > fin_st;
00227
00228 std::list<htransition_t> transition_list;
00229 for_all_(s_shortest_hash, it, shortest_hash)
00230 if (it->src != it->dst)
00231 {
00232 transition_list.clear();
00233 a.deltac(transition_list, it->dst, delta_kind::transitions());
00234 for_all_const_(std::list<htransition_t>, e, transition_list)
00235 tr_st.push(tr_t(it->src, a.dst_of(*e), it->dist * a.series_of(*e)));
00236 if (a.is_final(it->dst))
00237 fin_st.push(make_pair(it->src, it->dist * a.get_final(it->dst)));
00238 }
00239 else
00240 {
00241 if (it->dist != semiring_elt_one)
00242 {
00243 transition_list.clear();
00244 a.deltac(transition_list, it->dst, delta_kind::transitions());
00245 for_all_const_(std::list<htransition_t>, e, transition_list)
00246 tr_l.push_front(std::pair<htransition_t, semiring_elt_t>(*e, it->dist));
00247 if (a.is_final(it->dst))
00248 fin_l.push_front(std::pair<hstate_t, semiring_elt_t>(it->src, it->dist));
00249 }
00250 }
00251
00252 for (typename std::list<std::pair<htransition_t, semiring_elt_t> >::iterator it = tr_l.begin();
00253 it != tr_l.end(); ++it)
00254 {
00255 series_set_elt_t s = a.series_of(it->first) * it->second;
00256 if (s != null_series)
00257 a.add_series_transition(a.src_of(it->first), a.dst_of(it->first), s);
00258 a.del_transition(it->first);
00259 }
00260
00261 for (typename std::list<std::pair<hstate_t, semiring_elt_t> >::iterator it = fin_l.begin();
00262 it != fin_l.end(); ++it)
00263 a.set_final(it->first, it->second * a.get_final(it->first));
00264
00265 while (!tr_st.empty())
00266 {
00267 a.add_series_transition(tr_st.top().src, tr_st.top().dst, tr_st.top().series);
00268 tr_st.pop();
00269 }
00270
00271 while (!fin_st.empty())
00272 {
00273 a.set_final(fin_st.top().first, a.get_final(fin_st.top().first) +
00274 fin_st.top().second);
00275 fin_st.pop();
00276 }
00277 }
00278
00279 void forward_remove()
00280 {
00281 std::list<std::pair<htransition_t, semiring_elt_t> > tr_l;
00282 std::list<std::pair<hstate_t, semiring_elt_t> > fin_l;
00283 std::stack<tr_t> tr_st;
00284 std::stack<std::pair<hstate_t, series_set_elt_t> > init_st;
00285
00286 std::list<htransition_t> transition_list;
00287 for_all_(s_shortest_hash, it, shortest_hash)
00288 if (it->src != it->dst)
00289 {
00290 transition_list.clear();
00291 a.rdeltac(transition_list, it->src, delta_kind::transitions());
00292 for_all_const_(std::list<htransition_t>, e, transition_list)
00293 tr_st.push(tr_t(a.src_of(*e), it->dst, a.series_of(*e) * it->dist));
00294 if (a.is_initial(it->src))
00295 init_st.push(make_pair(it->dst, a.get_initial(it->src) * it->dist));
00296 }
00297 else
00298 {
00299 if (it->dist != semiring_elt_one)
00300 {
00301 transition_list.clear();
00302 a.rdeltac(transition_list, it->dst, delta_kind::transitions());
00303 for_all_const_(std::list<htransition_t>, e, transition_list)
00304 tr_l.push_front(std::pair<htransition_t, semiring_elt_t>(*e, it->dist));
00305 if (a.is_initial(it->src))
00306 fin_l.push_front(std::pair<hstate_t, semiring_elt_t>(it->dst, it->dist));
00307 }
00308 }
00309
00310 for (typename std::list<std::pair<htransition_t, semiring_elt_t> >::iterator it = tr_l.begin();
00311 it != tr_l.end(); ++it)
00312 {
00313 series_set_elt_t s = a.series_of(it->first) * it->second;
00314 if (s != null_series)
00315 a.add_series_transition(a.src_of(it->first), a.dst_of(it->first), s);
00316 a.del_transition(it->first);
00317 }
00318
00319 for (typename std::list<std::pair<hstate_t, semiring_elt_t> >::iterator it = fin_l.begin();
00320 it != fin_l.end(); ++it)
00321 a.set_initial(it->first, it->second * a.get_initial(it->first));
00322
00323 while (!tr_st.empty())
00324 {
00325 a.add_series_transition(tr_st.top().src, tr_st.top().dst, tr_st.top().series);
00326 tr_st.pop();
00327 }
00328
00329 while (!init_st.empty())
00330 {
00331 a.set_initial(init_st.top().first, a.get_initial(init_st.top().first) +
00332 init_st.top().second);
00333 init_st.pop();
00334 }
00335 }
00336
00337 automaton_t& a;
00338
00339
00340 series_set_elt_t null_series;
00341 semiring_elt_t semiring_elt_zero;
00342 semiring_elt_t semiring_elt_one;
00343 monoid_elt_t monoid_identity;
00344
00345
00346 s_shortest_hash shortest_hash;
00347 std::set<hstate_t> squeue;
00348 };
00349
00350
00351
00352
00353
00354 template<class A_, typename Auto, typename Weight>
00355 void
00356 do_eps_removal_here_sp(const AutomataBase<A_>& a_set,
00357 const Weight&,
00358 Auto& a,
00359 misc::direction_type dir)
00360 {
00361 TIMER_SCOPED("eps_removal");
00362
00363 EpsilonRemoverSp<A_, Auto, Weight> algo(a_set, a);
00364 algo(dir);
00365 }
00366
00367 template<typename A, typename AI>
00368 void
00369 eps_removal_here_sp(Element<A, AI>& a, misc::direction_type dir)
00370 {
00371 typedef Element<A, AI> automaton_t;
00372 AUTOMATON_TYPES(automaton_t);
00373
00374 do_eps_removal_here_sp(a.structure(),
00375 SELECT(semiring_elt_value_t),
00376 a, dir);
00377 }
00378
00379 template<typename A, typename AI>
00380 Element<A, AI>
00381 eps_removal_sp(const Element<A, AI>& a, misc::direction_type dir)
00382 {
00383 typedef Element<A, AI> automaton_t;
00384 AUTOMATON_TYPES(automaton_t);
00385
00386 automaton_t ret(a);
00387 do_eps_removal_here_sp(ret.structure(),
00388 SELECT(semiring_elt_value_t),
00389 ret, dir);
00390 return ret;
00391 }
00392
00393 template<typename A, typename AI>
00394 void
00395 backward_eps_removal_here_sp(Element<A, AI>& a)
00396 {
00397 typedef Element<A, AI> automaton_t;
00398 AUTOMATON_TYPES(automaton_t);
00399
00400 do_eps_removal_here_sp(a.structure(),
00401 SELECT(semiring_elt_value_t),
00402 a, misc::backward);
00403 }
00404
00405 template<typename A, typename AI>
00406 Element<A, AI>
00407 backward_eps_removal_sp(const Element<A, AI>& a)
00408 {
00409 typedef Element<A, AI> automaton_t;
00410 AUTOMATON_TYPES(automaton_t);
00411
00412 automaton_t ret(a);
00413 do_eps_removal_here_sp(ret.structure(),
00414 SELECT(semiring_elt_value_t),
00415 ret, misc::backward);
00416 return ret;
00417 }
00418
00419 template<typename A, typename AI>
00420 void
00421 forward_eps_removal_here_sp(Element<A, AI>& a)
00422 {
00423 typedef Element<A, AI> automaton_t;
00424 AUTOMATON_TYPES(automaton_t);
00425
00426 do_eps_removal_here_sp(a.structure(),
00427 SELECT(semiring_elt_value_t),
00428 a, misc::forward);
00429 }
00430
00431 template<typename A, typename AI>
00432 Element<A, AI>
00433 forward_eps_removal_sp(const Element<A, AI>& a)
00434 {
00435 typedef Element<A, AI> automaton_t;
00436 AUTOMATON_TYPES(automaton_t);
00437
00438 automaton_t ret(a);
00439 do_eps_removal_here_sp(ret.structure(),
00440 SELECT(semiring_elt_value_t),
00441 ret, misc::forward);
00442 return ret;
00443 }
00444
00445 }
00446
00447 #endif // ! VCSN_ALGORITHMS_EPS_REMOVAL_HXX
