accessible.hxx

00001 // accessible.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 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_ACCESSIBLE_HXX
00018 # define VCSN_ALGORITHMS_ACCESSIBLE_HXX
00019 
00020 # include <vaucanson/algorithms/accessible.hh>
00021 
00022 # include <vaucanson/automata/concept/automata_base.hh>
00023 # include <vaucanson/automata/implementation/transpose_view.hh>
00024 # include <vaucanson/algorithms/sub_automaton.hh>
00025 # include <vaucanson/misc/usual_macros.hh>
00026 
00027 # include <queue>
00028 # include <set>
00029 
00030 
00031 namespace vcsn {
00032 
00033   /*-----------------------.
00034   | do_accessible_states.  |
00035   `-----------------------*/
00036 
00037   template <class A_, typename Auto_>
00038   std::set<hstate_t>
00039   do_accessible_states(const AutomataBase<A_>&,
00040                        const Auto_&                a)
00041   {
00042     AUTOMATON_TYPES(Auto_);
00043     typedef std::set<hstate_t> state_set_t;
00044 
00045     std::queue<hstate_t>      queue;
00046     state_set_t               reachable_states;
00047 
00048     /*---------------.
00049     | Initialization |
00050     `---------------*/
00051     for_all_initial_states(i, a)
00052     {
00053       queue.push(*i);
00054       reachable_states.insert(*i);
00055     }
00056 
00057     /*----------.
00058     | Main loop |
00059     `----------*/
00060     while (!queue.empty())
00061     {
00062       hstate_t state = queue.front();
00063       queue.pop();
00064       state_set_t delta_ret;
00065       a.deltac(delta_ret, state, delta_kind::states());
00066       for_all_const_(state_set_t, j, delta_ret)
00067       {
00068         state = *j;
00069         if (reachable_states.find(state) == reachable_states.end())
00070         {
00071           reachable_states.insert(state);
00072           queue.push(state);
00073         }
00074       }
00075     }
00076     return reachable_states;
00077   }
00078 
00079   template<typename A, typename T>
00080   std::set<hstate_t>
00081   accessible_states(const Element<A, T>& a)
00082   {
00083     TIMER_SCOPED ("accessible_states");
00084     return do_accessible_states(a.structure(), a);
00085   }
00086 
00087   template<typename A, typename T>
00088   void
00089   accessible_here(Element<A, T>& a)
00090   {
00091     sub_automaton_here(a, accessible_states(a));
00092   }
00093 
00094   template<typename A, typename T>
00095   Element<A, T>
00096   accessible(const Element<A, T>& a)
00097   {
00098     return sub_automaton(a, accessible_states(a));
00099   }
00100 
00101   /*-----------------------.
00102   | do_coaccessible_states |
00103   `-----------------------*/
00104 
00105   template <class A_, typename Auto_>
00106   std::set<hstate_t>
00107   do_coaccessible_states(const AutomataBase<A_>&,
00108                          const Auto_&          a)
00109   {
00110     return accessible_states(transpose_view(a));
00111   }
00112 
00113   template<typename A, typename T>
00114   std::set<hstate_t>
00115   coaccessible_states(const Element<A, T>& a)
00116   {
00117     return do_coaccessible_states(a.structure(), a);
00118   }
00119 
00120   template<typename A, typename T>
00121   Element<A, T>
00122   coaccessible(const Element<A, T>& a)
00123   {
00124     return sub_automaton(a, coaccessible_states(a));
00125   }
00126 
00127   template<typename A, typename T>
00128   void
00129   coaccessible_here(Element<A, T>& a)
00130   {
00131     sub_automaton_here(a, coaccessible_states(a));
00132   }
00133 
00134 } // vcsn
00135 
00136 #endif // ! VCSN_ALGORITHMS_ACCESSIBLE_HXX

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