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
00042 namespace claw
00043 {
00044
00049 class graph_exception:
00050 public std::exception
00051 {
00052 public:
00053 graph_exception() throw();
00054 graph_exception( const std::string& s) throw();
00055 virtual ~graph_exception() throw();
00056
00057 virtual const char* what() const throw();
00058
00059 private:
00061 const std::string m_msg;
00062
00063 };
00064
00076 template <class S, class A = meta::no_type, class Comp = std::less<S> >
00077 class graph
00078 {
00079 public:
00081 typedef S vertex_type;
00082
00084 typedef A edge_type;
00085
00087 typedef Comp vertex_compare;
00088
00092 typedef std::map<vertex_type, edge_type, vertex_compare> neighbours_list;
00093
00095 typedef std::map<vertex_type, neighbours_list, vertex_compare>
00096 graph_content;
00097
00099 typedef claw::graph<vertex_type, edge_type, vertex_compare> self_type;
00100
00104 class graph_vertex_iterator
00105 {
00106 friend class graph<vertex_type, edge_type, vertex_compare>;
00107
00108 public:
00109 typedef const vertex_type value_type;
00110 typedef const vertex_type& reference;
00111 typedef const vertex_type* const pointer;
00112 typedef ptrdiff_t difference_type;
00113
00114 typedef std::bidirectional_iterator_tag iterator_category;
00115
00116 public:
00117 graph_vertex_iterator();
00118
00119 graph_vertex_iterator& operator++();
00120 graph_vertex_iterator operator++(int);
00121 graph_vertex_iterator& operator--();
00122 graph_vertex_iterator operator--(int);
00123 reference operator*() const;
00124 pointer operator->() const;
00125 bool operator==(const graph_vertex_iterator& it) const;
00126 bool operator!=(const graph_vertex_iterator& it) const;
00127
00128 private:
00129 explicit
00130 graph_vertex_iterator( typename graph_content::const_iterator it );
00131
00132 private:
00134 typename graph_content::const_iterator m_iterator;
00135
00136 };
00137
00138
00142 class graph_edge_iterator
00143 {
00144 friend class graph<vertex_type, edge_type, vertex_compare>;
00145
00146 public:
00147
00151 class edge
00152 {
00153 friend class graph_edge_iterator;
00154
00155 public:
00156 edge();
00157 const edge_type& label() const;
00158 const vertex_type& source() const;
00159 const vertex_type& target() const;
00160
00161 private:
00162 void set( const edge_type& l, const vertex_type& s,
00163 const vertex_type& t );
00164
00165 private:
00166 edge_type const* m_label;
00167 vertex_type const* m_source;
00168 vertex_type const* m_target;
00169 };
00170
00171 public:
00172 typedef const edge value_type;
00173 typedef const edge& reference;
00174 typedef const edge* const pointer;
00175 typedef ptrdiff_t difference_type;
00176
00177 typedef std::bidirectional_iterator_tag iterator_category;
00178
00179 public:
00180 graph_edge_iterator();
00181
00182 graph_edge_iterator& operator++();
00183 graph_edge_iterator operator++(int);
00184 graph_edge_iterator& operator--();
00185 graph_edge_iterator operator--(int);
00186 reference operator*() const;
00187 pointer operator->() const;
00188 bool operator==(const graph_edge_iterator& it) const;
00189 bool operator!=(const graph_edge_iterator& it) const;
00190
00191 private:
00192 explicit
00193 graph_edge_iterator( typename graph_content::const_iterator it_begin,
00194 typename graph_content::const_iterator it_end,
00195 typename graph_content::const_iterator it_s,
00196 typename neighbours_list::const_iterator it_d );
00197
00198 private:
00200 typename graph_content::const_iterator m_vertex_begin;
00201
00203 typename graph_content::const_iterator m_vertex_end;
00204
00206 typename graph_content::const_iterator m_vertex_iterator;
00207
00209 typename neighbours_list::const_iterator m_neighbours_iterator;
00210
00212 edge m_edge;
00213 };
00214
00215
00216
00217 public:
00218 typedef graph_vertex_iterator vertex_iterator;
00219 typedef graph_edge_iterator edge_iterator;
00220 typedef std::reverse_iterator<vertex_iterator> reverse_vertex_iterator;
00221 typedef std::reverse_iterator<edge_iterator> reverse_edge_iterator;
00222
00223 public:
00224 graph();
00225
00226 void add_edge( const vertex_type& s1, const vertex_type& s2,
00227 const edge_type& e = edge_type() );
00228 void add_vertex( const vertex_type& s );
00229
00230 bool edge_exists( const vertex_type& s, const vertex_type& r ) const;
00231 void neighbours( const vertex_type& s, std::vector<vertex_type>& v ) const;
00232 void vertices( std::vector<vertex_type>& v ) const;
00233
00234 vertex_iterator vertex_begin() const;
00235 vertex_iterator vertex_end() const;
00236 vertex_iterator vertex_begin( const vertex_type& s ) const;
00237
00238 reverse_vertex_iterator vertex_rbegin() const;
00239 reverse_vertex_iterator vertex_rend() const;
00240 reverse_vertex_iterator vertex_rbegin( const vertex_type& s ) const;
00241
00242 edge_iterator edge_begin() const;
00243 edge_iterator edge_end() const;
00244 edge_iterator edge_begin( const vertex_type& s1,
00245 const vertex_type& s2 ) const;
00246
00247 reverse_edge_iterator edge_rbegin() const;
00248 reverse_edge_iterator edge_rend() const;
00249 reverse_edge_iterator edge_rbegin( const vertex_type& s1,
00250 const vertex_type& s2 ) const;
00251
00252 const edge_type& label( const vertex_type& s, const vertex_type& r ) const;
00253
00254 std::size_t outer_degree( const vertex_type& s ) const;
00255 std::size_t inner_degree( const vertex_type& s ) const;
00256 std::size_t vertices_count() const;
00257 std::size_t edges_count() const;
00258
00259 private:
00261 graph_content m_edges;
00262
00264 std::map<vertex_type, std::size_t, vertex_compare> m_inner_degrees;
00265
00267 std::size_t m_edges_count;
00268
00269 };
00270
00271 }
00272
00273 #include <claw/impl/graph.tpp>
00274
00275 #endif // __CLAW_GRAPH_HPP__