graph.hpp

Go to the documentation of this file.
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-2008 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@yahoo.fr
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   }; // 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__

Generated on Mon Nov 9 05:07:09 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.4.7