Claw  1.7.0
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 namespace claw
43 {
44 
50  public std::exception
51  {
52  public:
53  graph_exception() throw();
54  graph_exception( const std::string& s) throw();
55  virtual ~graph_exception() throw();
56 
57  virtual const char* what() const throw();
58 
59  private:
61  const std::string m_msg;
62 
63  }; // graph_exception
64 
76  template <class S, class A = meta::no_type, class Comp = std::less<S> >
77  class graph
78  {
79  public:
81  typedef S vertex_type;
82 
84  typedef A edge_type;
85 
87  typedef Comp vertex_compare;
88 
92  typedef std::map<vertex_type, edge_type, vertex_compare> neighbours_list;
93 
95  typedef std::map<vertex_type, neighbours_list, vertex_compare>
97 
100 
105  {
106  friend class graph<vertex_type, edge_type, vertex_compare>;
107 
108  public:
109  typedef const vertex_type value_type;
110  typedef const vertex_type& reference;
111  typedef const vertex_type* const pointer;
112  typedef ptrdiff_t difference_type;
113 
114  typedef std::bidirectional_iterator_tag iterator_category;
115 
116  public:
118 
123  reference operator*() const;
124  pointer operator->() const;
125  bool operator==(const graph_vertex_iterator& it) const;
126  bool operator!=(const graph_vertex_iterator& it) const;
127 
128  private:
129  explicit
130  graph_vertex_iterator( typename graph_content::const_iterator it );
131 
132  private:
134  typename graph_content::const_iterator m_iterator;
135 
136  }; // class graph_vertex_iterator
137 
138 
143  {
144  friend class graph<vertex_type, edge_type, vertex_compare>;
145 
146  public:
147 
151  class edge
152  {
153  friend class graph_edge_iterator;
154 
155  public:
156  edge();
157  const edge_type& label() const;
158  const vertex_type& source() const;
159  const vertex_type& target() const;
160 
161  private:
162  void set( const edge_type& l, const vertex_type& s,
163  const vertex_type& t );
164 
165  private:
166  edge_type const* m_label;
167  vertex_type const* m_source;
168  vertex_type const* m_target;
169  }; // class edge
170 
171  public:
172  typedef const edge value_type;
173  typedef const edge& reference;
174  typedef const edge* const pointer;
175  typedef ptrdiff_t difference_type;
176 
177  typedef std::bidirectional_iterator_tag iterator_category;
178 
179  public:
181 
186  reference operator*() const;
187  pointer operator->() const;
188  bool operator==(const graph_edge_iterator& it) const;
189  bool operator!=(const graph_edge_iterator& it) const;
190 
191  private:
192  explicit
193  graph_edge_iterator( typename graph_content::const_iterator it_begin,
194  typename graph_content::const_iterator it_end,
195  typename graph_content::const_iterator it_s,
196  typename neighbours_list::const_iterator it_d );
197 
198  private:
200  typename graph_content::const_iterator m_vertex_begin;
201 
203  typename graph_content::const_iterator m_vertex_end;
204 
206  typename graph_content::const_iterator m_vertex_iterator;
207 
209  typename neighbours_list::const_iterator m_neighbours_iterator;
210 
212  edge m_edge;
213  }; // class graph_edge_iterator
214 
215 
216 
217  public:
220  typedef std::reverse_iterator<vertex_iterator> reverse_vertex_iterator;
221  typedef std::reverse_iterator<edge_iterator> reverse_edge_iterator;
222 
223  public:
224  graph();
225 
226  void add_edge( const vertex_type& s1, const vertex_type& s2,
227  const edge_type& e = edge_type() );
228  void add_vertex( const vertex_type& s );
229 
230  bool edge_exists( const vertex_type& s, const vertex_type& r ) const;
231  void neighbours( const vertex_type& s, std::vector<vertex_type>& v ) const;
232  void vertices( std::vector<vertex_type>& v ) const;
233 
235  vertex_iterator vertex_end() const;
236  vertex_iterator vertex_begin( const vertex_type& s ) const;
237 
238  reverse_vertex_iterator vertex_rbegin() const;
239  reverse_vertex_iterator vertex_rend() const;
240  reverse_vertex_iterator vertex_rbegin( const vertex_type& s ) const;
241 
242  edge_iterator edge_begin() const;
243  edge_iterator edge_end() const;
245  const vertex_type& s2 ) const;
246 
247  reverse_edge_iterator edge_rbegin() const;
248  reverse_edge_iterator edge_rend() const;
249  reverse_edge_iterator edge_rbegin( const vertex_type& s1,
250  const vertex_type& s2 ) const;
251 
252  const edge_type& label( const vertex_type& s, const vertex_type& r ) const;
253 
254  std::size_t outer_degree( const vertex_type& s ) const;
255  std::size_t inner_degree( const vertex_type& s ) const;
256  std::size_t vertices_count() const;
257  std::size_t edges_count() const;
258 
259  private:
261  graph_content m_edges;
262 
264  std::map<vertex_type, std::size_t, vertex_compare> m_inner_degrees;
265 
267  std::size_t m_edges_count;
268 
269  }; // class graph
270 
271 } // namespace claw
272 
273 #include <claw/impl/graph.tpp>
274 
275 #endif // __CLAW_GRAPH_HPP__