Vcsn  2.3a
Be Rational
shortest.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm>
4 #include <deque>
5 #include <fstream>
6 
7 #include <boost/heap/binomial_heap.hpp>
8 #include <boost/optional.hpp>
9 
10 #include <vcsn/ctx/context.hh>
11 #include <vcsn/dyn/automaton.hh>
12 #include <vcsn/dyn/fwd.hh>
13 #include <vcsn/dyn/value.hh>
15 
17 #include <vcsn/algos/is-acyclic.hh>
18 
19 namespace vcsn
20 {
21 
22  /*----------------------.
23  | shortest(automaton). |
24  `----------------------*/
25 
26  namespace detail
27  {
29  template <Automaton Aut>
30  class enumerater
31  {
32  public:
33  using automaton_t = Aut;
35 
39 
43 
47 
49  using profile_t = std::tuple<state_t, word_t, weight_t>;
50  struct profile_less
51  {
53  bool operator()(const profile_t& r, const profile_t& l) const
54  {
55  if (labelset_t::less(std::get<1>(l), std::get<1>(r)))
56  return true;
57  else if (labelset_t::less(std::get<1>(r), std::get<1>(l)))
58  return false;
59  else
60  return std::get<0>(l) < std::get<0>(r);
61  }
62  };
63 
67  enumerater(const automaton_t& aut)
68  : aut_(aut)
69  {}
70 
75  polynomial_t operator()(boost::optional<unsigned> num,
76  boost::optional<unsigned> len)
77  {
78  if (!num)
79  num = !len ? 1 : std::numeric_limits<unsigned>::max();
80  if (!len)
81  len = std::numeric_limits<unsigned>::max();
82 
83  return shortest_(*num, *len);
84  }
85 
92  {
93  return shortest_(1, std::numeric_limits<unsigned>::max(), src, dst);
94  }
95 
96  private:
106  template <typename LabelSet = labelset_t_of<context_t>>
107  auto shortest_(unsigned num, unsigned len,
108  state_t_of<Aut> src = Aut::element_type::pre(),
109  state_t_of<Aut> dst = Aut::element_type::post())
110  -> std::enable_if_t<LabelSet::is_free(), polynomial_t>
111  {
112  // Each step of propagation contributes a letter. We need to
113  // take the initial and final special characters into account.
114  if (len != std::numeric_limits<unsigned>::max())
115  len += 2;
116 
117  using queue_t = std::deque<profile_t>;
118  auto queue = queue_t{profile_t{src, ls_.one(), ws_.one()}};
119 
120  // The approximated behavior: the first orders to post's past.
121  polynomial_t output;
122  for (unsigned i = 0;
123  !queue.empty() && i < len && output.size() < num;
124  ++i)
125  {
126  queue_t q2;
127  for (const auto& sm: queue)
128  {
129  state_t s; word_t l; weight_t w;
130  std::tie(s, l, w) = sm;
131  for (const auto t: all_out(aut_, s))
132  {
133  auto t_dst = aut_->dst_of(t);
134  auto nw = ws_.mul(w, aut_->weight_of(t));
135  if (t_dst == aut_->post() && t_dst == dst)
136  ps_.add_here(output, l, std::move(nw));
137  else if (aut_->src_of(t) == aut_->pre() || t_dst == aut_->post())
138  q2.emplace_back(t_dst, l, std::move(nw));
139  else if (t_dst == dst)
140  ps_.add_here(output, ls_.mul(l, aut_->label_of(t)), std::move(nw));
141  else
142  q2.emplace_back(t_dst,
143  ls_.mul(l, aut_->label_of(t)),
144  std::move(nw));
145  }
146  }
147  queue.swap(q2);
148  }
149 
151  for (const auto& m: output)
152  {
153  ps_.add_here(res, m);
154  if (--num == 0)
155  break;
156  }
157  return res;
158  }
159 
164  template <typename LabelSet = labelset_t_of<context_t>>
165  auto shortest_(unsigned num, unsigned len,
166  state_t_of<Aut> src = Aut::element_type::pre(),
167  state_t_of<Aut> dst = Aut::element_type::post())
168  -> std::enable_if_t<!LabelSet::is_free(), polynomial_t>
169  {
170  // Benched as better than Fibonacci, Pairing and Skew Heaps.
171  // D-ary heaps and Priority Queue fail to compile.
172  using queue_t =
173  boost::heap::binomial_heap<profile_t,
174  boost::heap::compare<profile_less>>;
175 
176  auto queue = queue_t{};
177  queue.emplace(src, ls_.one(), ws_.one());
178 
179  // The approximated behavior: the first orders to post's past.
181  while (!queue.empty())
182  {
183  state_t s; word_t l; weight_t w;
184  std::tie(s, l, w) = queue.top();
185 
186  // Take all the top of the queue if they have the same
187  // label and state: sum the weights.
188  //
189  // Benches show that this is way more efficient than
190  // trying to update matching profile_t in the queue, even if
191  // we try to take advantage of the ordering in the heap.
192  // Here, we benefit from the fact that the queue provides
193  // matching profile_t in a row.
194  queue.pop();
195 
196  while (!queue.empty()
197  && std::get<0>(queue.top()) == s
198  && ls_.equal(std::get<1>(queue.top()), l))
199  {
200  w = ws_.add(w, std::get<2>(queue.top()));
201  queue.pop();
202  }
203 
204  for (const auto t: all_out(aut_, s))
205  {
206  auto t_dst = aut_->dst_of(t);
207  auto nw = ws_.mul(w, aut_->weight_of(t));
208  if (t_dst == aut_->post() && t_dst == dst)
209  ps_.add_here(res, l, std::move(nw));
210  else if (aut_->src_of(t) == aut_->pre() || t_dst == aut_->post())
211  queue.emplace(t_dst, l, std::move(nw));
212  else if (t_dst == dst)
213  {
214  auto nl = ls_.mul(l, aut_->label_of(t));
215  // Discard candidates that are too long.
216  if (ls_.size(nl) <= len)
217  ps_.add_here(res, std::move(nl), std::move(nw));
218  }
219  else
220  {
221  auto nl = ls_.mul(l, aut_->label_of(t));
222  // Discard candidates that are too long.
223  if (ls_.size(nl) <= len)
224  queue.emplace(t_dst, std::move(nl), std::move(nw));
225  }
226  }
227 
228  // If we found enough words *and* we have completely
229  // treated the current word (there are no other copies in
230  // other states), we're done.
231  if (queue.empty()
232  || (num == res.size()
233  && !ls_.equal(std::get<1>(queue.top()), l)))
234  break;
235  }
236 
237  return res;
238  }
239 
240  private:
242  template <typename Queue>
243  void show_heap_(const Queue& q, std::ostream& os = std::cerr) const
244  {
245  const char* sep = "";
246  for (auto i = q.ordered_begin(), end = q.ordered_end();
247  i != end; ++i)
248  {
249  os << sep;
250  sep = ", ";
251  aut_->print_state_name(std::get<0>(*i), os) << ":<";
252  ws_.print(std::get<2>(*i), os) << '>';
253  ls_.print(std::get<1>(*i), os);
254  }
255  os << '\n';
256  }
257 
261  const weightset_t& ws_ = *aut_->weightset();
263  const polynomialset_t ps_ = make_word_polynomialset(aut_->context());
265  const labelset_t& ls_ = *ps_.labelset();
266  };
267  }
268 
274  template <Automaton Aut>
276  shortest(const Aut& aut,
277  boost::optional<unsigned> num = {},
278  boost::optional<unsigned> len = {})
279  {
280  auto enumerater = detail::enumerater<Aut>{aut};
281  return enumerater(num, len);
282  }
283 
290  template <Automaton Aut>
291  typename detail::enumerater<Aut>::polynomial_t
292  shortest(const Aut& aut, state_t_of<Aut> src, state_t_of<Aut> dst)
293  {
294  auto enumerater = detail::enumerater<Aut>{aut};
295  return enumerater(src, dst);
296  }
297 
298 
303  template <Automaton Aut>
304  typename detail::enumerater<Aut>::polynomial_t
305  enumerate(const Aut& aut, unsigned len)
306  {
307  return shortest(aut, boost::none, len);
308  }
309 
310 
311  namespace dyn
312  {
313  namespace detail
314  {
316  template <Automaton Aut, typename Num, typename Len>
317  polynomial
318  shortest(const automaton& aut,
319  boost::optional<unsigned> num,
320  boost::optional<unsigned> len)
321  {
322  const auto& a = aut->as<Aut>();
323  auto ps = vcsn::detail::make_word_polynomialset(a->context());
324  return {ps, shortest(a, num, len)};
325  }
326  }
327  }
328 }
weight_t_of< automaton_t > weight_t
Definition: shortest.hh:45
detail::enumerater< Aut >::polynomial_t enumerate(const Aut &aut, unsigned len)
The approximated behavior of an automaton.
Definition: shortest.hh:305
state_t_of< automaton_t > state_t
Definition: shortest.hh:46
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:65
const polynomialset_t ps_
Shorthand to the polynomialset of words.
Definition: shortest.hh:263
const labelset_t & ls_
Shorthand to the (word) labelset.
Definition: shortest.hh:265
Definition: a-star.hh:8
polynomial_t operator()(state_t src, state_t dst)
The approximated behavior of a part of the automaton (looks for one word of unspecified length)...
Definition: shortest.hh:91
weightset_t_of< automaton_t > weightset_t
Definition: shortest.hh:44
return res
Definition: multiply.hh:398
void show_heap_(const Queue &q, std::ostream &os=std::cerr) const
Show the heap, for debugging.
Definition: shortest.hh:243
context_t_of< Aut > context_t
Definition: shortest.hh:34
value_impl< detail::polynomial_tag > polynomial
Definition: fwd.hh:27
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
enumerater(const automaton_t &aut)
Prepare to compute an approximation of the behavior.
Definition: shortest.hh:67
typename polynomialset_t::value_t polynomial_t
Definition: shortest.hh:38
std::ostringstream os
The output stream: the corresponding C++ snippet to compile.
Definition: translate.cc:375
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
auto shortest_(unsigned num, unsigned len, state_t_of< Aut > src=Aut::element_type::pre(), state_t_of< Aut > dst=Aut::element_type::post()) -> std::enable_if_t<!LabelSet::is_free(), polynomial_t >
Case of non free labelsets (e.g., law, lan x lan).
Definition: shortest.hh:165
polynomial_t operator()(boost::optional< unsigned > num, boost::optional< unsigned > len)
The approximated behavior of the automaton.
Definition: shortest.hh:75
Compute the shortest words accepted by an automaton.
Definition: shortest.hh:30
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
A dyn automaton.
Definition: automaton.hh:17
const weightset_t & ws_
Shorthand to the weightset.
Definition: shortest.hh:261
bool operator()(const profile_t &r, const profile_t &l) const
Whether l < r (as this is a max heap).
Definition: shortest.hh:53
polynomial shortest(const automaton &aut, boost::optional< unsigned > num, boost::optional< unsigned > len)
Bridge.
Definition: shortest.hh:318
auto make_word_polynomialset(const Ctx &ctx) -> word_polynomialset_t< Ctx >
The polynomialset of words of a labelset (not necessarily on words itself).
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
typename labelset_t_of< base_t< ValueSet >>::word_t word_t_of
Definition: traits.hh:90
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
std::tuple< state_t, word_t, weight_t > profile_t
Used in the case of non-free labelsets.
Definition: shortest.hh:49
detail::enumerater< Aut >::polynomial_t shortest(const Aut &aut, boost::optional< unsigned > num={}, boost::optional< unsigned > len={})
The approximated behavior of an automaton.
Definition: shortest.hh:276
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
automaton_t aut_
The automaton whose behavior to approximate.
Definition: shortest.hh:259
labelset_t_of< polynomialset_t > labelset_t
Wordset.
Definition: shortest.hh:41
word_t_of< automaton_t > word_t
Definition: shortest.hh:42
auto shortest_(unsigned num, unsigned len, state_t_of< Aut > src=Aut::element_type::pre(), state_t_of< Aut > dst=Aut::element_type::post()) -> std::enable_if_t< LabelSet::is_free(), polynomial_t >
Case of free labelsets (e.g., lal or lal x lal).
Definition: shortest.hh:107
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46