CLAW Library (a C++ Library Absolutely Wonderful) 1.5.5
Public Types | Public Member Functions | Private Attributes
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

Definition at line 213 of file graph_algorithm.tpp.

References claw::topological_sort< Graph >::begin().

Referenced by claw::topological_sort< Graph >::begin().

{
  return m_result.begin();
} // topological_sort::begin()
template<class Graph >
claw::topological_sort< Graph >::const_iterator claw::topological_sort< Graph >::end ( ) const

Definition at line 221 of file graph_algorithm.tpp.

References claw::topological_sort< Graph >::end().

Referenced by claw::topological_sort< Graph >::end().

{
  return m_result.end();
} // topological_sort::end()
template<class Graph >
void claw::topological_sort< Graph >::end_vertex ( const vertex_type s)

Reimplemented from claw::scan_events< Graph >.

Definition at line 188 of file graph_algorithm.tpp.

{
  m_result[m_next_index] = s;
  --m_next_index;
} // topological_sort::end()
template<class Graph>
void claw::topological_sort< Graph >::init ( const Graph &  g)

Initialize the scan.

Parameters:
gThe graph that will be scanned.

Reimplemented from claw::scan_events< Graph >.

Definition at line 179 of file graph_algorithm.tpp.

{
  m_result.resize( g.vertices_count() );
  m_next_index = (int)g.vertices_count()-1;
} // topological_sort::init()
template<class Graph>
void claw::topological_sort< Graph >::operator() ( const Graph &  g)

Definition at line 196 of file graph_algorithm.tpp.

{
  claw::depth_scan< Graph, self_type > scan( g, *this );
  scan();
} // topological_sort::operator()()
template<class Graph >
const claw::topological_sort< Graph >::vertex_type & claw::topological_sort< Graph >::operator[] ( unsigned int  index) const

Definition at line 205 of file graph_algorithm.tpp.

{
  return m_result[index];
} // 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.

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

The vector we're filling.

Definition at line 180 of file graph_algorithm.hpp.


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