Vaucanson  1.4.1
infiltration.hxx
1 // infiltration.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, 2007, 2008, 2011 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_INFILTRATION_HXX
18 # define VCSN_ALGORITHMS_INFILTRATION_HXX
19 
20 # include <set>
21 # include <map>
22 # include <queue>
23 # include <stack>
24 
25 # include <vaucanson/algorithms/infiltration.hh>
26 
27 # ifndef VCSN_NDEBUG
28 # include <vaucanson/algorithms/realtime.hh>
29 # endif // ! VCSN_NDEBUG
30 
31 # include <vaucanson/automata/concept/automata_base.hh>
32 # include <vaucanson/misc/usual_macros.hh>
33 # include <vaucanson/automata/implementation/geometry.hh>
34 # include <vaucanson/misc/static.hh>
35 
36 namespace vcsn
37 {
38 
39 /*--------------------------------.
40 | Functor for infiltration algorithm. |
41 `--------------------------------*/
42 template<typename A, typename T, typename U>
43 class Infiltration
44 {
45  public:
46  typedef AutomataBase<A> structure_t;
47  typedef Element<A, T> lhs_t;
48  typedef Element<A, U> rhs_t;
49  typedef lhs_t output_t;
50  typedef std::map<typename output_t::hstate_t,
51  std::pair<typename lhs_t::hstate_t, typename rhs_t::hstate_t> >
52  pair_map_t;
53 
54  Infiltration (const structure_t& structure,
55  const bool use_geometry)
56  : use_geometry_(use_geometry),
57  series_(structure.series()),
58  monoid_(series_.monoid()),
59  semiring_zero_(series_.semiring().zero(SELECT(semiring_elt_value_t)))
60  {
61  }
62 
63  // returns the infiltration of @c lhs and @c rhs (and put it also in @c output)
64  output_t&
65  operator() (output_t& output,
66  const lhs_t& lhs,
67  const rhs_t& rhs,
68  pair_map_t& m)
69  {
70  BENCH_TASK_SCOPED("infiltration");
71  visited_.clear();
72 
73  precondition(is_realtime(lhs));
74  precondition(is_realtime(rhs));
75 
76  this->initialize_queue(output, lhs, rhs, m);
77 
78  while (not to_process_.empty())
79  {
80  const pair_hstate_t current_pair = to_process_.front();
81  to_process_.pop();
82 
83  const hstate_t lhs_s = current_pair.first;
84  const hstate_t rhs_s = current_pair.second;
85  const hstate_t current_state = visited_[current_pair];
86 
87  output.set_initial(current_state,
88  lhs.get_initial(lhs_s) * rhs.get_initial(rhs_s));
89  output.set_final(current_state,
90  lhs.get_final(lhs_s) * rhs.get_final(rhs_s));
91 
92  for (typename lhs_t::delta_iterator l(lhs.value(), lhs_s);
93  ! l.done();
94  l.next())
95  for (typename rhs_t::delta_iterator r(rhs.value(), rhs_s);
96  ! r.done();
97  r.next())
98  {
99  series_set_elt_t prod_series(series_);
100 
101  if (is_product_not_null(lhs, rhs, l, r, prod_series))
102  {
103  const pair_hstate_t new_pair(lhs.dst_of(*l), rhs.dst_of(*r));
104  typename visited_t::const_iterator found = visited_.find(new_pair);
105 
106  hstate_t dst;
107  if (found == visited_.end())
108  {
109  dst = output.add_state();
110 
111  this->add_state_to_process(output, lhs, rhs, m, dst, new_pair);
112  }
113  else
114  dst = found->second;
115  output.add_series_transition(current_state, dst, prod_series);
116  }
117  }
118  for (typename lhs_t::delta_iterator l(lhs.value(), lhs_s);
119  ! l.done();
120  l.next())
121  {
122  const pair_hstate_t new_pair(lhs.dst_of(*l), rhs_s);
123  typename visited_t::const_iterator found = visited_.find(new_pair);
124 
125  hstate_t dst;
126  if (found == visited_.end())
127  {
128  dst = output.add_state();
129 
130  this->add_state_to_process(output, lhs, rhs, m, dst, new_pair);
131  }
132  else
133  dst = found->second;
134  output.add_series_transition(current_state, dst, lhs.series_of(*l));
135  }
136  for (typename rhs_t::delta_iterator r(rhs.value(), rhs_s);
137  ! r.done();
138  r.next())
139  {
140  const pair_hstate_t new_pair(lhs_s, rhs.dst_of(*r));
141  typename visited_t::const_iterator found = visited_.find(new_pair);
142 
143  hstate_t dst;
144  if (found == visited_.end())
145  {
146  dst = output.add_state();
147 
148  this->add_state_to_process(output, lhs, rhs, m, dst, new_pair);
149  }
150  else
151  dst = found->second;
152  output.add_series_transition(current_state, dst, rhs.series_of(*r));
153  }
154 
155  }
156  merge_transitions(output);
157  return output;
158  }
159 
160  private:
161  //merge transitions with the same ends
162  void merge_transitions(output_t& a)
163  {
164  typedef std::map<hstate_t, series_set_elt_t> map_t;
165  for_all_states(s, a)
166  {
167  map_t map;
168  std::list<htransition_t> transitions;
169  for (delta_iterator e(a.value(), *s); ! e.done(); e.next())
170  {
171  hstate_t target = a.dst_of(*e);
172  transitions.push_back(*e);
173  typename map_t::iterator it = map.find(target);
174  if (it == map.end())
175  map.insert(std::pair<hstate_t, series_set_elt_t>(target,
176  a.series_of(*e)));
177  else
178  it->second += a.series_of(*e);
179  }
180  for_all_(std::list<htransition_t>, e, transitions)
181  a.del_transition(*e);
182  for_all_(map_t, it, map)
183  if(it->second != a.series().zero_)
184  a.add_series_transition(*s, it->first, it->second);
185  }
186  }
187 
188  // Some little graphic tools
189  class grphx
190  {
191  public:
192  template <typename Output, typename Lhs, typename Rhs>
193  static void
194  setcoordfrom (Output& a,
195  const Lhs& lhs,
196  const Rhs& rhs,
197  const typename Output::hstate_t state,
198  const typename Lhs::hstate_t x_state,
199  const typename Rhs::hstate_t y_state)
200  {
201  typename std::map<typename Lhs::hstate_t,
202  typename Lhs::geometry_t::coords_t>::const_iterator iter;
203  typename std::map<typename Rhs::hstate_t,
204  typename Rhs::geometry_t::coords_t>::const_iterator iter2;
205  double x = 0, y = 0;
206 
207  iter = lhs.geometry().states().find(x_state);
208  if (iter != lhs.geometry().states().end())
209  x = iter->second.first;
210 
211  iter2 = rhs.geometry().states().find(y_state);
212  if (iter2 != rhs.geometry().states().end())
213  y = iter2->second.second;
214 
215  a.geometry().states()[state] = std::make_pair(x, y);
216  }
217  private:
218  // Diagonal alignement with a depth-first traversal
219  template<typename I>
220  void
221  align (const I& a)
222  {
223  AUTOMATON_TYPES(I);
224  std::map<hstate_t,bool> visited;
225  std::stack<hstate_t> stack;
226 
227  for_all_const_states(i, a)
228  {
229  visited[*i] = false;
230  // ensure inaccessible states will be visited
231  stack.push(*i);
232  }
233 
234  for_all_const_initial_states(i, a)
235  stack.push(*i);
236 
237  int x = 0;
238  while (!stack.empty())
239  {
240  hstate_t i = stack.top();
241  stack.pop();
242 
243  if (!visited[i])
244  {
245  visited[i] = true;
246 
247  a.geometry()[i] = std::make_pair(x, x);
248  x++;
249 
250  for (delta_iterator j(a.value(), i);
251  ! j.done();
252  j.next())
253  stack.push(a.dst_of(*j));
254  }
255  }
256  }
257 
258  };
259  class no_grphx
260  {
261  public:
262  template <typename Output, typename Lhs, typename Rhs>
263  static void
264  setcoordfrom (Output& a,
265  const Lhs& lhs,
266  const Rhs& rhs,
267  const typename Output::hstate_t state,
268  const typename Lhs::hstate_t x_state,
269  const typename Rhs::hstate_t y_state) {};
270  };
271 
272  // useful typedefs
273  AUTOMATON_TYPES(output_t);
274 
275  typedef std::pair<typename lhs_t::hstate_t, typename rhs_t::hstate_t>
276  pair_hstate_t;
277  typedef std::list<htransition_t> delta_ret_t;
278  typedef std::map<pair_hstate_t, hstate_t> visited_t;
279  typedef typename series_set_elt_t::support_t support_t;
280 
281  // add a @c new_state in the queue
282  inline void
283  add_state_to_process (output_t& output,
284  const lhs_t& lhs,
285  const rhs_t& rhs,
286  pair_map_t& m,
287  const hstate_t& new_state,
288  const pair_hstate_t& new_pair)
289  {
290  m[new_state] = new_pair;
291  visited_[new_pair] = new_state;
292  to_process_.push(new_pair);
293 
294 # define if_(Cond, ThenClause, ElseClause) \
295 misc::static_if_simple<Cond, ThenClause, ElseClause>::t
296 # define eq_(Type1, Type2) \
297 misc::static_eq<Type1, Type2>::value
298 # define DECLARE_GEOMETRY(Type) \
299  typedef geometry<typename Type::hstate_t, typename Type::htransition_t, typename Type::geometry_coords_t> geometry_ ## Type ;
300 
301  DECLARE_GEOMETRY(output_t)
302  DECLARE_GEOMETRY(lhs_t)
303  DECLARE_GEOMETRY(rhs_t)
304  if (use_geometry_)
305  if_(eq_(typename output_t::geometry_t, geometry_output_t) and \
306  eq_(typename rhs_t::geometry_t, geometry_rhs_t) and \
307  eq_(typename lhs_t::geometry_t, geometry_lhs_t), \
308  grphx, no_grphx)
309  ::setcoordfrom(output, lhs, rhs,
310  new_state, new_pair.first, new_pair.second);
311 # undef if_
312 # undef eq_
313  }
314 
315  // initialize queue with all pairs of intials states from @c lhs and @c rhs
316  inline void
317  initialize_queue (output_t& output,
318  const lhs_t& lhs,
319  const rhs_t& rhs,
320  pair_map_t& m)
321  {
322  for_all_const_initial_states(lhs_s, lhs)
323  for_all_const_initial_states(rhs_s, rhs)
324  {
325  const pair_hstate_t new_pair(*lhs_s, *rhs_s);
326  const hstate_t new_state = output.add_state();
327 
328  this->add_state_to_process(output, lhs, rhs, m, new_state, new_pair);
329  }
330  }
331 
332  inline bool
333  is_product_not_null (const lhs_t& lhs,
334  const rhs_t& rhs,
335  const typename lhs_t::delta_iterator& l,
336  const typename rhs_t::delta_iterator& r,
337  series_set_elt_t& prod_series) const
338  {
339  const series_set_elt_t left_series = lhs.series_of(*l);
340  const series_set_elt_t right_series = rhs.series_of(*r);
341 
342  bool prod_is_not_null = false;
343  for_all_(support_t, supp, left_series.supp())
344  {
345  const monoid_elt_t supp_elt (monoid_, *supp);
346  const semiring_elt_t l = left_series.get(supp_elt);
347  const semiring_elt_t r = right_series.get(supp_elt);
348  const semiring_elt_t p = l * r;
349  if (p != semiring_zero_)
350  {
351  prod_series.assoc(*supp, p.value());
352  prod_is_not_null = true;
353  }
354  }
355  return (prod_is_not_null);
356  }
357 
358  // If set to true, <geometry> tags of the result automaton should be filled
359  const bool use_geometry_;
360 
361  // keep traces of new states created
362  visited_t visited_;
363  // @c to_process_ stores all states of output that needs are not
364  std::queue<pair_hstate_t> to_process_;
365 
366  // frequently used objects in computation
367  const series_set_t& series_;
368  const monoid_t& monoid_;
369  // This variable's type must not be set to a reference.
370  const semiring_elt_t semiring_zero_;
371 };
372 
373 /*-----------.
374 | Wrappers. |
375 `-----------*/
376 
377 template<typename A, typename T, typename U>
378 Element<A, T>
379 infiltration (const Element<A, T>& lhs, const Element<A, U>& rhs,
380  std::map<typename T::hstate_t,
381  std::pair<typename T::hstate_t, typename U::hstate_t> >& m,
382  const bool use_geometry)
383 {
384  Element<A, T> ret(rhs.structure());
385  Infiltration<A, T, U> do_infiltration(ret.structure(), use_geometry);
386  return do_infiltration (ret, lhs, rhs, m);
387 }
388 
389 template<typename A, typename T, typename U>
390 Element<A, T>
391 infiltration (const Element<A, T>& lhs, const Element<A, U>& rhs,
392  const bool use_geometry)
393 {
394  std::map<typename T::hstate_t,
395  std::pair<typename T::hstate_t, typename U::hstate_t> > m;
396  return infiltration (lhs, rhs, m, use_geometry);
397 }
398 
399 } // End of namespace vcsn.
400 
401 #endif // ! VCSN_ALGORITHMS_INFILTRATION_HXX
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1