Vcsn  2.4
Be Rational
minimize-hopcroft.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm>
4 
6 #include <vcsn/algos/quotient.hh>
10 #include <vcsn/misc/set.hh>
11 #include <vcsn/misc/vector.hh>
12 #include <vcsn/misc/wet.hh>
13 #include <vcsn/weightset/b.hh>
15 
16 namespace vcsn
17 {
18 
19  /*------------------------------------------.
20  | minimization with Hopcrofts's algorithm. |
21  `------------------------------------------*/
22 
24  struct hopcroft_tag {};
25 
26  template <Automaton Aut>
27  std::enable_if_t<is_free_boolean<Aut>(), quotient_t<Aut>>
28  minimize(const Aut& a, hopcroft_tag)
29  {
30  using state_t = state_t_of<Aut>;
31  using stateset_t = stateset<Aut>;
32  require(std::is_same<weightset_t_of<Aut>, b>::value,
33  "hopcroft: require boolean weightset");
34  auto ctx = make_context(stateset_t(a), *a->weightset());
35  auto ps = detail::make_polynomialset<decltype(ctx),
37  using set_t = typename decltype(ps)::value_t;
38  using partition_t = std::set<set_t>;
39 
40  auto size = states_size(a);
41 
42  auto f = set_t(size);
43  f.set(a->post());
44 
45  auto q = set_t(size);
46  for (auto s: a->all_states())
47  q.set(s);
48  q.erase(a->post());
49 
50  auto p = partition_t{f, q};
51  auto w = partition_t{f};
52 
53  const auto& ls = *a->labelset();
54  auto generators = detail::make_vector(ls.generators());
55  generators.emplace_back(ls.special());
56 
57  while (!w.empty())
58  {
59  auto sub_w = std::move(*begin(w));
60  w.erase(begin(w));
61  for (const auto l: generators)
62  {
63  auto x = set_t(size);
64  for (auto s: sub_w)
65  for (auto t: in(a, label_of(s), l))
66  x.set(a->src_of(t));
67  auto p2 = partition_t(p);
68  for (auto y: p2)
69  {
70  auto xny = x & y;
71  auto x_y = y - x;
72  if (!xny.empty() && !x_y.empty())
73  {
74  auto it = w.find(y);
75  if (it != end(w))
76  {
77  w.erase(it);
78  w.insert(xny);
79  w.insert(x_y);
80  }
81  else
82  w.insert(xny.size() <= x_y.size() ? xny : x_y);
83  p.erase(y);
84  p.insert(std::move(xny));
85  p.insert(std::move(x_y));
86  }
87  }
88  }
89  }
90  auto res = std::vector<std::vector<state_t>>{};
91  std::transform(begin(p), end(p), std::back_inserter(res),
92  [](const set_t& set)
93  {
94  auto res = std::vector<state_t>();
95  res.reserve(set.size());
96  for (auto s: set)
97  res.push_back(label_of(s));
98  return res;
99  });
100  return quotient(a, res);
101  }
102 
103  namespace dyn
104  {
105  namespace detail
106  {
107  template <Automaton Aut>
108  ATTRIBUTE_NORETURN
109  std::enable_if_t<!is_free_boolean<Aut>(), quotient_t<Aut>>
110  minimize(const Aut&, hopcroft_tag)
111  {
112  raise("minimize: invalid algorithm"
113  " (non-Boolean or non-free labelset):",
114  " hopcroft");
115  }
116  }
117  }
118 } // namespace vcsn
std::vector< typename Cont::value_type > make_vector(const Cont &cont)
The content of cont as a vector.
Definition: vector.hh:20
auto minimize(const Aut &a, brzozowski_tag) -> std::enable_if_t< is_free_boolean< Aut >(), determinized_automaton< codeterminized_automaton< Aut >, wet_kind_t::bitset >>
Brzozowski-based minimization.
return res
Definition: multiply.hh:398
auto quotient(const Aut &a, typename detail::quotienter< Aut >::class_to_set_t &cs) -> quotient_t< Aut >
Definition: quotient.hh:123
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
size_t states_size(const Aut &aut)
The largest state number, plus one.
Definition: automaton.hh:40
polynomialset< Context, Kind > make_polynomialset(const Context &context)
Definition: a-star.hh:8
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:134
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
auto transform(const Container &c, Fun &&fun)
Map a unary function on a container of values, and return the vector the results. ...
Definition: algorithm.hh:157
State labelset.
Definition: stateset.hh:14
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
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
Request for Hopcroft implementation of minimize (B and free).
auto label_of(const welement< Label, Weight > &m) -> decltype(m.label())
The label of a welement.
Definition: wet.hh:146
Request the bitset implementation (bool weights).
Ctx make_context(const std::string &name)
Build a context from its name.
Definition: make-context.hh:22
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.