lightest-automaton.hh

Go to the documentation of this file.

#pragma once

#include <vcsn/algos/copy.hh>
#include <vcsn/algos/tags.hh>
#include <vcsn/algos/lightest-path.hh>
#include <vcsn/dyn/automaton.hh>
#include <vcsn/dyn/fwd.hh>
#include <vcsn/misc/set.hh>

namespace vcsn
{
  template <Automaton Aut, typename Algo = auto_tag>
  fresh_automaton_t_of<Aut>
  lightest_automaton(const Aut& aut, unsigned k, Algo algo = {})
  {
    require(is_tropical<weightset_t_of<Aut>>(),
            "lightest-automaton: require tropical weightset");
    auto res = make_fresh_automaton(aut);
    // The copy is not 'safe' (uses add_transition instead of new_transition),
    // as there can be the same transition multiple times.
    auto copy = make_copier(aut, res, false);
    if (1 < k)
      {
        auto paths = k_lightest_path(aut, aut->pre(), aut->post(), k);
        for (auto path : paths)
          for (auto t : path)
            if (t != aut->null_transition())
              copy(t);
      }
    else if (k == 1)
      {
        auto pred = lightest_path(aut, algo);
        for (auto t = pred[aut->post()];
             t != aut->null_transition();
             t = pred[aut->src_of(t)])
          copy(t);
      }
    return res;
  }

  namespace dyn
  {
    namespace detail
    {
      template <Automaton Aut, typename Num, typename String>
      automaton
      lightest_automaton(const automaton& aut, unsigned k, const std::string& algo)
      {
        const auto& a = aut->as<Aut>();
        return ::vcsn::lightest_automaton(a, k, algo);
      }
    }
  }
}