12 #include <vcsn/dyn/fwd.hh>
30 template <Automaton Aut, wet_kind_t Kind,
bool Lazy = false>
35 "determinize: requires free labelset");
65 return aut_->origins();
71 :
super_t{make_polystate_automaton<automaton_t, kind, Lazy>(a)}
76 aut_->input_->src_of(t),
77 aut_->input_->weight_of(t));
82 static auto res =
symbol{
"determinized_automaton<"
85 +
", " + (Lazy ?
"true" :
"false")
92 o <<
"determinized_automaton<";
93 aut_->input_->print_set(o, fmt);
102 while (!
aut_->todo_.empty())
105 const auto& ss =
aut_->state_name(
aut_->todo_.front());
115 if (Lazy &&
aut_->is_lazy(s))
117 return aut_->all_out(s);
130 template <wet_kind_t K = kind>
132 -> std::enable_if_t<K == wet_kind_t::bitset>
135 "determinize: boolean: requires B or F2 weights");
137 aut_->set_lazy(src,
false);
140 = std::map<label_t, state_name_t, vcsn::less<labelset_t>>;
141 auto dests = dests_t{};
142 for (
const auto& p : ss)
151 for (
auto t :
out(
aut_->input_, s))
153 auto l =
aut_->input_->label_of(t);
154 auto dst =
aut_->input_->dst_of(t);
155 if (j.find(l) == j.end())
156 j.emplace(l,
aut_->zero());
157 aut_->ns_.new_weight(j[l], dst,
aut_->ws_.one());
162 for (
const auto& p : i->second)
164 auto j = dests.find(p.first);
165 if (j == dests.end())
166 dests[p.first] = p.second;
168 aut_->ns_.add_here(j->second, p.second);
173 for (
auto& d : dests)
175 if (!
aut_->ns_.is_zero(d.second))
180 if (!
aut_->ws_.is_zero(w))
185 template <wet_kind_t K = kind>
187 -> std::enable_if_t<K != wet_kind_t::bitset>
190 aut_->set_lazy(src,
false);
193 = std::map<label_t, state_name_t, vcsn::less<labelset_t>>;
194 auto dests = dests_t{};
195 for (
const auto& p : ss)
199 for (
auto t :
out(
aut_->input_, s))
201 auto l =
aut_->input_->label_of(t);
202 auto dst =
aut_->input_->dst_of(t);
203 auto w =
aut_->ws_.mul(
v,
aut_->input_->weight_of(t));
208 dests.emplace(l,
aut_->zero());
209 aut_->ns_.add_here(dests[l], dst, w);
214 for (
auto& d : dests)
216 if (!
aut_->ns_.is_zero(d.second))
224 if (!
aut_->ws_.is_zero(w))
241 template <Automaton Aut, wet_kind_t Kind,
bool Lazy = false>
243 = std::shared_ptr<detail::determinized_automaton_impl<Aut, Kind, Lazy>>;
245 template <Automaton Aut,
typename Tag,
bool Lazy = false>
249 constexpr
auto kind =
250 std::is_same<Tag, boolean_tag>::value
252 : detail::wet_kind<labelset_t_of<Aut>, weightset_t_of<Aut>>();
253 auto res = make_shared_ptr<determinized_automaton<Aut, kind, Lazy>>(a);
263 template <Automaton Aut>
265 = std::conditional_t<std::is_same<weight_t_of<Aut>,
bool>::value,
271 template <Automaton Aut,
bool Lazy = false>
277 return determinize(a, detail::determinization_tag<Aut>{}, lazy);
279 catch(
const std::runtime_error& e)
281 raise(e,
" while determinizing");
296 template <Automaton Aut,
typename Type =
void>
298 = std::enable_if_t<std::is_same<weight_t_of<Aut>,
bool>::value, Type>;
301 template <Automaton Aut,
typename Type =
void>
303 = std::enable_if_t<!std::is_same<weight_t_of<Aut>,
bool>::value, Type>;
306 template <Automaton Aut,
typename Tag,
bool Lazy = false>
313 template <Automaton Aut,
typename String>
314 enable_if_boolean_t<Aut, automaton>
319 "determinization algorithm",
321 {
"auto", determinize_tag_<Aut, auto_tag>},
322 {
"boolean", determinize_tag_<Aut, boolean_tag>},
323 {
"weighted", determinize_tag_<Aut, weighted_tag>},
324 {
"lazy",
"lazy,auto"},
325 {
"lazy,auto",
"lazy,weighted"},
326 {
"lazy,weighted", determinize_tag_<Aut, weighted_tag, true>},
329 return map[algo](aut->
as<Aut>());
333 template <Automaton Aut,
typename String>
334 enable_if_not_boolean_t<Aut, automaton>
339 "determinization algorithm",
341 {
"auto", determinize_tag_<Aut, auto_tag>},
342 {
"weighted", determinize_tag_<Aut, weighted_tag>},
343 {
"lazy",
"lazy,auto"},
344 {
"lazy,auto",
"lazy,weighted"},
345 {
"lazy,weighted", determinize_tag_<Aut, weighted_tag, true>},
348 if (algo ==
"boolean")
349 raise(
"determinize: cannot apply Boolean"
350 " determinization to weighted automata");
351 return map[algo](aut->
as<Aut>());
355 template <Automaton Aut,
typename String>
359 return determinize_<Aut, String>(aut, algo);
369 template <Automaton Aut,
typename Tag = auto_tag>
385 template <Automaton Aut,
typename Tag>
392 template <Automaton Aut,
typename String>
393 enable_if_boolean_t<Aut, automaton>
398 "codeterminization algorithm",
400 {
"auto", codeterminize_tag_<Aut, auto_tag>},
401 {
"boolean", codeterminize_tag_<Aut, boolean_tag>},
402 {
"weighted", codeterminize_tag_<Aut, weighted_tag>},
405 return map[algo](aut->
as<Aut>());
409 template <Automaton Aut,
typename String>
410 enable_if_not_boolean_t<Aut, automaton>
415 "codeterminization algorithm",
417 {
"auto", codeterminize_tag_<Aut, auto_tag>},
418 {
"weighted", codeterminize_tag_<Aut, weighted_tag>},
421 if (algo ==
"boolean")
422 raise(
"codeterminize: cannot apply Boolean"
423 " determinization to weighted automata");
424 return map[algo](aut->
as<Aut>());
428 template <Automaton Aut,
typename String>
432 return codeterminize_<Aut, String>(aut, algo);
auto complete_(state_t src, const state_name_t &ss) -> std::enable_if_t< K==wet_kind_t::bitset >
Compute the outgoing transitions of this state.
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
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.
automaton codeterminize(const automaton &aut, const std::string &algo)
Bridge.
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
wet_kind_t
Different implementations of wets.
state_t_of< automaton_t > state_t
This is useful to make hashes with labels or weights as keys without using non-default constructors; ...
std::enable_if_t< std::is_same< weight_t_of< Aut >, bool >::value, Type > enable_if_boolean_t
Enable if Aut is over Booleans.
Request the bitset implementation (bool weights).
This is useful to make hashes with labels or weights as keys without using non-default constructors; ...
label_t_of< automaton_t > label_t
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Aggregate an automaton, and forward calls to it.
An input/output format for valuesets.
The subset construction automaton from another.
Tag to request the most appropriate version of an algorithm.
auto set_final(Args &&...args) -> decltype(aut_-> set_ final(std
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
std::ostream & print_set(std::ostream &o, format fmt={}) const
auto weight_of(Args &&...args) const -> decltype(aut_-> weight_of(std::forward< Args >(args)...))
auto complete_(state_t src, const state_name_t &ss) -> std::enable_if_t< K!=wet_kind_t::bitset >
Compute the outgoing transitions of this state.
auto label_of(Args &&...args) const -> decltype(aut_-> label_of(std::forward< Args >(args)...))
std::enable_if_t<!std::is_same< weight_t_of< Aut >, bool >::value, Type > enable_if_not_boolean_t
Enable if Aut is not over Booleans.
Request the unordered_map implementation.
weight_t_of< automaton_t > weight_t
std::map< state_t, label_map_t > successors_t
context_t_of< automaton_t > context_t
Labels and weights.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
automaton codeterminize_tag_(const Aut &aut)
labelset_t_of< automaton_t > labelset_t
automaton determinize(const automaton &aut, const std::string &algo)
Bridge.
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Aut transpose(const transpose_automaton< Aut > &aut)
The transpose of a transpose automaton is the original automaton.
std::integral_constant< bool, B > bool_constant
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
enable_if_not_boolean_t< Aut, automaton > codeterminize_(const automaton &aut, const std::string &algo)
Weighted Bridge.
Request for the weighted version of an algorithm.
void operator()()
Determinize the automaton.
enable_if_not_boolean_t< Aut, automaton > determinize_(const automaton &aut, const std::string &algo)
Weighted Bridge.
determinized_automaton_impl(const automaton_t &a)
Build the determinizer.
auto all_out(state_t s) const -> decltype(all_out(aut_, s))
All the outgoing transitions.
void complete_(state_t s) const
Complete a state: find its outgoing transitions.
automaton determinize_tag_(const Aut &aut)
Helper function to facilitate dispatch below.
A mapping from strings to Values.
std::unordered_map< label_t, state_name_t, vcsn::hash< labelset_t >, vcsn::equal_to< labelset_t >> label_map_t
successors[SOURCE-STATE][LABEL] = DEST-STATESET.
state_name_t finals_
Set of final states in the input automaton.
automaton_t aut_
The wrapped automaton, possibly const.
auto codeterminize(const Aut &aut, Tag tag={})
auto & as()
Extract wrapped typed automaton.
std::conditional_t< std::is_same< weight_t_of< Aut >, bool >::value, boolean_tag, weighted_tag > determinization_tag
The best tag depending on the type of Aut.
static constexpr wet_kind_t kind
std::shared_ptr< detail::determinized_automaton_impl< Aut, Kind, Lazy >> determinized_automaton
A determinized automaton as a shared pointer.
typename super_t::element_type::state_name_t state_name_t
The state name: set of (input) states.
auto final_transitions(const Aut &aut) -> decltype(aut->all_in(aut->post()))
Indexes of transitions from (visible) final states.
std::string to_string(direction d)
Conversion to string.
auto determinize(const Aut &a, Tag={}, bool_constant< Lazy >={})
weightset_t_of< automaton_t > weightset_t
auto new_transition(Args &&...args) -> decltype(aut_-> new_transition(std::forward< Args >(args)...))
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of