Claw 1.7.0
|
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-2011 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@gamned.org 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__