outsplitting.hxx

Go to the documentation of this file.

// outsplitting.hxx: this file is part of the Vaucanson project.
//
// Vaucanson, a generic library for finite state machines.
//
// Copyright (C) 2005, 2006 The Vaucanson Group.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// The complete GNU General Public Licence Notice can be found as the
// `COPYING' file in the root directory.
//
// The Vaucanson Group consists of people listed in the `AUTHORS' file.
//
#ifndef VCSN_ALGORITHMS_OUTSPLITTING_HXX
# define VCSN_ALGORITHMS_OUTSPLITTING_HXX


# include <vaucanson/algorithms/internal/outsplitting.hh>
# include <vaucanson/algorithms/accessible.hh>
# include <vaucanson/algebra/implementation/series/series.hh>
# include <vaucanson/algebra/concept/freemonoid_product.hh>

namespace vcsn {
  namespace splitting {


    template <typename S, typename M1, typename M2, typename Auto_t>
    Auto_t
    do_outsplitting(const AutomataBase<S>&,
                    const algebra::FreeMonoidProduct<M1, M2>&,
                    const Auto_t& aut,
                    std::set<typename Auto_t::hstate_t>& m)
    {
      AUTOMATON_TYPES(Auto_t);

      typedef typename series_set_elt_t::support_t      support_t;

      typedef typename monoid_t::second_monoid_t        second_monoid_t;

      typedef typename monoid_elt_value_t::second_type
        second_monoid_elt_value_t;
      typedef Element<second_monoid_t, second_monoid_elt_value_t>
        second_monoid_elt_t;

      typedef std::list<htransition_t>                  set_of_transitions_t;



      second_monoid_elt_t second_identity =
        algebra::identity_as<second_monoid_elt_value_t>::
        of(aut.structure().series().monoid().second_monoid());

      Auto_t res(aut);

      const series_set_t&       series   = res.structure().series();
      const monoid_t&   monoid   = series.monoid();



      for_all_states(s, res)
        {
          bool eps_out = false;
          bool other_out = false;
          bool diff = false;

          // Test whether there are different types of outgoing transitions.

          set_of_transitions_t transitions;
          for (delta_iterator e(res.value(), *s); ! e.done(); e.next())
            transitions.push_back(*e);
          for_all_const_(set_of_transitions_t, e, transitions)
            {
              const series_set_elt_t    series  = res.series_of(*e);
              support_t                 supp = series.supp();
              const monoid_elt_t                supp_elt (monoid, *(supp.begin()));

              if (supp_elt.value().second == second_identity.value())
                eps_out = true;
              else
                other_out = true;
              if (eps_out and other_out)
                {
                  diff = true;
                  break;
                }
            }

          if (eps_out and not diff)
            m.insert(*s);

          // If there are different types of outgoing transitions.
          if (diff)
            {
              hstate_t s2 = res.add_state();
              if (res.is_initial(*s))
                res.set_initial(s2, res.get_initial(*s));

              set_of_transitions_t in_transitions;
              for (rdelta_iterator e(res.value(), *s); ! e.done(); e.next())
                in_transitions.push_back(*e);

              for_all_(set_of_transitions_t, e, in_transitions)
                res.add_series_transition(res.src_of(*e), s2, res.series_of(*e));

              for_all_const_(set_of_transitions_t, e, transitions)
                {
                  const series_set_elt_t        series  = res.series_of(*e);
                  support_t             supp = series.supp();
                  const monoid_elt_t    supp_elt (monoid, *(supp.begin()));

                  if (supp_elt.value().second == second_identity.value())
                    {
                      res.add_series_transition(s2, res.dst_of(*e), res.series_of(*e));
                      res.del_transition(*e);
                    }
                }
              m.insert(s2);
            }
        }
      return coaccessible(res);
    }



