Claw
1.7.3
|
00001 /* 00002 CLAW - a C++ Library Absolutely Wonderful 00003 00004 CLAW is a free library without any particular aim but being useful to 00005 anyone. 00006 00007 Copyright (C) 2005-2011 Julien Jorge 00008 00009 This library is free software; you can redistribute it and/or 00010 modify it under the terms of the GNU Lesser General Public 00011 License as published by the Free Software Foundation; either 00012 version 2.1 of the License, or (at your option) any later version. 00013 00014 This library is distributed in the hope that it will be useful, 00015 but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00017 Lesser General Public License for more details. 00018 00019 You should have received a copy of the GNU Lesser General Public 00020 License along with this library; if not, write to the Free Software 00021 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00022 00023 contact: julien.jorge@gamned.org 00024 */ 00030 #ifndef __CLAW_GRAPH_HPP__ 00031 #define __CLAW_GRAPH_HPP__ 00032 00033 #include <claw/meta/no_type.hpp> 00034 00035 #include <map> 00036 #include <vector> 00037 #include <queue> 00038 #include <exception> 00039 #include <iterator> 00040 #include <utility> 00041 00042 #include <cstddef> 00043 00044 namespace claw 00045 { 00046 00051 class graph_exception: 00052 public std::exception 00053 { 00054 public: 00055 graph_exception() throw(); 00056 graph_exception( const std::string& s) throw(); 00057 virtual ~graph_exception() throw(); 00058 00059 virtual const char* what() const throw(); 00060 00061 private: 00063 const std::string m_msg; 00064 00065 }; // graph_exception 00066 00078 template <class S, class A = meta::no_type, class Comp = std::less<S> > 00079 class graph 00080 { 00081 public: 00083 typedef S vertex_type; 00084 00086 typedef A edge_type; 00087 00089 typedef Comp vertex_compare; 00090 00094 typedef std::map<vertex_type, edge_type, vertex_compare> neighbours_list; 00095 00097 typedef std::map<vertex_type, neighbours_list, vertex_compare> 00098 graph_content; 00099 00101 typedef claw::graph<vertex_type, edge_type, vertex_compare> self_type; 00102 00106 class graph_vertex_iterator 00107 { 00108 friend class graph<vertex_type, edge_type, vertex_compare>; 00109 00110 public: 00111 typedef const vertex_type value_type; 00112 typedef const vertex_type& reference; 00113 typedef const vertex_type* const pointer; 00114 typedef ptrdiff_t difference_type; 00115 00116 typedef std::bidirectional_iterator_tag iterator_category; 00117 00118 public: 00119 graph_vertex_iterator(); 00120 00121 graph_vertex_iterator& operator++(); 00122 graph_vertex_iterator operator++(int); 00123 graph_vertex_iterator& operator--(); 00124 graph_vertex_iterator operator--(int); 00125 reference operator*() const; 00126 pointer operator->() const; 00127 bool operator==(const graph_vertex_iterator& it) const; 00128 bool operator!=(const graph_vertex_iterator& it) const; 00129 00130 private: 00131 explicit 00132 graph_vertex_iterator( typename graph_content::const_iterator it ); 00133 00134 private: 00136 typename graph_content::const_iterator m_iterator; 00137 00138 }; // class graph_vertex_iterator 00139 00140 00144 class graph_edge_iterator 00145 { 00146 friend class graph<vertex_type, edge_type, vertex_compare>; 00147 00148 public: 00149 00153 class edge 00154 { 00155 friend class graph_edge_iterator; 00156 00157 public: 00158 edge(); 00159 const edge_type& label() const; 00160 const vertex_type& source() const; 00161 const vertex_type& target() const; 00162 00163 private: 00164 void set( const edge_type& l, const vertex_type& s, 00165 const vertex_type& t ); 00166 00167 private: 00168 edge_type const* m_label; 00169 vertex_type const* m_source; 00170 vertex_type const* m_target; 00171 }; // class edge 00172 00173 public: 00174 typedef const edge value_type; 00175 typedef const edge& reference; 00176 typedef const edge* const pointer; 00177 typedef ptrdiff_t difference_type; 00178 00179 typedef std::bidirectional_iterator_tag iterator_category; 00180 00181 public: 00182 graph_edge_iterator(); 00183 00184 graph_edge_iterator& operator++(); 00185 graph_edge_iterator operator++(int); 00186 graph_edge_iterator& operator--(); 00187 graph_edge_iterator operator--(int); 00188 reference operator*() const; 00189 pointer operator->() const; 00190 bool operator==(const graph_edge_iterator& it) const; 00191 bool operator!=(const graph_edge_iterator& it) const; 00192 00193 private: 00194 explicit 00195 graph_edge_iterator( typename graph_content::const_iterator it_begin, 00196 typename graph_content::const_iterator it_end, 00197 typename graph_content::const_iterator it_s, 00198 typename neighbours_list::const_iterator it_d ); 00199 00200 private: 00202 typename graph_content::const_iterator m_vertex_begin; 00203 00205 typename graph_content::const_iterator m_vertex_end; 00206 00208 typename graph_content::const_iterator m_vertex_iterator; 00209 00211 typename neighbours_list::const_iterator m_neighbours_iterator; 00212 00214 edge m_edge; 00215 }; // class graph_edge_iterator 00216 00217 00218 00219 public: 00220 typedef graph_vertex_iterator vertex_iterator; 00221 typedef graph_edge_iterator edge_iterator; 00222 typedef std::reverse_iterator<vertex_iterator> reverse_vertex_iterator; 00223 typedef std::reverse_iterator<edge_iterator> reverse_edge_iterator; 00224 00225 public: 00226 graph(); 00227 00228 void add_edge( const vertex_type& s1, const vertex_type& s2, 00229 const edge_type& e = edge_type() ); 00230 void add_vertex( const vertex_type& s ); 00231 00232 bool edge_exists( const vertex_type& s, const vertex_type& r ) const; 00233 void neighbours( const vertex_type& s, std::vector<vertex_type>& v ) const; 00234 void vertices( std::vector<vertex_type>& v ) const; 00235 00236 vertex_iterator vertex_begin() const; 00237 vertex_iterator vertex_end() const; 00238 vertex_iterator vertex_begin( const vertex_type& s ) const; 00239 00240 reverse_vertex_iterator vertex_rbegin() const; 00241 reverse_vertex_iterator vertex_rend() const; 00242 reverse_vertex_iterator vertex_rbegin( const vertex_type& s ) const; 00243 00244 edge_iterator edge_begin() const; 00245 edge_iterator edge_end() const; 00246 edge_iterator edge_begin( const vertex_type& s1, 00247 const vertex_type& s2 ) const; 00248 00249 reverse_edge_iterator edge_rbegin() const; 00250 reverse_edge_iterator edge_rend() const; 00251 reverse_edge_iterator edge_rbegin( const vertex_type& s1, 00252 const vertex_type& s2 ) const; 00253 00254 const edge_type& label( const vertex_type& s, const vertex_type& r ) const; 00255 00256 std::size_t outer_degree( const vertex_type& s ) const; 00257 std::size_t inner_degree( const vertex_type& s ) const; 00258 std::size_t vertices_count() const; 00259 std::size_t edges_count() const; 00260 00261 private: 00263 graph_content m_edges; 00264 00266 std::map<vertex_type, std::size_t, vertex_compare> m_inner_degrees; 00267 00269 std::size_t m_edges_count; 00270 00271 }; // class graph 00272 00273 } // namespace claw 00274 00275 #include <claw/impl/graph.tpp> 00276 00277 #endif // __CLAW_GRAPH_HPP__