claw  1.9.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@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 
45 namespace 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 
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:
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 
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:
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:
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__
Iterator on the graph&#39;s edges.
Definition: graph.hpp:130
S vertex_type
Type of the vertices.
Definition: graph.hpp:70
A edge_type
Type of the edges.
Definition: graph.hpp:73
Value pointed by the iterator.
Definition: graph.hpp:138
A simple class to use as exception with string message.
Definition: exception.hpp:42
claw::exception graph_exception
The exceptions thrown by the graphs.
Definition: graph.hpp:52
Comp vertex_compare
Binary predicate to compare vertices.
Definition: graph.hpp:76
Iterator on the graph&#39;s vertices.
Definition: graph.hpp:93
std::map< vertex_type, neighbours_list, vertex_compare > graph_content
The whole graph: an adjacency list for each vertex.
Definition: graph.hpp:85
An empty class not considered as a effective type.
A simple class to use as exception with string message.
claw::graph< vertex_type, edge_type, vertex_compare > self_type
Type of the current structure.
Definition: graph.hpp:88
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
A class to represent a graph.
Definition: graph.hpp:66
This is the main namespace.
Definition: application.hpp:49