Vcsn  2.4
Be Rational
epsilon-profile.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <ostream>
4 #include <tuple>
5 
6 namespace vcsn
7 {
8  namespace detail
9  {
11 
18  template <typename State>
20  {
21  using state_t = State;
22 
26  size_t in_sp;
28  size_t in_nsp;
30  size_t out_sp;
32  size_t out_nsp;
33 
42  size_t insp, size_t in,
43  size_t outsp, size_t out)
44  : state(s)
45  , in_sp(insp), in_nsp(in - insp)
46  , out_sp(outsp), out_nsp(out - outsp)
47  {}
48 
49  void update(size_t insp, size_t in,
50  size_t outsp, size_t out)
51  {
52  in_sp = insp;
53  in_nsp = in - insp;
54  out_sp = outsp;
55  out_nsp = out - outsp;
56  }
57 
62  bool operator<(const epsilon_profile& r) const
63  {
64  // (i) First, work on those with fewer outgoing spontaneous
65  // transitions.
66  // (ii) Prefer fewer outgoing transitions.
67  // (iii) Prefer fewer incoming spontaneous transitions.
68  // (iv) Then, ensure total order using state handle.
69  //
70  // Note the inversions between lhs and rhs.
71  return (std::tie (r.out_sp, r.out_nsp, r.in_sp, state)
72  < std::tie(out_sp, out_nsp, in_sp, r.state));
73  }
74 
75  friend std::ostream& operator<<(std::ostream& o, const epsilon_profile& p)
76  {
77  return o << p.state
78  << 'o' << p.out_sp
79  << 'O' << p.out_nsp
80  << 'i' << p.in_sp
81  << 'I' << p.in_nsp;
82  }
83  };
84  }
85 }
size_t in_sp
Number of incoming spontaneous transitions.
void update(size_t insp, size_t in, size_t outsp, size_t out)
This is used by some epsilon removal algorithms.
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
Definition: a-star.hh:8
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:85
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:134
bool operator<(const epsilon_profile &r) const
Whether l < r for the max-heap.
state_t state
From the heap's top, recover state to eliminate.
size_t in_nsp
Number of incoming non-spontaneous transitions.
epsilon_profile(state_t s, size_t insp, size_t in, size_t outsp, size_t out)
Generate a state profile.
friend std::ostream & operator<<(std::ostream &o, const epsilon_profile &p)
size_t out_sp
Number of outgoing spontaneous transitions.
size_t out_nsp
Number of outgoing non-spontaneous transitions.