graph_algorithm.hpp

Go to the documentation of this file.
00001 /*
00002   CLAW - a C++ Library Absolutely Wonderful
00003 
00004   CLAW is a free library without any particular aim but being useful to 
00005   anyone.
00006 
00007   Copyright (C) 2005-2008 Julien Jorge
00008 
00009   This library is free software; you can redistribute it and/or
00010   modify it under the terms of the GNU Lesser General Public
00011   License as published by the Free Software Foundation; either
00012   version 2.1 of the License, or (at your option) any later version.
00013 
00014   This library is distributed in the hope that it will be useful,
00015   but WITHOUT ANY WARRANTY; without even the implied warranty of
00016   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017   Lesser General Public License for more details.
00018 
00019   You should have received a copy of the GNU Lesser General Public
00020   License along with this library; if not, write to the Free Software
00021   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00022 
00023   contact: julien_jorge@yahoo.fr
00024 */
00030 #ifndef __CLAW_GRAPH_ALGORITHM_HPP__
00031 #define __CLAW_GRAPH_ALGORITHM_HPP__
00032 
00033 #include <map>
00034 
00035 namespace claw
00036 {
00037   //*************************** graph::scan_events ****************************
00038 
00042   template<class Graph>
00043   class scan_events
00044   {
00045   public:
00046     typedef typename Graph::vertex_type vertex_type;
00047 
00048   public:
00049     void init( const Graph& g ) {}
00050     void start_vertex( const vertex_type& v ) {}
00051     void visit_edge( const vertex_type& v1, const vertex_type& v2 ) {}
00052     void end_vertex( const vertex_type& v ) {}
00053   }; // class scan_events
00054 
00055 
00056 
00057 
00058 
00059 
00060 
00061   //************************** breadth_scan ***********************************
00062 
00063 
00064 
00065 
00066 
00071   template<class Graph, class Events = scan_events<Graph> >
00072   class breadth_scan
00073   {
00074   public:
00075     typedef typename Graph::vertex_type vertex_type;
00076     typedef typename Graph::vertex_iterator vertex_iterator ;
00083     typedef std::map<vertex_type, int,
00084                      typename Graph::vertex_compare> coloration;
00085 
00086   public:
00087     breadth_scan( const Graph& g, const vertex_type& source,
00088                   Events& events );
00089 
00090     void operator()();
00091 
00092   private:
00093     const Graph& m_g;
00094     const vertex_type& m_source;
00095     Events& m_events;
00096   }; // class breadth_scan
00097 
00098 
00099 
00100 
00101 
00102 
00103 
00104   //**************************** depth_scan ***********************************
00105 
00106 
00107 
00108 
00109 
00110 
00115   template<class Graph, class Events = typename Graph::scan_events>
00116   class depth_scan
00117   {
00118   public:
00119     typedef typename Graph::vertex_type vertex_type;
00120     typedef typename Graph::vertex_iterator vertex_iterator ;
00127     typedef std::map<vertex_type, int,
00128                      typename Graph::vertex_compare> coloration;
00129 
00130   public:
00131     depth_scan( const Graph& g, Events& events );
00132 
00133     void operator()();
00134 
00135   private:
00136     void recursive_scan(const vertex_type& s, coloration& seen_vertices);
00137 
00138   private:
00139     const Graph& m_g;
00140     Events& m_events;
00141   }; // class depth_scan
00142 
00143 
00144 
00145 
00146   //********************** topological_sort ***********************************
00147 
00148 
00149 
00150 
00159   template<class Graph>
00160   class topological_sort : public scan_events<Graph>
00161   {
00162   public:
00163     typedef typename scan_events<Graph>::vertex_type vertex_type;
00164     typedef std::vector<vertex_type> result_type;
00165     typedef typename result_type::const_iterator const_iterator;
00166     typedef topological_sort<Graph> self_type;
00167 
00168   public:
00169     void init( const Graph& g );
00170     void end_vertex( const vertex_type& s );
00171 
00172     void operator()( const Graph& g );
00173     const vertex_type& operator[](unsigned int index) const;
00174         
00175     const_iterator begin() const;
00176     const_iterator end() const;
00177 
00178   private:
00180     result_type m_result;
00182     int m_next_index;
00183   }; // class topological_sort
00184 
00185 } // namespace claw
00186 
00187 #include <claw/impl/graph_algorithm.tpp>
00188 
00189 #endif // __CLAW_GRAPH_ALGORITHM_HPP__

Generated on Mon Nov 9 05:07:33 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.4.7