product.hxx

00001 // product.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
00016 //
00017 #ifndef VCSN_ALGORITHMS_PRODUCT_HXX
00018 # define VCSN_ALGORITHMS_PRODUCT_HXX
00019 
00020 # include <set>
00021 # include <map>
00022 # include <queue>
00023 # include <stack>
00024 
00025 # include <vaucanson/algorithms/product.hh>
00026 # include <vaucanson/algorithms/is_realtime.hh>
00027 
00028 # include <vaucanson/automata/concept/automata_base.hh>
00029 # include <vaucanson/misc/usual_macros.hh>
00030 # include <vaucanson/automata/implementation/geometry.hh>
00031 # include <vaucanson/misc/static.hh>
00032 
00033 namespace vcsn
00034 {
00035 
00036   /*--------------------------------.
00037   | Functor for product algorithm.  |
00038   `--------------------------------*/
00039   template<typename A, typename T, typename U>
00040   class Product
00041   {
00042     public:
00043       typedef AutomataBase<A> structure_t;
00044       typedef Element<A, T> lhs_t;
00045       typedef Element<A, U> rhs_t;
00046       typedef lhs_t         output_t;
00047       typedef std::map<hstate_t, std::pair<hstate_t, hstate_t> > pair_map_t;
00048 
00049       Product (const structure_t& structure,
00050                const bool use_geometry)
00051         : use_geometry_(use_geometry),
00052           series_(structure.series()),
00053           monoid_(series_.monoid()),
00054           semiring_zero_(series_.semiring().zero(SELECT(semiring_elt_value_t)))
00055       {
00056       }
00057 
00058       // returns the product of @c lhs and @c rhs (and put it also in @c output)
00059       output_t&
00060       operator() (output_t& output,
00061                   const lhs_t& lhs,
00062                   const rhs_t& rhs,
00063                   pair_map_t& m)
00064       {
00065         TIMER_SCOPED("product");
00066         visited_.clear();
00067 
00068         precondition(is_realtime(lhs));
00069         precondition(is_realtime(rhs));
00070 
00071         this->initialize_queue(output, lhs, rhs, m);
00072 
00073         delta_ret_t transition_lhs;
00074         delta_ret_t transition_rhs;
00075         while (not to_process_.empty())
00076         {
00077           const pair_hstate_t current_pair = to_process_.front();
00078           to_process_.pop();
00079 
00080           const hstate_t lhs_s       = current_pair.first;
00081           const hstate_t rhs_s       = current_pair.second;
00082           const hstate_t current_state = visited_[current_pair];
00083 
00084           output.set_initial(current_state,
00085                              lhs.get_initial(lhs_s) * rhs.get_initial(rhs_s));
00086           output.set_final(current_state,
00087                            lhs.get_final(lhs_s) * rhs.get_final(rhs_s));
00088 
00089           transition_lhs.clear();
00090           transition_rhs.clear();
00091           lhs.deltac(transition_lhs, lhs_s, delta_kind::transitions());
00092           rhs.deltac(transition_rhs, rhs_s, delta_kind::transitions());
00093 
00094           for_all_const_(delta_ret_t, l, transition_lhs)
00095             for_all_const_(delta_ret_t, r, transition_rhs)
00096             {
00097               series_set_elt_t  prod_series(series_);
00098 
00099               if (is_product_not_null(lhs, rhs, l, r, prod_series))
00100               {
00101                 const pair_hstate_t new_pair(lhs.dst_of(*l), rhs.dst_of(*r));
00102                 typename visited_t::const_iterator found = visited_.find(new_pair);
00103 
00104                 hstate_t dst;
00105                 if (found == visited_.end())
00106                 {
00107                   dst = output.add_state();
00108 
00109                   this->add_state_to_process(output, lhs, rhs, m, dst, new_pair);
00110                 }
00111                 else
00112                   dst = found->second;
00113                 output.add_series_transition(current_state, dst, prod_series);
00114               }
00115             }
00116         }
00117         return output;
00118       }
00119 
00120     private:
00121       // Some little graphic tools
00122       class grphx
00123       {
00124         public:
00125           template <typename Output, typename Lhs, typename Rhs>
00126           static void
00127           setcoordfrom (Output& a,
00128                         const Lhs& lhs,
00129                         const Rhs& rhs,
00130                         const hstate_t state,
00131                         const hstate_t x_state,
00132                         const hstate_t y_state)
00133           {
00134             std::map<hstate_t, std::pair<double, double> >::const_iterator iter;
00135             double x = 0, y = 0;
00136 
00137             iter = lhs.geometry().states().find(x_state);
00138             if (iter != lhs.geometry().states().end())
00139               x = iter->second.first;
00140 
00141             iter = rhs.geometry().states().find(y_state);
00142             if (iter != rhs.geometry().states().end())
00143               y = iter->second.second;
00144 
00145             a.geometry().states()[state] = std::make_pair(x, y);
00146           }
00147         private:
00148           // Diagonal alignement with a depth-first traversal
00149           template<typename I>
00150           void
00151           align (const I& a)
00152           {
00153             AUTOMATON_TYPES(I);
00154             std::map<hstate_t,bool> visited;
00155             std::stack<hstate_t> stack;
00156 
00157             for_all_states(i, a)
00158               {
00159                 visited[*i] = false;
00160                 // ensure inaccessible states will be visited
00161                 stack.push(*i);
00162               }
00163 
00164             for_all_initial_states(i, a)
00165               stack.push(*i);
00166 
00167             int x = 0;
00168             while (!stack.empty())
00169             {
00170               hstate_t i = stack.top();
00171               stack.pop();
00172 
00173               if (!visited[i])
00174               {
00175                 visited[i] = true;
00176 
00177                 a.geometry()[i] = std::make_pair(x, x);
00178                 x++;
00179 
00180                 std::vector<htransition_t> dst;
00181                 a.deltac(dst, i, delta_kind::transitions());
00182                 for_all_const_(std::vector<htransition_t>, j, dst)
00183                   stack.push(a.dst_of(*j));
00184               }
00185             }
00186           }
00187 
00188       };
00189       class no_grphx
00190       {
00191         public:
00192           template <typename Output, typename Lhs, typename Rhs>
00193           static void
00194           setcoordfrom (Output& a,
00195                         const Lhs& lhs,
00196                         const Rhs& rhs,
00197                         const hstate_t state,
00198                         const hstate_t x_state,
00199                         const hstate_t y_state) {};
00200       };
00201 
00202       // useful typedefs
00203       AUTOMATON_TYPES(output_t);
00204 
00205       typedef std::pair<hstate_t, hstate_t>             pair_hstate_t;
00206       typedef std::set<htransition_t>                   delta_ret_t;
00207       typedef std::map<pair_hstate_t, hstate_t>         visited_t;
00208       typedef typename series_set_elt_t::support_t      support_t;
00209 
00210       // add a @c new_state in the queue
00211       inline void
00212       add_state_to_process (output_t& output,
00213                             const lhs_t& lhs,
00214                             const rhs_t& rhs,
00215                             pair_map_t& m,
00216                             const hstate_t& new_state,
00217                             const pair_hstate_t& new_pair)
00218       {
00219         m[new_state] = new_pair;
00220         visited_[new_pair] = new_state;
00221         to_process_.push(new_pair);
00222 
00223 # define if_(Cond, ThenClause, ElseClause)                      \
00224   misc::static_if_simple<Cond, ThenClause, ElseClause>::t
00225 # define eq_(Type1, Type2)                      \
00226   misc::static_eq<Type1, Type2>::value
00227 
00228         if (use_geometry_)
00229           if_(eq_(typename output_t::geometry_t, geometry) and  \
00230               eq_(typename rhs_t::geometry_t, geometry) and             \
00231               eq_(typename lhs_t::geometry_t, geometry),                \
00232               grphx, no_grphx)
00233             ::setcoordfrom(output, lhs, rhs,
00234                            new_state, new_pair.first, new_pair.second);
00235 # undef if_
00236 # undef eq_
00237       }
00238 
00239       // initialize queue with all pairs of intials states from @c lhs and @c rhs
00240       inline void
00241       initialize_queue (output_t& output,
00242                         const lhs_t& lhs,
00243                         const rhs_t& rhs,
00244                         pair_map_t& m)
00245       {
00246         for_all_initial_states(lhs_s, lhs)
00247           for_all_initial_states(rhs_s, rhs)
00248           {
00249             const pair_hstate_t new_pair(*lhs_s, *rhs_s);
00250             const hstate_t      new_state = output.add_state();
00251 
00252             this->add_state_to_process(output, lhs, rhs, m, new_state, new_pair);
00253           }
00254       }
00255 
00256       inline bool
00257       is_product_not_null (const lhs_t& lhs,
00258                            const rhs_t& rhs,
00259                            const delta_ret_t::const_iterator& l,
00260                            const delta_ret_t::const_iterator& r,
00261                            series_set_elt_t&  prod_series) const
00262       {
00263         const series_set_elt_t  left_series  = lhs.series_of(*l);
00264         const series_set_elt_t  right_series = rhs.series_of(*r);
00265 
00266         bool                    prod_is_not_null = false;
00267         for_all_(support_t, supp, left_series.supp())
00268           {
00269             const monoid_elt_t   supp_elt (monoid_, *supp);
00270             const semiring_elt_t l = left_series.get(supp_elt);
00271             const semiring_elt_t r = right_series.get(supp_elt);
00272             const semiring_elt_t p = l * r;
00273             if (p != semiring_zero_)
00274             {
00275               prod_series.assoc(*supp, p.value());
00276               prod_is_not_null = true;
00277             }
00278           }
00279         return (prod_is_not_null);
00280       }
00281 
00282       // If set to true, <geometry> tags of the result automaton should be filled
00283       const bool        use_geometry_;
00284 
00285       // keep traces of new states created
00286       visited_t                 visited_;
00287       // @c to_process_ stores all states of output that needs are not
00288       std::queue<pair_hstate_t> to_process_;
00289 
00290       // frequently used objects in computation
00291       const series_set_t&       series_;
00292       const monoid_t&           monoid_;
00293       // This variable's type must not be set to a reference.
00294       const semiring_elt_t      semiring_zero_;
00295   };
00296 
00297   /*-----------.
00298   | Wrappers.  |
00299   `-----------*/
00300 
00301   template<typename A, typename T, typename U>
00302   Element<A, T>
00303   product (const Element<A, T>& lhs, const Element<A, U>& rhs,
00304            std::map<hstate_t, std::pair<hstate_t, hstate_t> >& m,
00305            const bool use_geometry)
00306   {
00307     Element<A, T> ret(rhs.structure());
00308     Product<A, T, U> do_product(ret.structure(), use_geometry);
00309     return do_product (ret, lhs, rhs, m);
00310   }
00311 
00312   template<typename A, typename T, typename U>
00313   Element<A, T>
00314   product (const Element<A, T>& lhs, const Element<A, U>& rhs,
00315            const bool use_geometry)
00316   {
00317     std::map<hstate_t, std::pair<hstate_t, hstate_t> > m;
00318     return product (lhs, rhs, m, use_geometry);
00319   }
00320 
00321 } // End of namespace vcsn.
00322 
00323 #endif // ! VCSN_ALGORITHMS_PRODUCT_HXX

Generated on Sun Jul 29 19:35:28 2007 for Vaucanson by  doxygen 1.5.2