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 #include <queue> 00031 #include <stack> 00032 00033 /*---------------------------------------------------------------------------*/ 00040 template<class Graph, class Events> 00041 claw::breadth_scan<Graph, Events>::breadth_scan( const Graph& g, 00042 const vertex_type& source, 00043 Events& events ) 00044 : m_g(g), m_source(source), m_events(events) 00045 { 00046 00047 } // breadth_scan::breadth_scan() [constructor] 00048 00049 /*---------------------------------------------------------------------------*/ 00053 template<class Graph, class Events> 00054 void claw::breadth_scan<Graph, Events>::operator()() 00055 { 00056 coloration seen_vertices; 00057 std::queue<vertex_type> pending_vertices; 00058 vertex_type current_vertex; 00059 std::vector<vertex_type> neighbourhood; 00060 typename std::vector<vertex_type>::const_iterator it; 00061 00062 m_events.init(m_g); 00063 00064 for (vertex_iterator it_v=m_g.vertex_begin(); it_v!=m_g.vertex_end(); ++it_v) 00065 seen_vertices[*it_v] = 0; 00066 00067 seen_vertices[m_source] = 1; 00068 pending_vertices.push( m_source ); 00069 00070 while ( !pending_vertices.empty() ) 00071 { 00072 current_vertex = pending_vertices.front(); 00073 m_events.start_vertex(current_vertex); 00074 00075 m_g.neighbours( current_vertex, neighbourhood ); 00076 00077 for( it = neighbourhood.begin(); it != neighbourhood.end(); ++it ) 00078 { 00079 if ( seen_vertices[*it] == 0 ) 00080 { 00081 m_events.visit_edge(current_vertex, *it); 00082 seen_vertices[*it] = 1; 00083 } 00084 } 00085 00086 pending_vertices.pop(); 00087 m_events.end_vertex( current_vertex ); 00088 seen_vertices[current_vertex] = 2; 00089 } 00090 } // breadth_scan::operator() 00091 00092 00093 00094 //****************************** depth_scan *********************************** 00095 00096 00097 00098 /*---------------------------------------------------------------------------*/ 00104 template<class Graph, class Events> 00105 claw::depth_scan<Graph, Events>::depth_scan( const Graph& g, Events& events ) 00106 : m_g(g), m_events(events) 00107 { 00108 00109 } // depth_scan::depth_scan() [constructor] 00110 00111 /*---------------------------------------------------------------------------*/ 00115 template<class Graph, class Events> 00116 void claw::depth_scan<Graph, Events>::operator()() 00117 { 00118 coloration seen_vertices; 00119 vertex_iterator it; 00120 00121 m_events.init(m_g); 00122 00123 for (it=m_g.vertex_begin(); it!=m_g.vertex_end(); ++it) 00124 seen_vertices[*it] = 0; 00125 00126 for (it = m_g.vertex_begin(); it!=m_g.vertex_end(); ++it) 00127 if ( seen_vertices[*it] == 0 ) 00128 recursive_scan( *it, seen_vertices ); 00129 } // depth_scan::operator()() 00130 00131 /*---------------------------------------------------------------------------*/ 00135 template<class Graph, class Events> 00136 void claw::depth_scan<Graph, Events>::recursive_scan 00137 ( const vertex_type& s, coloration& seen_vertices ) 00138 { 00139 std::vector<vertex_type> neighbourhood; 00140 typename std::vector<vertex_type>::const_iterator it; 00141 00142 m_events.start_vertex(s); 00143 seen_vertices[s] = 1; 00144 00145 m_g.neighbours( s, neighbourhood ); 00146 00147 for( it = neighbourhood.begin(); it != neighbourhood.end(); ++it ) 00148 if ( seen_vertices[*it] == 0 ) 00149 { 00150 m_events.visit_edge(s, *it); 00151 recursive_scan( *it, seen_vertices ); 00152 } 00153 00154 m_events.end_vertex(s); 00155 seen_vertices[s] = 2; 00156 } // depth_scan::operator() 00157 00158 00159 00160 00161 00162 00163 //********************** topological_sort *********************************** 00164 00165 00166 00167 00168 00169 00170 00171 00172 00173 /*---------------------------------------------------------------------------*/ 00178 template<class Graph> 00179 void claw::topological_sort<Graph>::init( const Graph& g ) 00180 { 00181 m_result.resize( g.vertices_count() ); 00182 m_next_index = (int)g.vertices_count()-1; 00183 } // topological_sort::init() 00184 00185 #include <iostream> 00186 /*---------------------------------------------------------------------------*/ 00187 template<class Graph> 00188 void claw::topological_sort<Graph>::end_vertex( const vertex_type& s ) 00189 { 00190 m_result[m_next_index] = s; 00191 --m_next_index; 00192 } // topological_sort::end() 00193 00194 /*---------------------------------------------------------------------------*/ 00195 template<class Graph> 00196 void claw::topological_sort<Graph>::operator()( const Graph& g ) 00197 { 00198 claw::depth_scan< Graph, self_type > scan( g, *this ); 00199 scan(); 00200 } // topological_sort::operator()() 00201 00202 /*---------------------------------------------------------------------------*/ 00203 template<class Graph> 00204 const typename claw::topological_sort<Graph>::vertex_type & 00205 claw::topological_sort<Graph>::operator[](unsigned int index) const 00206 { 00207 return m_result[index]; 00208 } // topological_sort::operator[]() 00209 00210 /*---------------------------------------------------------------------------*/ 00211 template<class Graph> 00212 typename claw::topological_sort<Graph>::const_iterator 00213 claw::topological_sort<Graph>::begin() const 00214 { 00215 return m_result.begin(); 00216 } // topological_sort::begin() 00217 00218 /*---------------------------------------------------------------------------*/ 00219 template<class Graph> 00220 typename claw::topological_sort<Graph>::const_iterator 00221 claw::topological_sort<Graph>::end() const 00222 { 00223 return m_result.end(); 00224 } // topological_sort::end()