Vcsn  2.2
Be Rational
minimize-hopcroft.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm>
4 
8 #include <vcsn/misc/wet.hh>
9 #include <vcsn/misc/set.hh>
10 #include <vcsn/misc/vector.hh>
11 #include <vcsn/weightset/b.hh>
13 #include <vcsn/algos/quotient.hh>
14 
15 namespace vcsn
16 {
17 
18  /*------------------------------------------.
19  | minimization with Hopcrofts's algorithm. |
20  `------------------------------------------*/
21 
23  struct hopcroft_tag {};
24 
25  template <Automaton Aut>
26  std::enable_if_t<is_free_boolean<Aut>(), quotient_t<Aut>>
27  minimize(const Aut& a, hopcroft_tag)
28  {
29  using state_t = state_t_of<Aut>;
30  using stateset_t = stateset<Aut>;
31  require(std::is_same<weightset_t_of<Aut>, b>::value,
32  "hopcroft: require boolean weightset");
33  auto ctx = make_context(stateset_t(a), *a->weightset());
34  auto ps = detail::make_polynomialset<decltype(ctx),
36  using set_t = typename decltype(ps)::value_t;
37  using partition_t = std::set<set_t>;
38 
39  unsigned size = a->all_states().back() + 1;
40 
41  auto f = set_t(size);
42  f.set(a->post());
43 
44  auto q = set_t(size);
45  for (auto s: a->all_states())
46  q.set(s);
47  q.erase(a->post());
48 
49  auto p = partition_t{f, q};
50  auto w = partition_t{f};
51 
52  const auto& ls = *a->labelset();
53  auto generators = detail::make_vector(ls.generators());
54  generators.emplace_back(ls.special());
55 
56  while (!w.empty())
57  {
58  auto sub_w = std::move(*begin(w));
59  w.erase(begin(w));
60  for (const auto l: generators)
61  {
62  auto x = set_t(size);
63  for (auto s: sub_w)
64  for (auto t: in(a, label_of(s), l))
65  x.set(a->src_of(t));
66  auto p2 = partition_t(p);
67  for (auto y: p2)
68  {
69  auto xny = x & y;
70  auto x_y = y - x;
71  if (!xny.empty() && !x_y.empty())
72  {
73  auto it = w.find(y);
74  if (it != end(w))
75  {
76  w.erase(it);
77  w.insert(xny);
78  w.insert(x_y);
79  }
80  else
81  w.insert(xny.size() <= x_y.size() ? xny : x_y);
82  p.erase(y);
83  p.insert(std::move(xny));
84  p.insert(std::move(x_y));
85  }
86  }
87  }
88  }
89  auto res = std::vector<std::vector<state_t>>{};
90  std::transform(begin(p), end(p), std::back_inserter(res),
91  [](const set_t& set)
92  {
93  auto res = std::vector<state_t>();
94  res.reserve(set.size());
95  for (auto s: set)
96  res.push_back(label_of(s));
97  return res;
98  });
99  return quotient(a, res);
100  }
101 
102  namespace dyn
103  {
104  namespace detail
105  {
106  template <Automaton Aut>
107  ATTRIBUTE_NORETURN
108  std::enable_if_t<!is_free_boolean<Aut>(), quotient_t<Aut>>
109  minimize(const Aut&, hopcroft_tag)
110  {
111  raise("minimize: invalid algorithm"
112  " (non-Boolean or non-free labelset):",
113  " hopcroft");
114  }
115  }
116  }
117 } // namespace vcsn
ATTRIBUTE_NORETURN std::enable_if_t<!is_free_boolean< Aut >), Aut > minimize(const Aut &, brzozowski_tag)
Handling of errors for dyn::minimize.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
partition_automaton_t< Aut > quotient_t
The return type when calling quotient on Aut.
Definition: quotient.hh:119
Request the set implementation (bool weights).
Definition: a-star.hh:8
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:78
auto quotient(const Aut &a, typename detail::quotienter< Aut >::class_to_set_t &cs) -> quotient_t< Aut >
Definition: quotient.hh:124
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
std::vector< typename Cont::value_type > make_vector(const Cont &cont)
The content of cont as a vector.
Definition: vector.hh:20
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
static dyn::context ctx(const driver &d)
Get the context of the driver.
Definition: parse.cc:82
Request the bitset implementation (bool weights).
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.
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:105
polynomialset< Context, Kind > make_polynomialset(const Context &context)
State labelset.
Definition: fwd.hh:22
Ctx make_context(const std::string &name)
Definition: make-context.hh:21