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