    template <typename S, typename M1, typename M2, typename Auto_t>
    Auto_t
    do_insplitting(const AutomataBase<S>&,
                   const algebra::FreeMonoidProduct<M1, M2>&,
                   const Auto_t& aut,
                   std::set<typename Auto_t::hstate_t>& m)
    {
      AUTOMATON_TYPES(Auto_t);

      typedef typename series_set_elt_t::support_t      support_t;

      typedef typename monoid_t::first_monoid_t first_monoid_t;

      typedef typename monoid_elt_value_t::first_type
        first_monoid_elt_value_t;
      typedef Element<first_monoid_t, first_monoid_elt_value_t>
        first_monoid_elt_t;

      typedef std::list<htransition_t>                  set_of_transitions_t;



      first_monoid_elt_t first_identity =
        algebra::identity_as<first_monoid_elt_value_t>::
        of(aut.structure().series().monoid().first_monoid());

      Auto_t res(aut);

      const series_set_t&       series   = res.structure().series();
      const monoid_t&   monoid   = series.monoid();



      for_all_states(s, res)
        {
          bool eps_in = false;
          bool other_in = false;
          bool diff = false;

          // Test whether there are different types of incoming transitions.

          set_of_transitions_t transitions;
          for (rdelta_iterator e(res.value(), *s); ! e.done(); e.next())
            transitions.push_back(*e);
          for_all_const_(set_of_transitions_t, e, transitions)
            {
              const series_set_elt_t    series  = res.series_of(*e);
              support_t                 supp = series.supp();
              const monoid_elt_t                supp_elt (monoid, *(supp.begin()));

              if (supp_elt.value().first == first_identity.value())
                eps_in = true;
              else
                other_in = true;
              if (eps_in and other_in)
                {
                  diff = true;
                  break;
                }
            }

          if (eps_in and not diff)
            m.insert(*s);

          // If there are different types of incoming transitions.
          if (diff)
            {
              hstate_t s2 = res.add_state();
              if (res.is_final(*s))
                res.set_final(s2, res.get_final(*s));

              set_of_transitions_t out_transitions;
              for (delta_iterator e(res.value(), *s); ! e.done(); e.next())
                out_transitions.push_back(*e);

              for_all_(set_of_transitions_t, e, out_transitions)
                res.add_series_transition(s2, res.dst_of(*e), res.series_of(*e));

              for_all_const_(set_of_transitions_t, e, transitions)
                {
                  const series_set_elt_t        series  = res.series_of(*e);
                  support_t             supp = series.supp();
                  const monoid_elt_t    supp_elt (monoid, *(supp.begin()));

                  if (supp_elt.value().first == first_identity.value())
                    {
                      res.add_series_transition(res.src_of(*e), s2,
                                                res.series_of(*e));
                      res.del_transition(*e);
                    }
                }
              m.insert(s2);
            }
        }
      return res;
    }


    template <typename S, typename T>
    Element<S, T>
    outsplitting(const Element<S, T>& aut,
                 std::set<typename T::hstate_t>& states)
    {
      return do_outsplitting(aut.structure(),
                             aut.structure().series().monoid(),
                             aut,
                             states);
    }


    template <typename S, typename T>
    Element<S, T>
    insplitting(const Element<S, T>& aut,
                std::set<typename T::hstate_t>& states)
    {
      return do_insplitting(aut.structure(),
                            aut.structure().series().monoid(),
                            aut,
                            states);
    }



    template <typename S, typename T>
    Element<S, T>
    outsplitting(const Element<S, T>& aut)
    {
      std::set<typename T::hstate_t>            states;
      return do_outsplitting(aut.structure(),
                             aut.structure().series().monoid(),
                             aut,
                             states);
    }


    template <typename S, typename T>
    Element<S, T>
    insplitting(const Element<S, T>& aut)
    {
      std::set<typename T::hstate_t>            states;
      return do_insplitting(aut.structure(),
                            aut.structure().series().monoid(),
                            aut,
                            states);
    }
  }
} // End of namespace vcsn.

#endif // ! VCSN_ALGORITHMS_OUTSPLITTING_HXX