Pass this class as the "Envents" template parameter of the depth scan class to sort the vertices of a graph with the topological sort algorithm. More...
#include <graph_algorithm.hpp>
Public Types | |
typedef scan_events< Graph > ::vertex_type | vertex_type |
typedef std::vector< vertex_type > | result_type |
typedef result_type::const_iterator | const_iterator |
typedef topological_sort< Graph > | self_type |
Public Member Functions | |
void | init (const Graph &g) |
Initialize the scan. | |
void | end_vertex (const vertex_type &s) |
void | operator() (const Graph &g) |
const vertex_type & | operator[] (unsigned int index) const |
const_iterator | begin () const |
const_iterator | end () const |
Private Attributes | |
result_type | m_result |
The vector we're filling. | |
int | m_next_index |
Index of the next item to put in the vector. |
Pass this class as the "Envents" template parameter of the depth scan class to sort the vertices of a graph with the topological sort algorithm.
When a node process ends, the node is added to a vector. The vector is filled from end to begining.
Definition at line 160 of file graph_algorithm.hpp.
typedef result_type::const_iterator claw::topological_sort< Graph >::const_iterator |
Definition at line 165 of file graph_algorithm.hpp.
typedef std::vector<vertex_type> claw::topological_sort< Graph >::result_type |
Definition at line 164 of file graph_algorithm.hpp.
typedef topological_sort<Graph> claw::topological_sort< Graph >::self_type |
Definition at line 166 of file graph_algorithm.hpp.
typedef scan_events<Graph>::vertex_type claw::topological_sort< Graph >::vertex_type |
Reimplemented from claw::scan_events< Graph >.
Definition at line 163 of file graph_algorithm.hpp.
claw::topological_sort< Graph >::const_iterator claw::topological_sort< Graph >::begin | ( | ) | const [inline] |
Definition at line 213 of file graph_algorithm.tpp.
References claw::topological_sort< Graph >::m_result.
00214 { 00215 return m_result.begin(); 00216 } // topological_sort::begin()
claw::topological_sort< Graph >::const_iterator claw::topological_sort< Graph >::end | ( | ) | const [inline] |
Definition at line 221 of file graph_algorithm.tpp.
References claw::topological_sort< Graph >::m_result.
00222 { 00223 return m_result.end(); 00224 } // topological_sort::end()
void claw::topological_sort< Graph >::end_vertex | ( | const vertex_type & | s | ) | [inline] |
Reimplemented from claw::scan_events< Graph >.
Definition at line 188 of file graph_algorithm.tpp.
References claw::topological_sort< Graph >::m_next_index, and claw::topological_sort< Graph >::m_result.
00189 { 00190 m_result[m_next_index] = s; 00191 --m_next_index; 00192 } // topological_sort::end()
void claw::topological_sort< Graph >::init | ( | const Graph & | g | ) | [inline] |
Initialize the scan.
g | The graph that will be scanned. |
Reimplemented from claw::scan_events< Graph >.
Definition at line 179 of file graph_algorithm.tpp.
References claw::topological_sort< Graph >::m_next_index, and claw::topological_sort< Graph >::m_result.
00180 { 00181 m_result.resize( g.vertices_count() ); 00182 m_next_index = (int)g.vertices_count()-1; 00183 } // topological_sort::init()
void claw::topological_sort< Graph >::operator() | ( | const Graph & | g | ) | [inline] |
Definition at line 196 of file graph_algorithm.tpp.
00197 { 00198 claw::depth_scan< Graph, self_type > scan( g, *this ); 00199 scan(); 00200 } // topological_sort::operator()()
const claw::topological_sort< Graph >::vertex_type & claw::topological_sort< Graph >::operator[] | ( | unsigned int | index | ) | const [inline] |
Definition at line 205 of file graph_algorithm.tpp.
References claw::topological_sort< Graph >::m_result.
00206 { 00207 return m_result[index]; 00208 } // topological_sort::operator[]()
int claw::topological_sort< Graph >::m_next_index [private] |
Index of the next item to put in the vector.
Definition at line 182 of file graph_algorithm.hpp.
Referenced by claw::topological_sort< Graph >::end_vertex(), and claw::topological_sort< Graph >::init().
result_type claw::topological_sort< Graph >::m_result [private] |
The vector we're filling.
Definition at line 180 of file graph_algorithm.hpp.
Referenced by claw::topological_sort< Graph >::begin(), claw::topological_sort< Graph >::end(), claw::topological_sort< Graph >::end_vertex(), claw::topological_sort< Graph >::init(), and claw::topological_sort< Graph >::operator[]().