Public Types | Public Member Functions | Private Member Functions | Private Attributes

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 
)

Constructor.

Parameters:
gGraph to scan.
eventsUser'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.

{
  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.

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

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.

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.


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