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

This class performs a depth scan of a graph. All nodes 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

 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

Detailed Description

template<class Graph, class Events = typename Graph::scan_events>
class claw::depth_scan< Graph, Events >

This class performs a depth scan of a graph. All nodes are proceeded.

Definition at line 116 of file graph_algorithm.hpp.


Member Typedef Documentation

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

Colors are :

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

Definition at line 128 of file graph_algorithm.hpp.

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

Definition at line 120 of file graph_algorithm.hpp.

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

Definition at line 119 of file graph_algorithm.hpp.


Constructor & Destructor Documentation

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

Constructor.

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

Definition at line 105 of file graph_algorithm.tpp.

00106   : m_g(g), m_events(events)
00107 {
00108 
00109 } // depth_scan::depth_scan() [constructor]


Member Function Documentation

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

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


Member Data Documentation

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

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


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