Vaucanson  1.4.1
evaluation.hxx
1 // evaluation.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2009 The Vaucanson Group.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // The complete GNU General Public Licence Notice can be found as the
13 // `COPYING' file in the root directory.
14 //
15 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
16 //
17 #ifndef VCSN_ALGORITHMS_EVALUATION_HXX
18 # define VCSN_ALGORITHMS_EVALUATION_HXX
19 
20 # include <vaucanson/algorithms/internal/evaluation.hh>
21 
22 # include <vaucanson/misc/usual_macros.hh>
23 # include <vaucanson/automata/concept/transducer_base.hh>
24 
25 // FIXME: check dead code
26 //# include <vaucanson/algorithms/standard.hh>
27 
28 # include <vaucanson/algorithms/standard_of.hh>
29 
30 // Required by DefaultChooser.
31 # include <vaucanson/algorithms/aut_to_exp.hh>
32 
33 # include <vaucanson/algorithms/extension.hh>
34 # include <vaucanson/algorithms/product.hh>
35 # include <vaucanson/algorithms/trim.hh>
36 # include <vaucanson/algorithms/image.hh>
37 
38 namespace vcsn
39 {
40  template<typename SS, typename SM, typename V,
41  typename Series_t, typename Trans_t,
42  typename M>
43  void
44  do_partial_evaluation(const algebra::Series<SS, SM>&,
45  const Series_t& E,
46  const TransducerBase<V>&,
47  const Trans_t& S,
48  const typename Trans_t::hstate_t& p,
49  M& res)
50  {
51  // Type helpers.
52  typedef typename Trans_t::value_t W;
53  typedef typename output_projection_helper<V, W>::ret Auto_t;
54  AUTOMATON_TYPES(Auto_t);
55  AUTOMATON_TYPES_(Trans_t, t_);
56  typedef typename Auto_t::set_t Auto_set_t;
57  typedef typename Auto_set_t::series_set_t Auto_series_set_t;
58  typedef series_set_elt_t exp_t;
59  typedef t_series_set_elt_t t_exp_t;
60  typedef std::map<t_hstate_t, std::pair<t_hstate_t, t_hstate_t> >
61  state_pair_map_t;
62  typedef std::map<t_hstate_t, hstate_t> state_state_map_t;
63  typedef std::pair<t_hstate_t, exp_t> se_pair_t;
64  Auto_set_t auto_structure(Auto_series_set_t(S.structure().series().semiring()));
65 
66  //
67  // Part 1.
68  // Construct A = standard_of(E).
69  //
70 
71  // Hold standard_of(E).
72  Auto_t A(auto_structure);
73  standard_of(A, E.value());
74 
75  //
76  // Part 2.
77  // Sp construction.
78  //
79 
80  // Does a copy of S,
81  Trans_t Sp = S;
82  state_state_map_t Sp_to_S;
83  for_all_const_states_(t_, q, Sp)
84  {
85  hstate_t pSp = Sp_to_S[*q] = S.get_state(size_t(*q));
86  if (pSp == p)
87  Sp.set_initial(*q);
88  else
89  Sp.unset_initial(*q);
90  }
91 
92  //
93  // evaluation(A, Sp)
94  // Evaluation: we keep some information for later.
95  //
96 
97  // extension
98  Trans_t tmp_trans(Sp.structure());
99  tmp_trans = extension(A, Sp);
100 
101  // product
102  Trans_t pro(Sp.structure());
103  state_pair_map_t sp_m;
104  pro = product(tmp_trans, Sp, sp_m);
105 
106  // build map we will reuse later
107  std::map<typename Trans_t::hstate_t, typename Trans_t::hstate_t> states_map_for_sp_m;
108  for_all_iterator (typename state_pair_map_t::iterator, i, sp_m)
109  states_map_for_sp_m.insert(std::make_pair(pro.get_state(size_t(i->first)), i->first));
110 
111  // image
112  Auto_t G(auto_structure);
113  state_state_map_t proj_m;
114  G = image(pro, proj_m);
115 
116  std::map<typename Trans_t::hstate_t, typename Trans_t::hstate_t> states_map_for_proj_m;
117  for_all_iterator (typename state_state_map_t::iterator, i, proj_m)
118  states_map_for_proj_m.insert(std::make_pair(G.get_state(size_t(i->first)), i->first));
119 
120  // add i state
121  const hstate_t i = G.add_state();
122  for_all_const_initial_states(r, G)
123  {
124  exp_t old_label = G.get_initial(*r);
125  G.add_series_transition(i, *r, old_label);
126  G.unset_initial(*r);
127  }
128  G.set_initial(i);
129 
130  //
131  // Part 3.
132  // Initialize map.
133  //
134 
135  G.clear_final();
136  state_state_map_t state_of, is_state_of;
137  for_all_const_states_(t_, u, Sp)
138  {
139  hstate_t new_state = G.add_state();
140  state_of[*u] = new_state;
141  is_state_of[new_state] = *u;
142  G.set_final(new_state);
143  }
144 
145  //
146  // Part 4.
147  // Create spontaneous transitions.
148  //
149 
150  for_all_const_states(ig, G)
151  {
152  if (*ig != i && !G.is_final(*ig))
153  {
154  t_hstate_t t = sp_m[states_map_for_sp_m[proj_m[states_map_for_proj_m[*ig]]]].first;
155  t_hstate_t u = sp_m[states_map_for_sp_m[proj_m[states_map_for_proj_m[*ig]]]].second;
156 
157  if (tmp_trans.is_final(t))
158  G.add_spontaneous(*ig, state_of[u]);
159  }
160  }
161 
162  //
163  // Part 5.
164  // Construct the output map.
165  //
166 
167  M se;
168  partial_elimination(G, se);
169 
170  for_all_(M, p, se)
171  {
172  se_pair_t my_pair = std::make_pair(Sp_to_S[is_state_of[(*p).first]], p->second);
173  res.insert(my_pair);
174  }
175  }
176 
177  template <typename S1, typename T1,
178  typename S2, typename T2,
179  typename M>
180  void
181  partial_evaluation(const Element<S1, T1>& E,
182  const Element<S2, T2>& S,
183  const typename Element<S2, T2>::hstate_t& p,
184  M& res)
185  {
186  do_partial_evaluation(E.structure(), E, S.structure(), S, p, res);
187  }
188 
189  template<typename S, typename Auto_t, typename M, typename Chooser_t>
190  void
191  do_partial_elimination(const AutomataBase<S>&,
192  const Auto_t& a,
193  Chooser_t chooser,
194  M& state_exp_pair_set)
195  {
196  AUTOMATON_TYPES(Auto_t);
197  typedef typename std::set<htransition_t> htransition_set_t;
198  typedef typename Auto_t::hstate_t hstate_t;
199  typedef std::map<hstate_t, series_set_elt_t> sums_t;
200 
201  typename htransition_set_t::const_iterator i, j;
202  hstate_t q;
203  htransition_set_t transitions;
204 
205  Auto_t b = a;
206 
207  // Save a map linking hstates between automata a and b.
208  // This is needed to be able to fill state_exp_pair_set with correct hstates.
209  std::map<hstate_t, hstate_t> states_map;
210  for (state_iterator i = a.states().begin(), j = b.states().begin(),
211  end_ = a.states().end();
212  i != end_;
213  ++i, ++j)
214  states_map.insert(std::make_pair(*j, *i));
215 
216  // FIXME: check dead code
217 // standardize(b);
218 
219  // all final states and the initial state.
220  int num = b.final().size() + b.initial().size();
221 
222  while (int(b.states().size()) != num)
223  {
224  series_set_elt_t loop_sum(b.series());
225  sums_t in_sums, out_sums;
226  typename sums_t::iterator f;
227  q = chooser(b);
228  if (b.is_initial(q) || b.is_final(q))
229  continue;
230 
231  transitions.clear();
232  for (delta_iterator e(b.value(), q); ! e.done(); e.next())
233  transitions.insert(*e);
234  for (i = transitions.begin(); i != transitions.end(); i = j)
235  {
236  j = i; ++j;
237 
238  if (b.dst_of(*i) == q)
239  loop_sum += b.series_of(*i);
240  else if ((f = out_sums.find(b.dst_of(*i))) !=
241  out_sums.end())
242  f->second += b.series_of(*i);
243  else
244  out_sums.insert(std::make_pair(b.dst_of(*i), b.series_of(*i)));
245  b.del_transition(*i);
246  }
247  transitions.clear();
248  for (rdelta_iterator e(b.value(), q); ! e.done(); e.next())
249  transitions.insert(*e);
250  for (i = transitions.begin(); i != transitions.end(); i = j)
251  {
252  j = i; ++j;
253  // here all loops have already been removed
254  if ((f = in_sums.find(b.src_of(*i))) !=
255  in_sums.end())
256  f->second += b.series_of(*i);
257  else
258  in_sums.insert(std::make_pair(b.src_of(*i), b.series_of(*i)));
259  b.del_transition(*i);
260  }
261  loop_sum.star();
262  for_all_const_(sums_t, in, in_sums)
263  for_all_const_(sums_t, out, out_sums)
264  {
265  series_set_elt_t res = in->second * loop_sum * out->second;
266  b.add_series_transition(in->first, out->first, res);
267  }
268  b.del_state(q);
269  }
270 
271  typedef std::map<hstate_t, series_set_elt_t> se_map_t;
272  typedef std::pair<hstate_t, series_set_elt_t> state_exp_pair_t;
273  se_map_t se_m;
274 
275  // maybe there are more than one transition comming to one final state
276  // we must sum the labels
277  for_all_transitions(e, b)
278  {
279  hstate_t dst = b.dst_of(*e);
280  typename se_map_t::iterator i = se_m.find(dst);
281  if (i == se_m.end())
282  se_m.insert(std::make_pair(dst,
283  series_set_elt_t (b.structure().series(),
284  b.label_of(*e))));
285  else
286  i->second += b.label_of(*e);
287  }
288 
289  for_all_final_states(p, b)
290  {
291  typename se_map_t::iterator i = se_m.find(*p);
292  if (i != se_m.end())
293  state_exp_pair_set.insert(std::make_pair(states_map[*p], i->second));
294  }
295  }
296 
297  /*------------.
298  | elimination |
299  `------------*/
300  // FIXME: add the generalized automaton precondition
301  // preconditions :
302  // - hope that automaton's labels are sufficient to support "star"
303  // => in fact, generalized automaton are generally expected here.
304  template<typename A, typename T, typename M>
305  void
306  partial_elimination(const Element<A, T>& a,
307  M& state_exp_pair_set)
308  {
309  do_partial_elimination(a.structure(),
310  a,
311  DefaultChooser(),
312  state_exp_pair_set);
313  }
314 
315 } // ! vcsn
316 
317 #endif // ! VCSN_ALGORITHMS_EVALUATION_HXX
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1