Claw  1.7.0
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-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__