accessible.hh

Go to the documentation of this file.

#pragma once

#include <queue>

#include <vcsn/algos/filter.hh>
#include <vcsn/algos/transpose.hh>
#include <vcsn/dyn/fwd.hh>
#include <vcsn/misc/attributes.hh>
#include <vcsn/misc/unordered_set.hh>

namespace vcsn
{

  /*--------------------------------------------------.
  | Sets of accessible, coaccessible, useful states.  |
  `--------------------------------------------------*/

  template <Automaton Aut>
  using states_t = std::unordered_set<state_t_of<Aut>>;

  template <Automaton Aut>
  states_t<Aut>
  accessible_states(const Aut& aut, bool strict = true)
  {
    using automaton_t = Aut;
    using state_t = state_t_of<automaton_t>;

    // Reachable states.
    auto res = states_t<Aut>{aut->pre()};

    // States work list.
    using worklist_t = std::queue<state_t>;
    auto todo = worklist_t{};
    todo.emplace(aut->pre());

    while (!todo.empty())
      {
        const state_t src = todo.front();
        todo.pop();

        if (strict || !aut->is_lazy(src))
          for (auto tr : all_out(aut, src))
            {
              state_t dst = aut->dst_of(tr);
              // If we have not seen it already, explore its successors.
              if (res.emplace(dst).second)
                todo.emplace(dst);
            }
      }

    return res;
  }

  template <Automaton Aut>
  states_t<Aut>
  coaccessible_states(const Aut& a, bool strict = true)
  {
    return accessible_states(transpose(a), strict);
  }

  template <Automaton Aut>
  states_t<Aut>
  useful_states(const Aut& a, bool strict = true)
  {
    auto accessible = accessible_states(a, strict);
    auto coaccessible = coaccessible_states(a, strict);
    return set_intersection(accessible, coaccessible);
  }


  /*----------------------------------------------------.
  | Number of accessible, coaccessible, useful states.  |
  `----------------------------------------------------*/

  template <Automaton Aut>
  size_t
  num_accessible_states(const Aut& a)
  {
    auto set = accessible_states(a);
    size_t res = set.size();
    // Don't count pre().
    res -= 1;
    // Don't count post().
    if (has(set, a->post()))
      res -= 1;
    return res;
  }

  template <Automaton Aut>
  size_t
  num_coaccessible_states(const Aut& a)
  {
    return num_accessible_states(transpose(a));
  }

  template <Automaton Aut>
  size_t
  num_useful_states(const Aut& a)
  {
    auto set = useful_states(a);
    size_t res = set.size();
    // Don't count pre().
    if (has(set, a->pre()))
      res -= 1;
    // Don't count post().
    if (has(set, a->post()))
      res -= 1;
    return res;
  }


  /*-----------------------------------------------.
  | accessible, coaccessible, useful subautomata.  |
  `-----------------------------------------------*/

  template <Automaton Aut>
  filter_automaton<Aut>
  accessible(const Aut& a)
  {
    return vcsn::filter(a, accessible_states(a));
  }

  template <Automaton Aut>
  filter_automaton<Aut>
  coaccessible(const Aut& a)
  {
    return vcsn::filter(a, coaccessible_states(a));
  }

  template <Automaton Aut>
  filter_automaton<Aut>
  trim(const Aut& a)
  {
    return vcsn::filter(a, useful_states(a));
  }

  /*----------------------------------------------------------------.
  | is_trim, is_accessible, is_coaccessible, is_empty, is_useless.  |
  `----------------------------------------------------------------*/

  template <Automaton Aut>
  bool is_trim(const Aut& a)
  {
    return num_useful_states(a) == a->num_states();
  }

  template <Automaton Aut>
  bool is_useless(const Aut& a)
  {
    return num_useful_states(a) == 0;
  }

  template <Automaton Aut>
  bool is_accessible(const Aut& a)
  {
    return num_accessible_states(a) == a->num_states();
  }

  template <Automaton Aut>
  bool is_coaccessible(const Aut& a)
  {
    return num_coaccessible_states(a) == a->num_states();
  }

  template <Automaton Aut>
  bool is_empty(const Aut& a) ATTRIBUTE_PURE;

  template <Automaton Aut>
  bool is_empty(const Aut& a)
  {
    // FIXME: Beware of the case where there is a transition from
    // pre() to post().
    return a->num_states() == 0;
  }

  namespace dyn
  {
    namespace detail
    {
      template <Automaton Aut>
      automaton
      accessible(const automaton& aut)
      {
        const auto& a = aut->as<Aut>();
        return make_automaton(::vcsn::accessible(a));
      }

      template <Automaton Aut>
      automaton
      coaccessible(const automaton& aut)
      {
        const auto& a = aut->as<Aut>();
        return make_automaton(::vcsn::coaccessible(a));
      }

      template <Automaton Aut>
      automaton
      trim(const automaton& aut)
      {
        const auto& a = aut->as<Aut>();
        return make_automaton(::vcsn::trim(a));
      }

      template <Automaton Aut>
      bool
      is_accessible(const automaton& aut)
      {
        const auto& a = aut->as<Aut>();
        return is_accessible(a);
      }

      template <Automaton Aut>
      bool
      is_coaccessible(const automaton& aut)
      {
        const auto& a = aut->as<Aut>();
        return is_coaccessible(a);
      }

      template <Automaton Aut>
      bool
      is_trim(const automaton& aut)
      {
        const auto& a = aut->as<Aut>();
        return is_trim(a);
      }

      template <Automaton Aut>
      bool
      is_useless(const automaton& aut)
      {
        const auto& a = aut->as<Aut>();
        return is_useless(a);
      }

      template <Automaton Aut>
      bool
      is_empty(const automaton& aut)
      {
        const auto& a = aut->as<Aut>();
        return is_empty(a);
      }
    }
  }
}