Claw 1.7.0
|
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 #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 }; // graph_exception 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 }; // class graph_vertex_iterator 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 }; // class edge 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 }; // class graph_edge_iterator 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 }; // class graph 00271 00272 } // namespace claw 00273 00274 #include <claw/impl/graph.tpp> 00275 00276 #endif // __CLAW_GRAPH_HPP__