Claw 1.7.3
graph_algorithm.hpp
Go to the documentation of this file.
1/*
2 CLAW - a C++ Library Absolutely Wonderful
3
4 CLAW is a free library without any particular aim but being useful to
5 anyone.
6
7 Copyright (C) 2005-2011 Julien Jorge
8
9 This library is free software; you can redistribute it and/or
10 modify it under the terms of the GNU Lesser General Public
11 License as published by the Free Software Foundation; either
12 version 2.1 of the License, or (at your option) any later version.
13
14 This library is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 Lesser General Public License for more details.
18
19 You should have received a copy of the GNU Lesser General Public
20 License along with this library; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22
23 contact: julien.jorge@gamned.org
24*/
30#ifndef __CLAW_GRAPH_ALGORITHM_HPP__
31#define __CLAW_GRAPH_ALGORITHM_HPP__
32
33#include <map>
34
35namespace claw
36{
37 //*************************** graph::scan_events ****************************
38
42 template<class Graph>
44 {
45 public:
46 typedef typename Graph::vertex_type vertex_type;
47
48 public:
49 void init( const Graph& g ) {}
50 void start_vertex( const vertex_type& v ) {}
51 void visit_edge( const vertex_type& v1, const vertex_type& v2 ) {}
52 void end_vertex( const vertex_type& v ) {}
53 }; // class scan_events
54
55
56
57
58
59
60
61 //************************** breadth_scan ***********************************
62
63
64
65
66
71 template<class Graph, class Events = scan_events<Graph> >
73 {
74 public:
75 typedef typename Graph::vertex_type vertex_type;
76 typedef typename Graph::vertex_iterator vertex_iterator ;
83 typedef std::map<vertex_type, int,
84 typename Graph::vertex_compare> coloration;
85
86 public:
87 breadth_scan( const Graph& g, const vertex_type& source,
88 Events& events );
89
90 void operator()();
91
92 private:
93 const Graph& m_g;
94 const vertex_type& m_source;
95 Events& m_events;
96 }; // class breadth_scan
97
98
99
100
101
102
103
104 //**************************** depth_scan ***********************************
105
106
107
108
109
110
115 template<class Graph, class Events = typename Graph::scan_events>
117 {
118 public:
119 typedef typename Graph::vertex_type vertex_type;
120 typedef typename Graph::vertex_iterator vertex_iterator ;
127 typedef std::map<vertex_type, int,
128 typename Graph::vertex_compare> coloration;
129
130 public:
131 depth_scan( const Graph& g, Events& events );
132
133 void operator()();
134
135 private:
136 void recursive_scan(const vertex_type& s, coloration& seen_vertices);
137
138 private:
139 const Graph& m_g;
140 Events& m_events;
141 }; // class depth_scan
142
143
144
145
146 //********************** topological_sort ***********************************
147
148
149
150
159 template<class Graph>
160 class topological_sort : public scan_events<Graph>
161 {
162 public:
163 typedef typename scan_events<Graph>::vertex_type vertex_type;
164 typedef std::vector<vertex_type> result_type;
165 typedef typename result_type::const_iterator const_iterator;
167
168 public:
169 void init( const Graph& g );
170 void end_vertex( const vertex_type& s );
171
172 void operator()( const Graph& g );
173 const vertex_type& operator[](unsigned int index) const;
174
175 const_iterator begin() const;
176 const_iterator end() const;
177
178 private:
180 result_type m_result;
182 int m_next_index;
183 }; // class topological_sort
184
185} // namespace claw
186
187#include <claw/impl/graph_algorithm.tpp>
188
189#endif // __CLAW_GRAPH_ALGORITHM_HPP__
This class performs a depth scan of a graph. Only reachables vertices from a given vertex are proceed...
std::map< vertex_type, int, typename Graph::vertex_compare > coloration
Colors are :
This class performs a depth scan of a graph. All nodes are proceeded.
std::map< vertex_type, int, typename Graph::vertex_compare > coloration
Colors are :
Different stages of graph scanning.
Pass this class as the "Envents" template parameter of the depth scan class to sort the vertices of a...
This is the main namespace.
Definition algorithm.hpp:34