claw 1.9.0
 
Loading...
Searching...
No Matches
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@stuff-o-matic.com
24*/
30#ifndef __CLAW_GRAPH_HPP__
31#define __CLAW_GRAPH_HPP__
32
33#include <claw/exception.hpp>
34#include <claw/meta/no_type.hpp>
35
36#include <exception>
37#include <iterator>
38#include <map>
39#include <queue>
40#include <utility>
41#include <vector>
42
43#include <cstddef>
44
45namespace claw
46{
47
53
65 template <class S, class A = meta::no_type, class Comp = std::less<S> >
66 class graph
67 {
68 public:
70 typedef S vertex_type;
71
73 typedef A edge_type;
74
76 typedef Comp vertex_compare;
77
81 typedef std::map<vertex_type, edge_type, vertex_compare> neighbours_list;
82
84 typedef std::map<vertex_type, neighbours_list, vertex_compare>
86
89
93 class graph_vertex_iterator
94 {
95 friend class graph<vertex_type, edge_type, vertex_compare>;
96
97 public:
98 typedef const vertex_type value_type;
99 typedef const vertex_type& reference;
100 typedef const vertex_type* const pointer;
101 typedef ptrdiff_t difference_type;
102
103 typedef std::bidirectional_iterator_tag iterator_category;
104
105 public:
106 graph_vertex_iterator();
107
108 graph_vertex_iterator& operator++();
109 graph_vertex_iterator operator++(int);
110 graph_vertex_iterator& operator--();
111 graph_vertex_iterator operator--(int);
112 reference operator*() const;
113 pointer operator->() const;
114 bool operator==(const graph_vertex_iterator& it) const;
115 bool operator!=(const graph_vertex_iterator& it) const;
116
117 private:
118 explicit graph_vertex_iterator(
119 typename graph_content::const_iterator it);
120
121 private:
123 typename graph_content::const_iterator m_iterator;
124
125 }; // class graph_vertex_iterator
126
130 class graph_edge_iterator
131 {
132 friend class graph<vertex_type, edge_type, vertex_compare>;
133
134 public:
138 class edge
139 {
140 friend class graph_edge_iterator;
141
142 public:
143 edge();
144 const edge_type& label() const;
145 const vertex_type& source() const;
146 const vertex_type& target() const;
147
148 private:
149 void set(const edge_type& l, const vertex_type& s,
150 const vertex_type& t);
151
152 private:
153 edge_type const* m_label;
154 vertex_type const* m_source;
155 vertex_type const* m_target;
156 }; // class edge
157
158 public:
159 typedef const edge value_type;
160 typedef const edge& reference;
161 typedef const edge* const pointer;
162 typedef ptrdiff_t difference_type;
163
164 typedef std::bidirectional_iterator_tag iterator_category;
165
166 public:
167 graph_edge_iterator();
168
169 graph_edge_iterator& operator++();
170 graph_edge_iterator operator++(int);
171 graph_edge_iterator& operator--();
172 graph_edge_iterator operator--(int);
173 reference operator*() const;
174 pointer operator->() const;
175 bool operator==(const graph_edge_iterator& it) const;
176 bool operator!=(const graph_edge_iterator& it) const;
177
178 private:
179 explicit graph_edge_iterator(
180 typename graph_content::const_iterator it_begin,
181 typename graph_content::const_iterator it_end,
182 typename graph_content::const_iterator it_s,
183 typename neighbours_list::const_iterator it_d);
184
185 private:
187 typename graph_content::const_iterator m_vertex_begin;
188
190 typename graph_content::const_iterator m_vertex_end;
191
193 typename graph_content::const_iterator m_vertex_iterator;
194
196 typename neighbours_list::const_iterator m_neighbours_iterator;
197
199 edge m_edge;
200 }; // class graph_edge_iterator
201
202 public:
203 typedef graph_vertex_iterator vertex_iterator;
204 typedef graph_edge_iterator edge_iterator;
205 typedef std::reverse_iterator<vertex_iterator> reverse_vertex_iterator;
206 typedef std::reverse_iterator<edge_iterator> reverse_edge_iterator;
207
208 public:
209 graph();
210
211 void add_edge(const vertex_type& s1, const vertex_type& s2,
212 const edge_type& e = edge_type());
213 void add_vertex(const vertex_type& s);
214
215 bool edge_exists(const vertex_type& s, const vertex_type& r) const;
216 void neighbours(const vertex_type& s, std::vector<vertex_type>& v) const;
217 void vertices(std::vector<vertex_type>& v) const;
218
219 vertex_iterator vertex_begin() const;
220 vertex_iterator vertex_end() const;
221 vertex_iterator vertex_begin(const vertex_type& s) const;
222
223 reverse_vertex_iterator vertex_rbegin() const;
224 reverse_vertex_iterator vertex_rend() const;
225 reverse_vertex_iterator vertex_rbegin(const vertex_type& s) const;
226
227 edge_iterator edge_begin() const;
228 edge_iterator edge_end() const;
229 edge_iterator edge_begin(const vertex_type& s1,
230 const vertex_type& s2) const;
231
232 reverse_edge_iterator edge_rbegin() const;
233 reverse_edge_iterator edge_rend() const;
234 reverse_edge_iterator edge_rbegin(const vertex_type& s1,
235 const vertex_type& s2) const;
236
237 const edge_type& label(const vertex_type& s, const vertex_type& r) const;
238
239 std::size_t outer_degree(const vertex_type& s) const;
240 std::size_t inner_degree(const vertex_type& s) const;
241 std::size_t vertices_count() const;
242 std::size_t edges_count() const;
243
244 private:
246 graph_content m_edges;
247
249 std::map<vertex_type, std::size_t, vertex_compare> m_inner_degrees;
250
252 std::size_t m_edges_count;
253
254 }; // class graph
255
256}
257
258#include <claw/graph.tpp>
259
260#endif // __CLAW_GRAPH_HPP__
A simple class to use as exception with string message.
Definition exception.hpp:43
Value pointed by the iterator.
Definition graph.hpp:139
Iterator on the graph's edges.
Definition graph.hpp:131
Iterator on the graph's vertices.
Definition graph.hpp:94
A class to represent a graph.
Definition graph.hpp:67
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:81
std::map< vertex_type, neighbours_list, vertex_compare > graph_content
The whole graph: an adjacency list for each vertex.
Definition graph.hpp:85
S vertex_type
Type of the vertices.
Definition graph.hpp:70
claw::graph< vertex_type, edge_type, vertex_compare > self_type
Type of the current structure.
Definition graph.hpp:88
Comp vertex_compare
Binary predicate to compare vertices.
Definition graph.hpp:76
A edge_type
Type of the edges.
Definition graph.hpp:73
A simple class to use as exception with string message.
This is the main namespace.
claw::exception graph_exception
The exceptions thrown by the graphs.
Definition graph.hpp:52
An empty class not considered as a effective type.