graph_algorithm.tpp
Go to the documentation of this file.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 }