CLAW Library (a C++ Library Absolutely Wonderful) 1.5.5
|
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 | ||
) |
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() | ( | ) |
Performs the scan.
Definition at line 116 of file graph_algorithm.tpp.
{ coloration seen_vertices; vertex_iterator it; m_events.init(m_g); for (it=m_g.vertex_begin(); it!=m_g.vertex_end(); ++it) seen_vertices[*it] = 0; for (it = m_g.vertex_begin(); it!=m_g.vertex_end(); ++it) if ( seen_vertices[*it] == 0 ) recursive_scan( *it, seen_vertices ); } // depth_scan::operator()()
void claw::depth_scan< Graph, Events >::recursive_scan | ( | const vertex_type & | s, |
coloration & | seen_vertices | ||
) | [private] |
Performs the recursive part of the scan.
Definition at line 137 of file graph_algorithm.tpp.
{ std::vector<vertex_type> neighbourhood; typename std::vector<vertex_type>::const_iterator it; m_events.start_vertex(s); seen_vertices[s] = 1; m_g.neighbours( s, neighbourhood ); for( it = neighbourhood.begin(); it != neighbourhood.end(); ++it ) if ( seen_vertices[*it] == 0 ) { m_events.visit_edge(s, *it); recursive_scan( *it, seen_vertices ); } m_events.end_vertex(s); seen_vertices[s] = 2; } // depth_scan::operator()
Events& claw::depth_scan< Graph, Events >::m_events [private] |
Definition at line 140 of file graph_algorithm.hpp.
const Graph& claw::depth_scan< Graph, Events >::m_g [private] |
Definition at line 139 of file graph_algorithm.hpp.