3 #include <unordered_map>
4 #include <unordered_set>
27 template <Automaton Aut>
31 "minimize: signature: requires Boolean weights");
33 using automaton_t = Aut;
39 using set_t = std::vector<state_t>;
40 using state_to_class_t = std::unordered_map<state_t, class_t>;
41 using class_to_set_t = std::vector<set_t>;
43 constexpr
static const char* me() {
return "minimize-signature"; }
46 constexpr
static class_t class_invalid = -1;
48 struct state_output_for_label_t
52 std::vector<state_t> to_states;
56 using state_output_t = std::vector<state_output_for_label_t>;
58 struct signature_hasher
65 size_t operator()(
const state_output_t& state_output)
const noexcept
69 for (
auto& t : state_output)
71 const label_t&
label = t.label;
76 for (
auto s : t.to_states)
77 bits.set(state_to_class_.at(s));
83 size_t operator()(state_t s)
const noexcept
85 return operator()(minimizer_.state_to_state_output_.at(s));
89 const state_to_class_t& state_to_class_ = minimizer_.state_to_class_;
90 unsigned num_classes_ = minimizer_.num_classes_;
93 struct signature_equal_to
99 bool operator()(
const state_output_t& as,
100 const state_output_t& bs)
const noexcept
102 if (as.size() != bs.size())
106 for (
auto i = as.cbegin(), i_end = as.cend(), j = bs.cbegin();
110 if (! ls_.equal(i->label, j->label))
113 a_bits.reset(); b_bits.reset();
114 for (
auto s : i->to_states)
115 a_bits.set(state_to_class_.at(s));
116 for (
auto s : j->to_states)
117 b_bits.set(state_to_class_.at(s));
118 if (a_bits != b_bits)
125 bool operator()(
const state_t& a,
const state_t&
b)
const noexcept
127 return operator()(minimizer_.state_to_state_output_.at(a),
128 minimizer_.state_to_state_output_.at(b));
132 const labelset_t& ls_ = minimizer_.ls_;
133 const state_to_class_t& state_to_class_ = minimizer_.state_to_class_;
134 const size_t num_classes_ = minimizer_.num_classes_;
141 using signature_multimap
143 signature_hasher, signature_equal_to>;
147 class_to_set_.clear();
148 state_to_class_.clear();
160 if (number == class_invalid)
161 number = num_classes_++;
164 state_to_class_[s] = number;
166 if (number < class_to_set_.size())
167 class_to_set_[number] = std::move(set);
170 assert(number == class_to_set_.size());
171 class_to_set_.emplace_back(std::move(set));
184 for (
auto s : a_->all_states())
187 using label_to_states_t
191 label_to_states_t label_to_states;
193 label_to_states[a_->label_of(t)].emplace_back(a_->dst_of(t));
196 state_output_t& state_output = state_to_state_output_[s];
197 for (
auto& l_ss : label_to_states)
200 state_output.emplace_back(state_output_for_label_t{l_ss.first,
201 std::move(l_ss.second)});
207 class_to_set_t& classes()
210 return class_to_set_;
215 void build_classes_()
221 std::unordered_set<class_t> classes;
223 const auto&
all = a_->all_states();
224 classes.insert(make_class(set_t{std::begin(
all), std::end(
all)}));
227 for (
bool go_on =
true; go_on; )
230 for (
auto i = std::begin(classes), end = std::end(classes);
235 const set_t& c_states = class_to_set_.at(c);
240 = signature_multimap{1,
241 signature_hasher{*
this},
242 signature_equal_to{*
this}};
243 for (
auto s : c_states)
244 sig_to_state[s].emplace_back(s);
246 if (2 <= sig_to_state.size())
250 i = classes.erase(i);
254 for (
auto& p: sig_to_state)
256 bool singleton = p.second.size() == 1;
257 class_t c2 = make_class(std::move(p.second), c);
272 const labelset_t& ls_ = *a_->labelset();
274 unsigned num_classes_ = 0;
276 class_to_set_t class_to_set_;
277 state_to_class_t state_to_class_;
281 std::unordered_map<state_t, state_output_t> state_to_state_output_;
289 template <Automaton Aut>
291 std::enable_if_t<!std::is_same<weightset_t_of<Aut>,
b>::value,
295 raise(
"minimize: invalid algorithm (non-Boolean): signature");
Request for Moore implementation of minimize (B).
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
void hash_combine(std::size_t &seed, const T &v)
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
auto sort(const Aut &a) -> permutation_automaton< Aut >
void hash_combine_hash(std::size_t &seed, size_t h)
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
bool all(Bool &&...values)
Whether all the values evaluate as true.
Request the unordered_map implementation.
Provide a variadic mul on top of a binary mul(), and one().
Functor to compare Values of ValueSets.
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.
boost::dynamic_bitset<> dynamic_bitset
value_impl< detail::label_tag > label
Indentation relative functions.
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