Vcsn  2.3
Be Rational
minimize-weighted.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <map>
4 #include <unordered_map>
5 #include <unordered_set>
6 #include <vector>
7 
8 #include <vcsn/algos/tags.hh>
9 #include <vcsn/algos/accessible.hh> // is_trim
10 #include <vcsn/misc/indent.hh>
11 #include <vcsn/misc/raise.hh>
12 
13 namespace vcsn
14 {
15 
16  /*-------------------------------------------------------------------------.
17  | minimization with signatures; general version working on any weightset. |
18  `-------------------------------------------------------------------------*/
19 
20  namespace detail
21  {
22  template <Automaton Aut>
23  class minimizer<Aut, weighted_tag>
24  {
25  using automaton_t = Aut;
26 
32  using class_t = unsigned;
33  using set_t = std::vector<state_t>;
34  using state_to_class_t = std::unordered_map<state_t, class_t>;
35  using class_to_set_t = std::vector<set_t>;
36 
37  constexpr static const char* me() { return "minimize-weighted"; }
38 
40  constexpr static class_t class_invalid = -1;
42  struct classset
43  {
44  using value_t = class_t;
45 
46  using kind_t = void;
47  static bool equal(class_t l, class_t r)
48  {
49  return l == r;
50  }
51 
52  static bool less(class_t l, class_t r)
53  {
54  return l < r;
55  }
56 
57  static size_t hash(class_t s)
58  {
59  return hash_value(s);
60  }
61  };
62 
65  using class_polynomialset_t
67 
68  using class_polynomial_t = typename class_polynomialset_t::value_t;
69 
71  using signature_t = std::map<label_t, class_polynomial_t>;
74  {
75  auto res = signature_t{};
76  for (auto t: all_out(a_, s))
77  cps_.add_here(res[a_->label_of(t)],
78  state_to_class_.at(a_->dst_of(t)),
79  a_->weight_of(t));
80  return res;
81  }
82 
83  struct signature_hasher
84  {
85  size_t operator()(const signature_t& sig) const noexcept
86  {
87  size_t res = 0;
88  for (auto& t : sig)
89  {
90  hash_combine_hash(res, minimizer_.ls_.hash(t.first));
91  hash_combine_hash(res, minimizer_.cps_.hash(t.second));
92  }
93  return res;
94  }
95 
97  }; // class signature_hasher
98 
99  struct signature_equal_to
100  {
101  bool operator()(const signature_t& as,
102  const signature_t& bs) const noexcept
103  {
104  if (as.size() != bs.size())
105  return false;
106 
107  using std::begin; using std::end;
108  for (auto i = begin(as), i_end = end(as), j = begin(bs);
109  i != i_end;
110  ++i, ++j)
111  if (!minimizer_.ls_.equal(i->first, j->first)
112  || !minimizer_.cps_.equal(i->second, j->second))
113  return false;
114  return true;
115  }
116 
118  }; // class signature_equal_to
119 
121  using signature_multimap
123  signature_hasher, signature_equal_to>;
124 
125  void clear()
126  {
127  class_to_set_.clear();
128  state_to_class_.clear();
129  num_classes_ = 0;
130  }
131 
138  class_t make_class(set_t&& set, class_t number = class_invalid)
139  {
140  if (number == class_invalid)
141  number = num_classes_++;
142 
143  for (auto s : set)
144  state_to_class_[s] = number;
145 
146  if (number < class_to_set_.size())
147  class_to_set_[number] = std::move(set);
148  else
149  {
150  assert(number == class_to_set_.size());
151  class_to_set_.emplace_back(std::move(set));
152  }
153 
154  return number;
155  }
156 
157  public:
158  minimizer(const Aut& a)
159  : a_(a)
160  {
161  require(is_trim(a_), me(), ": input must be trim");
162  }
163 
166  {
167  build_classes_();
168  return class_to_set_;
169  }
170 
173  {
174  // Don't even bother splitting into final and non-final
175  // states: post will be set apart anyway because of its
176  // signature.
177  std::unordered_set<class_t> classes;
178  {
179  const auto& all = a_->all_states();
180  classes.insert(make_class(set_t{std::begin(all), std::end(all)}));
181  }
182 
183  for (bool go_on = true; go_on; /* Nothing. */)
184  {
185  go_on = false;
186  for (auto i = std::begin(classes), end = std::end(classes);
187  i != end;
188  /* Nothing. */)
189  {
190  auto c = *i;
191  const set_t& c_states = class_to_set_.at(c);
192 
193  // Look for distinguishable states in c_states:
194  // cluster the signatures.
195  auto signature_to_state
196  = signature_multimap{1,
197  signature_hasher{*this},
198  signature_equal_to{*this}};
199  for (auto s: c_states)
200  signature_to_state[signature(s)].emplace_back(s);
201 
202  if (2 <= signature_to_state.size())
203  {
204  // Split class c.
205  go_on = true;
206  i = classes.erase(i);
207  // To keep class numbers contiguous, reuse 'c' as
208  // first class number, and then use new one (via
209  // "c = class_invalid" below).
210  for (auto& p: signature_to_state)
211  {
212  bool singleton = p.second.size() == 1;
213  class_t c2 = make_class(std::move(p.second), c);
214  if (!singleton)
215  classes.insert(c2);
216  c = class_invalid;
217  }
218  }
219  else
220  ++i;
221  } // for on classes
222  }
223  }
224 
227 
228  const labelset_t& ls_ = *a_->labelset();
229  const weightset_t& ws_ = *a_->weightset();
230 
231  unsigned num_classes_ = 0;
232 
235 
237  class_polynomialset_t cps_{{classset{}, ws_}};
238  };
239  } // weighted::
240 } // namespace vcsn
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
std::map< label_t, class_polynomial_t > signature_t
A signature: for each label, the outgoing class polynomial.
void build_classes_()
Build the initial classes, and split until fix point.
size_t operator()(const signature_t &sig) const noexcept
class_to_set_t & classes()
The minimized automaton.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
class_t make_class(set_t &&set, class_t number=class_invalid)
Make a new class with the given set of states.
automaton_t a_
Input automaton, supplied at construction time.
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
Request the unordered_map implementation.
typename class_polynomialset_t::value_t class_polynomial_t
return res
Definition: multiply.hh:398
auto hash_value(const T &v) -> decltype(std::hash< T >
Following the naming convention of Boost.
Definition: functional.hh:30
signature_t signature(state_t s) const
The signature of state s.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
Definition: a-star.hh:8
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
std::unordered_map< state_t, class_t > state_to_class_t
Request for the weighted version of an algorithm.
Definition: tags.hh:140
Indentation relative functions.
std::set< std::pair< std::string, std::string >> class_t
A set of label ranges.
Definition: fwd.hh:12
Request the set implementation (bool weights).
bool all(Bool &&...values)
Whether all the values evaluate as true.
Definition: tuple.hh:446
bool operator()(const signature_t &as, const signature_t &bs) const noexcept
void hash_combine_hash(std::size_t &seed, size_t h)
Definition: functional.hh:41
Signature of a function call.
Definition: signature.hh:15
std::unordered_map< signature_t, set_t, signature_hasher, signature_equal_to > signature_multimap
Cluster states per signature.
polynomialset< context< classset, weightset_t >> class_polynomialset_t
The output of a given letter from a given state, keeping into account classes and weights...
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:45
bool is_trim(const Aut &a)
Whether all its states are useful.
Definition: accessible.hh:161
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54