normalized_composition.hxx

Go to the documentation of this file.

// normalized_composition.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_NORMALIZED_COMPOSITION_HXX
# define VCSN_ALGORITHMS_NORMALIZED_COMPOSITION_HXX


# include <set>
# include <queue>
# include <vaucanson/algorithms/normalized_composition.hh>
# include <vaucanson/algorithms/internal/outsplitting.hh>
# include <vaucanson/algebra/concept/freemonoid_product.hh>
# include <vaucanson/algebra/implementation/series/series.hh>
# include <vaucanson/automata/concept/automata.hh>


namespace vcsn {

  struct composition_traits
  {
    typedef std::pair<hstate_t, hstate_t>       pair_hstate_t;
    typedef std::map<pair_hstate_t, hstate_t>   visited_t;
    typedef std::map<hstate_t, pair_hstate_t >  map_of_states_t;
    typedef std::queue<pair_hstate_t>           to_process_t;
  };


  // FIXME: Document.
  template <typename res_t>
  inline
  void
  add_transition(res_t&                         output,
                 composition_traits::visited_t&         visited,
                 composition_traits::to_process_t&      to_process,
                 std::set<hstate_t>&            lhs_states,
                 std::set<hstate_t>&            rhs_states,
                 composition_traits::map_of_states_t& m,
                 const hstate_t current_state,
                 const hstate_t from,
                 const hstate_t to,
                 typename res_t::series_set_elt_t& prod_series)
  {
    if (lhs_states.find(from) == lhs_states.end()
        or rhs_states.find(to) == rhs_states.end())
      {
        const composition_traits::pair_hstate_t new_pair (from, to);

        typename composition_traits::visited_t::const_iterator found =
          visited.find(new_pair);
        hstate_t dst;
        if (found == visited.end())
          {
            dst = output.add_state();
            visited[new_pair] = dst;
            m[dst] = new_pair;
            to_process.push(new_pair);
          }
        else
          dst = found->second;
        output.add_series_transition(current_state, dst, prod_series);
      }
  }



