This class performs a depth scan of a graph. Only reachables vertices from a given vertex 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 | |
breadth_scan (const Graph &g, const vertex_type &source, Events &events) | |
Constructor. | |
void | operator() () |
Performs the scan. | |
Private Attributes | |
const Graph & | m_g |
const vertex_type & | m_source |
Events & | m_events |
This class performs a depth scan of a graph. Only reachables vertices from a given vertex are proceeded.
Definition at line 72 of file graph_algorithm.hpp.
typedef std::map<vertex_type, int, typename Graph::vertex_compare> claw::breadth_scan< Graph, Events >::coloration |
Colors are :
Definition at line 84 of file graph_algorithm.hpp.
typedef Graph::vertex_iterator claw::breadth_scan< Graph, Events >::vertex_iterator |
Definition at line 76 of file graph_algorithm.hpp.
typedef Graph::vertex_type claw::breadth_scan< Graph, Events >::vertex_type |
Definition at line 75 of file graph_algorithm.hpp.
claw::breadth_scan< Graph, Events >::breadth_scan | ( | const Graph & | g, |
const vertex_type & | source, | ||
Events & | events | ||
) |
Constructor.
g | Graph to scan. |
source | Start_Vertexing vertex. |
events | User's processings. |
Definition at line 41 of file graph_algorithm.tpp.
void claw::breadth_scan< Graph, Events >::operator() | ( | ) |
Performs the scan.
Definition at line 54 of file graph_algorithm.tpp.
{ coloration seen_vertices; std::queue<vertex_type> pending_vertices; vertex_type current_vertex; std::vector<vertex_type> neighbourhood; typename std::vector<vertex_type>::const_iterator it; m_events.init(m_g); for (vertex_iterator it_v=m_g.vertex_begin(); it_v!=m_g.vertex_end(); ++it_v) seen_vertices[*it_v] = 0; seen_vertices[m_source] = 1; pending_vertices.push( m_source ); while ( !pending_vertices.empty() ) { current_vertex = pending_vertices.front(); m_events.start_vertex(current_vertex); m_g.neighbours( current_vertex, neighbourhood ); for( it = neighbourhood.begin(); it != neighbourhood.end(); ++it ) { if ( seen_vertices[*it] == 0 ) { m_events.visit_edge(current_vertex, *it); seen_vertices[*it] = 1; } } pending_vertices.pop(); m_events.end_vertex( current_vertex ); seen_vertices[current_vertex] = 2; } } // breadth_scan::operator()
Events& claw::breadth_scan< Graph, Events >::m_events [private] |
Definition at line 95 of file graph_algorithm.hpp.
const Graph& claw::breadth_scan< Graph, Events >::m_g [private] |
Definition at line 93 of file graph_algorithm.hpp.
const vertex_type& claw::breadth_scan< Graph, Events >::m_source [private] |
Definition at line 94 of file graph_algorithm.hpp.