00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
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 }
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 }
00091
00092
00093
00094
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 }
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 }
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 }
00157
00158
00159
00160
00161
00162
00163
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 }
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 }
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 }
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 }
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 }
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 }