Vcsn  2.3a
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  using genset_t = decltype(std::declval<labelset_t>().generators());
43  const genset_t gs_;
44 
47  using class_t = unsigned;
48  using classes_t = std::vector<class_t>;
49  using set_t = std::vector<state_t>;
50  using state_to_class_t = std::unordered_map<state_t, class_t>;
51  using target_class_to_states_t = std::unordered_map<class_t, set_t>;
52  using class_to_set_t = std::vector<set_t>;
53 
54  constexpr static const char* me() { return "minimize-moore"; }
55 
57  constexpr static class_t class_invalid = -1;
58  unsigned num_classes_ = 0;
59 
60  // First two classes are reserved, and are empty.
63 
66  using transition_map_t
69  /* Deterministic: */ true,
70  /* AllOut: */ true>;
72 
73  void clear()
74  {
75  class_to_set_.clear();
76  state_to_class_.clear();
77  num_classes_ = 0;
78  transition_map_.clear();
79  }
80 
82  class_t make_class(set_t&& set, class_t number = class_invalid)
83  {
84  assert(! set.empty());
85 
86  if (number == class_invalid)
87  number = num_classes_++;
88 
89  for (auto s : set)
90  state_to_class_[s] = number;
91 
92  if (number < class_to_set_.size())
93  class_to_set_[number] = std::move(set);
94  else
95  {
96  assert(number == class_to_set_.size());
97  class_to_set_.emplace_back(std::move(set));
98  }
99 
100  return number;
101  }
102 
106  {
107  const auto& map = transition_map_[s];
108  auto dst = map.find(l);
109  if (dst == std::end(map))
110  return class_invalid;
111  else
112  return state_to_class_[dst->second.dst];
113  }
114 
115  public:
117  minimizer(const Aut& a)
118  : a_(a)
119  , gs_(a_->labelset()->generators())
120  , transition_map_(a)
121  {
122  // We _really_ need determinism here. See for instance
123  // minimization of standard(aa+a) (not a+aa).
124  require(is_deterministic(a_), me(), ": input must be deterministic");
125  require(is_trim(a_), me(), ": input must be trim");
126  }
127 
130  {
131  build_classes_();
132  return class_to_set_;
133  }
134 
135  private:
138  {
139  // Initialization: two classes, partitioning final and
140  // non-final states.
141  make_class({a_->pre()});
142  make_class({a_->post()});
143  {
144  set_t nonfinals, finals;
145  for (auto s : a_->states())
146  if (a_->is_final(s))
147  finals.emplace_back(s);
148  else
149  nonfinals.emplace_back(s);
150  if (! nonfinals.empty())
151  make_class(std::move(nonfinals));
152  if (! finals.empty())
153  make_class(std::move(finals));
154  }
155 
156  bool go_on = true;
157  while (go_on)
158  {
159  go_on = false;
160  for (class_t c = 0; c < num_classes_; ++c)
161  {
162  const set_t& c_states = class_to_set_[c];
163  for (auto l : gs_)
164  {
165  // See the "alreadyminimal" test comment in
166  // tests/python/minimize.py.
167  target_class_to_states_t target_class_to_c_states;
168  for (auto s : c_states)
169  {
170  auto c2 = out_class(s, l);
171  target_class_to_c_states[c2].emplace_back(s);
172  }
173 
174  // Are there at least two keys?
175  //
176  // std::unordered_map::size is said to be O(1).
177  if (2 <= target_class_to_c_states.size())
178  {
179  go_on = true;
180  class_t num = c;
181  for (auto& p : target_class_to_c_states)
182  {
183  make_class(std::move(p.second), num);
184  num = class_invalid;
185  }
186  // Ignore other labels for this partition
187  break;
188  }
189  } // for on labels
190  } // for on classes
191  }
192  }
193  };
194  }
195 
196  namespace dyn
197  {
198  namespace detail
199  {
200  template <Automaton Aut>
201  ATTRIBUTE_NORETURN
202  std::enable_if_t<!is_free_boolean<Aut>(), quotient_t<Aut>>
203  minimize(const Aut&, moore_tag)
204  {
205  raise("minimize: invalid algorithm"
206  " (non-Boolean or non-free labelset):",
207  " moore");
208  }
209  }
210  }
211 } // namespace vcsn
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:177
Request for Moore implementation of minimize (B and free).
labelset_t_of< automaton_t > labelset_t
Definition: a-star.hh:8
bool is_deterministic(const Aut &aut, state_t_of< Aut > s)
Whether state s is deterministic in aut.
void build_classes_()
Build the initial classes, and split until fix point.
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
bool is_trim(const Aut &a)
Whether all its states are useful.
Definition: accessible.hh:161
std::unordered_map< state_t, class_t > state_to_class_t
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
std::unordered_map< class_t, set_t > target_class_to_states_t
ATTRIBUTE_NORETURN std::enable_if_t<!is_free_boolean< Aut >), Aut > minimize(const Aut &, brzozowski_tag)
Handling of errors for dyn::minimize.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
automaton_t a_
Input automaton, supplied at construction time.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
class_to_set_t & classes()
The partition, as a list of classes.
minimizer(const Aut &a)
Build the minimizer. Computes the classes.
class_t make_class(set_t &&set, class_t number=class_invalid)
Make a new class with the given set of states.
class_t out_class(state_t s, label_t l)
The destination class of s with l in a.
Request the set implementation (bool weights).
decltype(std::declval< labelset_t >().generators()) genset_t
The generators.
static constexpr const char * me()
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46