00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef VCSN_ALGORITHMS_RW_COMPOSITION_HXX
00019 # define VCSN_ALGORITHMS_RW_COMPOSITION_HXX
00020
00021 # include <map>
00022 # include <queue>
00023 # include <set>
00024
00025 # include <vaucanson/algorithms/rw_composition.hh>
00026 # include <vaucanson/automata/concept/transducer.hh>
00027 # include <vaucanson/automata/implementation/geometry.hh>
00028
00029 namespace vcsn {
00030
00031 template<typename U, typename Trans_t>
00032 void
00033 do_rw_composition(const TransducerBase<U>&,
00034 const Trans_t& R,
00035 const Trans_t& S,
00036 Trans_t& T)
00037 {
00038 TIMER_SCOPED("rw_composition");
00039
00040
00041 AUTOMATON_TYPES(Trans_t);
00042 typedef series_set_elt_t exp_t;
00043 typedef typename series_set_elt_t::semiring_elt_t output_exp_t;
00044 typedef std::set<std::pair<hstate_t, output_exp_t> > state_exp_pair_set_t;
00045 typedef typename std::map<hstate_t, typename Trans_t::geometry_t::coords_t>::const_iterator geom_iter_t;
00046 typedef std::pair<hstate_t, hstate_t> state_pair_t;
00047 typedef std::queue<state_pair_t> state_pair_queue_t;
00048 typedef std::map<state_pair_t, hstate_t> state_pair_map_t;
00049 typedef std::set<htransition_t> set_of_transitions_t;
00050
00051
00052 state_pair_queue_t queue;
00053
00054
00055
00056
00057 state_exp_pair_set_t sep_set;
00058
00059
00060
00061
00062 state_pair_map_t Tstates;
00063
00064
00065
00066 double xgeom;
00067 double ygeom;
00068 geom_iter_t iter;
00069
00070
00071
00072
00073
00074
00075 for_all_const_initial_states (p, R)
00076 {
00077
00078 exp_t E = R.get_initial(*p);
00079
00080 for_all_const_initial_states (q, S)
00081 {
00082
00083 exp_t F = S.get_initial(*q);
00084
00085
00086 sep_set.clear();
00087 partial_evaluation(E, S, *q, sep_set);
00088
00089
00090 for_all_const_(state_exp_pair_set_t, ig, sep_set)
00091 {
00092
00093 state_pair_t sp;
00094 sp.first = *p;
00095 sp.second = (*ig).first;
00096
00097
00098 if (Tstates.find(sp) == Tstates.end())
00099 {
00100
00101
00102
00103
00104 hstate_t new_state = T.add_state();
00105
00106
00107 iter = R.geometry().states().find(*p);
00108 if (iter != R.geometry().states().end())
00109 xgeom = (*iter).second.first;
00110 else
00111 xgeom = 0;
00112 iter = S.geometry().states().find(*q);
00113 if (iter != S.geometry().states().end())
00114 ygeom = (*iter).second.second;
00115 else
00116 ygeom = 0;
00117 T.geometry().states()[new_state] = std::make_pair(xgeom, ygeom);
00118
00119
00120 Tstates[sp] = new_state;
00121
00122
00123
00124 T.set_initial(new_state, F * ((*ig).second));
00125
00126
00127 queue.push(sp);
00128 }
00129 else
00130 {
00131
00132
00133 T.set_initial(Tstates[sp],
00134 T.get_initial(Tstates[sp]) + F * ((*ig).second));
00135 }
00136 }
00137 }
00138 }
00139
00140
00141
00142
00143
00144
00145
00146 while (not queue.empty())
00147 {
00148
00149 const state_pair_t sp = queue.front();
00150 queue.pop();
00151
00152 const hstate_t p = sp.first;
00153 const hstate_t q = sp.second;
00154
00155
00156
00157 set_of_transitions_t transitions;
00158 R.deltac(transitions, p, delta_kind::transitions());
00159
00160 for_all_const_(set_of_transitions_t, e, transitions)
00161 {
00162
00163 hstate_t s = R.dst_of(*e);
00164
00165 exp_t E = R.series_of(*e);
00166
00167
00168 assertion(E.supp().size() == 1);
00169 monoid_elt_t x(E.structure().monoid(), *E.supp().begin());
00170
00171
00172 sep_set.clear();
00173 partial_evaluation(E, S, q, sep_set);
00174
00175 for_all_const_(state_exp_pair_set_t, ig, sep_set)
00176 {
00177
00178 state_pair_t sp1;
00179 sp1.first = s;
00180 sp1.second = (*ig).first;
00181
00182
00183 if (Tstates.find(sp1) == Tstates.end())
00184 {
00185
00186
00187
00188
00189 hstate_t new_state = T.add_state();
00190
00191
00192 iter = R.geometry().states().find(sp1.first);
00193 if (iter != R.geometry().states().end())
00194 xgeom = (*iter).second.first;
00195 else
00196 xgeom = 0;
00197 iter = S.geometry().states().find(sp1.second);
00198 if (iter != S.geometry().states().end())
00199 ygeom = (*iter).second.second;
00200 else
00201 ygeom = 0;
00202 T.geometry().states()[new_state] = std::make_pair(xgeom, ygeom);
00203
00204
00205 Tstates[sp1] = new_state;
00206
00207
00208 queue.push(sp1);
00209 }
00210
00211 exp_t Gexp (R.structure().series());
00212 Gexp.assoc(x, (*ig).second);
00213
00214 T.add_series_transition(Tstates[sp], Tstates[sp1], Gexp);
00215 }
00216 }
00217
00218
00219 if (R.is_final(p))
00220 {
00221
00222 sep_set.clear();
00223 partial_evaluation(R.get_final(p), S, q, sep_set);
00224
00225 for_all_const_(state_exp_pair_set_t, ig, sep_set)
00226 {
00227 const hstate_t r = (*ig).first;
00228 if (S.is_final(r))
00229 T.set_final(Tstates[sp], (*ig).second * S.get_final(r));
00230 }
00231 }
00232 }
00233 }
00234
00235
00236
00237
00238
00239 template< typename S, typename T>
00240 void
00241 rw_composition(const Element<S, T>& lhs,
00242 const Element<S, T>& rhs,
00243 Element<S, T>& ret)
00244 {
00245 typedef Element<S, T> auto_t;
00246 AUTOMATON_TYPES(auto_t);
00247 for_all_states (s, ret)
00248 ret.del_state (*s);
00249 do_rw_composition(lhs.structure(), lhs, rhs, ret);
00250 }
00251
00252
00253
00254 template< typename S, typename T>
00255 Element<S, T>
00256 rw_composition(const Element<S, T>& lhs, const Element<S, T>& rhs)
00257 {
00258 Element<S, T> ret (lhs.structure());
00259 do_rw_composition(lhs.structure(), lhs, rhs, ret);
00260 return ret;
00261 }
00262
00263 }
00264
00265 #endif // ! VCSN_ALGORITHMS_RW_COMPOSITION_HXX