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 | |||
) | [inline] |
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() | ( | ) | [inline] |
Performs the scan.
Definition at line 54 of file graph_algorithm.tpp.
References claw::breadth_scan< Graph, Events >::m_events, claw::breadth_scan< Graph, Events >::m_g, and claw::breadth_scan< Graph, Events >::m_source.
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 } // breadth_scan::operator()
Events& claw::breadth_scan< Graph, Events >::m_events [private] |
Definition at line 95 of file graph_algorithm.hpp.
Referenced by claw::breadth_scan< Graph, Events >::operator()().
const Graph& claw::breadth_scan< Graph, Events >::m_g [private] |
Definition at line 93 of file graph_algorithm.hpp.
Referenced by claw::breadth_scan< Graph, Events >::operator()().
const vertex_type& claw::breadth_scan< Graph, Events >::m_source [private] |
Definition at line 94 of file graph_algorithm.hpp.
Referenced by claw::breadth_scan< Graph, Events >::operator()().