Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00030 #ifndef __CLAW_GRAPH_HPP__
00031 #define __CLAW_GRAPH_HPP__
00032
00033 #include <claw/meta.hpp>
00034
00035 #include <map>
00036 #include <vector>
00037 #include <queue>
00038 #include <exception>
00039 #include <iterator>
00040 #include <utility>
00041 #include <cstddef>
00042
00043 namespace claw
00044 {
00045
00050 class graph_exception:
00051 public std::exception
00052 {
00053 public:
00054 graph_exception() throw();
00055 graph_exception( const std::string& s) throw();
00056 virtual ~graph_exception() throw();
00057
00058 virtual const char* what() const throw();
00059
00060 private:
00062 const std::string m_msg;
00063
00064 };
00065
00077 template <class S, class A = meta::no_type, class Comp = std::less<S> >
00078 class graph
00079 {
00080 public:
00082 typedef S vertex_type;
00083
00085 typedef A edge_type;
00086
00088 typedef Comp vertex_compare;
00089
00093 typedef std::map<vertex_type, edge_type, vertex_compare> neighbours_list;
00094
00096 typedef std::map<vertex_type, neighbours_list, vertex_compare>
00097 graph_content;
00098
00100 typedef claw::graph<vertex_type, edge_type, vertex_compare> self_type;
00101
00105 class graph_vertex_iterator
00106 {
00107 friend class graph<vertex_type, edge_type, vertex_compare>;
00108
00109 public:
00110 typedef const vertex_type value_type;
00111 typedef const vertex_type& reference;
00112 typedef const vertex_type* const pointer;
00113 typedef ptrdiff_t difference_type;
00114
00115 typedef std::bidirectional_iterator_tag iterator_category;
00116
00117 public:
00118 graph_vertex_iterator();
00119
00120 graph_vertex_iterator& operator++();
00121 graph_vertex_iterator operator++(int);
00122 graph_vertex_iterator& operator--();
00123 graph_vertex_iterator operator--(int);
00124 reference operator*() const;
00125 pointer operator->() const;
00126 bool operator==(const graph_vertex_iterator& it) const;
00127 bool operator!=(const graph_vertex_iterator& it) const;
00128
00129 private:
00130 explicit
00131 graph_vertex_iterator( typename graph_content::const_iterator it );
00132
00133 private:
00135 typename graph_content::const_iterator m_iterator;
00136
00137 };
00138
00139
00143 class graph_edge_iterator
00144 {
00145 friend class graph<vertex_type, edge_type, vertex_compare>;
00146
00147 public:
00148
00152 class edge
00153 {
00154 friend class graph_edge_iterator;
00155
00156 public:
00157 edge();
00158 const edge_type& label() const;
00159 const vertex_type& source() const;
00160 const vertex_type& target() const;
00161
00162 private:
00163 void set( const edge_type& l, const vertex_type& s,
00164 const vertex_type& t );
00165
00166 private:
00167 edge_type const* m_label;
00168 vertex_type const* m_source;
00169 vertex_type const* m_target;
00170 };
00171
00172 public:
00173 typedef const edge value_type;
00174 typedef const edge& reference;
00175 typedef const edge* const pointer;
00176 typedef ptrdiff_t difference_type;
00177
00178 typedef std::bidirectional_iterator_tag iterator_category;
00179
00180 public:
00181 graph_edge_iterator();
00182
00183 graph_edge_iterator& operator++();
00184 graph_edge_iterator operator++(int);
00185 graph_edge_iterator& operator--();
00186 graph_edge_iterator operator--(int);
00187 reference operator*() const;
00188 pointer operator->() const;
00189 bool operator==(const graph_edge_iterator& it) const;
00190 bool operator!=(const graph_edge_iterator& it) const;
00191
00192 private:
00193 explicit
00194 graph_edge_iterator( typename graph_content::const_iterator it_begin,
00195 typename graph_content::const_iterator it_end,
00196 typename graph_content::const_iterator it_s,
00197 typename neighbours_list::const_iterator it_d );
00198
00199 private:
00201 typename graph_content::const_iterator m_vertex_begin;
00202
00204 typename graph_content::const_iterator m_vertex_end;
00205
00207 typename graph_content::const_iterator m_vertex_iterator;
00208
00210 typename neighbours_list::const_iterator m_neighbours_iterator;
00211
00213 edge m_edge;
00214 };
00215
00216
00217
00218 public:
00219 typedef graph_vertex_iterator vertex_iterator;
00220 typedef graph_edge_iterator edge_iterator;
00221 typedef std::reverse_iterator<vertex_iterator> reverse_vertex_iterator;
00222 typedef std::reverse_iterator<edge_iterator> reverse_edge_iterator;
00223
00224 public:
00225 graph();
00226
00227 void add_edge( const vertex_type& s1, const vertex_type& s2,
00228 const edge_type& e = edge_type() );
00229 void add_vertex( const vertex_type& s );
00230
00231 bool edge_exists( const vertex_type& s, const vertex_type& r ) const;
00232 void neighbours( const vertex_type& s, std::vector<vertex_type>& v ) const;
00233 void vertices( std::vector<vertex_type>& v ) const;
00234
00235 vertex_iterator vertex_begin() const;
00236 vertex_iterator vertex_end() const;
00237 vertex_iterator vertex_begin( const vertex_type& s ) const;
00238
00239 reverse_vertex_iterator vertex_rbegin() const;
00240 reverse_vertex_iterator vertex_rend() const;
00241 reverse_vertex_iterator vertex_rbegin( const vertex_type& s ) const;
00242
00243 edge_iterator edge_begin() const;
00244 edge_iterator edge_end() const;
00245 edge_iterator edge_begin( const vertex_type& s1,
00246 const vertex_type& s2 ) const;
00247
00248 reverse_edge_iterator edge_rbegin() const;
00249 reverse_edge_iterator edge_rend() const;
00250 reverse_edge_iterator edge_rbegin( const vertex_type& s1,
00251 const vertex_type& s2 ) const;
00252
00253 const edge_type& label( const vertex_type& s, const vertex_type& r ) const;
00254
00255 std::size_t outer_degree( const vertex_type& s ) const;
00256 std::size_t inner_degree( const vertex_type& s ) const;
00257 std::size_t vertices_count() const;
00258 std::size_t edges_count() const;
00259
00260 private:
00262 graph_content m_edges;
00263
00265 std::map<vertex_type, std::size_t, vertex_compare> m_inner_degrees;
00266
00268 std::size_t m_edges_count;
00269
00270 };
00271
00272 }
00273
00274 #include <claw/impl/graph.tpp>
00275
00276 #endif // __CLAW_GRAPH_HPP__