Vcsn  2.2a
Be Rational
minimize-moore.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <unordered_map>
4 #include <vector>
5 
8 #include <vcsn/algos/accessible.hh> // is_trim
10 #include <vcsn/algos/quotient.hh>
12 #include <vcsn/misc/raise.hh>
13 #include <vcsn/weightset/fwd.hh> // b
14 
15 namespace vcsn
16 {
17 
18  /*--------------------------------------.
19  | minimization with Moore's algorithm. |
20  `--------------------------------------*/
21 
23  struct moore_tag {};
24 
25  namespace detail
26  {
27  template <Automaton Aut>
28  class minimizer<Aut, moore_tag>
29  {
30  static_assert(std::is_same<weightset_t_of<Aut>, b>::value,
31  "minimize: moore: requires Boolean weights");
32  static_assert(labelset_t_of<Aut>::is_free(),
33  "minimize: moore: requires free labelset");
34 
35  using automaton_t = Aut;
36 
39 
42 
45  using class_t = unsigned;
46  using classes_t = std::vector<class_t>;
47  using set_t = std::vector<state_t>;
48  using state_to_class_t = std::unordered_map<state_t, class_t>;
49  using target_class_to_states_t = std::unordered_map<class_t, set_t>;
50  using class_to_set_t = std::vector<set_t>;
51 
52  constexpr static const char* me() { return "minimize-moore"; }
53 
55  constexpr static class_t class_invalid = -1;
56  unsigned num_classes_ = 0;
57 
58  // First two classes are reserved, and are empty.
61 
64  using transition_map_t
67  /* Deterministic: */ true,
68  /* AllOut: */ true>;
70 
71  void clear()
72  {
73  class_to_set_.clear();
74  state_to_class_.clear();
75  num_classes_ = 0;
76  transition_map_.clear();
77  }
78 
80  class_t make_class(set_t&& set, class_t number = class_invalid)
81  {
82  assert(! set.empty());
83 
84  if (number == class_invalid)
85  number = num_classes_++;
86 
87  for (auto s : set)
88  state_to_class_[s] = number;
89 
90  if (number < class_to_set_.size())
91  class_to_set_[number] = std::move(set);
92  else
93  {
94  assert(number == class_to_set_.size());
95  class_to_set_.emplace_back(std::move(set));
96  }
97 
98  return number;
99  }
100 
104  {
105  const auto& map = transition_map_[s];
106  auto dst = map.find(l);
107  if (dst == std::end(map))
108  return class_invalid;
109  else
110  return state_to_class_[dst->second.dst];
111  }
112 
113  public:
115  minimizer(const Aut& a)
116  : a_(a)
117  , gs_(a_->labelset()->generators())
118  , transition_map_(a)
119  {
120  // We _really_ need determinism here. See for instance
121  // minimization of standard(aa+a) (not a+aa).
122  require(is_deterministic(a_), me(), ": input must be deterministic");
123  require(is_trim(a_), me(), ": input must be trim");
124  }
125 
128  {
129  build_classes_();
130  return class_to_set_;
131  }
132 
133  private:
136  {
137  // Initialization: two classes, partitioning final and
138  // non-final states.
139  make_class({a_->pre()});
140  make_class({a_->post()});
141  {
142  set_t nonfinals, finals;
143  for (auto s : a_->states())
144  if (a_->is_final(s))
145  finals.emplace_back(s);
146  else
147  nonfinals.emplace_back(s);
148  if (! nonfinals.empty())
149  make_class(std::move(nonfinals));
150  if (! finals.empty())
151  make_class(std::move(finals));
152  }
153 
154  bool go_on = true;
155  while (go_on)
156  {
157  go_on = false;
158  for (class_t c = 0; c < num_classes_; ++c)
159  {
160  const set_t& c_states = class_to_set_[c];
161  for (auto l : gs_)
162  {
163  // See the "alreadyminimal" test comment in
164  // tests/python/minimize.py.
165  target_class_to_states_t target_class_to_c_states;
166  for (auto s : c_states)
167  {
168  auto c2 = out_class(s, l);
169  target_class_to_c_states[c2].emplace_back(s);
170  }
171 
172  // Are there at least two keys?
173  //
174  // std::unordered_map::size is said to be O(1).
175  if (2 <= target_class_to_c_states.size())
176  {
177  go_on = true;
178  class_t num = c;
179  for (auto& p : target_class_to_c_states)
180  {
181  make_class(std::move(p.second), num);
182  num = class_invalid;
183  }
184  // Ignore other labels for this partition
185  break;
186  }
187  } // for on labels
188  } // for on classes
189  }
190  }
191  };
192  }
193 
194  namespace dyn
195  {
196  namespace detail
197  {
198  template <Automaton Aut>
199  ATTRIBUTE_NORETURN
200  std::enable_if_t<!is_free_boolean<Aut>(), quotient_t<Aut>>
201  minimize(const Aut&, moore_tag)
202  {
203  raise("minimize: invalid algorithm"
204  " (non-Boolean or non-free labelset):",
205  " moore");
206  }
207  }
208  }
209 } // namespace vcsn
class_t make_class(set_t &&set, class_t number=class_invalid)
Make a new class with the given set of states.
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
bool is_deterministic(const Aut &aut, state_t_of< Aut > s)
Whether state s is deterministic in aut.
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:54
minimizer(const Aut &a)
Build the minimizer. Computes the classes.
void build_classes_()
Build the initial classes, and split until fix point.
static constexpr const char * me()
const labelset_t_of< Aut >::genset_t gs_
The generators.
ATTRIBUTE_NORETURN std::enable_if_t<!is_free_boolean< Aut >), Aut > minimize(const Aut &, brzozowski_tag)
Handling of errors for dyn::minimize.
auto map(const std::tuple< Ts... > &ts, Fun f) -> decltype(map_tuple_(f, ts, make_index_sequence< sizeof...(Ts)>()))
Map a function on a tuple, return tuple of the results.
Definition: tuple.hh:160
std::unordered_map< state_t, class_t > state_to_class_t
std::unordered_map< class_t, set_t > target_class_to_states_t
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:78
Request the set implementation (bool weights).
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
class_to_set_t & classes()
The partition, as a list of classes.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
Request for Moore implementation of minimize (B and free).
bool is_trim(const Aut &a)
Whether all its states are useful.
Definition: accessible.hh:161
class_t out_class(state_t s, label_t l)
The destination class of s with l in a.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
automaton_t a_
Input automaton, supplied at construction time.
Definition: a-star.hh:8