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