Vcsn  2.3
Be Rational
epsilon-remover.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <stdexcept>
4 #include <type_traits>
5 #include <unordered_map>
6 #include <unordered_set>
7 #include <utility>
8 
9 #include <boost/lexical_cast.hpp>
10 #include <boost/heap/fibonacci_heap.hpp>
11 
12 #include <vcsn/algos/copy.hh>
13 #include <vcsn/algos/dot.hh>
14 #include <vcsn/algos/fwd.hh>
15 #include <vcsn/algos/is-proper.hh>
16 #include <vcsn/core/kind.hh>
17 #include <vcsn/misc/debug-level.hh>
18 #include <vcsn/misc/direction.hh>
20 #include <vcsn/misc/vector.hh> // make_vector
21 
22 #define STATS
23 
24 namespace vcsn
25 {
26  namespace detail
27  {
32  template <Automaton Aut,
33  bool has_one = labelset_t_of<Aut>::has_one()>
35  {
36  using automaton_t = Aut;
39  using weight_t = typename weightset_t::value_t;
43 
46 
47  public:
51  epsilon_remover(automaton_t& aut, bool prune = true)
52  : debug_(debug_level())
53  , aut_(aut)
54  , prune_(prune)
55  {}
56 
58  {
59  auto proper_ctx = make_proper_context(aut_->context());
60  auto res = make_shared_ptr<aut_proper_t>(proper_ctx);
61 
63 
64  copy_into(aut_, res);
65  return res;
66  }
67 
69  {
70  if (!is_proper(aut_))
72  }
73 
105  private:
108  {
109  if (auto p = profile(s))
110  p->update(in(aut_, s, empty_word_).size(),
111  in(aut_, s).size(),
112  out(aut_, s, empty_word_).size(),
113  all_out(aut_, s).size());
114  }
115 
118  void build_heap_()
119  {
120  for (auto s: aut_->states())
121  // We don't care about states without incoming spontaneous
122  // transitions.
123  if (auto in_sp = in(aut_, s, empty_word_).size())
124  {
125  auto ins = in(aut_, s).size();
126  auto out_sp = out(aut_, s, empty_word_).size();
127  auto out = all_out(aut_, s).size();
128  auto h = todo_.emplace(epsilon_profile<state_t>
129  {s, in_sp, ins, out_sp, out});
130  handles_.emplace(s, h);
131  }
132  }
133 
135  void show_heap_() const
136  {
137  const char* sep = "";
138  for (auto i = todo_.ordered_begin(), end = todo_.ordered_end();
139  i != end; ++i)
140  {
141  std::cerr << sep << *i;
142  sep = " > ";
143  }
144  }
145 
149  {
150  if (3 < debug_)
151  {
152  std::cerr << "update heap (" << s << " : ";
153  show_heap_();
154  }
155  auto i = handles_.find(s);
156  if (i != handles_.end())
157  todo_.update(i->second);
158  if (3 < debug_)
159  {
160  std::cerr << ") => ";
161  show_heap_();
162  std::cerr << '\n';
163  }
164  }
165 
166 #ifdef STATS
167  unsigned added_ = 0;
168  unsigned removed_ = 0;
169 #endif
170 
173  {
174  auto i = handles_.find(s);
175  if (i == handles_.end())
176  return nullptr;
177  else
178  return &*i->second;
179  }
180 
193  {
194  // Iterate on a copy, as we remove these transitions in the
195  // loop.
197  // The star of the weight of the loop on 's' (1 if no loop).
198  weight_t star = ws_.one();
199  using state_weight_t = std::pair<state_t, weight_t>;
200  std::vector<state_weight_t> closure;
201  for (auto t : transitions)
202  {
203  weight_t weight = aut_->weight_of(t);
204  state_t src = aut_->src_of(t);
205  if (src == s) //loop
206  star = ws_.star(weight);
207  else
208  closure.emplace_back(src, weight);
209  // Delete incoming epsilon transitions.
210  aut_->del_transition(t);
211  }
212 
213  /*
214  For each transition (t : s -- label|weight --> dst),
215  for each former
216  epsilon transition closure->first -- e|closure->second --> s
217  a transition
218  (closure->first -- label | closure->second*weight --> dst)
219  is added to the automaton (add, not set !!)
220 
221  If (s) is final with weight (weight),
222  for each former
223  epsilon transition closure->first -- e|closure->second --> s
224  pair-second * weight is added to the final weight
225  of closure->first
226  */
227  for (auto t: all_out(aut_, s))
228  {
229  // "Blowing": For each transition (or terminal arrow)
230  // outgoing from (s), the weight is multiplied by
231  // (star).
232  weight_t blow = ws_.mul(star, aut_->weight_of(t));
233  aut_->set_weight(t, blow);
234 
235  label_t label = aut_->label_of(t);
236  state_t dst = aut_->dst_of(t);
237  for (auto pair: closure)
238  {
239  state_t src = pair.first;
240  weight_t w = ws_.mul(pair.second, blow);
241  aut_->add_transition(src, dst, label, w);
242  }
243  }
244 #ifdef STATS
245  unsigned added = all_out(aut_, s).size() * closure.size();
246  unsigned removed = transitions.size();
247 #endif
248  if (prune_ && all_in(aut_, s).empty())
249  {
250 #ifdef STATS
251  removed += all_out(aut_, s).size();
252 #endif
253  aut_->del_state(s);
254  }
255 #ifdef STATS
256  added_ += added;
257  removed_ += removed;
258  if (1 < debug_)
259  std::cerr << " -" << removed << "+" << added
260  << " (-" << removed_ << "+" << added_ << ")";
261 #endif
262  }
263 
277  {
278  build_heap_();
279  /* For each state (s), for each incoming epsilon-transitions
280  (t), if (t) is a loop, the star of its weight is computed,
281  otherwise, (t) is stored into the closure list. Then (t)
282  is removed. */
283 
284  // The neighbors of s: their profiles need to be updated after
285  // s was processed.
286  std::unordered_set<state_t> neighbors;
287  while (!todo_.empty())
288  {
289  if (2 < debug_)
290  {
291  std::cerr << "Before: ";
292  show_heap_();
293  std::cerr << '\n';
294  }
295  auto p = todo_.top();
296  todo_.pop();
297  if (1 < debug_)
298  std::cerr << "Remove: " << p;
299 
300  auto s = p.state;
301  handles_.erase(s);
302  neighbors.clear();
303  for (auto t: in(aut_, s))
304  {
305  state_t n = aut_->src_of(t);
306  if (n != s)
307  neighbors.emplace(n);
308  }
309  for (auto t: out(aut_, s))
310  {
311  state_t n = aut_->dst_of(t);
312  if (n != s)
313  neighbors.emplace(n);
314  }
315 
316  in_situ_remover_(s);
317 
318  // Update all neighbors and then the heap.
319  for (auto n: neighbors)
320  update_profile_(n);
321  for (auto n: neighbors)
322  update_heap_(n);
323  if (1 < debug_)
324  std::cerr << " #tr: "
326  << "/" << aut_->num_transitions() << '\n';
327  if (2 < debug_)
328  {
329  std::cerr << "After: ";
330  show_heap_();
331  std::cerr << '\n';
332  }
333  if (4 < debug_)
334  dot(aut_, std::cerr) << '\n';
335  if (2 < debug_)
336  std::cerr << '\n';
337  }
338 #ifdef STATS
339  if (0 < debug_)
340  std::cerr << "Total transitions -" << removed_
341  << "+" << added_ << '\n';
342 #endif
343  }
344 
350  {
351  size_t res = 0;
352  for (auto t : transitions(aut_))
353  res += aut_->labelset()->is_one(aut_->label_of(t));
354  return res;
355  }
356 
357  private:
359  int debug_;
361  automaton_t aut_;
363  const weightset_t& ws_ = *aut_->weightset();
365  label_t empty_word_ = aut_->labelset()->one();
366 
368  using heap_t = boost::heap::fibonacci_heap<epsilon_profile<state_t>>;
371  std::unordered_map<state_t, typename heap_t::handle_type> handles_;
372 
374  bool prune_;
375  };
376 
377 
378  /*----------------------------------------------.
379  | Specialization when there is no 'one' label. |
380  `----------------------------------------------*/
381 
382  template <Automaton Aut>
383  class epsilon_remover<Aut, false>
384  {
385  using automaton_t = Aut;
387  public:
388  epsilon_remover(automaton_t& aut, bool = true)
389  : aut_(aut)
390  {}
391 
395  {
396  return copy(aut_);
397  }
398 
400  void in_situ_remover() {}
401 
402 
403  private:
404  automaton_t aut_;
405  };
406  }
407 }
value_impl< detail::weight_tag > weight
Definition: fwd.hh:28
void show_heap_() const
Show the heap, for debugging.
labelset_t_of< automaton_t > labelset_t
int debug_
Debug level. The higher, the more details are reported.
#define Automaton
Definition: automaton.hh:23
weightset_t_of< automaton_t > weightset_t
std::vector< typename Cont::value_type > make_vector(const Cont &cont)
The content of cont as a vector.
Definition: vector.hh:20
auto transitions(const Aut &aut) -> decltype(all_transitions(aut, is_special_t< Aut >
All the transition indexes between visible states.
Definition: automaton.hh:226
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
transition_t_of< automaton_t > transition_t
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:113
typename weightset_t::value_t weight_t
aut_proper_t operator()()
Just a copy of the automata in the proper context, since there aren't any transitions to remove...
This class contains the core of the proper algorithm.
epsilon_profile< state_t > * profile(state_t s)
size_t num_spontaneous_transitions_() const
The number of spontaneous transitions in aut_.
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:64
state_t_of< automaton_t > state_t
void in_situ_remover_()
Remove all the states with incoming spontaneous transitions.
static int debug_level()
Debug level set in the user's environment.
Definition: debug-level.hh:11
return res
Definition: multiply.hh:398
bool prune_
Whether to prune states that become inaccessible.
void update_heap_(state_t s)
Update the heap for s.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
value_impl< detail::label_tag > label
Definition: fwd.hh:26
void in_situ_remover()
Nothing to do to remove the transitions in place.
This is used by some epsilon removal algorithms.
auto copy(const AutIn &input, KeepState keep_state, KeepTrans keep_trans) -> decltype(keep_state(input->null_state()), keep_trans(input->null_transition()), make_fresh_automaton< AutIn, AutOut >(input))
A copy of input keeping only its states that are accepted by keep_state, and transitions accepted by ...
Definition: copy.hh:322
boost::heap::fibonacci_heap< epsilon_profile< state_t >> heap_t
Max-heap to decide the order of state-elimination.
epsilon_remover(automaton_t &aut, bool=true)
std::unordered_map< state_t, typename heap_t::handle_type > handles_
Map: state -> heap-handle.
Definition: a-star.hh:8
epsilon_remover(automaton_t &aut, bool prune=true)
Get ready to eliminate spontaneous transitions.
void build_heap_()
Build the profiles and the heap for states with incoming spontaneous transitions. ...
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
typename Aut::element_type::template fresh_automaton_t< Context > fresh_automaton_t_of
Given an automaton type, the type of its copies.
Definition: traits.hh:82
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
Definition: pair.hh:252
void copy_into(const AutIn &in, AutOut &out, KeepState keep_state, KeepTrans keep_trans)
Copy selected states and transitions of an automaton.
Definition: copy.hh:267
fresh_automaton_t_of< automaton_t > aut_proper_t
label_t_of< automaton_t > label_t
void update_profile_(state_t s)
The core of the (backward) epsilon-removal.
auto all_in(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions entering state s.
Definition: automaton.hh:94
const weightset_t & ws_
Shorthand to the weightset.
label_t empty_word_
Shorthand to the empty word.
bool is_proper(const Aut &aut)
Test whether an automaton is proper.
Definition: is-proper.hh:47
automaton_t aut_
The automaton we work on.
std::ostream & dot(const Aut &aut, std::ostream &out=std::cout, format fmt={})
Print an automaton in Graphviz's Dot format.
Definition: dot.hh:377
void in_situ_remover_(state_t s)
For each state (s), for each incoming epsilon-transitions (t), if (t) is a loop, the star of its weig...
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:45
fresh_automaton_t_of< automaton_t, detail::proper_context< context_t_of< automaton_t >>> aut_proper_t
auto make_proper_context(const context< LabelSet, WeightSet > &ctx) -> proper_context< context< LabelSet, WeightSet >>
From a context, its non-nullable context.
Definition: labelset.hh:215