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 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   // preconditions :
00037   //
00038   //
00039   template <class A_, typename Auto_>
00040   std::set<hstate_t>
00041   do_accessible_states(const AutomataBase<A_>&,
00042                        const Auto_&                a)
00043   {
00044     AUTOMATON_TYPES(Auto_);
00045     typedef std::set<hstate_t>                  reachable_set_t;
00046     typedef std::set<hstate_t>                  delta_ret_t;
00047     typedef std::queue<hstate_t>                queue_t;
00048 
00049     delta_ret_t                       delta_ret;
00050     hstate_t                          state;
00051     queue_t                           queue;
00052     reachable_set_t                   reachable_states;
00053 
00054     /*---------------.
00055     | Initialization |
00056     `---------------*/
00057     for_all_initial_states(i, a)
00058     {
00059       queue.push(*i);
00060       reachable_states.insert(*i);
00061     }
00062 
00063     /*----------.
00064     | Main loop |
00065     `----------*/
00066     while (!queue.empty())
00067     {
00068       state = queue.front();
00069       queue.pop();
00070       delta_ret.clear();
00071       a.deltac(delta_ret, state, delta_kind::states());
00072       for_all_const_(delta_ret_t, j, delta_ret)
00073       {
00074         state = *j;
00075         if (reachable_states.find(state) == reachable_states.end())
00076         {
00077           reachable_states.insert(state);
00078           queue.push(state);
00079         }
00080       }
00081     }
00082     return reachable_states;
00083   }
00084 
00085   template<typename A, typename T>
00086   std::set<hstate_t>
00087   accessible_states(const Element<A, T>& a)
00088   {
00089     return do_accessible_states(a.structure(), a);
00090   }
00091 
00092   template<typename A, typename T>
00093   void
00094   accessible_here(Element<A, T>& a)
00095   {
00096     sub_automaton_here(a, accessible_states(a));
00097   }
00098 
00099   template<typename A, typename T>
00100   Element<A, T>
00101   accessible(const Element<A, T>& a)
00102   {
00103     return sub_automaton(a, accessible_states(a));
00104   }
00105 
00106   /*-----------------------.
00107   | do_coaccessible_states |
00108   `-----------------------*/
00109   // preconditions :
00110   //
00111   //
00112   template <class A_, typename Auto_>
00113   std::set<hstate_t>
00114   do_coaccessible_states(const AutomataBase<A_>&,
00115                          const Auto_&          a)
00116   {
00117     return accessible_states(transpose_view(a));
00118   }
00119 
00120   template<typename A, typename T>
00121   std::set<hstate_t>
00122   coaccessible_states(const Element<A, T>& a)
00123   {
00124     return do_coaccessible_states(a.structure(), a);
00125   }
00126 
00127   template<typename A, typename T>
00128   Element<A, T>
00129   coaccessible(const Element<A, T>& a)
00130   {
00131     return sub_automaton(a, coaccessible_states(a));
00132   }
00133 
00134   template<typename A, typename T>
00135   void
00136   coaccessible_here(Element<A, T>& a)
00137   {
00138     sub_automaton_here(a, coaccessible_states(a));
00139   }
00140 
00141 } // vcsn
00142 
00143 #endif // ! VCSN_ALGORITHMS_ACCESSIBLE_HXX

Generated on Sat Jul 29 17:12:57 2006 for Vaucanson by  doxygen 1.4.6