Vcsn  2.2
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/polynomial.hh>
15 
17 
18 namespace vcsn
19 {
20 
21  /*----------------------.
22  | shortest(automaton). |
23  `----------------------*/
24 
25  namespace detail
26  {
28  template <Automaton Aut>
29  class enumerater
30  {
31  public:
32  using automaton_t = Aut;
34 
38 
42 
46 
48  using profile_t = std::tuple<state_t, word_t, weight_t>;
49  struct profile_less
50  {
52  bool operator()(const profile_t& r, const profile_t& l) const
53  {
54  if (labelset_t::less(std::get<1>(l), std::get<1>(r)))
55  return true;
56  else if (labelset_t::less(std::get<1>(r), std::get<1>(l)))
57  return false;
58  else
59  return std::get<0>(l) < std::get<0>(r);
60  }
61  };
62 
66  enumerater(const automaton_t& aut)
67  : aut_(aut)
68  {}
69 
73  polynomial_t operator()(boost::optional<unsigned> num,
74  boost::optional<unsigned> len)
75  {
76  if (!num)
77  num = !len ? 1 : std::numeric_limits<unsigned>::max();
78  if (!len)
79  len = std::numeric_limits<unsigned>::max();
80 
81  // If the user did not specify a maximum length, and required only one
82  // path, a lightest-path algorithm is eligible.
83  if (*num == 1 && *len == std::numeric_limits<unsigned>::max())
84  {
85  auto get_value = [this](auto lhs, transition_t_of<Aut> t)
86  {
87  auto rhs = aut_->label_of(t);
88  return (aut_->labelset()->is_special(rhs))
89  ? lhs
90  : ps_.labelset()->mul(lhs, aut_->label_of(t));
91  };
92  auto algo = detail::make_dijkstra_impl(aut_, *ps_.labelset(), get_value);
93  auto res = path_monomial(aut_, algo(aut_->pre(), aut_->post()));
94  return res ? polynomial_t{*res} : polynomial_t{};
95  }
96  else
97  return shortest_(*num, *len);
98  }
99 
100  private:
110  template <typename LabelSet = labelset_t_of<context_t>>
111  auto shortest_(unsigned num, unsigned len)
112  -> std::enable_if_t<LabelSet::is_free(), polynomial_t>
113  {
114  // Each step of propagation contributes a letter. We need to
115  // take the initial and final special characters into account.
116  if (len != std::numeric_limits<unsigned>::max())
117  len += 2;
118 
119  using queue_t = std::deque<profile_t>;
120  auto queue = queue_t{profile_t{aut_->pre(), ls_.one(), ws_.one()}};
121 
122  // The approximated behavior: the first orders to post's past.
123  polynomial_t output;
124  for (unsigned i = 0;
125  !queue.empty() && i < len && output.size() < num;
126  ++i)
127  {
128  queue_t q2;
129  for (const auto& sm: queue)
130  {
131  state_t s; word_t l; weight_t w;
132  std::tie(s, l, w) = sm;
133  for (const auto t: all_out(aut_, s))
134  {
135  auto dst = aut_->dst_of(t);
136  auto nw = ws_.mul(w, aut_->weight_of(t));
137  if (aut_->src_of(t) == aut_->pre())
138  q2.emplace_back(dst, l, std::move(nw));
139  else if (dst == aut_->post())
140  ps_.add_here(output, l, std::move(nw));
141  else
142  q2.emplace_back(dst,
143  ls_.mul(l, aut_->label_of(t)),
144  std::move(nw));
145  }
146  }
147  queue.swap(q2);
148  }
149 
150  polynomial_t res;
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  -> std::enable_if_t<!LabelSet::is_free(), polynomial_t>
167  {
168  // Benched as better than Fibonacci, Pairing and Skew Heaps.
169  // D-ary heaps and Priority Queue fail to compile.
170  using queue_t =
171  boost::heap::binomial_heap<profile_t,
172  boost::heap::compare<profile_less>>;
173 
174  auto queue = queue_t{};
175  queue.emplace(aut_->pre(), ls_.one(), ws_.one());
176 
177  // The approximated behavior: the first orders to post's past.
178  polynomial_t res;
179  while (!queue.empty())
180  {
181  state_t s; word_t l; weight_t w;
182  std::tie(s, l, w) = queue.top();
183 
184  // Take all the top of the queue if they have the same
185  // label and state: sum the weights.
186  //
187  // Benches show that this is way more efficient than
188  // trying to update matching profile_t in the queue, even if
189  // we try to take advantage of the ordering in the heap.
190  // Here, we benefit from the fact that the queue provides
191  // matching profile_t in a row.
192  queue.pop();
193 
194  while (!queue.empty()
195  && std::get<0>(queue.top()) == s
196  && ls_.equal(std::get<1>(queue.top()), l))
197  {
198  w = ws_.add(w, std::get<2>(queue.top()));
199  queue.pop();
200  }
201 
202  for (const auto t: all_out(aut_, s))
203  {
204  auto dst = aut_->dst_of(t);
205  auto nw = ws_.mul(w, aut_->weight_of(t));
206  if (aut_->src_of(t) == aut_->pre())
207  queue.emplace(dst, l, std::move(nw));
208  else if (dst == aut_->post())
209  ps_.add_here(res, l, std::move(nw));
210  else
211  {
212  auto nl = ls_.mul(l, aut_->label_of(t));
213  // Discard candidates that are too long.
214  if (ls_.size(nl) <= len)
215  queue.emplace(dst, std::move(nl), std::move(nw));
216  }
217  }
218 
219  // If we found enough words *and* we have completely
220  // treated the current word (there are no other copies in
221  // other states), we're done.
222  if (queue.empty()
223  || (num == res.size()
224  && !ls_.equal(std::get<1>(queue.top()), l)))
225  break;
226  }
227 
228  return res;
229  }
230 
231  private:
233  template <typename Queue>
234  void show_heap_(const Queue& q, std::ostream& os = std::cerr) const
235  {
236  const char* sep = "";
237  for (auto i = q.ordered_begin(), end = q.ordered_end();
238  i != end; ++i)
239  {
240  os << sep;
241  sep = ", ";
242  aut_->print_state_name(std::get<0>(*i), os) << ":<";
243  ws_.print(std::get<2>(*i), os) << '>';
244  ls_.print(std::get<1>(*i), os);
245  }
246  os << '\n';
247  }
248 
252  const weightset_t& ws_ = *aut_->weightset();
254  const polynomialset_t ps_ = make_word_polynomialset(aut_->context());
256  const labelset_t& ls_ = *ps_.labelset();
257  };
258  }
259 
265  template <Automaton Aut>
267  shortest(const Aut& aut,
268  boost::optional<unsigned> num = {},
269  boost::optional<unsigned> len = {})
270  {
271  auto enumerater = detail::enumerater<Aut>{aut};
272  return enumerater(num, len);
273  }
274 
275 
280  template <Automaton Aut>
281  typename detail::enumerater<Aut>::polynomial_t
282  enumerate(const Aut& aut, unsigned len)
283  {
284  return shortest(aut, boost::none, len);
285  }
286 
287 
288  namespace dyn
289  {
290  namespace detail
291  {
293  template <Automaton Aut, typename Num, typename Len>
294  polynomial
295  shortest(const automaton& aut,
296  boost::optional<unsigned> num,
297  boost::optional<unsigned> len)
298  {
299  const auto& a = aut->as<Aut>();
300  auto ps = vcsn::detail::make_word_polynomialset(a->context());
301  return make_polynomial(ps, shortest(a, num, len));
302  }
303  }
304  }
305 }
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:37
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:267
std::shared_ptr< const detail::polynomial_base > polynomial
Definition: fwd.hh:70
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
polynomial make_polynomial(const PolynomialSet &ps, const typename PolynomialSet::value_t &p)
Definition: polynomial.hh:103
const polynomialset_t ps_
Shorthand to the polynomialset of words.
Definition: shortest.hh:254
Definition: a-star.hh:8
typename polynomialset_t::value_t polynomial_t
Definition: shortest.hh:37
std::ostringstream os
The output stream: the corresponding C++ snippet to compile.
Definition: translate.cc:382
state_t_of< automaton_t > state_t
Definition: shortest.hh:45
auto path_monomial(const Aut &aut, const std::vector< transition_t_of< Aut >> &path, state_t_of< Aut > src=Aut::element_type::pre(), state_t_of< Aut > dst=Aut::element_type::post()) -> boost::optional< typename detail::word_polynomialset_t< context_t_of< Aut >>::monomial_t >
Given a path (typically computed by lightest_path), the corresponding monomial (label, weight).
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
void show_heap_(const Queue &q, std::ostream &os=std::cerr) const
Show the heap, for debugging.
Definition: shortest.hh:234
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:58
detail::enumerater< Aut >::polynomial_t enumerate(const Aut &aut, unsigned len)
The approximated behavior of an automaton.
Definition: shortest.hh:282
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
const weightset_t & ws_
Shorthand to the weightset.
Definition: shortest.hh:252
const labelset_t & ls_
Shorthand to the (word) labelset.
Definition: shortest.hh:256
enumerater(const automaton_t &aut)
Prepare to compute an approximation of the behavior.
Definition: shortest.hh:66
bool operator()(const profile_t &r, const profile_t &l) const
Whether l < r (as this is a max heap).
Definition: shortest.hh:52
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:57
auto make_dijkstra_impl(const Aut &aut, const ValueSet &vs, Mul mul)
Definition: dijkstra.hh:129
context_t_of< Aut > context_t
Definition: shortest.hh:33
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:53
auto make_word_polynomialset(const Ctx &ctx) -> word_polynomialset_t< Ctx >
The polynomialset of words of a labelset (not necessarily on words itself).
auto shortest_(unsigned num, unsigned len) -> std::enable_if_t<!LabelSet::is_free(), polynomial_t >
Case of non free labelsets (e.g., law, lan x lan).
Definition: shortest.hh:165
Compute the shortest words accepted by an automaton.
Definition: shortest.hh:29
polynomial_t operator()(boost::optional< unsigned > num, boost::optional< unsigned > len)
The approximated behavior of the automaton.
Definition: shortest.hh:73
labelset_t_of< polynomialset_t > labelset_t
Wordset.
Definition: shortest.hh:40
auto shortest_(unsigned num, unsigned len) -> std::enable_if_t< LabelSet::is_free(), polynomial_t >
Case of free labelsets (e.g., lal or lal x lal).
Definition: shortest.hh:111
word_t_of< automaton_t > word_t
Definition: shortest.hh:41
typename labelset_t_of< base_t< ValueSet >>::word_t word_t_of
Definition: traits.hh:82
automaton_t aut_
The automaton whose behavior to approximate.
Definition: shortest.hh:250
polynomial shortest(const automaton &aut, boost::optional< unsigned > num, boost::optional< unsigned > len)
Bridge.
Definition: shortest.hh:295
value_t mul(const Ts &...ts) const
A variadic multiplication.
Definition: weightset.hh:36
std::tuple< state_t, word_t, weight_t > profile_t
Used in the case of non-free labelsets.
Definition: shortest.hh:48
weight_t_of< automaton_t > weight_t
Definition: shortest.hh:44
weightset_t_of< automaton_t > weightset_t
Definition: shortest.hh:43