Claw 1.7.3
graph.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_HPP__
31#define __CLAW_GRAPH_HPP__
32
33#include <claw/meta/no_type.hpp>
34
35#include <map>
36#include <vector>
37#include <queue>
38#include <exception>
39#include <iterator>
40#include <utility>
41
42#include <cstddef>
43
44namespace claw
45{
46
52 public std::exception
53 {
54 public:
55 graph_exception() throw();
56 graph_exception( const std::string& s) throw();
57 virtual ~graph_exception() throw();
58
59 virtual const char* what() const throw();
60
61 private:
63 const std::string m_msg;
64
65 }; // graph_exception
66
78 template <class S, class A = meta::no_type, class Comp = std::less<S> >
79 class graph
80 {
81 public:
83 typedef S vertex_type;
84
86 typedef A edge_type;
87
89 typedef Comp vertex_compare;
90
94 typedef std::map<vertex_type, edge_type, vertex_compare> neighbours_list;
95
97 typedef std::map<vertex_type, neighbours_list, vertex_compare>
99
102
107 {
109
110 public:
111 typedef const vertex_type value_type;
112 typedef const vertex_type& reference;
113 typedef const vertex_type* const pointer;
114 typedef ptrdiff_t difference_type;
115
116 typedef std::bidirectional_iterator_tag iterator_category;
117
118 public:
120
121 graph_vertex_iterator& operator++();
122 graph_vertex_iterator operator++(int);
123 graph_vertex_iterator& operator--();
124 graph_vertex_iterator operator--(int);
125 reference operator*() const;
126 pointer operator->() const;
127 bool operator==(const graph_vertex_iterator& it) const;
128 bool operator!=(const graph_vertex_iterator& it) const;
129
130 private:
131 explicit
132 graph_vertex_iterator( typename graph_content::const_iterator it );
133
134 private:
136 typename graph_content::const_iterator m_iterator;
137
138 }; // class graph_vertex_iterator
139
140
145 {
147
148 public:
149
153 class edge
154 {
155 friend class graph_edge_iterator;
156
157 public:
158 edge();
159 const edge_type& label() const;
160 const vertex_type& source() const;
161 const vertex_type& target() const;
162
163 private:
164 void set( const edge_type& l, const vertex_type& s,
165 const vertex_type& t );
166
167 private:
168 edge_type const* m_label;
169 vertex_type const* m_source;
170 vertex_type const* m_target;
171 }; // class edge
172
173 public:
174 typedef const edge value_type;
175 typedef const edge& reference;
176 typedef const edge* const pointer;
177 typedef ptrdiff_t difference_type;
178
179 typedef std::bidirectional_iterator_tag iterator_category;
180
181 public:
183
184 graph_edge_iterator& operator++();
185 graph_edge_iterator operator++(int);
186 graph_edge_iterator& operator--();
187 graph_edge_iterator operator--(int);
188 reference operator*() const;
189 pointer operator->() const;
190 bool operator==(const graph_edge_iterator& it) const;
191 bool operator!=(const graph_edge_iterator& it) const;
192
193 private:
194 explicit
195 graph_edge_iterator( typename graph_content::const_iterator it_begin,
196 typename graph_content::const_iterator it_end,
197 typename graph_content::const_iterator it_s,
198 typename neighbours_list::const_iterator it_d );
199
200 private:
202 typename graph_content::const_iterator m_vertex_begin;
203
205 typename graph_content::const_iterator m_vertex_end;
206
208 typename graph_content::const_iterator m_vertex_iterator;
209
211 typename neighbours_list::const_iterator m_neighbours_iterator;
212
214 edge m_edge;
215 }; // class graph_edge_iterator
216
217
218
219 public:
222 typedef std::reverse_iterator<vertex_iterator> reverse_vertex_iterator;
223 typedef std::reverse_iterator<edge_iterator> reverse_edge_iterator;
224
225 public:
226 graph();
227
228 void add_edge( const vertex_type& s1, const vertex_type& s2,
229 const edge_type& e = edge_type() );
230 void add_vertex( const vertex_type& s );
231
232 bool edge_exists( const vertex_type& s, const vertex_type& r ) const;
233 void neighbours( const vertex_type& s, std::vector<vertex_type>& v ) const;
234 void vertices( std::vector<vertex_type>& v ) const;
235
236 vertex_iterator vertex_begin() const;
237 vertex_iterator vertex_end() const;
238 vertex_iterator vertex_begin( const vertex_type& s ) const;
239
240 reverse_vertex_iterator vertex_rbegin() const;
241 reverse_vertex_iterator vertex_rend() const;
242 reverse_vertex_iterator vertex_rbegin( const vertex_type& s ) const;
243
244 edge_iterator edge_begin() const;
245 edge_iterator edge_end() const;
246 edge_iterator edge_begin( const vertex_type& s1,
247 const vertex_type& s2 ) const;
248
249 reverse_edge_iterator edge_rbegin() const;
250 reverse_edge_iterator edge_rend() const;
251 reverse_edge_iterator edge_rbegin( const vertex_type& s1,
252 const vertex_type& s2 ) const;
253
254 const edge_type& label( const vertex_type& s, const vertex_type& r ) const;
255
256 std::size_t outer_degree( const vertex_type& s ) const;
257 std::size_t inner_degree( const vertex_type& s ) const;
258 std::size_t vertices_count() const;
259 std::size_t edges_count() const;
260
261 private:
263 graph_content m_edges;
264
266 std::map<vertex_type, std::size_t, vertex_compare> m_inner_degrees;
267
269 std::size_t m_edges_count;
270
271 }; // class graph
272
273} // namespace claw
274
275#include <claw/impl/graph.tpp>
276
277#endif // __CLAW_GRAPH_HPP__
Value pointed by the iterator.
Definition graph.hpp:154
Iterator on the graph's edges.
Definition graph.hpp:145
Iterator on the graph's vertices.
Definition graph.hpp:107
The exceptions thrown by the graphs.
Definition graph.hpp:53
A class to represent a graph.
Definition graph.hpp:80
std::map< vertex_type, edge_type, vertex_compare > neighbours_list
The adjacency list of a vertex. vertex_type is the target vertex, edge_type is the label on the edge.
Definition graph.hpp:94
std::map< vertex_type, neighbours_list, vertex_compare > graph_content
The whole graph: an adjacency list for each vertex.
Definition graph.hpp:98
S vertex_type
Type of the vertices.
Definition graph.hpp:83
claw::graph< vertex_type, edge_type, vertex_compare > self_type
Type of the current structure.
Definition graph.hpp:101
Comp vertex_compare
Binary predicate to compare vertices.
Definition graph.hpp:89
A edge_type
Type of the edges.
Definition graph.hpp:86
This is the main namespace.
Definition algorithm.hpp:34
An empty class not considered as a effective type.