Vcsn  2.3
Be Rational
lightest-automaton.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <vcsn/algos/copy.hh>
4 #include <vcsn/algos/tags.hh>
6 #include <vcsn/dyn/automaton.hh>
7 #include <vcsn/dyn/fwd.hh>
8 #include <vcsn/misc/set.hh>
9 
10 namespace vcsn
11 {
20  template <Automaton Aut, typename Algo = auto_tag>
21  fresh_automaton_t_of<Aut>
22  lightest_automaton(const Aut& aut, unsigned k, Algo algo = {})
23  {
24  require(is_tropical<weightset_t_of<Aut>>(),
25  "lightest-automaton: require tropical weightset");
26  auto res = make_fresh_automaton(aut);
27  // The copy is not 'safe' (uses add_transition instead of new_transition),
28  // as there can be the same transition multiple times.
29  auto copy = make_copier(aut, res, false);
30  if (1 < k)
31  {
32  auto paths = k_lightest_path(aut, aut->pre(), aut->post(), k);
33  for (auto path : paths)
34  for (auto t : path)
35  if (t != aut->null_transition())
36  copy(t);
37  }
38  else if (k == 1)
39  {
40  auto pred = lightest_path(aut, algo);
41  for (auto t = pred[aut->post()];
42  t != aut->null_transition();
43  t = pred[aut->src_of(t)])
44  copy(t);
45  }
46  return res;
47  }
48 
49  namespace dyn
50  {
51  namespace detail
52  {
54  template <Automaton Aut, typename Num, typename String>
55  automaton
56  lightest_automaton(const automaton& aut, unsigned k, const std::string& algo)
57  {
58  const auto& a = aut->as<Aut>();
60  }
61  }
62  }
63 }
std::vector< std::vector< transition_t_of< Aut > > > k_lightest_path(const Aut &aut, state_t_of< Aut > source, state_t_of< Aut > dest, unsigned k)
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
return res
Definition: multiply.hh:398
auto copy(const AutIn &input, KeepState keep_state, KeepTrans keep_trans) -> decltype(keep_state(input->null_state()), keep_trans(input->null_transition()), make_fresh_automaton< AutIn, AutOut >(input))
A copy of input keeping only its states that are accepted by keep_state, and transitions accepted by ...
Definition: copy.hh:322
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
Definition: copy.hh:91
Definition: a-star.hh:8
A dyn automaton.
Definition: automaton.hh:17
detail::copier< AutIn, AutOut > make_copier(const AutIn &in, AutOut &out, bool safe=true)
Build an automaton copier.
Definition: copy.hh:256
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
fresh_automaton_t_of< Aut > lightest_automaton(const Aut &aut, unsigned k, Algo algo={})
Lightest Automaton.
automaton lightest_automaton(const automaton &aut, unsigned k, const std::string &algo)
Bridge.
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