3 #include <unordered_map>
27 template <Automaton Aut>
31 "minimize: moore: requires Boolean weights");
33 "minimize: moore: requires free labelset");
35 using automaton_t = Aut;
42 using genset_t = decltype(std::declval<labelset_t>().generators());
48 using classes_t = std::vector<class_t>;
49 using set_t = std::vector<state_t>;
50 using state_to_class_t = std::unordered_map<state_t, class_t>;
51 using target_class_to_states_t = std::unordered_map<class_t, set_t>;
52 using class_to_set_t = std::vector<set_t>;
54 constexpr
static const char* me() {
return "minimize-moore"; }
57 constexpr
static class_t class_invalid = -1;
58 unsigned num_classes_ = 0;
61 class_to_set_t class_to_set_;
62 state_to_class_t state_to_class_;
66 using transition_map_t
71 transition_map_t transition_map_;
75 class_to_set_.clear();
76 state_to_class_.clear();
78 transition_map_.clear();
84 assert(!
set.empty());
86 if (number == class_invalid)
87 number = num_classes_++;
90 state_to_class_[s] = number;
92 if (number < class_to_set_.size())
93 class_to_set_[number] = std::move(set);
96 assert(number == class_to_set_.size());
97 class_to_set_.emplace_back(std::move(set));
105 class_t out_class(state_t s, label_t l)
107 const auto&
map = transition_map_[s];
108 auto dst =
map.find(l);
109 if (dst == std::end(
map))
110 return class_invalid;
112 return state_to_class_[dst->second.dst];
119 , gs_(a_->labelset()->generators())
129 class_to_set_t& classes()
132 return class_to_set_;
137 void build_classes_()
141 make_class({a_->pre()});
142 make_class({a_->post()});
144 set_t nonfinals, finals;
145 for (
auto s : a_->states())
147 finals.emplace_back(s);
149 nonfinals.emplace_back(s);
150 if (! nonfinals.empty())
151 make_class(std::move(nonfinals));
152 if (! finals.empty())
153 make_class(std::move(finals));
160 for (
class_t c = 0; c < num_classes_; ++c)
162 const set_t& c_states = class_to_set_[c];
167 target_class_to_states_t target_class_to_c_states;
168 for (
auto s : c_states)
170 auto c2 = out_class(s, l);
171 target_class_to_c_states[c2].emplace_back(s);
177 if (2 <= target_class_to_c_states.size())
181 for (
auto& p : target_class_to_c_states)
183 make_class(std::move(p.second), num);
200 template <Automaton Aut>
205 raise(
"minimize: invalid algorithm"
206 " (non-Boolean or non-free labelset):",
auto map(const std::tuple< Ts...> &ts, Fun f) -> decltype(map_tuple_(f, ts, make_index_sequence< sizeof...(Ts)>()))
Map a function on a tuple, return tuple of the results.
bool is_deterministic(const Aut &aut, state_t_of< Aut > s)
Whether state s is deterministic in aut.
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
bool is_trim(const Aut &a)
Whether all its states are useful.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
ATTRIBUTE_NORETURN std::enable_if_t<!is_free_boolean< Aut >), Aut > minimize(const Aut &, brzozowski_tag)
Handling of errors for dyn::minimize.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Request for Moore implementation of minimize (B and free).
Provide a variadic mul on top of a binary mul(), and one().
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
partition_automaton_t< Aut > quotient_t
The return type when calling quotient on Aut.
Cache the outgoing transitions of an automaton as efficient maps label -> vector<(weight, dst)>.
Request the set implementation (bool weights).
std::set< std::pair< std::string, std::string >> class_t
A set of label ranges.
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of