Vcsn  2.4
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>
142  automaton minimize_tag_(const Aut& aut)
143  {
144  // There are several "minimize" that will match this
145  // definition: some are vcsn::minimize (e.g., for
146  // weighted_tag), but others will comes from vcsn::dyn::detail
147  // (e.g., for brzozowski_tag when inapplicable). So do not
148  // specify the namespace.
149  return minimize(aut, Tag{});
150  }
151 #if defined __GNUC__ && ! defined __clang__
152 # pragma GCC diagnostic pop
153 #endif
154 
156  template <Automaton Aut, typename String>
157  automaton
158  minimize(const automaton& aut, const std::string& algo)
159  {
160  static const auto map = getarg<std::function<automaton(const Aut&)>>
161  {
162  "minimization algorithm",
163  {
164  {"auto", minimize_tag_<Aut, auto_tag>},
165  {"brzozowski", minimize_tag_<Aut, brzozowski_tag>},
166  {"hopcroft", minimize_tag_<Aut, hopcroft_tag>},
167  {"moore", minimize_tag_<Aut, moore_tag>},
168  {"signature", minimize_tag_<Aut, signature_tag>},
169  {"weighted", minimize_tag_<Aut, weighted_tag>},
170  }
171  };
172  return map[algo](aut->as<Aut>());
173  }
174  }
175  }
176 
177 
178  /*-----------------.
179  | dyn::cominimize. |
180  `-----------------*/
181 
182  namespace dyn
183  {
184  namespace detail
185  {
187  template <Automaton Aut, typename Tag>
188  automaton cominimize_tag_(const Aut& aut)
189  {
190  return transpose(minimize(transpose(aut), Tag{}));
191  }
192 
194  template <Automaton Aut, typename String>
195  automaton
196  cominimize(const automaton& aut, const std::string& algo)
197  {
198  static const auto map = getarg<std::function<automaton(const Aut&)>>
199  {
200  "cominimization algorithm",
201  {
202  {"auto", cominimize_tag_<Aut, auto_tag>},
203  {"brzozowski", cominimize_tag_<Aut, brzozowski_tag>},
204  {"hopcroft", cominimize_tag_<Aut, hopcroft_tag>},
205  {"moore", cominimize_tag_<Aut, moore_tag>},
206  {"signature", cominimize_tag_<Aut, signature_tag>},
207  {"weighted", cominimize_tag_<Aut, weighted_tag>},
208  }
209  };
210  return map[algo](aut->as<Aut>());
211  }
212  }
213  }
214 
215 } // namespace vcsn
automaton cominimize(const automaton &aut, const std::string &algo)
Bridge.
Definition: minimize.hh:196
automaton transpose(automaton &aut)
Bridge.
Definition: transpose.hh:273
Request for Moore implementation of minimize (B and free).
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.
automaton minimize_tag_(const Aut &aut)
Helper function to facilitate dispatch below.
Definition: minimize.hh:142
auto quotient(const Aut &a, typename detail::quotienter< Aut >::class_to_set_t &cs) -> quotient_t< Aut >
Definition: quotient.hh:123
weightset_mixin< detail::b_impl > b
Definition: fwd.hh:48
Tag to request the most appropriate version of an algorithm.
Definition: tags.hh:16
Definition: a-star.hh:8
automaton cominimize_tag_(const Aut &aut)
Helper function to facilitate dispatch below.
Definition: minimize.hh:188
A dyn automaton.
Definition: automaton.hh:17
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).
auto cominimize(const Aut &a, Tag tag={}) -> decltype(transpose(minimize(transpose(a), tag)))
Cominimization.
Definition: minimize.hh:122
A mapping from strings to Values.
Definition: getargs.hh:33
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
Request for the weighted version of an algorithm.
Definition: tags.hh:149
Request for Hopcroft implementation of minimize (B and free).
Aut transpose(const transpose_automaton< Aut > &aut)
The transpose of a transpose automaton is the original automaton.
Definition: transpose.hh:253
ATTRIBUTE_NORETURN std::enable_if_t<!is_free_boolean< Aut >), Aut > minimize(const Aut &, brzozowski_tag)
Handling of errors for dyn::minimize.