  template <typename S, typename M1, typename M2, typename lhs_t,
            typename rhs_t, typename res_t>
  void
  do_b_composition(const AutomataBase<S>&,
                   const algebra::FreeMonoidProduct<M1, M2>&,
                   const lhs_t&                 lhs,
                   const rhs_t&                 rhs,
                   res_t&                       output,
                   std::set<hstate_t>&          lhs_states,
                   std::set<hstate_t>&          rhs_states,
                   composition_traits::map_of_states_t&  m)
  {
    AUTOMATON_TYPES(res_t);
    AUTOMATON_TYPES_(lhs_t, lhs_);
    AUTOMATON_TYPES_(rhs_t, rhs_);

    typedef composition_traits::pair_hstate_t           pair_hstate_t;
    typedef std::set<htransition_t>                     delta_ret_t;
    typedef typename series_set_elt_t::support_t        support_t;
    typedef typename lhs_series_set_elt_t::support_t    lhs_support_t;
    typedef typename rhs_series_set_elt_t::support_t    rhs_support_t;


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

    const lhs_series_set_t&     lhs_series   = lhs.structure().series();
    const lhs_monoid_t&         lhs_monoid   = lhs_series.monoid();

    const rhs_series_set_t&     rhs_series   = rhs.structure().series();
    const rhs_monoid_t&         rhs_monoid   = rhs_series.monoid();


    typedef typename lhs_monoid_t::first_monoid_t
      lhs_first_monoid_t;
    typedef typename lhs_monoid_elt_value_t::first_type
      lhs_first_monoid_elt_value_t;
    typedef Element<lhs_first_monoid_t, lhs_first_monoid_elt_value_t>
      lhs_first_monoid_elt_t;

    typedef typename rhs_monoid_t::first_monoid_t
      rhs_first_monoid_t;
    typedef typename rhs_monoid_elt_value_t::first_type
      rhs_first_monoid_elt_value_t;
    typedef Element<rhs_first_monoid_t, rhs_first_monoid_elt_value_t>
      rhs_first_monoid_elt_t;

    typedef typename lhs_monoid_t::second_monoid_t
      lhs_second_monoid_t;
    typedef typename lhs_monoid_elt_value_t::second_type
      lhs_second_monoid_elt_value_t;
    typedef Element<lhs_second_monoid_t, lhs_second_monoid_elt_value_t>
      lhs_second_monoid_elt_t;

    typedef typename rhs_monoid_t::second_monoid_t
      rhs_second_monoid_t;
    typedef typename rhs_monoid_elt_value_t::second_type
      rhs_second_monoid_elt_value_t;
    typedef Element<rhs_second_monoid_t, rhs_second_monoid_elt_value_t>
      rhs_second_monoid_elt_t;



    lhs_first_monoid_elt_t lhs_first_identity =
      algebra::identity_as<lhs_first_monoid_elt_value_t>::
      of(lhs.structure().series().monoid().first_monoid());
    rhs_first_monoid_elt_t rhs_first_identity =
      algebra::identity_as<rhs_first_monoid_elt_value_t>::
      of(rhs.structure().series().monoid().first_monoid());
    lhs_second_monoid_elt_t lhs_second_identity =
      algebra::identity_as<lhs_second_monoid_elt_value_t>::
      of(lhs.structure().series().monoid().second_monoid());
    rhs_second_monoid_elt_t rhs_second_identity =
      algebra::identity_as<rhs_second_monoid_elt_value_t>::
      of(rhs.structure().series().monoid().second_monoid());


    composition_traits::visited_t       visited;
    composition_traits::to_process_t    to_process;

    /*----------------------------------.
    | Get initial states of the product |
    `----------------------------------*/
    for_all_initial_states(lhs_s, lhs)
      for_all_initial_states(rhs_s, rhs)
      {
        if (lhs_states.find(*lhs_s) == lhs_states.end() or
            rhs_states.find(*rhs_s) == rhs_states.end())
          {
            const hstate_t      new_state = output.add_state();
            const pair_hstate_t new_pair (*lhs_s, *rhs_s);

            m[new_state] = new_pair;
            visited[new_pair] = new_state;
            to_process.push(new_pair);
          }
      }

    /*-----------.
    | Processing |
    `-----------*/
    while (not to_process.empty())
    {
      const pair_hstate_t current_pair  = to_process.front();
      to_process.pop();

      const hstate_t lhs_s           = current_pair.first;
      const hstate_t rhs_s           = current_pair.second;
      const hstate_t current_state = visited[current_pair];

      if (lhs.is_initial(lhs_s) and rhs.is_initial(rhs_s))
      {
        lhs_series_set_elt_t in_l = lhs.get_initial(lhs_s);
        rhs_series_set_elt_t in_r = rhs.get_initial(rhs_s);

        lhs_support_t           in_left_supp = in_l.supp();
        rhs_support_t           in_right_supp = in_r.supp();

        semiring_elt_t in_semi_elt = in_l.get(*(in_left_supp.begin())) *
          in_r.get(*(in_right_supp.begin()));

        series_set_elt_t in_series_elt(series);

        in_series_elt.assoc(monoid_elt_t(monoid,
                                         algebra::identity_as<
                                         monoid_elt_value_t>::
                                         of(monoid).value()),
                            in_semi_elt);

        output.set_initial(current_state, in_series_elt);
      }

      if (lhs.is_final(lhs_s) and rhs.is_final(rhs_s))
      {
        lhs_series_set_elt_t out_l = lhs.get_final(lhs_s);
        rhs_series_set_elt_t out_r = rhs.get_final(rhs_s);

        lhs_support_t out_left_supp = out_l.supp();
        rhs_support_t out_right_supp = out_r.supp();

        semiring_elt_t out_semi_elt = out_l.get(*(out_left_supp.begin())) *
          out_r.get(*(out_right_supp.begin()));

        series_set_elt_t out_series_elt(series);

        out_series_elt.assoc(monoid_elt_t(monoid,
                                          algebra::identity_as<
                                          monoid_elt_value_t>::of(monoid)),
                             out_semi_elt);


        output.set_final(current_state, out_series_elt);
      }

      delta_ret_t transition_lhs;
      delta_ret_t transition_rhs;
      lhs.deltac(transition_lhs, lhs_s, delta_kind::transitions());
      rhs.deltac(transition_rhs, rhs_s, delta_kind::transitions());

      for_all_const_(delta_ret_t, l, transition_lhs)
      {
        const lhs_series_set_elt_t      left_series  = lhs.series_of(*l);
        lhs_support_t           left_supp = left_series.supp();
        const lhs_monoid_elt_t  left_supp_elt (lhs_monoid,
                                               *(left_supp.begin()));

        // If the outgoing transition is of type (*, 1).
        if (left_supp_elt.value().second == lhs_second_identity.value())
        {
          typename res_t::series_set_elt_t          prod_series (series);
          const monoid_elt_value_t word(left_supp_elt.value().first,
                                        rhs_second_identity.value());
          prod_series.assoc(monoid_elt_t(monoid, word),
                            left_series.get(left_supp_elt));

          add_transition (output, visited, to_process,
                          lhs_states, rhs_states,
                          m, current_state,
                          lhs.dst_of(*l), rhs_s, prod_series);
        }
        else
        {
          for_all_const_(delta_ret_t, r, transition_rhs)
          {
            const rhs_series_set_elt_t  right_series =
              rhs.series_of(*r);
            rhs_support_t               right_supp =
              right_series.supp();
            const rhs_monoid_elt_t      right_supp_elt
              (rhs_monoid, *(right_supp.begin()));

            // If the incoming transition is not of type (1, *).
            if (right_supp_elt.value().first !=
                rhs_first_identity.value())
            {
              //  we try to connect a transition of lhs and
              // a transition of rhs.
              if (left_supp_elt.value().second ==
                  right_supp_elt.value().first)
              {
                typename res_t::series_set_elt_t        prod_series (series);
                const monoid_elt_value_t                word
                  (left_supp_elt.value().first,
                   right_supp_elt.value().second);
                const semiring_elt_t            p =
                  left_series.get(left_supp_elt) *
                  right_series.get(right_supp_elt);

                prod_series.assoc(word, p.value());

                add_transition (output, visited, to_process,
                                lhs_states, rhs_states,
                                m, current_state,
                                lhs.dst_of(*l), rhs.dst_of(*r), prod_series);
              }
            }
          }
        }
      }

      for_all_const_(delta_ret_t, r, transition_rhs)
      {
        const rhs_series_set_elt_t  right_series = rhs.series_of(*r);
        rhs_support_t           right_supp = right_series.supp();
        const rhs_monoid_elt_t  right_supp_elt (rhs_monoid, *(right_supp.begin()));

        if (right_supp_elt.value().first ==
            rhs_first_identity.value())
        {
          typename res_t::series_set_elt_t      prod_series (series);
          const monoid_elt_value_t      word
            (lhs_first_identity.value(),
             right_supp_elt.value().second);
          prod_series.assoc(monoid_elt_t(monoid, word),
                            right_series.get(right_supp_elt));

          add_transition (output, visited, to_process,
                          lhs_states, rhs_states,
                          m, current_state,
                          lhs_s, rhs.dst_of(*r), prod_series);
        }
      }
    }
  }


