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 <map>
00034 #include <vector>
00035 #include <queue>
00036 #include <exception>
00037 #include <iterator>
00038 #include <utility>
00039
00040 namespace claw
00041 {
00042
00043
00044
00045
00050 class graph_exception : 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
00065
00076 template <class S, class A, class Comp = std::less<S> > class graph
00077 {
00078 public:
00080 typedef S vertex_type;
00081
00083 typedef A edge_type;
00084
00086 typedef Comp vertex_compare;
00087
00091 typedef std::map<vertex_type, edge_type, vertex_compare> neighbours_list;
00092
00094 typedef std::map<vertex_type, neighbours_list, vertex_compare>
00095 graph_content;
00096
00098 typedef claw::graph<vertex_type, edge_type, vertex_compare> self_type;
00099
00100
00101
00102
00103
00104
00105
00106
00110 class graph_vertex_iterator
00111 {
00112 friend class graph<vertex_type, edge_type, vertex_compare>;
00113
00114 public:
00115 typedef const vertex_type value_type;
00116 typedef const vertex_type& reference;
00117 typedef const vertex_type* const pointer;
00118 typedef ptrdiff_t difference_type;
00119
00120 typedef std::bidirectional_iterator_tag iterator_category;
00121
00122 public:
00123 graph_vertex_iterator();
00124
00125 graph_vertex_iterator& operator++();
00126 graph_vertex_iterator operator++(int);
00127 graph_vertex_iterator& operator--();
00128 graph_vertex_iterator operator--(int);
00129 reference operator*() const;
00130 pointer operator->() const;
00131 bool operator==(const graph_vertex_iterator& it) const;
00132 bool operator!=(const graph_vertex_iterator& it) const;
00133
00134 private:
00135 explicit
00136 graph_vertex_iterator( typename graph_content::const_iterator it );
00137
00138 private:
00140 typename graph_content::const_iterator m_iterator;
00141 };
00142
00143
00144
00145
00149 class graph_edge_iterator
00150 {
00151 friend class graph<vertex_type, edge_type, vertex_compare>;
00152
00153
00154 public:
00155
00159 class edge
00160 {
00161 friend class graph_edge_iterator;
00162
00163 public:
00164 edge();
00165 const edge_type& label() const;
00166 const vertex_type& source() const;
00167 const vertex_type& target() const;
00168
00169 private:
00170 void set( const edge_type& l, const vertex_type& s,
00171 const vertex_type& t );
00172
00173 private:
00174 edge_type const* m_label;
00175 vertex_type const* m_source;
00176 vertex_type const* m_target;
00177 };
00178
00179
00180 public:
00181 typedef const edge value_type;
00182 typedef const edge& reference;
00183 typedef const edge* const pointer;
00184 typedef ptrdiff_t difference_type;
00185
00186 typedef std::bidirectional_iterator_tag iterator_category;
00187
00188 public:
00189 graph_edge_iterator();
00190
00191 graph_edge_iterator& operator++();
00192 graph_edge_iterator operator++(int);
00193 graph_edge_iterator& operator--();
00194 graph_edge_iterator operator--(int);
00195 reference operator*() const;
00196 pointer operator->() const;
00197 bool operator==(const graph_edge_iterator& it) const;
00198 bool operator!=(const graph_edge_iterator& it) const;
00199
00200 private:
00201 explicit
00202 graph_edge_iterator( typename graph_content::const_iterator it_begin,
00203 typename graph_content::const_iterator it_end,
00204 typename graph_content::const_iterator it_s,
00205 typename neighbours_list::const_iterator it_d );
00206
00207 private:
00209 typename graph_content::const_iterator m_vertex_begin;
00210
00212 typename graph_content::const_iterator m_vertex_end;
00213
00215 typename graph_content::const_iterator m_vertex_iterator;
00216
00218 typename neighbours_list::const_iterator m_neighbours_iterator;
00219
00221 edge m_edge;
00222 };
00223
00224
00225
00226 public:
00227 typedef graph_vertex_iterator vertex_iterator;
00228 typedef graph_edge_iterator edge_iterator;
00229 typedef std::reverse_iterator<vertex_iterator> reverse_vertex_iterator;
00230 typedef std::reverse_iterator<edge_iterator> reverse_edge_iterator;
00231
00232 public:
00233
00234
00235 graph();
00236
00237 void add_edge( const vertex_type& s1, const vertex_type& s2,
00238 const edge_type& e );
00239 void add_vertex( const vertex_type& s );
00240
00241 bool edge_exists( const vertex_type& s, const vertex_type& r ) const;
00242 void neighbours( const vertex_type& s, std::vector<vertex_type>& v ) const;
00243 void vertices( std::vector<vertex_type>& v ) const;
00244
00245 vertex_iterator vertex_begin() const;
00246 vertex_iterator vertex_end() const;
00247 vertex_iterator vertex_begin( const vertex_type& s ) const;
00248
00249 reverse_vertex_iterator vertex_rbegin() const;
00250 reverse_vertex_iterator vertex_rend() const;
00251 reverse_vertex_iterator vertex_rbegin( const vertex_type& s ) const;
00252
00253 edge_iterator edge_begin() const;
00254 edge_iterator edge_end() const;
00255 edge_iterator edge_begin( const vertex_type& s1,
00256 const vertex_type& s2 ) const;
00257
00258 reverse_edge_iterator edge_rbegin() const;
00259 reverse_edge_iterator edge_rend() const;
00260 reverse_edge_iterator edge_rbegin( const vertex_type& s1,
00261 const vertex_type& s2 ) const;
00262
00263 const edge_type& label( const vertex_type& s, const vertex_type& r ) const;
00264
00265 unsigned int outer_degree( const vertex_type& s ) const;
00266 unsigned int inner_degree( const vertex_type& s ) const;
00267 unsigned int vertices_count() const;
00268 unsigned int edges_count() const;
00269
00270 private:
00272 graph_content m_edges;
00273
00275 std::map<vertex_type, unsigned int, vertex_compare> m_inner_degrees;
00276
00278 unsigned int m_edges_count;
00279 };
00280
00281 }
00282
00283 #include <claw/impl/graph.tpp>
00284
00285 #endif // __CLAW_GRAPH_HPP__