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 
44 namespace 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  {
108  friend class graph<vertex_type, edge_type, vertex_compare>;
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 
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  {
146  friend class graph<vertex_type, edge_type, vertex_compare>;
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 
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 
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;
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__
virtual ~graph_exception()
Destructor.
Definition: graph.tpp:60
bool operator==(const graph_vertex_iterator &it) const
Equality.
Definition: graph.tpp:173
pointer operator->() const
Pointer.
Definition: graph.tpp:407
Iterator on the graph's edges.
Definition: graph.hpp:144
S vertex_type
Type of the vertices.
Definition: graph.hpp:83
void vertices(std::vector< vertex_type > &v) const
Get all the vertices.
Definition: graph.tpp:580
graph()
Constructor.
Definition: graph.tpp:484
const edge_type & label() const
Gets edge's label.
Definition: graph.tpp:224
reverse_vertex_iterator vertex_rend() const
Get a reverse node iterator past the last node.
Definition: graph.tpp:642
A edge_type
Type of the edges.
Definition: graph.hpp:86
Implementation of the claw::graph class.
Value pointed by the iterator.
Definition: graph.hpp:153
void add_vertex(const vertex_type &s)
Add a vertex.
Definition: graph.tpp:522
reverse_edge_iterator edge_rend() const
Get a reverse edge iterator after the last edge.
Definition: graph.tpp:743
edge_iterator edge_begin() const
Get an edge iterator on the first edge.
Definition: graph.tpp:671
reference operator*() const
Reference.
Definition: graph.tpp:395
Comp vertex_compare
Binary predicate to compare vertices.
Definition: graph.hpp:89
bool edge_exists(const vertex_type &s, const vertex_type &r) const
Check if there is an edge linking to vertices.
Definition: graph.tpp:543
Iterator on the graph's vertices.
Definition: graph.hpp:106
std::size_t inner_degree(const vertex_type &s) const
Get the inner degree of a vertex.
Definition: graph.tpp:816
std::size_t edges_count() const
Get the number of edges.
Definition: graph.tpp:843
graph_vertex_iterator & operator++()
Preincrement.
Definition: graph.tpp:94
graph_vertex_iterator & operator--()
Predecrement.
Definition: graph.tpp:121
std::size_t vertices_count() const
Get the number of vertices.
Definition: graph.tpp:833
std::size_t outer_degree(const vertex_type &s) const
Get the outter degree of a vertex.
Definition: graph.tpp:800
const vertex_type & target() const
Gets edge's target.
Definition: graph.tpp:248
graph_edge_iterator & operator++()
Preincrement.
Definition: graph.tpp:287
void neighbours(const vertex_type &s, std::vector< vertex_type > &v) const
Get the neighbors of a vertex.
Definition: graph.tpp:561
bool operator==(const graph_edge_iterator &it) const
Equality.
Definition: graph.tpp:420
edge_iterator edge_end() const
Get an edge iterator after the last edge.
Definition: graph.tpp:697
std::map< vertex_type, neighbours_list, vertex_compare > graph_content
The whole graph: an adjacency list for each vertex.
Definition: graph.hpp:98
reverse_vertex_iterator vertex_rbegin() const
Get a reverse node iterator on the first node.
Definition: graph.tpp:631
reverse_edge_iterator edge_rbegin() const
Get a reverse edge iterator on the first edge.
Definition: graph.tpp:732
pointer operator->() const
Reference.
Definition: graph.tpp:160
bool operator!=(const graph_edge_iterator &it) const
Difference.
Definition: graph.tpp:449
An empty class not considered as a effective type.
bool operator!=(const graph_vertex_iterator &it) const
Difference.
Definition: graph.tpp:186
claw::graph< vertex_type, edge_type, vertex_compare > self_type
Type of the current structure.
Definition: graph.hpp:101
The exceptions thrown by the graphs.
Definition: graph.hpp:51
graph_edge_iterator & operator--()
Predecrement.
Definition: graph.tpp:337
graph_vertex_iterator()
Constructor of the graph_vertex_iterator class.
Definition: graph.tpp:82
const edge_type & label(const vertex_type &s, const vertex_type &r) const
Get the label of an edge.
Definition: graph.tpp:775
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
A class to represent a graph.
Definition: graph.hpp:79
vertex_iterator vertex_begin() const
Get a node iterator on the first node.
Definition: graph.tpp:596
const vertex_type & source() const
Gets edge's source.
Definition: graph.tpp:236
graph_exception()
Default constructor.
Definition: graph.tpp:39
vertex_iterator vertex_end() const
Get a node iterator past the last node.
Definition: graph.tpp:607
graph_edge_iterator()
Constructor of the graph_edge_iterator class.
Definition: graph.tpp:275
virtual const char * what() const
Get an explanation of the problem.
Definition: graph.tpp:69
void add_edge(const vertex_type &s1, const vertex_type &s2, const edge_type &e=edge_type())
Add an edge in the graph.
Definition: graph.tpp:499
reference operator*() const
Dereference.
Definition: graph.tpp:148