lightest.hh

Go to the documentation of this file.

#pragma once

#include <algorithm>
#include <deque>
#include <fstream>

#include <boost/heap/binomial_heap.hpp>
#include <boost/optional.hpp>

#include <vcsn/ctx/context.hh>
#include <vcsn/dyn/automaton.hh>
#include <vcsn/dyn/fwd.hh>
#include <vcsn/dyn/polynomial.hh>
#include <vcsn/labelset/word-polynomialset.hh>

namespace vcsn
{

  /*----------------------.
  | lightest(automaton).  |
  `----------------------*/

  namespace detail
  {

    template <typename Aut>
    class weighter
    {
    public:
      using automaton_t = Aut;
      using context_t = context_t_of<Aut>;

      using wordset_context_t = word_context_t<context_t>;
      using polynomialset_t = polynomialset<wordset_context_t>;
      using polynomial_t = typename polynomialset_t::value_t;
      using monomial_t = typename polynomialset_t::monomial_t;

      using labelset_t = labelset_t_of<polynomialset_t>;
      using word_t = word_t_of<automaton_t>;

      using weightset_t = weightset_t_of<automaton_t>;
      using weight_t = weight_t_of<automaton_t>;
      using state_t = state_t_of<automaton_t>;

      using datum_t = std::tuple<state_t, word_t, weight_t>;
      struct datum_less
      {
        bool operator()(const datum_t& r, const datum_t& l) const
        {
          if (weightset_t::less(std::get<2>(l), std::get<2>(r)))
            return true;
          else if (weightset_t::less(std::get<2>(r), std::get<2>(l)))
            return false;
          else if (labelset_t::less(std::get<1>(l), std::get<1>(r)))
            return true;
          else if (labelset_t::less(std::get<1>(r), std::get<1>(l)))
            return false;
          else
            return std::get<0>(l) < std::get<0>(r);
        }
      };
      using queue_t =
        boost::heap::binomial_heap<datum_t,
                                   boost::heap::compare<datum_less>>;

      weighter(const automaton_t& aut)
        : aut_(aut)
      {}

      polynomial_t operator()(boost::optional<unsigned> num)
      {
        if (!num)
          num = 1;

        return lightest_(*num);
      }

    private:
      polynomial_t lightest_(unsigned num)
      {
        auto queue = queue_t{};
        queue.emplace(aut_->pre(), ls_.one(), ws_.one());

        // The approximated behavior: the first orders to post's past.
        polynomial_t res;
        while (!queue.empty())
          {
            state_t s; word_t l; weight_t w;
            std::tie(s, l, w) = queue.top();

            queue.pop();

            for (const auto t: aut_->all_out(s))
              {
                auto dst = aut_->dst_of(t);
                auto nw = ws_.mul(w, aut_->weight_of(t));
                if (aut_->src_of(t) == aut_->pre())
                  queue.emplace(dst, l, std::move(nw));
                else if (dst == aut_->post())
                  ps_.add_here(res, l, std::move(nw));
                else
                  {
                    auto nl = ls_.mul(l, aut_->label_of(t));
                    queue.emplace(dst, std::move(nl), std::move(nw));
                  }
              }

            // If we found enough words *and* we have completely
            // treated the current word (there are no other copies in
            // other states), we're done.
            if (queue.empty()
                || (num == res.size()
                    && !ls_.equal(std::get<1>(queue.top()), l)))
              break;
          }

        return res;
      }

      void show_heap_(const queue_t& q, std::ostream& os = std::cerr)
      {
        const char* sep = "";
        for (auto i = q.ordered_begin(), end = q.ordered_end();
             i != end; ++i)
          {
            os << sep;
            sep = " , ";
            aut_->print_state_name(std::get<0>(*i), os) << ":<";
            ws_.print(std::get<2>(*i), os);
            os << ">:";
            ls_.print(std::get<1>(*i), os);
          }
        os << '\n';
      }

      automaton_t aut_;
      const weightset_t& ws_ = *aut_->weightset();
      const polynomialset_t ps_ = make_word_polynomialset(aut_->context());
      const labelset_t& ls_ = *ps_.labelset();
    };
  }

  template <typename Automaton>
  inline
  typename detail::weighter<Automaton>::polynomial_t
  lightest(const Automaton& aut, boost::optional<unsigned> num = {})
  {
    detail::weighter<Automaton> weighter(aut);
    return weighter(num);
  }


  template <typename Automaton>
  inline
  typename detail::weighter<Automaton>::polynomial_t
  weigh(const Automaton& aut)
  {
    return lightest(aut, boost::none);
  }


  namespace dyn
  {
    namespace detail
    {
      template <typename Aut, typename Num>
      polynomial
      lightest(const automaton& aut, boost::optional<unsigned> num)
      {
        const auto& a = aut->as<Aut>();
        auto ps = vcsn::detail::make_word_polynomialset(a->context());
        return make_polynomial(ps, lightest(a, num));
      }
    }
  }
}