Vcsn  2.4
Be Rational
minimize-signature.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <unordered_map>
4 #include <unordered_set>
5 
6 #include <vcsn/algos/accessible.hh> // is_trim
7 #include <vcsn/algos/quotient.hh>
10 #include <vcsn/misc/indent.hh>
11 #include <vcsn/misc/map.hh> // vcsn::less
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: signature variant. |
20  `---------------------------------------------------------*/
21 
23  struct signature_tag {};
24 
25  namespace detail
26  {
27  template <Automaton Aut>
29  {
30  static_assert(std::is_same<weightset_t_of<Aut>, b>::value,
31  "minimize: signature: requires Boolean weights");
32 
33  using automaton_t = Aut;
34 
38  using class_t = unsigned;
39  using set_t = std::vector<state_t>;
40  using state_to_class_t = std::unordered_map<state_t, class_t>;
41  using class_to_set_t = std::vector<set_t>;
42 
43  constexpr static const char* me() { return "minimize-signature"; }
44 
46  constexpr static class_t class_invalid = -1;
47  // For a given state, destination states for a specific label.
48  struct state_output_for_label_t
49  {
50  // For some unstored state.
52  std::vector<state_t> to_states; // Ordered.
53  };
54 
55  // This is sorted by label.
56  using state_output_t = std::vector<state_output_for_label_t>;
57 
58  struct signature_hasher
59  {
60  // FIXME: G++ 4.9 requires this ctor, which is wrong.
62  : minimizer_(m)
63  {}
64 
65  size_t operator()(const state_output_t& state_output) const noexcept
66  {
67  size_t res = 0;
68  dynamic_bitset bits(num_classes_);
69  for (auto& t : state_output)
70  {
71  const label_t& label = t.label;
72  hash_combine_hash(res, minimizer_.ls_.hash(label));
73  // Hash the set of classes reached with label. Of
74  // course the hash must not depend on class ordering.
75  bits.reset();
76  for (auto s : t.to_states)
77  bits.set(state_to_class_.at(s));
78  vcsn::hash_combine(res, bits);
79  }
80  return res;
81  }
82 
83  size_t operator()(state_t s) const noexcept
84  {
85  return operator()(minimizer_.state_to_state_output_.at(s));
86  }
87 
89  const state_to_class_t& state_to_class_ = minimizer_.state_to_class_;
90  unsigned num_classes_ = minimizer_.num_classes_;
91  }; // class signature_hasher
92 
93  struct signature_equal_to
94  {
95  // FIXME: G++ 4.9 requires this ctor, which is wrong.
97  : minimizer_(m)
98  {}
99  bool operator()(const state_output_t& as,
100  const state_output_t& bs) const noexcept
101  {
102  if (as.size() != bs.size())
103  return false;
104 
105  dynamic_bitset a_bits(num_classes_), b_bits(num_classes_);
106  for (auto i = as.cbegin(), i_end = as.cend(), j = bs.cbegin();
107  i != i_end;
108  ++i, ++j)
109  {
110  if (! ls_.equal(i->label, j->label))
111  return false;
112 
113  a_bits.reset(); b_bits.reset();
114  for (auto s : i->to_states)
115  a_bits.set(state_to_class_.at(s));
116  for (auto s : j->to_states)
117  b_bits.set(state_to_class_.at(s));
118  if (a_bits != b_bits)
119  return false;
120  }
121 
122  return true;
123  }
124 
125  bool operator()(const state_t& a, const state_t& b) const noexcept
126  {
127  return operator()(minimizer_.state_to_state_output_.at(a),
128  minimizer_.state_to_state_output_.at(b));
129  }
130 
132  const labelset_t& ls_ = minimizer_.ls_;
133  const state_to_class_t& state_to_class_ = minimizer_.state_to_class_;
134  const size_t num_classes_ = minimizer_.num_classes_;
135  }; // class signature_equal_to
136 
141  using signature_multimap
143  signature_hasher, signature_equal_to>;
144 
145  void clear()
146  {
147  class_to_set_.clear();
148  state_to_class_.clear();
149  num_classes_ = 0;
150  }
151 
158  class_t make_class(set_t&& set, class_t number = class_invalid)
159  {
160  if (number == class_invalid)
161  number = num_classes_++;
162 
163  for (auto s : set)
164  state_to_class_[s] = number;
165 
166  if (number < class_to_set_.size())
167  class_to_set_[number] = std::move(set);
168  else
169  {
170  assert(number == class_to_set_.size());
171  class_to_set_.emplace_back(std::move(set));
172  }
173 
174  return number;
175  }
176 
177  public:
178  minimizer(const Aut& a)
179  : a_(a)
180  {
181  require(is_trim(a_), me(), ": input must be trim");
182 
183  // Fill state_to_state_output.
184  for (auto s : a_->all_states())
185  {
186  // Sort of a transition-map for state s.
187  using label_to_states_t
188  = std::map<label_t, std::vector<state_t>, vcsn::less<labelset_t>>;
189 
190  // Get the out-states from s, by label:
191  label_to_states_t label_to_states;
192  for (auto t : all_out(a_, s))
193  label_to_states[a_->label_of(t)].emplace_back(a_->dst_of(t));
194 
195  // Associate this information to s, as a vector sorted by label:
196  state_output_t& state_output = state_to_state_output_[s];
197  for (auto& l_ss : label_to_states)
198  {
199  boost::sort(l_ss.second);
200  state_output.emplace_back(state_output_for_label_t{l_ss.first,
201  std::move(l_ss.second)});
202  }
203  }
204  }
205 
208  {
209  build_classes_();
210  return class_to_set_;
211  }
212 
213  private:
216  {
217  // The list of classes candidates for splitting.
218  //
219  // Don't even bother to split between final and non-final
220  // states, this initialization is useless.
221  std::unordered_set<class_t> classes;
222  {
223  const auto& all = a_->all_states();
224  classes.insert(make_class(set_t{std::begin(all), std::end(all)}));
225  }
226 
227  for (bool go_on = true; go_on; /* Nothing. */)
228  {
229  go_on = false;
230  for (auto i = std::begin(classes), end = std::end(classes);
231  i != end;
232  /* nothing. */)
233  {
234  auto c = *i;
235  const set_t& c_states = class_to_set_.at(c);
236 
237  // Look for distinguishable states in c_states:
238  // cluster the signatures.
239  auto sig_to_state
240  = signature_multimap{1,
241  signature_hasher{*this},
242  signature_equal_to{*this}};
243  for (auto s : c_states)
244  sig_to_state[s].emplace_back(s);
245 
246  if (2 <= sig_to_state.size())
247  {
248  // Split class c.
249  go_on = true;
250  i = classes.erase(i);
251  // To keep class numbers contiguous, reuse 'c' as
252  // first class number, and then use new one (via
253  // "c = class_invalid" below).
254  for (auto& p: sig_to_state)
255  {
256  bool singleton = p.second.size() == 1;
257  class_t c2 = make_class(std::move(p.second), c);
258  if (!singleton)
259  classes.insert(c2);
260  c = class_invalid;
261  }
262  }
263  else
264  ++i;
265  } // for on classes
266  }
267  }
268 
271 
272  const labelset_t& ls_ = *a_->labelset();
273 
274  unsigned num_classes_ = 0;
275 
278 
281  std::unordered_map<state_t, state_output_t> state_to_state_output_;
282  };
283  } // detail::
284 
285  namespace dyn
286  {
287  namespace detail
288  {
289  template <Automaton Aut>
290  ATTRIBUTE_NORETURN
291  std::enable_if_t<!std::is_same<weightset_t_of<Aut>, b>::value,
293  minimize(const Aut&, signature_tag)
294  {
295  raise("minimize: invalid algorithm (non-Boolean): signature");
296  }
297  }
298  }
299 } // namespace vcsn
return res
Definition: multiply.hh:398
bool operator()(const state_t &a, const state_t &b) const noexcept
std::vector< state_output_for_label_t > state_output_t
Functor to compare Values of ValueSets.
Definition: functional.hh:76
automaton_t a_
Input automaton, supplied at construction time.
class_t make_class(set_t &&set, class_t number=class_invalid)
Make a new class with the given set of states.
bool all(Bool &&...values)
Whether all the values evaluate as true.
Definition: tuple.hh:446
void hash_combine_hash(std::size_t &seed, size_t h)
Definition: functional.hh:41
size_t operator()(const state_output_t &state_output) const noexcept
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
bool operator()(const state_output_t &as, const state_output_t &bs) const noexcept
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
class_to_set_t & classes()
The partition, as a list of classes.
Definition: a-star.hh:8
boost::dynamic_bitset<> dynamic_bitset
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:66
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
partition_automaton_t< Aut > quotient_t
The return type when calling quotient on Aut.
Definition: quotient.hh:119
Request for Moore implementation of minimize (B).
Indentation relative functions.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
value_impl< detail::label_tag > label
Definition: fwd.hh:26
std::unordered_map< state_t, class_t > state_to_class_t
auto sort(const Aut &a) -> permutation_automaton< Aut >
Definition: sort.hh:161
std::unordered_map< state_t, set_t, signature_hasher, signature_equal_to > signature_multimap
Cluster states per signature.
void hash_combine(std::size_t &seed, const T &v)
Definition: functional.hh:48
std::unordered_map< state_t, state_output_t > state_to_state_output_
Sort of a transition map for each state: state -> vector of (label, destination states).
void build_classes_()
Build the initial classes, and split until fix point.
Request the unordered_map implementation.
bool is_trim(const Aut &a)
Whether all its states are useful.
Definition: accessible.hh:161
Request the set implementation (bool weights).
ATTRIBUTE_NORETURN std::enable_if_t<!is_free_boolean< Aut >), Aut > minimize(const Aut &, brzozowski_tag)
Handling of errors for dyn::minimize.