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 <queue>
00033 # include <map>
00034 # include <utility>
00035 # include <set>
00036
00037 namespace vcsn {
00038
00039
00040
00041
00042
00043 template
00044 <class A_, typename Auto, typename Weight>
00045 class EpsilonRemoverSp
00046 {
00047 AUTOMATON_TYPES(Auto);
00048 public:
00049 struct s_shortest
00050 {
00051 s_shortest(const hstate_t src_, const hstate_t dst_, semiring_elt_t& d_, semiring_elt_t& r_)
00052 : src(src_),
00053 dst(dst_),
00054 dist(d_),
00055 rel(r_)
00056 {}
00057
00058 const hstate_t src;
00059 const hstate_t dst;
00060 semiring_elt_t dist;
00061 semiring_elt_t rel;
00062 };
00063
00064 struct change_rel
00065 {
00066 change_rel(const semiring_elt_t& new_rel)
00067 : new_rel(new_rel)
00068 {}
00069
00070 void operator() (s_shortest& s)
00071 {
00072 s.rel = new_rel;
00073 }
00074 private:
00075 semiring_elt_t new_rel;
00076 };
00077
00078 struct change_dist
00079 {
00080 change_dist(const semiring_elt_t& new_dist)
00081 : new_dist(new_dist)
00082 {}
00083
00084 void operator() (s_shortest& s)
00085 {
00086 s.dist = new_dist;
00087 }
00088 private:
00089 semiring_elt_t new_dist;
00090 };
00091
00092 struct add_dr
00093 {
00094 add_dr(const semiring_elt_t& new_dist, const semiring_elt_t& new_rel)
00095 : new_dist(new_dist),
00096 new_rel(new_rel)
00097 {}
00098
00099 void operator() (s_shortest& s)
00100 {
00101 s.dist += new_dist;
00102 s.rel += new_rel;
00103 }
00104 private:
00105 semiring_elt_t new_dist;
00106 semiring_elt_t new_rel;
00107 };
00108
00109 typedef boost::multi_index_container
00110 <
00111 s_shortest,
00112 boost::multi_index::indexed_by
00113 <
00114 boost::multi_index::hashed_unique
00115 <
00116 boost::multi_index::composite_key
00117 <
00118 s_shortest,
00119 BOOST_MULTI_INDEX_MEMBER(s_shortest, const hstate_t, src),
00120 BOOST_MULTI_INDEX_MEMBER(s_shortest, const hstate_t, dst)
00121 >
00122 >
00123 >
00124 > s_shortest_hash;
00125
00126 EpsilonRemoverSp(const AutomataBase<A_>&,
00127 Auto& aut)
00128 : a(aut),
00129 null_series(aut.series().zero_),
00130 semiring_elt_zero(aut.series().semiring().wzero_),
00131 semiring_elt_one(aut.series().semiring().wone_),
00132 monoid_identity(aut.series().monoid().vcsn_empty)
00133 {
00134 shortest_eps_distance();
00135 }
00136
00137 void operator() (misc::direction_type dir)
00138 {
00139 if (dir == misc::backward)
00140 backward_remove();
00141 else
00142 forward_remove();
00143 }
00144
00145 private:
00146 void shortest_eps_distance()
00147 {
00148 for_all_states(s, a)
00149 {
00150 typename s_shortest_hash::iterator it;
00151 shortest_hash.insert(s_shortest(*s, *s, semiring_elt_one, semiring_elt_one));
00152 squeue.insert(*s);
00153 while (!squeue.empty())
00154 {
00155 hstate_t curr = *squeue.begin();
00156 squeue.erase(squeue.begin());
00157 semiring_elt_t R = semiring_elt_zero;
00158 it = shortest_hash.find(boost::make_tuple(*s, curr));
00159 if (it != shortest_hash.end())
00160 {
00161 R = it->rel;
00162 shortest_hash.modify(it, change_rel(semiring_elt_zero));
00163 }
00164
00165 std::list<htransition_t> transition_list;
00166 a.spontaneous_deltac(transition_list, curr, delta_kind::transitions());
00167 for_all_const_(std::list<htransition_t>, e, transition_list)
00168 {
00169 semiring_elt_t dist = semiring_elt_zero;
00170 it = shortest_hash.find(boost::make_tuple(*s, a.dst_of(*e)));
00171 if (it != shortest_hash.end())
00172 dist = it->dist;
00173 semiring_elt_t we = a.series_of(*e).get(monoid_identity);
00174 we = R * we;
00175 if (dist != dist + we)
00176 if (it != shortest_hash.end())
00177 {
00178 shortest_hash.modify(it, add_dr(we, we));
00179 squeue.insert(a.dst_of(*e));
00180 }
00181 else
00182 {
00183 shortest_hash.insert(s_shortest(*s, a.dst_of(*e), we, we));
00184 squeue.insert(a.dst_of(*e));
00185 }
00186 }
00187
00188
00189 }
00190 }
00191 }
00192
00193 void backward_remove()
00194 {
00195
00196
00197 for_all_transitions(e,a)
00198 {
00199 series_set_elt_t t = a.series_of(*e);
00200 if (t.get(monoid_identity) != semiring_elt_zero)
00201 {
00202 t.assoc(monoid_identity.value(), semiring_elt_zero.value());
00203 if (t != null_series)
00204 a.add_series_transition(a.src_of(*e), a.dst_of(*e), t);
00205 a.del_transition(*e);
00206 }
00207 }
00208 std::map<hstate_t, series_set_elt_t> state_to_wfinal;
00209 for_all_states(s, a)
00210 state_to_wfinal.insert(std::make_pair(*s, a.get_final(*s)));
00211 a.clear_final();
00212
00213
00214 for_all_states(s, a)
00215 {
00216 std::list<htransition_t> transition_list;
00217 a.rdeltac(transition_list, *s, delta_kind::transitions());
00218 for_all_const_(std::list<htransition_t>, e, transition_list)
00219 {
00220 series_set_elt_t t = a.series_of(*e);
00221 for_all_states(s1, a)
00222 {
00223 typename s_shortest_hash::iterator it = shortest_hash.find(boost::make_tuple(*s1, a.src_of(*e)));
00224 if (it != shortest_hash.end() && it->dist != semiring_elt_zero)
00225 a.add_series_transition(*s1, *s, it->dist * t);
00226 }
00227 a.del_transition(*e);
00228 }
00229 series_set_elt_t tw = null_series;
00230 for_all_states(s1, a)
00231 {
00232 typename s_shortest_hash::iterator it = shortest_hash.find(boost::make_tuple(*s, *s1));
00233 if (it != shortest_hash.end())
00234 tw += it->dist * state_to_wfinal.find(*s1)->second;
00235 }
00236 if (tw != null_series)
00237 a.set_final(*s, tw);
00238 }
00239 }
00240
00241 void forward_remove()
00242 {
00243
00244
00245 for_all_transitions(e,a)
00246 {
00247 series_set_elt_t t = a.series_of(*e);
00248 if (t.get(monoid_identity) != semiring_elt_zero)
00249 {
00250 t.assoc(monoid_identity.value(), semiring_elt_zero.value());
00251 if (t != null_series)
00252 a.add_series_transition(a.src_of(*e), a.dst_of(*e), t);
00253 a.del_transition(*e);
00254 }
00255 }
00256 std::map<hstate_t, series_set_elt_t> state_to_winitial;
00257 for_all_states(s, a)
00258 state_to_winitial.insert(std::make_pair(*s, a.get_initial(*s)));
00259 a.clear_final();
00260
00261
00262 for_all_states(s, a)
00263 {
00264 std::list<htransition_t> transition_list;
00265 a.deltac(transition_list, *s, delta_kind::transitions());
00266 for_all_const_(std::list<htransition_t>, e, transition_list)
00267 {
00268 series_set_elt_t t = a.series_of(*e);
00269 for_all_states(s1, a)
00270 {
00271 typename s_shortest_hash::iterator it = shortest_hash.find(boost::make_tuple(a.dst_of(*e), *s1));
00272 if (it != shortest_hash.end() && it->dist != semiring_elt_zero)
00273 a.add_series_transition(*s, *s1, it->dist * t);
00274 }
00275 a.del_transition(*e);
00276 }
00277 series_set_elt_t tw = null_series;
00278 for_all_states(s1, a)
00279 {
00280 typename s_shortest_hash::iterator it = shortest_hash.find(boost::make_tuple(*s1, *s));
00281 if (it != shortest_hash.end())
00282 tw += it->dist * state_to_winitial.find(*s1)->second;
00283 }
00284 if (tw != null_series)
00285 a.set_initial(*s, tw);
00286 }
00287 }
00288
00289 automaton_t& a;
00290
00291
00292 series_set_elt_t null_series;
00293 semiring_elt_t semiring_elt_zero;
00294 semiring_elt_t semiring_elt_one;
00295 monoid_elt_t monoid_identity;
00296
00297
00298 s_shortest_hash shortest_hash;
00299 std::set<hstate_t> squeue;
00300 };
00301
00302
00303
00304
00305
00306 template<class A_, typename Auto, typename Weight>
00307 void
00308 do_eps_removal_here_sp(const AutomataBase<A_>& a_set,
00309 const Weight&,
00310 Auto& a,
00311 misc::direction_type dir)
00312 {
00313 TIMER_SCOPED("eps_removal");
00314
00315 EpsilonRemoverSp<A_, Auto, Weight> algo(a_set, a);
00316 algo(dir);
00317 }
00318
00319 template<typename A, typename T>
00320 void
00321 eps_removal_here_sp(Element<A, T>& a, misc::direction_type dir)
00322 {
00323 typedef Element<A, T> auto_t;
00324 AUTOMATON_TYPES(auto_t);
00325
00326 do_eps_removal_here(a.structure(),
00327 SELECT(semiring_elt_value_t),
00328 a, dir);
00329 }
00330
00331 template<typename A, typename T>
00332 Element<A, T>
00333 eps_removal_sp(const Element<A, T>& a, misc::direction_type dir)
00334 {
00335 typedef Element<A, T> auto_t;
00336 AUTOMATON_TYPES(auto_t);
00337
00338 Element<A, T> ret(a);
00339 do_eps_removal_here(ret.structure(),
00340 SELECT(semiring_elt_value_t),
00341 ret, dir);
00342 return ret;
00343 }
00344
00345 template<typename A, typename T>
00346 void
00347 backward_eps_removal_here_sp(Element<A, T>& a)
00348 {
00349 typedef Element<A, T> auto_t;
00350 AUTOMATON_TYPES(auto_t);
00351
00352 do_eps_removal_here(a.structure(),
00353 SELECT(semiring_elt_value_t),
00354 a, misc::backward);
00355 }
00356
00357 template<typename A, typename T>
00358 Element<A, T>
00359 backward_eps_removal_sp(const Element<A, T>& a)
00360 {
00361 typedef Element<A, T> auto_t;
00362 AUTOMATON_TYPES(auto_t);
00363
00364 Element<A, T> ret(a);
00365 do_eps_removal_here(ret.structure(),
00366 SELECT(semiring_elt_value_t),
00367 ret, misc::backward);
00368 return ret;
00369 }
00370
00371 template<typename A, typename T>
00372 void
00373 forward_eps_removal_here_sp(Element<A, T>& a)
00374 {
00375 typedef Element<A, T> auto_t;
00376 AUTOMATON_TYPES(auto_t);
00377
00378 do_eps_removal_here(a.structure(),
00379 SELECT(semiring_elt_value_t),
00380 a, misc::forward);
00381 }
00382
00383 template<typename A, typename T>
00384 Element<A, T>
00385 forward_eps_removal_sp(const Element<A, T>& a)
00386 {
00387 typedef Element<A, T> auto_t;
00388 AUTOMATON_TYPES(auto_t);
00389
00390 Element<A, T> ret(a);
00391 do_eps_removal_here(ret.structure(),
00392 SELECT(semiring_elt_value_t),
00393 ret, misc::forward);
00394 return ret;
00395 }
00396
00397 }
00398
00399 #endif // ! VCSN_ALGORITHMS_EPS_REMOVAL_HXX