claw::topological_sort< Graph > Class Template Reference

Pass this class as the "Envents" template parameter of the depth scan class to sort the vertices of a graph with the topological sort algorithm. More...

#include <graph_algorithm.hpp>

Inheritance diagram for claw::topological_sort< Graph >:
claw::scan_events< Graph >

List of all members.

Public Types

typedef scan_events< Graph >
::vertex_type 
vertex_type
typedef std::vector< vertex_typeresult_type
typedef result_type::const_iterator const_iterator
typedef topological_sort< Graph > self_type

Public Member Functions

void init (const Graph &g)
 Initialize the scan.
void end_vertex (const vertex_type &s)
void operator() (const Graph &g)
const vertex_typeoperator[] (unsigned int index) const
const_iterator begin () const
const_iterator end () const

Private Attributes

result_type m_result
 The vector we're filling.
int m_next_index
 Index of the next item to put in the vector.

Detailed Description

template<class Graph>
class claw::topological_sort< Graph >

Pass this class as the "Envents" template parameter of the depth scan class to sort the vertices of a graph with the topological sort algorithm.

When a node process ends, the node is added to a vector. The vector is filled from end to begining.

Definition at line 160 of file graph_algorithm.hpp.


Member Typedef Documentation

template<class Graph>
typedef result_type::const_iterator claw::topological_sort< Graph >::const_iterator

Definition at line 165 of file graph_algorithm.hpp.

template<class Graph>
typedef std::vector<vertex_type> claw::topological_sort< Graph >::result_type

Definition at line 164 of file graph_algorithm.hpp.

template<class Graph>
typedef topological_sort<Graph> claw::topological_sort< Graph >::self_type

Definition at line 166 of file graph_algorithm.hpp.

template<class Graph>
typedef scan_events<Graph>::vertex_type claw::topological_sort< Graph >::vertex_type

Reimplemented from claw::scan_events< Graph >.

Definition at line 163 of file graph_algorithm.hpp.


Member Function Documentation

template<class Graph >
claw::topological_sort< Graph >::const_iterator claw::topological_sort< Graph >::begin (  )  const [inline]

Definition at line 213 of file graph_algorithm.tpp.

References claw::topological_sort< Graph >::m_result.

00214 {
00215   return m_result.begin();
00216 } // topological_sort::begin()

template<class Graph >
claw::topological_sort< Graph >::const_iterator claw::topological_sort< Graph >::end (  )  const [inline]

Definition at line 221 of file graph_algorithm.tpp.

References claw::topological_sort< Graph >::m_result.

00222 {
00223   return m_result.end();
00224 } // topological_sort::end()

template<class Graph >
void claw::topological_sort< Graph >::end_vertex ( const vertex_type s  )  [inline]

Reimplemented from claw::scan_events< Graph >.

Definition at line 188 of file graph_algorithm.tpp.

References claw::topological_sort< Graph >::m_next_index, and claw::topological_sort< Graph >::m_result.

00189 {
00190   m_result[m_next_index] = s;
00191   --m_next_index;
00192 } // topological_sort::end()

template<class Graph>
void claw::topological_sort< Graph >::init ( const Graph &  g  )  [inline]

Initialize the scan.

Parameters:
g The graph that will be scanned.

Reimplemented from claw::scan_events< Graph >.

Definition at line 179 of file graph_algorithm.tpp.

References claw::topological_sort< Graph >::m_next_index, and claw::topological_sort< Graph >::m_result.

00180 {
00181   m_result.resize( g.vertices_count() );
00182   m_next_index = (int)g.vertices_count()-1;
00183 } // topological_sort::init()

template<class Graph>
void claw::topological_sort< Graph >::operator() ( const Graph &  g  )  [inline]

Definition at line 196 of file graph_algorithm.tpp.

00197 {
00198   claw::depth_scan< Graph, self_type > scan( g, *this );
00199   scan();
00200 } // topological_sort::operator()()

template<class Graph >
const claw::topological_sort< Graph >::vertex_type & claw::topological_sort< Graph >::operator[] ( unsigned int  index  )  const [inline]

Definition at line 205 of file graph_algorithm.tpp.

References claw::topological_sort< Graph >::m_result.

00206 {
00207   return m_result[index];
00208 } // topological_sort::operator[]()


Member Data Documentation

template<class Graph>
int claw::topological_sort< Graph >::m_next_index [private]

Index of the next item to put in the vector.

Definition at line 182 of file graph_algorithm.hpp.

Referenced by claw::topological_sort< Graph >::end_vertex(), and claw::topological_sort< Graph >::init().

template<class Graph>
result_type claw::topological_sort< Graph >::m_result [private]

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