  template <typename S, typename M1, typename M2, typename coeff_t, typename lhs_t,
            typename rhs_t, typename res_t>
  void
  do_compose(const AutomataBase<S>&,
             const algebra::FreeMonoidProduct<M1, M2>&,
             const coeff_t&,
             const lhs_t& lhs,
             const rhs_t& rhs,
             res_t& ret)
  {
    typedef std::set<hstate_t>                  set_of_states_t;
    set_of_states_t lhs_states;
    set_of_states_t rhs_states;

    lhs_t lhs_cov = splitting::outsplitting(lhs, lhs_states);
    rhs_t rhs_cov = splitting::insplitting(rhs, rhs_states);

    composition_traits::map_of_states_t m;
    do_b_composition(ret.structure(), ret.structure().series().monoid(),
                     lhs_cov, rhs_cov, ret, lhs_states, rhs_states, m);
    eps_removal_here (ret);
    sub_automaton_here (ret, useful_states (ret));
  }


  template <typename S, typename M1, typename M2, typename lhs_t,
            typename rhs_t, typename res_t>
  void
  do_compose(const AutomataBase<S>&,
             const algebra::FreeMonoidProduct<M1, M2>&,
             SELECTOR(bool),
             const lhs_t& lhs,
             const rhs_t& rhs,
             res_t& ret)
  {
    AUTOMATON_TYPES(res_t);

    typedef std::set<hstate_t>                  set_of_states_t;
    set_of_states_t lhs_states;
    set_of_states_t rhs_states;
    composition_traits::map_of_states_t m;

    do_b_composition(ret.structure(), ret.structure().series().monoid(),
                     lhs, rhs, ret, lhs_states, rhs_states, m);
  }

