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 : 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
	)

Constructor.

Parameters:

	g	Graph to scan.
	events	User's processings.

Definition at line 105 of file graph_algorithm.tpp.

  : m_g(g), m_events(events)
{

} // depth_scan::depth_scan() [constructor]

Member Function Documentation

template<class Graph , class Events >

void claw::depth_scan< Graph, Events >::operator() ( )

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().

{
  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()()

template<class Graph , class Events >

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.

Referenced by claw::depth_scan< Graph, Events >::operator()().

{
  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()