Vcsn  2.3a
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:
48 
80  epsilon_remover(automaton_t& aut, bool prune = true)
84  : debug_(debug_level())
85  , aut_(aut)
86  , prune_(prune)
87  {}
88 
90  {
91  auto proper_ctx = make_proper_context(aut_->context());
92  auto res = make_shared_ptr<aut_proper_t>(proper_ctx);
93 
95 
96  copy_into(aut_, res);
97  return res;
98  }
99 
101  {
102  if (!is_proper(aut_))
104  }
105 
106  private:
109  {
110  if (auto p = profile(s))
111  p->update(in(aut_, s, empty_word_).size(),
112  in(aut_, s).size(),
113  out(aut_, s, empty_word_).size(),
114  all_out(aut_, s).size());
115  }
116 
119  void build_heap_()
120  {
121  for (auto s: aut_->states())
122  // We don't care about states without incoming spontaneous
123  // transitions.
124  if (auto in_sp = in(aut_, s, empty_word_).size())
125  {
126  auto ins = in(aut_, s).size();
127  auto out_sp = out(aut_, s, empty_word_).size();
128  auto out = all_out(aut_, s).size();
129  auto h = todo_.emplace(epsilon_profile<state_t>
130  {s, in_sp, ins, out_sp, out});
131  handles_.emplace(s, h);
132  }
133  }
134 
136  void show_heap_() const
137  {
138  const char* sep = "";
139  for (auto i = todo_.ordered_begin(), end = todo_.ordered_end();
140  i != end; ++i)
141  {
142  std::cerr << sep << *i;
143  sep = " > ";
144  }
145  }
146 
150  {
151  if (3 < debug_)
152  {
153  std::cerr << "update heap (" << s << " : ";
154  show_heap_();
155  }
156  auto i = handles_.find(s);
157  if (i != handles_.end())
158  todo_.update(i->second);
159  if (3 < debug_)
160  {
161  std::cerr << ") => ";
162  show_heap_();
163  std::cerr << '\n';
164  }
165  }
166 
167 #ifdef STATS
168  unsigned added_ = 0;
169  unsigned removed_ = 0;
170 #endif
171 
174  {
175  auto i = handles_.find(s);
176  if (i == handles_.end())
177  return nullptr;
178  else
179  return &*i->second;
180  }
181 
194  {
195  // Iterate on a copy, as we remove these transitions in the
196  // loop.
198  // The star of the weight of the loop on 's' (1 if no loop).
199  weight_t star = ws_.one();
200  using state_weight_t = std::pair<state_t, weight_t>;
201  std::vector<state_weight_t> closure;
202  for (auto t : transitions)
203  {
204  weight_t weight = aut_->weight_of(t);
205  state_t src = aut_->src_of(t);
206  if (src == s) //loop
207  star = ws_.star(weight);
208  else
209  closure.emplace_back(src, weight);
210  // Delete incoming epsilon transitions.
211  aut_->del_transition(t);
212  }
213 
214  /*
215  For each transition (t : s -- label|weight --> dst),
216  for each former
217  epsilon transition closure->first -- e|closure->second --> s
218  a transition
219  (closure->first -- label | closure->second*weight --> dst)
220  is added to the automaton (add, not set !!)
221 
222  If (s) is final with weight (weight),
223  for each former
224  epsilon transition closure->first -- e|closure->second --> s
225  pair-second * weight is added to the final weight
226  of closure->first
227  */
228  for (auto t: all_out(aut_, s))
229  {
230  // "Blowing": For each transition (or terminal arrow)
231  // outgoing from (s), the weight is multiplied by
232  // (star).
233  weight_t blow = ws_.mul(star, aut_->weight_of(t));
234  aut_->set_weight(t, blow);
235 
236  label_t label = aut_->label_of(t);
237  state_t dst = aut_->dst_of(t);
238  for (auto pair: closure)
239  {
240  state_t src = pair.first;
241  weight_t w = ws_.mul(pair.second, blow);
242  aut_->add_transition(src, dst, label, w);
243  }
244  }
245 #ifdef STATS
246  unsigned added = all_out(aut_, s).size() * closure.size();
247  unsigned removed = transitions.size();
248 #endif
249  if (prune_ && all_in(aut_, s).empty())
250  {
251 #ifdef STATS
252  removed += all_out(aut_, s).size();
253 #endif
254  aut_->del_state(s);
255  }
256 #ifdef STATS
257  added_ += added;
258  removed_ += removed;
259  if (1 < debug_)
260  std::cerr << " -" << removed << "+" << added
261  << " (-" << removed_ << "+" << added_ << ")";
262 #endif
263  }
264 
278  {
279  build_heap_();
280  /* For each state (s), for each incoming epsilon-transitions
281  (t), if (t) is a loop, the star of its weight is computed,
282  otherwise, (t) is stored into the closure list. Then (t)
283  is removed. */
284 
285  // The neighbors of s: their profiles need to be updated after
286  // s was processed.
287  std::unordered_set<state_t> neighbors;
288  while (!todo_.empty())
289  {
290  if (2 < debug_)
291  {
292  std::cerr << "Before: ";
293  show_heap_();
294  std::cerr << '\n';
295  }
296  auto p = todo_.top();
297  todo_.pop();
298  if (1 < debug_)
299  std::cerr << "Remove: " << p;
300 
301  auto s = p.state;
302  handles_.erase(s);
303  neighbors.clear();
304  for (auto t: in(aut_, s))
305  {
306  state_t n = aut_->src_of(t);
307  if (n != s)
308  neighbors.emplace(n);
309  }
310  for (auto t: out(aut_, s))
311  {
312  state_t n = aut_->dst_of(t);
313  if (n != s)
314  neighbors.emplace(n);
315  }
316 
317  in_situ_remover_(s);
318 
319  // Update all neighbors and then the heap.
320  for (auto n: neighbors)
321  update_profile_(n);
322  for (auto n: neighbors)
323  update_heap_(n);
324  if (1 < debug_)
325  std::cerr << " #tr: "
327  << "/" << aut_->num_transitions() << '\n';
328  if (2 < debug_)
329  {
330  std::cerr << "After: ";
331  show_heap_();
332  std::cerr << '\n';
333  }
334  if (4 < debug_)
335  dot(aut_, std::cerr) << '\n';
336  if (2 < debug_)
337  std::cerr << '\n';
338  }
339 #ifdef STATS
340  if (0 < debug_)
341  std::cerr << "Total transitions -" << removed_
342  << "+" << added_ << '\n';
343 #endif
344  }
345 
351  {
352  size_t res = 0;
353  for (auto t : transitions(aut_))
354  res += aut_->labelset()->is_one(aut_->label_of(t));
355  return res;
356  }
357 
358  private:
360  int debug_;
362  automaton_t aut_;
364  const weightset_t& ws_ = *aut_->weightset();
366  label_t empty_word_ = aut_->labelset()->one();
367 
369  using heap_t = boost::heap::fibonacci_heap<epsilon_profile<state_t>>;
372  std::unordered_map<state_t, typename heap_t::handle_type> handles_;
373 
375  bool prune_;
376  };
377 
378 
379  /*----------------------------------------------.
380  | Specialization when there is no 'one' label. |
381  `----------------------------------------------*/
382 
383  template <Automaton Aut>
384  class epsilon_remover<Aut, false>
385  {
386  using automaton_t = Aut;
388  public:
389  epsilon_remover(automaton_t& aut, bool = true)
390  : aut_(aut)
391  {}
392 
396  {
397  return copy(aut_);
398  }
399 
401  void in_situ_remover() {}
402 
403 
404  private:
405  automaton_t aut_;
406  };
407  }
408 }
automaton_t aut_
The automaton we work on.
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
aut_proper_t operator()()
Just a copy of the automata in the proper context, since there aren't any transitions to remove...
void show_heap_() const
Show the heap, for debugging.
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:84
int debug_
Debug level. The higher, the more details are reported.
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:65
Definition: a-star.hh:8
bool is_proper(const Aut &aut)
Test whether an automaton is proper.
Definition: is-proper.hh:47
return res
Definition: multiply.hh:398
weightset_t_of< automaton_t > weightset_t
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:217
transition_t_of< automaton_t > transition_t
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
void in_situ_remover()
Nothing to do to remove the transitions in place.
This is used by some epsilon removal algorithms.
labelset_t_of< automaton_t > labelset_t
typename weightset_t::value_t weight_t
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
size_t num_spontaneous_transitions_() const
The number of spontaneous transitions in aut_.
epsilon_remover(automaton_t &aut, bool prune=true)
The core of the (backward) epsilon-removal.
state_t_of< automaton_t > state_t
bool prune_
Whether to prune states that become inaccessible.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
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:246
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
label_t_of< automaton_t > label_t
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
Definition: pair.hh:252
auto all_in(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions entering state s.
Definition: automaton.hh:114
epsilon_profile< state_t > * profile(state_t s)
void update_heap_(state_t s)
Update the heap for s.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
std::ostream & dot(const Aut &aut, std::ostream &out=std::cout, format fmt={}, bool mathjax=false)
Print an automaton in Graphviz's Dot format.
Definition: dot.hh:395
boost::heap::fibonacci_heap< epsilon_profile< state_t >> heap_t
Max-heap to decide the order of state-elimination.
void build_heap_()
Build the profiles and the heap for states with incoming spontaneous transitions. ...
void update_profile_(state_t s)
Update the profile of s.
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
value_impl< detail::label_tag > label
Definition: fwd.hh:26
fresh_automaton_t_of< automaton_t > aut_proper_t
label_t empty_word_
Shorthand to the empty word.
std::unordered_map< state_t, typename heap_t::handle_type > handles_
Map: state -> heap-handle.
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...
value_impl< detail::weight_tag > weight
Definition: fwd.hh:28
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:133
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
#define Automaton
Definition: automaton.hh:23
This class contains the core of the proper algorithm.
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
const weightset_t & ws_
Shorthand to the weightset.
epsilon_remover(automaton_t &aut, bool=true)
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62