36 template <
typename Aut>
41 "determinize: boolean: requires free labelset");
43 "determinize: boolean: requires Boolean weights");
48 template <
typename Ctx = context_t>
75 for (
auto t :
input_->final_transitions())
81 static symbol res(
"determinized_automaton<"
88 o <<
"determinized_automaton<";
95 state_t state(const state_name_t& ss)
97 // Benches show that the map_.emplace technique is slower, and
98 // then that operator[] is faster than emplace.
100 auto i = map_.find(ss);
101 if (i == std::end(map_))
103 res = this->new_state();
106 if (ss.intersects(finals_))
107 this->set_final(res);
120 = std::map<label_t, state_name_t, vcsn::less<labelset_t>>;
121 auto dests = dests_t{};
122 while (!todo_.empty())
124 auto ss = std::move(todo_.top());
125 state_t src = state(ss);
129 for (auto s = ss.find_first(); s != ss.npos;
132 // Cache the output transitions of state s.
133 auto i = successors_.find(s);
134 if (i == successors_.end())
136 i = successors_.emplace(s, label_map_t{}).first;
138 for (auto t : input_->out(s))
140 auto l = input_->label_of(t);
141 if (j.find(l) == j.end())
142 j[l].resize(state_size_);
143 j[l].set(input_->dst_of(t));
147 // Store in dests the possible destinations per label.
148 for (const auto& p : i->second)
150 auto j = dests.find(p.first);
151 if (j == dests.end())
152 dests[p.first] = p.second;
154 j->second |= p.second;
158 // Outgoing transitions from the current (result) state.
159 for (const auto& d : dests)
160 this->new_transition(src, state(d.second), d.first);
164 bool state_has_name(state_t s) const
166 return has(origins(), s);
170 print_state_name(state_t s, std::ostream& o,
172 bool delimit = false) const
174 auto i = origins().find(s);
175 if (i == std::end(origins()))
176 this->print_state(s, o);
181 const char* sep = "";
182 for (auto s: i->second)
185 input_->print_state_name(s, o, fmt, true);
195 using origins_t = std::map<state_t, std::set<state_t>>;
196 mutable origins_t origins_;
201 if (origins_.empty())
202 for (const auto& p: map_)
204 std::set<state_t> from;
205 const auto& ss = p.first;
206 for (auto s = ss.find_first(); s != ss.npos;
209 origins_.emplace(p.second, std::move(from));
216 using map_t = std::unordered_map<state_name_t, state_t>;
225 size_t state_size_ = input_->all_states().back() + 1;
228 using stack = std::stack<state_name_t>;
232 state_name_t finals_;
235 using label_map_t = std::unordered_map<label_t, state_name_t,
236 vcsn::hash<labelset_t>,
237 vcsn::equal_to<labelset_t>>;
238 using successors_t = std::map<state_t, label_map_t>;
239 successors_t successors_;
244 template <typename Aut>
245 using determinized_automaton
246 = std::shared_ptr<detail::determinized_automaton_impl<Aut>>;
248 template <typename Aut>
251 determinize(const Aut& a)
252 -> determinized_automaton<Aut>
254 auto res = make_shared_ptr<determinized_automaton<Aut>>(a);
260 template <typename Aut>
263 codeterminize(const Aut& a)
264 -> decltype(transpose(determinize(transpose(a))))
266 return transpose(determinize(transpose(a)));
269 /*---------------------------.
270 | weighted determinization. |
271 `---------------------------*/
279 template <typename Aut>
280 class detweighted_automaton_impl
281 : public automaton_decorator<fresh_automaton_t_of<Aut>>
283 static_assert(labelset_t_of<Aut>::is_free(),
284 "determinize: weighted: requires free labelset");
287 using automaton_t = Aut;
288 using context_t = context_t_of<automaton_t>;
289 template <typename Ctx = context_t>
290 using fresh_automaton_t = fresh_automaton_t_of<Aut, Ctx>;
291 using super_t = automaton_decorator<fresh_automaton_t<>>;
293 using label_t = label_t_of<automaton_t>;
294 using labelset_t = labelset_t_of<automaton_t>;
295 using weightset_t = weightset_t_of<automaton_t>;
297 using state_t = state_t_of<automaton_t>;
298 using weight_t = weight_t_of<automaton_t>;
303 stateset(const automaton_t& aut)
307 using value_t = state_t;
310 static constexpr
bool
336 return aut_->print_state_name(s, out, fmt);
353 n.set(
input_->pre(), ws_.one());
359 n.set(
input_->post(), ws_.one());
365 static symbol res(
"detweighted_automaton<"
372 o <<
"detweighted_automaton<";
373 input_->print_set(o, fmt);
380 // label -> <destination, sum of weights>.
382 = std::map<label_t, state_name_t, vcsn::less<labelset_t>>;
383 auto dests = dests_t{};
384 while (!todo_.empty())
386 auto ss = std::move(todo_.front());
391 for (const auto& p : ss)
393 auto s = label_of(p);
394 auto v = weight_of(p);
395 for (auto t : input_->all_out(s))
397 auto l = input_->label_of(t);
398 auto dst = input_->dst_of(t);
399 auto w = ws_.mul(v, input_->weight_of(t));
401 // For each letter, update destination state, and
404 dests.emplace(l, ns_.zero());
406 ns_.add_here(d, dst, w);
410 for (auto& d : dests)
411 if (!ns_.is_zero(d.second))
413 weight_t w = ns_.normalize_here(d.second);
414 this->new_transition(src, state_(d.second),
420 bool state_has_name(state_t s) const
422 return has(origins(), s);
426 print_state_name(state_t ss, std::ostream& o,
427 format fmt = {}, bool delimit = false) const
429 auto i = origins().find(ss);
430 if (i == origins().end())
431 this->print_state(ss, o);
436 ns_.print(i->second, o, fmt, ", ");
444 using origins_t = std::map<state_t, state_name_t>;
445 mutable origins_t origins_;
449 if (origins_.empty())
450 for (const auto& p: map_)
451 origins_.emplace(p.second, p.first);
458 state_t state_(const state_name_t& name)
460 // Benches show that the map_.emplace technique is slower, and
461 // then that operator[] is faster than emplace.
463 auto i = map_.find(name);
464 if (i == std::end(map_))
466 res = this->new_state();
476 using map_t = std::unordered_map<state_name_t, state_t,
477 vcsn::hash<state_nameset_t>,
478 vcsn::equal_to<state_nameset_t>>;
485 weightset_t ws_ = *input_->weightset();
488 state_nameset_t ns_ = {{stateset(input_), ws_}};
491 using queue = std::queue<state_name_t>;
497 template <typename Aut>
498 using detweighted_automaton
499 = std::shared_ptr<detail::detweighted_automaton_impl<Aut>>;
501 template <typename Aut>
504 determinize_weighted(const Aut& a)
505 -> detweighted_automaton<Aut>
507 auto res = make_shared_ptr<detweighted_automaton<Aut>>(a);
512 template <typename Aut>
515 codeterminize_weighted(const Aut& aut)
516 -> decltype(transpose(determinize_weighted(transpose(aut))))
518 return transpose(determinize_weighted(transpose(aut)));
521 /*-------------------.
522 | dyn::determinize. |
523 `-------------------*/
529 template <typename Aut, typename Type>
531 = vcsn::enable_if_t<std::is_same<weightset_t_of<Aut>, b>::value, Type>;
533 template <typename Aut, typename Type>
534 using if_not_boolean_t
535 = vcsn::enable_if_t<!std::is_same<weightset_t_of<Aut>, b>::value, Type>;
539 template <typename Aut, typename String>
541 if_boolean_t<Aut, automaton>
542 determinize_(const automaton& aut, const std::string& algo)
544 const auto& a = aut->as<Aut>();
545 if (algo == "auto" || algo == "boolean")
546 return make_automaton(::vcsn::determinize(a));
547 else if (algo == "weighted")
548 return make_automaton(::vcsn::determinize_weighted(a));
550 raise("determinize: invalid algorithm: ", str_escape(algo));
554 template <typename Aut, typename String>
556 if_not_boolean_t<Aut, automaton>
557 determinize_(const automaton& aut, const std::string& algo)
559 const auto& a = aut->as<Aut>();
560 if (algo == "boolean")
561 raise("determinize: cannot apply Boolean determinization");
562 else if (algo == "auto" || algo == "weighted")
563 return make_automaton(::vcsn::determinize_weighted(a));
565 raise("determinize: invalid algorithm: ", str_escape(algo));
569 template <typename Aut, typename String>
572 determinize(const automaton& aut, const std::string& algo)
574 return determinize_<Aut, String>(aut, algo);
580 /*---------------------.
581 | dyn::codeterminize. |
582 `---------------------*/
584 // FIXME: duplicate code with determinize.
590 template <typename Aut, typename String>
592 if_boolean_t<Aut, automaton>
593 codeterminize_(const automaton& aut, const std::string& algo)
595 const auto& a = aut->as<Aut>();
596 if (algo == "auto" || algo == "boolean")
597 return make_automaton(::vcsn::codeterminize(a));
598 else if (algo == "weighted")
599 return make_automaton(::vcsn::codeterminize_weighted(a));
601 raise("codeterminize: invalid algorithm: ", str_escape(algo));
605 template <typename Aut, typename String>
607 if_not_boolean_t<Aut, automaton>
608 codeterminize_(const automaton& aut, const std::string& algo)
610 const auto& a = aut->as<Aut>();
611 if (algo == "boolean")
612 raise("codeterminize: cannot apply Boolean determinization");
613 else if (algo == "auto" || algo == "weighted")
614 return make_automaton(::vcsn::codeterminize_weighted(a));
616 raise("codeterminize: invalid algorithm: ", str_escape(algo));
620 template <typename Aut, typename String>
623 codeterminize(const automaton& aut, const std::string& algo)
625 return codeterminize_<Aut, String>(aut, algo);
boost::dynamic_bitset<> dynamic_bitset
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
auto out(Args &&...args) const -> decltype(aut_-> out(std::forward< Args >(args)...))
std::ostream & print(state_t s, std::ostream &out, format fmt={}) const
static size_t hash(state_t s)
fresh_automaton_t_of< Aut, Ctx > fresh_automaton_t
std::ostream & print(const std::tuple< Args...> &args, std::ostream &o)
weightset_mixin< detail::r_impl > r
typename state_nameset_t::value_t state_name_t
static constexpr auto pre(Args &&...args) -> decltype(element_type::pre(std::forward< Args >(args)...))
static bool equal(state_t l, state_t r)
static constexpr auto post(Args &&...args) -> decltype(element_type::post(std::forward< Args >(args)...))
auto states(Args &&...args) const -> decltype(aut_-> states(std::forward< Args >(args)...))
size_t state_size_
We use state numbers as indexes, so we need to know the last state number.
state_t_of< automaton_t > state_t
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
polynomialset< context< stateset, weightset_t >> state_nameset_t
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
state_name_t finals_
Set of final states in the input automaton.
Aggregate an automaton, and forward calls to it.
detweighted_automaton_impl(const automaton_t &a)
Build the weighted determinizer.
The subset construction automaton from another.
std::ostream & print_set(std::ostream &o, format fmt={}) const
auto hash_value(const T &v) -> decltype(std::hash< T >
Following the naming convention of Boost.
determinized_automaton_impl(const automaton_t &a)
Build the determinizer.
typename Aut::element_type::template fresh_automaton_t< Context > fresh_automaton_t_of
context_t_of< automaton_t > context_t
Provide a variadic mul on top of a binary mul(), and one().
labelset_t_of< automaton_t > labelset_t
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
std::ostream & print_set(std::ostream &o, format fmt={}) const
state_t_of< automaton_t > state_t
Result automaton state type.
label_t_of< automaton_t > label_t
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
dynamic_bitset state_name_t
The name: set of (input) states.
automaton_t input_
Input automaton.
automaton_t aut_
The wrapped automaton, possibly const.
static constexpr bool is_letterized()
static bool less(state_t l, state_t r)