3 #include <unordered_map>
19 namespace detail_moore
21 template <
typename Aut>
25 "minimize: moore: requires Boolean weights");
27 "minimize: moore: requires free labelset");
41 using set_t = std::vector<state_t>;
47 constexpr
static const char*
me() {
return "minimize-moore"; }
69 class_to_set_.clear();
70 state_to_class_.clear();
72 class_to_res_state_.clear();
73 transition_map_.clear();
79 assert(!
set.empty());
81 if (number == class_invalid)
82 number = num_classes_++;
85 state_to_class_[s] = number;
87 if (number < class_to_set_.size())
88 class_to_set_[number] = std::move(set);
91 assert(number == class_to_set_.size());
92 class_to_set_.emplace_back(std::move(set));
102 const auto& map = transition_map_[s];
103 auto dst = map.find(l);
104 if (dst == std::end(map))
107 return state_to_class_[dst->second.dst];
114 , gs_(a_->labelset()->genset())
139 set_t nonfinals, finals;
140 for (
auto s : a_->states())
142 finals.emplace_back(s);
144 nonfinals.emplace_back(s);
145 if (! nonfinals.empty())
147 if (! finals.empty())
157 const set_t& c_states = class_to_set_[c];
163 for (
auto s : c_states)
166 target_class_to_c_states[c2].emplace_back(s);
172 if (2 <= target_class_to_c_states.size())
176 for (
auto& p : target_class_to_c_states)
192 template <
typename Aut>
class_t make_class(set_t &&set, class_t number=class_invalid)
Make a new class with the given set of states.
minimizer(const Aut &a)
Build the minimizer. Computes the classes.
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
partition_automaton_t< Aut > quotient_t
The return type when calling quotient on Aut.
void build_classes_()
Build the initial classes, and split until fix point.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
static constexpr class_t class_invalid
An invalid class.
auto quotient(const Aut &a, typename detail::quotienter< Aut >::class_to_set_t &cs) -> quotient_t< Aut >
static constexpr const char * me()
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
class_to_set_t & classes()
The partition, as a list of classes.
std::unordered_map< state_t, class_t > state_to_class_t
state_to_class_t state_to_class_
std::vector< state_t > set_t
state_t_of< automaton_t > state_t
label_t_of< automaton_t > label_t
const labelset_t_of< Aut >::genset_t gs_
The generators.
vcsn::enable_if_t< std::is_same< weightset_t_of< Aut >, b >::value &&labelset_t_of< Aut >::is_free(), quotient_t< Aut > > minimize(const Aut &a, const std::string &algo="auto")
std::vector< state_t > class_to_state_t
std::vector< class_t > classes_t
Provide a variadic mul on top of a binary mul(), and one().
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
void require(bool b, Args &&...args)
If b is not verified, raise an error with args as message.
class_t out_class(state_t s, label_t l)
The destination class of s with l in a.
std::unordered_map< class_t, set_t > target_class_to_states_t
automaton_t a_
Input automaton, supplied at construction time.
bool is_trim(const Aut &a)
Whether all its states are useful.
std::vector< set_t > class_to_set_t
bool is_deterministic(const Aut &aut, state_t_of< Aut > s)
Whether state s is deterministic in aut.
transition_map_t transition_map_
class_to_set_t class_to_set_
class_to_state_t class_to_res_state_
auto minimize_moore(const Aut &a) -> quotient_t< Aut >
Minimize automaton a using the Moore algorithm.