Vcsn  2.3
Be Rational
determinize.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <string>
4 
5 #include <vcsn/algos/tags.hh>
7 #include <vcsn/core/automaton.hh>
8 #include <vcsn/core/automaton-decorator.hh> // all_out
10 #include <vcsn/ctx/traits.hh>
11 #include <vcsn/dyn/automaton.hh> // dyn::make_automaton
12 #include <vcsn/dyn/fwd.hh>
13 #include <vcsn/misc/getargs.hh>
14 #include <vcsn/misc/raise.hh>
16 
17 namespace vcsn
18 {
19  /*----------------------.
20  | subset construction. |
21  `----------------------*/
22 
23  namespace detail
24  {
30  template <Automaton Aut, wet_kind_t Kind, bool Lazy = false>
32  : public automaton_decorator<polystate_automaton<Aut, Kind, Lazy>>
33  {
34  static_assert(labelset_t_of<Aut>::is_free(),
35  "determinize: requires free labelset");
36 
37  public:
38  using automaton_t = Aut;
39  constexpr static wet_kind_t kind = Kind;
40  using super_t
43 
50 
54 
56  using state_name_t = typename super_t::element_type::state_name_t;
57 
58  using super_t::aut_;
59  auto strip() const
60  {
61  return aut_->strip();
62  }
63  auto origins() const
64  {
65  return aut_->origins();
66  }
67 
71  : super_t{make_polystate_automaton<automaton_t, kind, Lazy>(a)}
72  {
73  // Final states.
74  for (auto t : final_transitions(aut_->input_))
75  aut_->ns_.new_weight(finals_,
76  aut_->input_->src_of(t),
77  aut_->input_->weight_of(t));
78  }
79 
80  static symbol sname()
81  {
82  static auto res = symbol{"determinized_automaton<"
84  + ", " + to_string(kind)
85  + ", " + (Lazy ? "true" : "false")
86  + '>'};
87  return res;
88  }
89 
90  std::ostream& print_set(std::ostream& o, format fmt = {}) const
91  {
92  o << "determinized_automaton<";
93  aut_->input_->print_set(o, fmt);
94  return o << ", " << to_string(kind)
95  << ", " << Lazy
96  << '>';
97  }
98 
100  void operator()()
101  {
102  while (!aut_->todo_.empty())
103  {
104  state_t src = aut_->state(aut_->todo_.front());
105  const auto& ss = aut_->state_name(aut_->todo_.front());
106  aut_->todo_.pop();
107  complete_(src, ss);
108  }
109  }
110 
112  auto all_out(state_t s) const
113  -> decltype(all_out(aut_, s))
114  {
115  if (Lazy && aut_->is_lazy(s))
116  complete_(s);
117  return aut_->all_out(s);
118  }
119 
120  private:
122  void complete_(state_t s) const
123  {
124  const auto& orig = origins();
125  const_cast<self_t&>(*this).complete_(s, orig.at(s));
126  }
127 
130  template <wet_kind_t K = kind>
131  auto complete_(state_t src, const state_name_t& ss)
132  -> std::enable_if_t<K == wet_kind_t::bitset>
133  {
134  static_assert(std::is_same<weight_t_of<Aut>, bool>::value,
135  "determinize: boolean: requires B or F2 weights");
136  if (Lazy)
137  aut_->set_lazy(src, false);
138  // label -> <destination, sum of weights>.
139  using dests_t
140  = std::map<label_t, state_name_t, vcsn::less<labelset_t>>;
141  auto dests = dests_t{};
142  for (const auto& p : ss)
143  {
144  auto s = label_of(p);
145  // Cache the output transitions of state s.
146  auto i = successors_.find(s);
147  if (i == successors_.end())
148  {
149  i = successors_.emplace(s, label_map_t{}).first;
150  auto& j = i->second;
151  for (auto t : out(aut_->input_, s))
152  {
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());
158  }
159  }
160 
161  // Store in dests the possible destinations per label.
162  for (const auto& p : i->second)
163  {
164  auto j = dests.find(p.first);
165  if (j == dests.end())
166  dests[p.first] = p.second;
167  else
168  aut_->ns_.add_here(j->second, p.second);
169  }
170  }
171 
172  // Outgoing transitions from the current (result) state.
173  for (auto& d : dests)
174  // Don't create transitions to the empty state.
175  if (!aut_->ns_.is_zero(d.second))
176  this->new_transition(src, aut_->state_(std::move(d.second)),
177  d.first);
178 
179  auto w = aut_->ns_.scalar_product(ss, finals_);
180  if (!aut_->ws_.is_zero(w))
181  this->set_final(src, w);
182  }
183 
185  template <wet_kind_t K = kind>
186  auto complete_(state_t src, const state_name_t& ss)
187  -> std::enable_if_t<K != wet_kind_t::bitset>
188  {
189  if (Lazy)
190  aut_->set_lazy(src, false);
191  // label -> <destination, sum of weights>.
192  using dests_t
193  = std::map<label_t, state_name_t, vcsn::less<labelset_t>>;
194  auto dests = dests_t{};
195  for (const auto& p : ss)
196  {
197  auto s = label_of(p);
198  auto v = weight_of(p);
199  for (auto t : out(aut_->input_, s))
200  {
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));
204 
205  // For each letter, update destination state, and
206  // sum of weights.
207  if (!has(dests, l))
208  dests.emplace(l, aut_->zero());
209  aut_->ns_.add_here(dests[l], dst, w);
210  }
211  }
212 
213  // Outgoing transitions from the current (result) state.
214  for (auto& d : dests)
215  // Don't create transitions to the empty state.
216  if (!aut_->ns_.is_zero(d.second))
217  {
218  weight_t w = aut_->ns_.normalize_here(d.second);
219  this->new_transition(src, aut_->state_(std::move(d.second)),
220  d.first, w);
221  }
222 
223  auto w = aut_->ns_.scalar_product(ss, finals_);
224  if (!aut_->ws_.is_zero(w))
225  this->set_final(src, w);
226  }
227 
230 
235  using successors_t = std::map<state_t, label_map_t>;
237  };
238  }
239 
241  template <Automaton Aut, wet_kind_t Kind, bool Lazy = false>
243  = std::shared_ptr<detail::determinized_automaton_impl<Aut, Kind, Lazy>>;
244 
245  template <Automaton Aut, typename Tag, bool Lazy = false>
246  auto
247  determinize(const Aut& a, Tag = {}, bool_constant<Lazy> = {})
248  {
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);
254  // Determinize.
255  if (!Lazy)
256  res->operator()();
257  return res;
258  }
259 
260  namespace detail
261  {
263  template <Automaton Aut>
264  using determinization_tag
265  = std::conditional_t<std::is_same<weight_t_of<Aut>, bool>::value,
266  boolean_tag,
268  }
269 
271  template <Automaton Aut, bool Lazy = false>
272  auto
273  determinize(const Aut& a, auto_tag = {}, bool_constant<Lazy> lazy = {})
274  {
275  try
276  {
277  return determinize(a, detail::determinization_tag<Aut>{}, lazy);
278  }
279  catch(const std::runtime_error& e)
280  {
281  raise(e, " while determinizing");
282  }
283  }
284 
285 
286 
287  /*-------------------.
288  | dyn::determinize. |
289  `-------------------*/
290 
291  namespace dyn
292  {
293  namespace detail
294  {
296  template <Automaton Aut, typename Type = void>
297  using enable_if_boolean_t
298  = std::enable_if_t<std::is_same<weight_t_of<Aut>, bool>::value, Type>;
299 
301  template <Automaton Aut, typename Type = void>
303  = std::enable_if_t<!std::is_same<weight_t_of<Aut>, bool>::value, Type>;
304 
306  template <Automaton Aut, typename Tag, bool Lazy = false>
307  automaton determinize_tag_(const Aut& aut)
308  {
310  }
311 
313  template <Automaton Aut, typename String>
314  enable_if_boolean_t<Aut, automaton>
315  determinize_(const automaton& aut, const std::string& algo)
316  {
318  {
319  "determinization algorithm",
320  {
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>},
327  }
328  };
329  return map[algo](aut->as<Aut>());
330  }
331 
333  template <Automaton Aut, typename String>
334  enable_if_not_boolean_t<Aut, automaton>
335  determinize_(const automaton& aut, const std::string& algo)
336  {
338  {
339  "determinization algorithm",
340  {
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>},
346  }
347  };
348  if (algo == "boolean")
349  raise("determinize: cannot apply Boolean"
350  " determinization to weighted automata");
351  return map[algo](aut->as<Aut>());
352  }
353 
355  template <Automaton Aut, typename String>
356  automaton
357  determinize(const automaton& aut, const std::string& algo)
358  {
359  return determinize_<Aut, String>(aut, algo);
360  }
361  }
362  }
363 
364 
365  /*----------------.
366  | codeterminize. |
367  `----------------*/
368 
369  template <Automaton Aut, typename Tag = auto_tag>
370  auto
371  codeterminize(const Aut& aut, Tag tag = {})
372  {
373  return transpose(determinize(transpose(aut), tag));
374  }
375 
376  /*---------------------.
377  | dyn::codeterminize. |
378  `---------------------*/
379 
380  // FIXME: code duplication with determinize.
381  namespace dyn
382  {
383  namespace detail
384  {
385  template <Automaton Aut, typename Tag>
387  {
388  return ::vcsn::codeterminize(aut, Tag{});
389  }
390 
392  template <Automaton Aut, typename String>
393  enable_if_boolean_t<Aut, automaton>
394  codeterminize_(const automaton& aut, const std::string& algo)
395  {
397  {
398  "codeterminization algorithm",
399  {
400  {"auto", codeterminize_tag_<Aut, auto_tag>},
401  {"boolean", codeterminize_tag_<Aut, boolean_tag>},
402  {"weighted", codeterminize_tag_<Aut, weighted_tag>},
403  }
404  };
405  return map[algo](aut->as<Aut>());
406  }
407 
409  template <Automaton Aut, typename String>
410  enable_if_not_boolean_t<Aut, automaton>
411  codeterminize_(const automaton& aut, const std::string& algo)
412  {
414  {
415  "codeterminization algorithm",
416  {
417  {"auto", codeterminize_tag_<Aut, auto_tag>},
418  {"weighted", codeterminize_tag_<Aut, weighted_tag>},
419  }
420  };
421  if (algo == "boolean")
422  raise("codeterminize: cannot apply Boolean"
423  " determinization to weighted automata");
424  return map[algo](aut->as<Aut>());
425  }
426 
428  template <Automaton Aut, typename String>
429  automaton
430  codeterminize(const automaton& aut, const std::string& algo)
431  {
432  return codeterminize_<Aut, String>(aut, algo);
433  }
434  }
435  }
436 } // namespace vcsn
label_t_of< automaton_t > label_t
Definition: determinize.hh:47
std::enable_if_t< std::is_same< weight_t_of< Aut >, bool >::value, Type > enable_if_boolean_t
Enable if Aut is over Booleans.
Definition: determinize.hh:298
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
Aut transpose(const transpose_automaton< Aut > &aut)
Definition: transpose.hh:238
std::map< state_t, label_map_t > successors_t
Definition: determinize.hh:235
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
context_t_of< automaton_t > context_t
Labels and weights.
Definition: determinize.hh:45
void operator()()
Determinize the automaton.
Definition: determinize.hh:100
auto all_out(state_t s) const -> decltype(all_out(aut_, s))
All the outgoing transitions.
Definition: determinize.hh:112
symbol sname()
Definition: name.hh:65
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
Aggregate an automaton, and forward calls to it.
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
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.
Definition: determinize.hh:131
Request the bitset implementation (bool weights).
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.
Definition: determinize.hh:267
typename super_t::element_type::state_name_t state_name_t
The state name: set of (input) states.
Definition: determinize.hh:56
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:64
Tag to request the most appropriate version of an algorithm.
Definition: tags.hh:16
auto set_final(Args &&...args) -> decltype(aut_-> set_ final(std
determinized_automaton_impl(const automaton_t &a)
Build the determinizer.
Definition: determinize.hh:70
void complete_(state_t s) const
Complete a state: find its outgoing transitions.
Definition: determinize.hh:122
Request the unordered_map implementation.
weightset_t_of< automaton_t > weightset_t
Definition: determinize.hh:48
return res
Definition: multiply.hh:398
auto weight_of(Args &&...args) const -> decltype(aut_-> weight_of(std::forward< Args >(args)...))
wet_kind_t
Different implementations of wets.
Definition: wet.hh:197
auto label_of(Args &&...args) const -> decltype(aut_-> label_of(std::forward< Args >(args)...))
enable_if_not_boolean_t< Aut, automaton > codeterminize_(const automaton &aut, const std::string &algo)
Weighted Bridge.
Definition: determinize.hh:411
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
Definition: setalpha.hh:25
enable_if_not_boolean_t< Aut, automaton > determinize_(const automaton &aut, const std::string &algo)
Weighted Bridge.
Definition: determinize.hh:335
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
std::shared_ptr< detail::determinized_automaton_impl< Aut, Kind, Lazy >> determinized_automaton
A determinized automaton as a shared pointer.
Definition: determinize.hh:243
static constexpr wet_kind_t kind
Definition: determinize.hh:39
state_t_of< automaton_t > state_t
Definition: determinize.hh:53
The subset construction automaton from another.
Definition: determinize.hh:31
auto codeterminize(const Aut &aut, Tag tag={})
Definition: determinize.hh:371
Definition: a-star.hh:8
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
This is useful to make hashes with labels or weights as keys without using non-default constructors; ...
Definition: functional.hh:57
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.
Definition: determinize.hh:234
A dyn automaton.
Definition: automaton.hh:17
An input/output format for valuesets.
Definition: format.hh:13
state_name_t finals_
Set of final states in the input automaton.
Definition: determinize.hh:229
auto determinize(const Aut &a, Tag={}, bool_constant< Lazy >={})
Definition: determinize.hh:247
Request for the weighted version of an algorithm.
Definition: tags.hh:140
automaton determinize(const automaton &aut, const std::string &algo)
Bridge.
Definition: determinize.hh:357
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.
Definition: tuple.hh:177
State labelset.
Definition: stateset.hh:14
std::string to_string(direction d)
Conversion to string.
Definition: direction.cc:7
weight_t_of< automaton_t > weight_t
Definition: determinize.hh:49
automaton codeterminize_tag_(const Aut &aut)
Definition: determinize.hh:386
labelset_t_of< automaton_t > labelset_t
Definition: determinize.hh:46
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: determinize.hh:90
automaton determinize_tag_(const Aut &aut)
Helper function to facilitate dispatch below.
Definition: determinize.hh:307
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.
Definition: determinize.hh:186
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
automaton_t aut_
The wrapped automaton, possibly const.
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
automaton codeterminize(const automaton &aut, const std::string &algo)
Bridge.
Definition: determinize.hh:430
A mapping from strings to Values.
Definition: getargs.hh:33
std::integral_constant< bool, B > bool_constant
Definition: type_traits.hh:12
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.
Definition: determinize.hh:303
auto final_transitions(const Aut &aut) -> decltype(aut->all_in(aut->post()))
Indexes of transitions from (visible) final states.
Definition: automaton.hh:156
This is useful to make hashes with labels or weights as keys without using non-default constructors; ...
Definition: functional.hh:12
auto new_transition(Args &&...args) -> decltype(aut_-> new_transition(std::forward< Args >(args)...))