Vcsn  2.2
Be Rational
cerny.hh
Go to the documentation of this file.
1 #pragma once
2 
4 #include <vcsn/dyn/automaton.hh>
5 #include <vcsn/dyn/context.hh>
6 
7 namespace vcsn
8 {
9 
10  /*--------.
11  | cerny. |
12  `--------*/
13 
22 
23  template <typename Ctx>
24  mutable_automaton<Ctx>
25  cerny(const Ctx& ctx, unsigned num_states)
26  {
27  require(0 < num_states, "num_states must be > 0");
28 
29  using automaton_t = mutable_automaton<Ctx>;
30  using state_t = state_t_of<automaton_t>;
31  automaton_t res = make_shared_ptr<automaton_t>(ctx);
32 
33  std::vector<state_t> states;
34  states.reserve(num_states);
35 
36  for (unsigned i = 0; i < num_states; ++i)
37  states.push_back(res->new_state());
38 
39  for (unsigned i = 0; i < num_states; ++i)
40  {
41  bool la = true;
42  for (auto l : ctx.labelset()->generators())
43  {
44  auto dest = (la || i == num_states - 1) ? (i + 1) % num_states : i;
45  res->add_transition(states[i], states[dest], l,
46  ctx.weightset()->one());
47  la = false;
48  }
49  }
50 
51  res->set_initial(states[0]);
52  res->set_final(states[0]);
53 
54  return res;
55  }
56 
57  namespace dyn
58  {
59  namespace detail
60  {
62  template <typename Ctx, typename>
63  automaton
64  cerny(const context& ctx, unsigned num_states)
65  {
66  const auto& c = ctx->as<Ctx>();
67  return make_automaton(vcsn::cerny(c, num_states));
68  }
69  }
70  }
71 }
mutable_automaton< Ctx > cerny(const Ctx &ctx, unsigned num_states)
Cerny automata are automata whose synchronizing word length is always (n - 1)^2, the upper bound of t...
Definition: cerny.hh:25
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
Definition: automaton.hh:75
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
Definition: a-star.hh:8
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:78
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
std::shared_ptr< const detail::context_base > context
A dyn::context.
Definition: fwd.hh:43
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69
automaton cerny(const context &ctx, unsigned num_states)
Bridge.
Definition: cerny.hh:64
static dyn::context ctx(const driver &d)
Get the context of the driver.
Definition: parse.cc:82