This class performs a depth scan of a graph. All nodes are proceeded. More...
#include <graph_algorithm.hpp>
Public Types | |
typedef Graph::vertex_type | vertex_type |
typedef Graph::vertex_iterator | vertex_iterator |
typedef std::map< vertex_type, int, typename Graph::vertex_compare > | coloration |
Colors are :
| |
Public Member Functions | |
depth_scan (const Graph &g, Events &events) | |
Constructor. | |
void | operator() () |
Performs the scan. | |
Private Member Functions | |
void | recursive_scan (const vertex_type &s, coloration &seen_vertices) |
Performs the recursive part of the scan. | |
Private Attributes | |
const Graph & | m_g |
Events & | m_events |
This class performs a depth scan of a graph. All nodes are proceeded.
Definition at line 116 of file graph_algorithm.hpp.
typedef std::map<vertex_type, int, typename Graph::vertex_compare> claw::depth_scan< Graph, Events >::coloration |
Colors are :
Definition at line 128 of file graph_algorithm.hpp.
typedef Graph::vertex_iterator claw::depth_scan< Graph, Events >::vertex_iterator |
Definition at line 120 of file graph_algorithm.hpp.
typedef Graph::vertex_type claw::depth_scan< Graph, Events >::vertex_type |
Definition at line 119 of file graph_algorithm.hpp.
claw::depth_scan< Graph, Events >::depth_scan | ( | const Graph & | g, | |
Events & | events | |||
) | [inline] |
Constructor.
g | Graph to scan. | |
events | User's processings. |
Definition at line 105 of file graph_algorithm.tpp.
void claw::depth_scan< Graph, Events >::operator() | ( | ) | [inline] |
Performs the scan.
Definition at line 116 of file graph_algorithm.tpp.
References claw::depth_scan< Graph, Events >::m_events, claw::depth_scan< Graph, Events >::m_g, and claw::depth_scan< Graph, Events >::recursive_scan().
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()()
void claw::depth_scan< Graph, Events >::recursive_scan | ( | const vertex_type & | s, | |
coloration & | seen_vertices | |||
) | [inline, private] |
Performs the recursive part of the scan.
Definition at line 137 of file graph_algorithm.tpp.
Referenced by claw::depth_scan< Graph, Events >::operator()().
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()
Events& claw::depth_scan< Graph, Events >::m_events [private] |
Definition at line 140 of file graph_algorithm.hpp.
Referenced by claw::depth_scan< Graph, Events >::operator()().
const Graph& claw::depth_scan< Graph, Events >::m_g [private] |
Definition at line 139 of file graph_algorithm.hpp.
Referenced by claw::depth_scan< Graph, Events >::operator()().