Vcsn  2.4
Be Rational
lightest.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 
12 #include <vcsn/ctx/context.hh>
13 #include <vcsn/dyn/automaton.hh>
14 #include <vcsn/dyn/fwd.hh>
15 #include <vcsn/dyn/value.hh>
17 
18 namespace vcsn
19 {
20 
21  /*----------------------.
22  | lightest(automaton). |
23  `----------------------*/
24 
25  namespace detail
26  {
27 
36  template <Automaton Aut>
38  {
39  public:
40  using automaton_t = Aut;
42 
46  using monomial_t = typename polynomialset_t::monomial_t;
47 
51 
55 
56  using profile_t = std::tuple<state_t, word_t, weight_t>;
57  struct profile_less
58  {
69  bool operator()(const profile_t& r, const profile_t& l) const
70  {
71  if (weightset_t::less(std::get<2>(l), std::get<2>(r)))
72  return true;
73  else if (weightset_t::less(std::get<2>(r), std::get<2>(l)))
74  return false;
75  else if (labelset_t::less(std::get<1>(l), std::get<1>(r)))
76  return true;
77  else if (labelset_t::less(std::get<1>(r), std::get<1>(l)))
78  return false;
79  else if (std::get<0>(r) == automaton_t::element_type::post())
80  return true;
81  else if (std::get<0>(l) == automaton_t::element_type::post())
82  return false;
83  else
84  return std::get<0>(l) < std::get<0>(r);
85  }
86  };
87  using queue_t =
88  boost::heap::binomial_heap<profile_t,
89  boost::heap::compare<profile_less>>;
90 
95  : aut_(aut)
96  {}
97 
100  polynomial_t operator()(unsigned num)
101  {
103  "lightest(n > 1): requires automaton without lightening cycles");
104  return lightest_(num);
105  }
106 
107  private:
108  polynomial_t lightest_(unsigned num)
109  {
110  auto queue = queue_t{};
111  queue.emplace(aut_->pre(), ls_.one(), ws_.one());
112 
113  // The approximated behavior: the first orders to post's past.
115  while (!queue.empty() && num != res.size())
116  {
117  state_t s; word_t l; weight_t w;
118  std::tie(s, l, w) = queue.top();
119 
120  queue.pop();
121 
124  if (!queue.empty()
125  && std::get<0>(queue.top()) == s
126  && ls_.equal(std::get<1>(queue.top()), l))
127  {
128  while (!queue.empty()
129  && std::get<0>(queue.top()) == s
130  && ls_.equal(std::get<1>(queue.top()), l))
131  {
132  w = ws_.add(w, std::get<2>(queue.top()));
133  queue.pop();
134  }
135  queue.emplace(s, l, w);
136  continue;
137  }
138 
139  if (s == aut_->post())
140  ps_.add_here(res, std::move(l), std::move(w));
141 
142  for (const auto t: all_out(aut_, s))
143  {
144  auto dst = aut_->dst_of(t);
145  auto nw = ws_.mul(w, aut_->weight_of(t));
146  if (aut_->src_of(t) == aut_->pre() || dst == aut_->post())
147  queue.emplace(dst, l, std::move(nw));
148  else
149  {
150  auto nl = ls_.mul(l, aut_->label_of(t));
151  queue.emplace(dst, std::move(nl), std::move(nw));
152  }
153  }
154  }
155 
156  return res;
157  }
158 
160  void show_heap_(const queue_t& q, std::ostream& os = std::cerr)
161  {
162  const char* sep = "";
163  for (auto i = q.ordered_begin(), end = q.ordered_end();
164  i != end; ++i)
165  {
166  os << sep;
167  sep = " , ";
168  aut_->print_state_name(std::get<0>(*i), os) << ":<";
169  ws_.print(std::get<2>(*i), os);
170  os << ">:";
171  ls_.print(std::get<1>(*i), os);
172  }
173  os << '\n';
174  }
175 
178  const weightset_t& ws_ = *aut_->weightset();
179  const polynomialset_t ps_ = make_word_polynomialset(aut_->context());
180  const labelset_t& ls_ = *ps_.labelset();
181  };
182  }
183 
189  template <Automaton Aut>
191  lightest(const Aut& aut, unsigned num = 1, const std::string& algo = "auto")
192  {
193  if (algo == "yen")
194  {
195  const auto ps = make_word_polynomialset(aut->context());
196  auto res = ps.zero();
197  auto paths = k_lightest_path(aut, aut->pre(), aut->post(), num);
198  for (const auto& path : paths)
199  if (auto m = path_monomial(aut, format_lightest(aut, path)))
200  ps.add_here(res, *m);
201  return res;
202  }
203  else if ((algo == "auto" && num != 1) || algo == "breadth-first")
204  {
206  return lightest(num);
207  }
208  else if (num == 1)
209  {
210  if (auto res = path_monomial(aut, lightest_path(aut, algo)))
211  return {*res};
212  else
213  return {};
214  }
215  else
216  raise("lightest: invalid algorithm: ", algo);
217  }
218 
219 
220  namespace dyn
221  {
222  namespace detail
223  {
225  template <Automaton Aut, typename Num, typename String>
226  polynomial
227  lightest(const automaton& aut, unsigned num, const std::string& algo)
228  {
229  const auto& a = aut->as<Aut>();
230  auto ps = vcsn::detail::make_word_polynomialset(a->context());
231  return {ps, lightest(a, num, algo)};
232  }
233  }
234  }
235 }
std::vector< path_t_of< Aut > > k_lightest_path(const Aut &aut, state_t_of< Aut > src, state_t_of< Aut > dst, unsigned k)
return res
Definition: multiply.hh:398
weight_t_of< automaton_t > weight_t
Definition: lightest.hh:53
weightset_t_of< automaton_t > weightset_t
Definition: lightest.hh:52
typename polynomialset_t::value_t polynomial_t
Definition: lightest.hh:45
const polynomialset_t ps_
Definition: lightest.hh:179
state_t_of< automaton_t > state_t
Definition: lightest.hh:54
predecessors_t_of< Aut > format_lightest(const Aut &aut, const std::vector< transition_t_of< Aut >> &path)
A state-indexed vector of predecessor transitions from the path path.
auto make_word_polynomialset(const Ctx &ctx) -> word_polynomialset_t< Ctx >
The polynomialset of words of a labelset (not necessarily on words itself).
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
void show_heap_(const queue_t &q, std::ostream &os=std::cerr)
Show the heap, for debugging.
Definition: lightest.hh:160
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
bool operator()(const profile_t &r, const profile_t &l) const
Whether l < r (as this is a max heap).
Definition: lightest.hh:69
polynomial_t operator()(unsigned num)
The approximated behavior of the automaton.
Definition: lightest.hh:100
polynomial_t lightest_(unsigned num)
Definition: lightest.hh:108
std::ostringstream os
The output stream: the corresponding C++ snippet to compile.
Definition: translate.cc:375
Definition: a-star.hh:8
typename polynomialset_t::monomial_t monomial_t
Definition: lightest.hh:46
std::tuple< state_t, word_t, weight_t > profile_t
Definition: lightest.hh:56
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:66
polynomial lightest(const automaton &aut, unsigned num, const std::string &algo)
Bridge.
Definition: lightest.hh:227
const labelset_t & ls_
Definition: lightest.hh:180
automaton_t aut_
The automaton whose behavior to approximate.
Definition: lightest.hh:177
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
typename labelset_t_of< base_t< ValueSet >>::word_t word_t_of
Definition: traits.hh:90
A dyn automaton.
Definition: automaton.hh:17
detail::word_polynomialset_t< context_t_of< Aut > >::value_t lightest(const Aut &aut, unsigned num=1, const std::string &algo="auto")
The approximated behavior of an automaton.
Definition: lightest.hh:191
std::enable_if_t< weightset_t_of< Aut >::has_lightening_weights(), bool > has_lightening_cycle(const Aut &aut)
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
The lightest algorithm computes the paths between pre and post with the smallest weight possible...
Definition: lightest.hh:37
lightest_impl(const automaton_t &aut)
Prepare to compute an approximation of the behavior.
Definition: lightest.hh:94
labelset_t_of< polynomialset_t > labelset_t
Wordset.
Definition: lightest.hh:49
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
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::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
std::vector< transition_t_of< Aut > > lightest_path(const Aut &aut, state_t_of< Aut > source, state_t_of< Aut > dest, a_star_tag)
Definition: a-star.hh:151
boost::heap::binomial_heap< profile_t, boost::heap::compare< profile_less >> queue_t
Definition: lightest.hh:89
value_impl< detail::polynomial_tag > polynomial
Definition: fwd.hh:27
word_t_of< automaton_t > word_t
Definition: lightest.hh:50
const weightset_t & ws_
Definition: lightest.hh:178
context_t_of< Aut > context_t
Definition: lightest.hh:41
Paths in filesystems, i.e., file names.
Definition: path.hh:21