Vcsn  2.2
Be Rational
minimize.hh
Go to the documentation of this file.
1 #pragma once
2 
10 #include <vcsn/algos/tags.hh>
11 #include <vcsn/dyn/automaton.hh>
12 #include <vcsn/misc/getargs.hh>
13 #include <vcsn/weightset/fwd.hh> // b
14 
15 namespace vcsn
16 {
22  template <Automaton Aut, typename Tag>
23  auto
24  minimize(const Aut& a, Tag)
26  {
28  return quotient(a, minimize.classes());
29  }
30 
32  template <Automaton Aut>
33  std::enable_if_t<std::is_same<weightset_t_of<Aut>, b>::value,
34  quotient_t<Aut>>
35  minimize(const Aut& a, auto_tag = {})
36  {
37  return minimize(a, signature_tag{});
38  }
39 
41  template <Automaton Aut>
42  std::enable_if_t<!std::is_same<weightset_t_of<Aut>, b>::value,
43  quotient_t<Aut>>
44  minimize(const Aut& a, auto_tag = {})
45  {
46  return minimize(a, weighted_tag{});
47  }
48 
54  template <Automaton Aut>
55  std::enable_if_t<is_free_boolean<Aut>(), quotient_t<Aut>>
56  minimize(const Aut& a, const std::string& algo)
57  {
58  static const auto map
60  {
61  "minimization algorithm",
62  {
63  {"auto", [](const Aut& a){ return minimize(a, auto_tag{}); }},
64  {"hopcroft", [](const Aut& a){ return minimize(a, hopcroft_tag{}); }},
65  {"moore", [](const Aut& a){ return minimize(a, moore_tag{}); }},
66  {"signature", [](const Aut& a){ return minimize(a, signature_tag{}); }},
67  {"weighted", [](const Aut& a){ return minimize(a, weighted_tag{}); }},
68  }
69  };
70  return map[algo](a);
71  }
72 
73 
79  template <Automaton Aut>
80  std::enable_if_t<std::is_same<weightset_t_of<Aut>, b>::value
81  && !labelset_t_of<Aut>::is_free(),
82  quotient_t<Aut>>
83  minimize(const Aut& a, const std::string& algo)
84  {
85  static const auto map
87  {
88  "minimization algorithm",
89  {
90  {"auto", [](const Aut& a){ return minimize(a, auto_tag{}); }},
91  {"signature", [](const Aut& a){ return minimize(a, signature_tag{}); }},
92  {"weighted", [](const Aut& a){ return minimize(a, weighted_tag{}); }},
93  }
94  };
95  return map[algo](a);
96  }
97 
102  template <Automaton Aut>
103  std::enable_if_t<!std::is_same<weightset_t_of<Aut>, b>::value,
104  quotient_t<Aut>>
105  minimize(const Aut& a, const std::string& algo)
106  {
107  static const auto map
109  {
110  "minimization algorithm",
111  {
112  {"auto", [](const Aut& a){ return minimize(a, auto_tag{}); }},
113  {"weighted", [](const Aut& a){ return minimize(a, weighted_tag{}); }},
114  }
115  };
116  return map[algo](a);
117  }
118 
120  template <Automaton Aut, typename Tag = auto_tag>
121  auto
122  cominimize(const Aut& a, Tag tag = {})
123  -> decltype(transpose(minimize(transpose(a), tag)))
124  {
125  return transpose(minimize(transpose(a), tag));
126  }
127 
128  /*----------------.
129  | dyn::minimize. |
130  `----------------*/
131 
132  namespace dyn
133  {
134  namespace detail
135  {
136 #if defined __GNUC__ && ! defined __clang__
137 # pragma GCC diagnostic push
138 # pragma GCC diagnostic ignored "-Wsuggest-attribute=noreturn"
139 #endif
140  template <Automaton Aut, typename Tag>
141  automaton minimize_tag_(const Aut& aut)
142  {
143  // There are several "minimize" that will match this
144  // definition: some are vcsn::minimize (e.g., for
145  // weighted_tag), but others will comes from vcsn::dyn::detail
146  // (e.g., for brzozowski_tag when inapplicable). So do not
147  // specify the namespace.
148  return make_automaton(minimize(aut, Tag{}));
149  }
150 #if defined __GNUC__ && ! defined __clang__
151 # pragma GCC diagnostic pop
152 #endif
153 
155  template <Automaton Aut, typename String>
156  automaton
157  minimize(const automaton& aut, const std::string& algo)
158  {
159  static const auto map = getarg<std::function<automaton(const Aut&)>>
160  {
161  "minimization algorithm",
162  {
163  {"auto", minimize_tag_<Aut, auto_tag>},
164  {"brzozowski", minimize_tag_<Aut, brzozowski_tag>},
165  {"hopcroft", minimize_tag_<Aut, hopcroft_tag>},
166  {"moore", minimize_tag_<Aut, moore_tag>},
167  {"signature", minimize_tag_<Aut, signature_tag>},
168  {"weighted", minimize_tag_<Aut, weighted_tag>},
169  }
170  };
171  return map[algo](aut->as<Aut>());
172  }
173  }
174  }
175 
176 
177  /*-----------------.
178  | dyn::cominimize. |
179  `-----------------*/
180 
181  namespace dyn
182  {
183  namespace detail
184  {
185  template <Automaton Aut, typename Tag>
186  automaton cominimize_tag_(const Aut& aut)
187  {
188  auto res = transpose(minimize(transpose(aut), Tag{}));
189  return make_automaton(res);
190  }
191 
193  template <Automaton Aut, typename String>
194  automaton
195  cominimize(const automaton& aut, const std::string& algo)
196  {
197  static const auto map = getarg<std::function<automaton(const Aut&)>>
198  {
199  "cominimization algorithm",
200  {
201  {"auto", cominimize_tag_<Aut, auto_tag>},
202  {"brzozowski", cominimize_tag_<Aut, brzozowski_tag>},
203  {"hopcroft", cominimize_tag_<Aut, hopcroft_tag>},
204  {"moore", cominimize_tag_<Aut, moore_tag>},
205  {"signature", cominimize_tag_<Aut, signature_tag>},
206  {"weighted", cominimize_tag_<Aut, weighted_tag>},
207  }
208  };
209  return map[algo](aut->as<Aut>());
210  }
211  }
212  }
213 
214 } // namespace vcsn
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
Definition: automaton.hh:75
ATTRIBUTE_NORETURN std::enable_if_t<!is_free_boolean< Aut >), Aut > minimize(const Aut &, brzozowski_tag)
Handling of errors for dyn::minimize.
partition_automaton_t< Aut > quotient_t
The return type when calling quotient on Aut.
Definition: quotient.hh:119
Definition: a-star.hh:8
auto quotient(const Aut &a, typename detail::quotienter< Aut >::class_to_set_t &cs) -> quotient_t< Aut >
Definition: quotient.hh:124
automaton cominimize_tag_(const Aut &aut)
Definition: minimize.hh:186
Aut transpose(const transpose_automaton< Aut > &aut)
Definition: transpose.hh:227
Request for Moore implementation of minimize (B and free).
A mapping from strings to Values.
Definition: getargs.hh:33
Tag to request the most appropriate version of an algorithm.
Definition: tags.hh:16
Request for Hopcroft implementation of minimize (B and free).
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69
auto cominimize(const Aut &a, Tag tag={}) -> decltype(transpose(minimize(transpose(a), tag)))
Cominimization.
Definition: minimize.hh:122
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.
Request for Moore implementation of minimize (B).
automaton minimize_tag_(const Aut &aut)
Definition: minimize.hh:141
automaton transpose(automaton &aut)
Bridge.
Definition: transpose.hh:247
Request for the weighted version of an algorithm.
Definition: tags.hh:122
automaton cominimize(const automaton &aut, const std::string &algo)
Bridge.
Definition: minimize.hh:195
weightset_mixin< detail::b_impl > b
Definition: fwd.hh:48