Vcsn  2.3
Be Rational
epsilon-remover-separate.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 #include <vector>
9 
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/core/kind.hh>
16 #include <vcsn/misc/debug-level.hh>
17 #include <vcsn/misc/direction.hh>
19 #include <vcsn/misc/vector.hh> // make_vector
20 
21 #define STATS
22 
23 namespace vcsn
24 {
25  namespace detail
26  {
31  template <Automaton Aut,
32  bool has_one = labelset_t_of<Aut>::has_one()>
34  {
35  using automaton_t = std::remove_cv_t<Aut>;
37  using weight_t = typename weightset_t::value_t;
39 
46 
53 
54  public:
58  epsilon_remover_separate(const automaton_t& aut, bool prune = true)
59  : debug_(debug_level())
60  , ws_(*aut->weightset())
61  , prune_(prune)
62  , d2p_(states_size(aut),
63  aut_proper_t::element_type::null_state())
64  , p2d_(states_size(aut),
65  aut_dirty_t::element_type::null_state())
66  {
67  auto dirty_ctx = dirty_ctx_t{{}, ws_};
68  auto proper_ctx = make_proper_context(aut->context());
69  aut_dirty_ = make_shared_ptr<aut_dirty_t>(dirty_ctx);
70  aut_proper_ = make_shared_ptr<aut_proper_t>(proper_ctx);
71 
72  auto pcopier = make_copier(aut, aut_proper_);
73  auto dcopier = make_copier(aut, aut_dirty_);
74 
75  using state_t = state_t_of<automaton_t>;
76  using transition_t = transition_t_of<automaton_t>;
77  pcopier([](state_t) { return true; },
78  [&aut](transition_t t) {
79  return !aut->labelset()->is_one(aut->label_of(t));
80  }
81  );
82  dcopier([&aut](state_t s) {
83  return (!in(aut, s, aut->labelset()->one()).empty()
84  || !out(aut, s, aut->labelset()->one()).empty());
85  },
86  [&aut](transition_t t) {
87  return aut->labelset()->is_one(aut->label_of(t));
88  }
89  );
90 
91  const auto& dorigins = dcopier.state_map();
92  const auto& porigins = pcopier.state_map();
93  for (const auto& dp : dorigins)
94  {
95  auto pp = porigins.find(dp.first);
96  assert(pp != porigins.end());
97  d2p_[dp.second] = pp->second;
98  p2d_[pp->second] = dp.second;
99  }
100  }
101 
102  private:
105 
108  {
109  auto dirty_s = p2d_[proper_s];
110  if (auto p = profile_(proper_s))
111  {
112  auto in_dirty = in(aut_dirty_, dirty_s).size();
113  auto in_proper = in(aut_proper_, proper_s).size();
114  auto out_dirty = out(aut_dirty_, dirty_s).size();
115  auto out_proper = all_out(aut_proper_, proper_s).size();
116 
117  p->update(in_dirty, in_proper + in_dirty,
118  out_dirty, out_proper + out_dirty);
119  }
120  }
121 
124  void build_heap_()
125  {
126  for (auto s: aut_dirty_->states())
127  // We don't care about states without incoming spontaneous
128  // transitions.
129  if (in(aut_dirty_, s).size())
130  {
131  auto proper_s = d2p_[s];
132  auto h = todo_.emplace(profile_t{proper_s, 0, 0, 0, 0});
133  handles_.emplace(proper_s, h);
134  update_profile_(proper_s);
135  }
136  }
137 
139  void show_heap_() const
140  {
141  const char* sep = "";
142  for (auto i = todo_.ordered_begin(), end = todo_.ordered_end();
143  i != end; ++i)
144  {
145  std::cerr << sep << *i;
146  sep = " > ";
147  }
148  }
149 
153  {
154  if (3 < debug_)
155  {
156  std::cerr << "update heap (" << s << " : ";
157  show_heap_();
158  }
159  auto i = handles_.find(s);
160  if (i != handles_.end())
161  todo_.update(i->second);
162  if (3 < debug_)
163  {
164  std::cerr << ") => ";
165  show_heap_();
166  std::cerr << '\n';
167  }
168  }
169 
170 #ifdef STATS
171  unsigned added_ = 0;
172  unsigned removed_ = 0;
173 #endif
174 
178  {
179  auto i = handles_.find(s);
180  if (i == handles_.end())
181  return nullptr;
182  else
183  return &*i->second;
184  }
185 
197  void remover_on(state_proper_t proper_s, state_dirty_t dirty_s)
198  {
199  // The star of the weight of the loop on 's' (1 if no loop).
200  weight_t star = ws_.one();
201  using state_weight_t = std::pair<state_dirty_t, weight_t>;
202  auto closure = std::vector<state_weight_t>{};
203 
204 #ifdef STATS
205  // Number of transitions that will be removed.
206  auto removed = in(aut_dirty_, dirty_s).size();
207 #endif
208  // Iterate on a copy: we remove these transitions in the loop.
209  for (auto t : make_vector(in(aut_dirty_, dirty_s)))
210  {
211  weight_t weight = aut_dirty_->weight_of(t);
212  auto src = aut_dirty_->src_of(t);
213  if (src == dirty_s) //loop
214  star = ws_.star(weight);
215  else
216  closure.emplace_back(src, weight);
217  // Delete incoming epsilon transitions.
218  aut_dirty_->del_transition(t);
219  }
220 
221  /*
222  For each transition (t : s -- label|weight --> dst),
223  for each former
224  epsilon transition closure->first -- e|closure->second --> s
225  a transition
226  (closure->first -- label | closure->second*weight --> dst)
227  is added to the automaton (add, not set !!)
228 
229  If (s) is final with weight (weight),
230  for each former
231  epsilon transition closure->first -- e|closure->second --> s
232  pair-second * weight is added to the final weight
233  of closure->first
234  */
235 
236 
237  // TODO: factoring with lambda
238  for (auto t: out(aut_dirty_, dirty_s))
239  {
240  weight_t blow = ws_.mul(star, aut_dirty_->weight_of(t));
241  aut_dirty_->set_weight(t, blow);
242 
243  auto dst = aut_dirty_->dst_of(t);
244  for (auto pair: closure)
245  {
246  auto src = pair.first;
247  weight_t w = ws_.mul(pair.second, blow);
248  aut_dirty_->add_transition(src, dst, {}, w);
249  }
250  }
251 
252  for (auto t: all_out(aut_proper_, proper_s))
253  {
254  weight_t blow = ws_.mul(star, aut_proper_->weight_of(t));
255  aut_proper_->set_weight(t, blow);
256 
257  label_proper_t label = aut_proper_->label_of(t);
258  auto dst = aut_proper_->dst_of(t);
259  for (auto pair: closure)
260  {
261  auto src = pair.first;
262  weight_t w = ws_.mul(pair.second, blow);
263  aut_proper_->add_transition(d2p_[src], dst, label, w);
264  }
265  }
266 #ifdef STATS
267  // Number of transition that have been added.
268  auto added = (all_out(aut_proper_, proper_s).size()
269  + out(aut_dirty_, dirty_s).size()) * closure.size();
270 #endif
271  if (prune_
272  && in(aut_dirty_, dirty_s).empty()
273  && all_in(aut_proper_, proper_s).empty())
274  {
275 #ifdef STATS
276  removed += (all_out(aut_proper_, proper_s).size()
277  + out(aut_dirty_, dirty_s).size());
278 #endif
279  aut_proper_->del_state(proper_s);
280  aut_dirty_->del_state(dirty_s);
281  }
282 #ifdef STATS
283  added_ += added;
284  removed_ += removed;
285  if (1 < debug_)
286  std::cerr << " -" << removed << "+" << added
287  << " (-" << removed_ << "+" << added_ << ")";
288 #endif
289  }
290 
291  public:
294  {
295  state_dirty_t dirty_s = p2d_[proper_s];
296  if (dirty_s == aut_dirty_->null_state())
297  return false;
298  else
299  return !in(aut_dirty_, dirty_s).empty();
300  }
301 
303  void remover_on(state_proper_t proper_s)
304  {
305  state_dirty_t dirty_s = p2d_[proper_s];
306  if (dirty_s != aut_dirty_->null_state())
307  remover_on(proper_s, dirty_s);
308  }
309 
323  {
324  if (4 < debug_)
325  {
326  dot(aut_proper_, std::cerr) << '\n';
327  dot(aut_dirty_, std::cerr) << '\n';
328  }
329  build_heap_();
330  /* For each state (s), for each incoming epsilon-transitions
331  (t), if (t) is a loop, the star of its weight is computed,
332  otherwise, (t) is stored into the closure list. Then (t)
333  is removed. */
334 
335  // The neighbors of s: their profiles need to be updated after
336  // s was processed.
337  auto neighbors = std::unordered_set<state_proper_t>{};
338  while (!todo_.empty())
339  {
340  if (2 < debug_)
341  {
342  std::cerr << "Before: ";
343  show_heap_();
344  std::cerr << '\n';
345  }
346  auto p = todo_.top();
347  todo_.pop();
348  if (1 < debug_)
349  std::cerr << "Remove: " << p;
350 
351  state_proper_t proper_s = p.state;
352  auto dirty_s = p2d_[proper_s];
353  handles_.erase(proper_s);
354 
355  // Adjacent states.
356  neighbors.clear();
357  for (auto t: in(aut_proper_, proper_s))
358  if (aut_proper_->src_of(t) != proper_s)
359  neighbors.emplace(aut_proper_->src_of(t));
360  for (auto t: out(aut_proper_, proper_s))
361  if (aut_proper_->dst_of(t) != proper_s)
362  neighbors.emplace(aut_proper_->dst_of(t));
363 
364  if (dirty_s != aut_dirty_->null_state())
365  {
366  state_dirty_t n;
367  for (auto t: in(aut_dirty_, dirty_s))
368  if ((n = aut_dirty_->src_of(t)) != dirty_s)
369  neighbors.emplace(d2p_[n]);
370  for (auto t: out(aut_dirty_, dirty_s))
371  if ((n = aut_dirty_->dst_of(t)) != dirty_s)
372  neighbors.emplace(d2p_[n]);
373 
374  remover_on(proper_s, dirty_s);
375  }
376 
377  // Update all neighbors and then the heap.
378  for (auto n: neighbors)
379  update_profile_(n);
380  for (auto n: neighbors)
381  update_heap_(n);
382  if (1 < debug_)
383  std::cerr << " #tr: "
384  << transitions(aut_dirty_).size()
385  << "/" << (transitions(aut_dirty_).size()
386  + transitions(aut_proper_).size())
387  << '\n';
388  if (2 < debug_)
389  {
390  std::cerr << "After: ";
391  show_heap_();
392  std::cerr << '\n';
393  }
394  if (4 < debug_)
395  {
396  dot(aut_proper_, std::cerr) << '\n';
397  dot(aut_dirty_, std::cerr) << '\n';
398  }
399  if (2 < debug_)
400  std::cerr << '\n';
401  }
402 #ifdef STATS
403  if (0 < debug_)
404  std::cerr << "Total transitions -" << removed_
405  << "+" << added_ << '\n';
406 #endif
407 
408  return aut_proper_;
409  }
410 
413  {
414  return aut_proper_;
415  }
416 
417  private:
419  int debug_;
420 
424 
428 
430  const weightset_t& ws_;
431 
433  using heap_t = boost::heap::fibonacci_heap<profile_t>;
436  std::unordered_map<state_proper_t, typename heap_t::handle_type> handles_;
437 
439  bool prune_;
440 
441  std::vector<state_proper_t> d2p_; // dirty states -> proper states
442  std::vector<state_dirty_t> p2d_; // proper states -> dirty states
443  };
444 
445  template <Automaton Aut>
446  class epsilon_remover_separate<Aut, false>
447  {
448  using automaton_t = std::remove_cv_t<Aut>;
450  public:
452  : aut_(aut)
453  {}
454 
456  {
457  return copy(aut_);
458  }
459 
461  {
462  return aut_;
463  }
464 
465  private:
467  };
468  }
469 } // namespace vcsn
bool prune_
Whether to prune states that become inaccessible.
value_impl< detail::weight_tag > weight
Definition: fwd.hh:28
#define Automaton
Definition: automaton.hh:23
std::vector< typename Cont::value_type > make_vector(const Cont &cont)
The content of cont as a vector.
Definition: vector.hh:20
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
boost::heap::fibonacci_heap< profile_t > heap_t
Max-heap to decide the order of state-elimination.
fresh_automaton_t_of< Aut, proper_ctx_t > aut_proper_t
Proper automaton.
aut_dirty_t aut_dirty_
The sponteanous part.
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
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
size_t states_size(const Aut &aut)
The largest state number, plus one.
Definition: automaton.hh:19
aut_proper_t get_proper()
Return the proper part. Needed by lazy algorithm.
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:113
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:64
static int debug_level()
Debug level set in the user's environment.
Definition: debug-level.hh:11
const weightset_t & ws_
Shorthand to the weightset.
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
This is used by some epsilon removal algorithms.
mutable_automaton< dirty_ctx_t > aut_dirty_t
Spontaneous automaton.
void update_profile_(state_proper_t proper_s)
Update the profile of s.
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
void remover_on(state_proper_t proper_s)
Wrapper around remover_on() which does a lookup of the dirty state.
Definition: a-star.hh:8
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
aut_proper_t operator()()
Remove all the states with incoming spontaneous transitions.
int debug_
Debug level. The higher, the more details are reported.
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 remover_on(state_proper_t proper_s, state_dirty_t dirty_s)
For each state (s), for each incoming epsilon-transitions (t), if (t) is a loop, the star of its weig...
void update_heap_(state_proper_t s)
Update the heap for s.
epsilon_remover_separate(const automaton_t &aut, bool prune=true)
Get ready to eliminate spontaneous transitions.
auto all_in(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions entering state s.
Definition: automaton.hh:94
detail::copier< AutIn, AutOut > make_copier(const AutIn &in, AutOut &out, bool safe=true)
Build an automaton copier.
Definition: copy.hh:256
bool state_has_spontaneous_in(state_proper_t proper_s) const
Whether the given state has incoming spontaneous transitions.
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
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
std::unordered_map< state_proper_t, typename heap_t::handle_type > handles_
Map: state -> heap-handle.
profile_t * profile_(state_proper_t s) const
The profile of state s, or nullptr if it is not to be processed.
void show_heap_() const
Show the heap, for debugging.
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:45
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