  template <typename S, typename M1, typename M2, typename lhs_t,
            typename rhs_t, typename res_t>
  void
  do_u_compose(const AutomataBase<S>&,
               const algebra::FreeMonoidProduct<M1, M2>&,
               SELECTOR(bool),
               const lhs_t& lhs,
               const rhs_t& rhs,
               res_t& ret)
  {
    AUTOMATON_TYPES(res_t);

    typedef std::set<hstate_t>                  set_of_states_t;
    set_of_states_t lhs_states;
    set_of_states_t rhs_states;
    composition_traits::map_of_states_t m;

    do_b_composition(ret.structure(), ret.structure().series().monoid(),
                     lhs, rhs, ret, lhs_states, rhs_states, m);
    eps_removal_here (ret);
    sub_automaton_here (ret, useful_states (ret));
  }



  template <typename S, typename T>
  void
  compose(const Element<S, T>& lhs,
          const Element<S, T>& rhs,
          Element<S, T>& ret)
  {
    typedef Element<S, T> auto_t;
    AUTOMATON_TYPES(auto_t);

    for_all_states (s, ret)
      ret.del_state (*s);

    do_compose (ret.structure(),
                ret.structure().series().monoid(),
                SELECT(semiring_elt_value_t),
                lhs, rhs, ret);
  }



  template <typename S, typename T>
  Element<S, T>
  compose(const Element<S, T>& lhs,
          const Element<S, T>& rhs)
  {
    typedef Element<S, T> auto_t;
    AUTOMATON_TYPES(auto_t);

    typedef algebra::FreeMonoidProduct<
      typename auto_t::series_set_t::monoid_t::first_monoid_t,
      typename auto_t::series_set_t::monoid_t::second_monoid_t> res_monoid_t;

    typedef algebra::Series<typename auto_t::series_set_t::semiring_t,
      res_monoid_t>
      res_series_set_t;

    res_monoid_t monoid(lhs.structure().series().monoid().first_monoid(),
                    rhs.structure().series().monoid().second_monoid());


    res_series_set_t series(lhs.structure().series().semiring(), monoid);

    Automata<series_set_t> aut_set(series);

    Element< Automata<series_set_t>, T> ret(aut_set);
    do_compose(ret.structure(),
               ret.structure().series().monoid(),
               SELECT(semiring_elt_value_t),
               lhs, rhs, ret);
    return ret;
  }



  template <typename S, typename T>
  void
  u_compose(const Element<S, T>& lhs,
            const Element<S, T>& rhs,
            Element<S, T>& ret)
  {
    typedef Element<S, T> auto_t;
    AUTOMATON_TYPES(auto_t);

    for_all_states (s, ret)
      ret.del_state (*s);

    do_u_compose (ret.structure(),
                  ret.structure().series().monoid(),
                  SELECT(semiring_elt_value_t),
                  lhs, rhs, ret);
  }

  template <typename S, typename T>
  Element<S, T>
  u_compose(const Element<S, T>& lhs,
            const Element<S, T>& rhs)
  {
    typedef Element<S, T> auto_t;
    AUTOMATON_TYPES(auto_t);

    typedef algebra::FreeMonoidProduct<
      typename auto_t::series_set_t::monoid_t::first_monoid_t,
      typename auto_t::series_set_t::monoid_t::second_monoid_t> res_monoid_t;

    typedef algebra::Series<typename auto_t::series_set_t::semiring_t,
      res_monoid_t>
      res_series_set_t;

    res_monoid_t monoid(lhs.structure().series().monoid().first_monoid(),
                    rhs.structure().series().monoid().second_monoid());


    res_series_set_t series(lhs.structure().series().semiring(), monoid);

    Automata<series_set_t> aut_set(series);

    Element< Automata<series_set_t>, T> ret(aut_set);
    do_u_compose(ret.structure(),
                 ret.structure().series().monoid(),
                 SELECT(semiring_elt_value_t),
                 lhs, rhs, ret);
    return ret;
  }

} // vcsn

#endif // ! VCSN_ALGORITHMS_NORMALIZED_COMPOSITION_HXX

---