claw::breadth_scan< Graph, Events > Class Template Reference

This class performs a depth scan of a graph. Only reachables vertices from a given vertex are proceeded. More...

#include <graph_algorithm.hpp>

List of all members.

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 :

  • 0 : never seen.
  • 1 : seen but not done.
  • 2 : done.

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_typem_source
Events & m_events

Detailed Description

template<class Graph, class Events = scan_events<Graph>>
class claw::breadth_scan< Graph, 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.


Member Typedef Documentation

template<class Graph , class Events = scan_events<Graph>>
typedef std::map<vertex_type, int, typename Graph::vertex_compare> claw::breadth_scan< Graph, Events >::coloration

Colors are :

  • 0 : never seen.
  • 1 : seen but not done.
  • 2 : done.

Definition at line 84 of file graph_algorithm.hpp.

template<class Graph , class Events = scan_events<Graph>>
typedef Graph::vertex_iterator claw::breadth_scan< Graph, Events >::vertex_iterator

Definition at line 76 of file graph_algorithm.hpp.

template<class Graph , class Events = scan_events<Graph>>
typedef Graph::vertex_type claw::breadth_scan< Graph, Events >::vertex_type

Definition at line 75 of file graph_algorithm.hpp.


Constructor & Destructor Documentation

template<class Graph , class Events >
claw::breadth_scan< Graph, Events >::breadth_scan ( const Graph &  g,
const vertex_type source,
Events &  events 
) [inline]

Constructor.

Parameters:
g Graph to scan.
source Start_Vertexing vertex.
events User's processings.

Definition at line 41 of file graph_algorithm.tpp.

00044   : m_g(g), m_source(source), m_events(events)
00045 {
00046 
00047 } // breadth_scan::breadth_scan() [constructor]


Member Function Documentation

template<class Graph , class Events >
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()


Member Data Documentation

template<class Graph , class Events = scan_events<Graph>>
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()().

template<class Graph , class Events = scan_events<Graph>>
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()().

template<class Graph , class Events = scan_events<Graph>>
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()().


The documentation for this class was generated from the following files:

Generated on 9 Nov 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.6.1