00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00030 #ifndef __CLAW_GRAPH_ALGORITHM_HPP__
00031 #define __CLAW_GRAPH_ALGORITHM_HPP__
00032
00033 #include <map>
00034
00035 namespace claw
00036 {
00037
00038
00042 template<class Graph>
00043 class scan_events
00044 {
00045 public:
00046 typedef typename Graph::vertex_type vertex_type;
00047
00048 public:
00049 void init( const Graph& g ) {}
00050 void start_vertex( const vertex_type& v ) {}
00051 void visit_edge( const vertex_type& v1, const vertex_type& v2 ) {}
00052 void end_vertex( const vertex_type& v ) {}
00053 };
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00071 template<class Graph, class Events = scan_events<Graph> >
00072 class breadth_scan
00073 {
00074 public:
00075 typedef typename Graph::vertex_type vertex_type;
00076 typedef typename Graph::vertex_iterator vertex_iterator ;
00083 typedef std::map<vertex_type, int,
00084 typename Graph::vertex_compare> coloration;
00085
00086 public:
00087 breadth_scan( const Graph& g, const vertex_type& source,
00088 Events& events );
00089
00090 void operator()();
00091
00092 private:
00093 const Graph& m_g;
00094 const vertex_type& m_source;
00095 Events& m_events;
00096 };
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00115 template<class Graph, class Events = typename Graph::scan_events>
00116 class depth_scan
00117 {
00118 public:
00119 typedef typename Graph::vertex_type vertex_type;
00120 typedef typename Graph::vertex_iterator vertex_iterator ;
00127 typedef std::map<vertex_type, int,
00128 typename Graph::vertex_compare> coloration;
00129
00130 public:
00131 depth_scan( const Graph& g, Events& events );
00132
00133 void operator()();
00134
00135 private:
00136 void recursive_scan(const vertex_type& s, coloration& seen_vertices);
00137
00138 private:
00139 const Graph& m_g;
00140 Events& m_events;
00141 };
00142
00143
00144
00145
00146
00147
00148
00149
00150
00159 template<class Graph>
00160 class topological_sort : public scan_events<Graph>
00161 {
00162 public:
00163 typedef typename scan_events<Graph>::vertex_type vertex_type;
00164 typedef std::vector<vertex_type> result_type;
00165 typedef typename result_type::const_iterator const_iterator;
00166 typedef topological_sort<Graph> self_type;
00167
00168 public:
00169 void init( const Graph& g );
00170 void end_vertex( const vertex_type& s );
00171
00172 void operator()( const Graph& g );
00173 const vertex_type& operator[](unsigned int index) const;
00174
00175 const_iterator begin() const;
00176 const_iterator end() const;
00177
00178 private:
00180 result_type m_result;
00182 int m_next_index;
00183 };
00184
00185 }
00186
00187 #include <claw/impl/graph_algorithm.tpp>
00188
00189 #endif // __CLAW_GRAPH_ALGORITHM_HPP__