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 if (it != shortest_hash.end())
00205 {
00206 shortest_hash.modify(it, add_dr(we, we));
00207 squeue.insert(a.dst_of(*e));
00208 }
00209 else
00210 {
00211 shortest_hash.insert(s_shortest(*s, a.dst_of(*e), we, we));
00212 squeue.insert(a.dst_of(*e));
00213 }
00214 }
00215 }
00216 }
00217 }
00218
00219 void backward_remove()
00220 {
00221 std::list<std::pair<htransition_t, semiring_elt_t> > tr_l;
00222 std::list<std::pair<hstate_t, semiring_elt_t> > fin_l;
00223 std::stack<tr_t> tr_st;
00224 std::stack<std::pair<hstate_t, series_set_elt_t> > fin_st;
00225
00226 std::list<htransition_t> transition_list;
00227 for_all_(s_shortest_hash, it, shortest_hash)
00228 if (it->src != it->dst)
00229 {
00230 transition_list.clear();
00231 a.deltac(transition_list, it->dst, delta_kind::transitions());
00232 for_all_const_(std::list<htransition_t>, e, transition_list)
00233 tr_st.push(tr_t(it->src, a.dst_of(*e), it->dist * a.series_of(*e)));
00234 if (a.is_final(it->dst))
00235 fin_st.push(make_pair(it->src, it->dist * a.get_final(it->dst)));
00236 }
00237 else
00238 {
00239 if (it->dist != semiring_elt_one)
00240 {
00241 transition_list.clear();
00242 a.deltac(transition_list, it->dst, delta_kind::transitions());
00243 for_all_const_(std::list<htransition_t>, e, transition_list)
00244 tr_l.push_front(std::pair<htransition_t, semiring_elt_t>(*e, it->dist));
00245 if (a.is_final(it->dst))
00246 fin_l.push_front(std::pair<hstate_t, semiring_elt_t>(it->src, it->dist));
00247 }
00248 }
00249
00250 for (typename std::list<std::pair<htransition_t, semiring_elt_t> >::iterator it = tr_l.begin();
00251 it != tr_l.end(); ++it)
00252 {
00253 series_set_elt_t s = a.series_of(it->first) * it->second;
00254 if (s != null_series)
00255 a.add_series_transition(a.src_of(it->first), a.dst_of(it->first), s);
00256 a.del_transition(it->first);
00257 }
00258
00259 for (typename std::list<std::pair<hstate_t, semiring_elt_t> >::iterator it = fin_l.begin();
00260 it != fin_l.end(); ++it)
00261 a.set_final(it->first, it->second * a.get_final(it->first));
00262
00263 while (!tr_st.empty())
00264 {
00265 a.add_series_transition(tr_st.top().src, tr_st.top().dst, tr_st.top().series);
00266 tr_st.pop();
00267 }
00268
00269 while (!fin_st.empty())
00270 {
00271 a.set_final(fin_st.top().first, a.get_final(fin_st.top().first) +
00272 fin_st.top().second);
00273 fin_st.pop();
00274 }
00275 }
00276
00277 void forward_remove()
00278 {
00279 std::list<std::pair<htransition_t, semiring_elt_t> > tr_l;
00280 std::list<std::pair<hstate_t, semiring_elt_t> > fin_l;
00281 std::stack<tr_t> tr_st;
00282 std::stack<std::pair<hstate_t, series_set_elt_t> > init_st;
00283
00284 std::list<htransition_t> transition_list;
00285 for_all_(s_shortest_hash, it, shortest_hash)
00286 if (it->src != it->dst)
00287 {
00288 transition_list.clear();
00289 a.rdeltac(transition_list, it->src, delta_kind::transitions());
00290 for_all_const_(std::list<htransition_t>, e, transition_list)
00291 tr_st.push(tr_t(a.src_of(*e), it->dst, a.series_of(*e) * it->dist));
00292 if (a.is_initial(it->src))
00293 init_st.push(make_pair(it->dst, a.get_initial(it->src) * it->dist));
00294 }
00295 else
00296 {
00297 if (it->dist != semiring_elt_one)
00298 {
00299 transition_list.clear();
00300 a.rdeltac(transition_list, it->dst, delta_kind::transitions());
00301 for_all_const_(std::list<htransition_t>, e, transition_list)
00302 tr_l.push_front(std::pair<htransition_t, semiring_elt_t>(*e, it->dist));
00303 if (a.is_initial(it->src))
00304 fin_l.push_front(std::pair<hstate_t, semiring_elt_t>(it->dst, it->dist));
00305 }
00306 }
00307
00308 for (typename std::list<std::pair<htransition_t, semiring_elt_t> >::iterator it = tr_l.begin();
00309 it != tr_l.end(); ++it)
00310 {
00311 series_set_elt_t s = a.series_of(it->first) * it->second;
00312 if (s != null_series)
00313 a.add_series_transition(a.src_of(it->first), a.dst_of(it->first), s);
00314 a.del_transition(it->first);
00315 }
00316
00317 for (typename std::list<std::pair<hstate_t, semiring_elt_t> >::iterator it = fin_l.begin();
00318 it != fin_l.end(); ++it)
00319 a.set_initial(it->first, it->second * a.get_initial(it->first));
00320
00321 while (!tr_st.empty())
00322 {
00323 a.add_series_transition(tr_st.top().src, tr_st.top().dst, tr_st.top().series);
00324 tr_st.pop();
00325 }
00326
00327 while (!init_st.empty())
00328 {
00329 a.set_initial(init_st.top().first, a.get_initial(init_st.top().first) +
00330 init_st.top().second);
00331 init_st.pop();
00332 }
00333 }
00334
00335 automaton_t& a;
00336
00337
00338 series_set_elt_t null_series;
00339 semiring_elt_t semiring_elt_zero;
00340 semiring_elt_t semiring_elt_one;
00341 monoid_elt_t monoid_identity;
00342
00343
00344 s_shortest_hash shortest_hash;
00345 std::set<hstate_t> squeue;
00346 };
00347
00348
00349
00350
00351
00352 template<class A_, typename Auto, typename Weight>
00353 void
00354 do_eps_removal_here_sp(const AutomataBase<A_>& a_set,
00355 const Weight&,
00356 Auto& a,
00357 misc::direction_type dir)
00358 {
00359 TIMER_SCOPED("eps_removal");
00360
00361 EpsilonRemoverSp<A_, Auto, Weight> algo(a_set, a);
00362 algo(dir);
00363 }
00364
00365 template<typename A, typename T>
00366 void
00367 eps_removal_here_sp(Element<A, T>& a, misc::direction_type dir)
00368 {
00369 typedef Element<A, T> auto_t;
00370 AUTOMATON_TYPES(auto_t);
00371
00372 do_eps_removal_here_sp(a.structure(),
00373 SELECT(semiring_elt_value_t),
00374 a, dir);
00375 }
00376
00377 template<typename A, typename T>
00378 Element<A, T>
00379 eps_removal_sp(const Element<A, T>& a, misc::direction_type dir)
00380 {
00381 typedef Element<A, T> auto_t;
00382 AUTOMATON_TYPES(auto_t);
00383
00384 Element<A, T> ret(a);
00385 do_eps_removal_here_sp(ret.structure(),
00386 SELECT(semiring_elt_value_t),
00387 ret, dir);
00388 return ret;
00389 }
00390
00391 template<typename A, typename T>
00392 void
00393 backward_eps_removal_here_sp(Element<A, T>& a)
00394 {
00395 typedef Element<A, T> auto_t;
00396 AUTOMATON_TYPES(auto_t);
00397
00398 do_eps_removal_here_sp(a.structure(),
00399 SELECT(semiring_elt_value_t),
00400 a, misc::backward);
00401 }
00402
00403 template<typename A, typename T>
00404 Element<A, T>
00405 backward_eps_removal_sp(const Element<A, T>& a)
00406 {
00407 typedef Element<A, T> auto_t;
00408 AUTOMATON_TYPES(auto_t);
00409
00410 Element<A, T> ret(a);
00411 do_eps_removal_here_sp(ret.structure(),
00412 SELECT(semiring_elt_value_t),
00413 ret, misc::backward);
00414 return ret;
00415 }
00416
00417 template<typename A, typename T>
00418 void
00419 forward_eps_removal_here_sp(Element<A, T>& a)
00420 {
00421 typedef Element<A, T> auto_t;
00422 AUTOMATON_TYPES(auto_t);
00423
00424 do_eps_removal_here_sp(a.structure(),
00425 SELECT(semiring_elt_value_t),
00426 a, misc::forward);
00427 }
00428
00429 template<typename A, typename T>
00430 Element<A, T>
00431 forward_eps_removal_sp(const Element<A, T>& a)
00432 {
00433 typedef Element<A, T> auto_t;
00434 AUTOMATON_TYPES(auto_t);
00435
00436 Element<A, T> ret(a);
00437 do_eps_removal_here_sp(ret.structure(),
00438 SELECT(semiring_elt_value_t),
00439 ret, misc::forward);
00440 return ret;
00441 }
00442
00443 }
00444
00445 #endif // ! VCSN_ALGORITHMS_EPS_REMOVAL_HXX
