graph.hpp

Go to the documentation of this file.

/*
  CLAW - a C++ Library Absolutely Wonderful

  CLAW is a free library without any particular aim but being useful to 
  anyone.

  Copyright (C) 2005-2011 Julien Jorge

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

  contact: julien.jorge@gamned.org
*/
#ifndef __CLAW_GRAPH_HPP__
#define __CLAW_GRAPH_HPP__

#include <claw/meta/no_type.hpp>

#include <map>
#include <vector>
#include <queue>
#include <exception>
#include <iterator>
#include <utility>

#include <cstddef>

namespace claw
{

  class graph_exception:
    public std::exception
  {
  public:
    graph_exception() throw();
    graph_exception( const std::string& s) throw();
    virtual ~graph_exception() throw();

    virtual const char* what() const throw();

  private:
    const std::string m_msg;

  }; // graph_exception

  template <class S, class A = meta::no_type, class Comp = std::less<S> >
  class graph
  {
  public:
    typedef S vertex_type;

    typedef A edge_type;

    typedef Comp vertex_compare;

    typedef std::map<vertex_type, edge_type, vertex_compare> neighbours_list;

    typedef std::map<vertex_type, neighbours_list, vertex_compare>
    graph_content;

    typedef claw::graph<vertex_type, edge_type, vertex_compare> self_type;

    class graph_vertex_iterator
    {
      friend class graph<vertex_type, edge_type, vertex_compare>;

    public:
      typedef const vertex_type  value_type;
      typedef const vertex_type& reference;
      typedef const vertex_type* const pointer;
      typedef   ptrdiff_t difference_type;
          
      typedef std::bidirectional_iterator_tag iterator_category;

    public:
      graph_vertex_iterator();

      graph_vertex_iterator& operator++();
      graph_vertex_iterator operator++(int);
      graph_vertex_iterator& operator--();
      graph_vertex_iterator operator--(int);
      reference operator*() const;
      pointer   operator->() const;
      bool operator==(const graph_vertex_iterator& it) const;
      bool operator!=(const graph_vertex_iterator& it) const;

    private:
      explicit
      graph_vertex_iterator( typename graph_content::const_iterator it );

    private:
      typename graph_content::const_iterator m_iterator;

    }; // class graph_vertex_iterator


    class graph_edge_iterator
    {
      friend class graph<vertex_type, edge_type, vertex_compare>;

    public:

      class edge
      {
        friend class graph_edge_iterator;

      public:
        edge();
        const edge_type& label() const;
        const vertex_type& source() const;
        const vertex_type& target() const;
                
      private:
        void set( const edge_type& l, const vertex_type& s, 
                  const vertex_type& t );

      private:
        edge_type const* m_label;
        vertex_type const* m_source;
        vertex_type const* m_target;
      }; // class edge
        
    public:
      typedef const edge  value_type;
      typedef const edge& reference;
      typedef const edge* const pointer;
      typedef ptrdiff_t difference_type;
          
      typedef std::bidirectional_iterator_tag iterator_category;

    public:
      graph_edge_iterator();

      graph_edge_iterator& operator++();
      graph_edge_iterator operator++(int);
      graph_edge_iterator& operator--();
      graph_edge_iterator operator--(int);
      reference operator*() const;
      pointer   operator->() const;
      bool operator==(const graph_edge_iterator& it) const;
      bool operator!=(const graph_edge_iterator& it) const;

    private:
      explicit
      graph_edge_iterator( typename graph_content::const_iterator it_begin,
                           typename graph_content::const_iterator it_end,
                           typename graph_content::const_iterator it_s,
                           typename neighbours_list::const_iterator it_d );

    private:
      typename graph_content::const_iterator m_vertex_begin;

      typename graph_content::const_iterator m_vertex_end;

      typename graph_content::const_iterator m_vertex_iterator;

      typename neighbours_list::const_iterator m_neighbours_iterator;

      edge m_edge;
    }; // class graph_edge_iterator


        
  public:
    typedef graph_vertex_iterator vertex_iterator;
    typedef graph_edge_iterator   edge_iterator;
    typedef std::reverse_iterator<vertex_iterator> reverse_vertex_iterator;
    typedef std::reverse_iterator<edge_iterator>   reverse_edge_iterator;

  public:
    graph();

    void add_edge( const vertex_type& s1, const vertex_type& s2, 
                   const edge_type& e = edge_type() );
    void add_vertex( const vertex_type& s );
    
    bool edge_exists( const vertex_type& s, const vertex_type& r ) const;
    void neighbours( const vertex_type& s, std::vector<vertex_type>& v ) const;
    void vertices( std::vector<vertex_type>& v ) const;
    
    vertex_iterator vertex_begin() const;
    vertex_iterator vertex_end() const;
    vertex_iterator vertex_begin( const vertex_type& s ) const;

    reverse_vertex_iterator vertex_rbegin() const;
    reverse_vertex_iterator vertex_rend() const;
    reverse_vertex_iterator vertex_rbegin( const vertex_type& s ) const;

    edge_iterator edge_begin() const;
    edge_iterator edge_end() const;
    edge_iterator edge_begin( const vertex_type& s1, 
                              const vertex_type& s2 ) const;

    reverse_edge_iterator edge_rbegin() const;
    reverse_edge_iterator edge_rend() const;
    reverse_edge_iterator edge_rbegin( const vertex_type& s1, 
                                       const vertex_type& s2 ) const;

    const edge_type& label( const vertex_type& s, const vertex_type& r ) const;

    std::size_t outer_degree( const vertex_type& s ) const;
    std::size_t inner_degree( const vertex_type& s ) const;
    std::size_t vertices_count() const;
    std::size_t edges_count() const;

  private:
    graph_content m_edges;

    std::map<vertex_type, std::size_t, vertex_compare> m_inner_degrees;

    std::size_t m_edges_count;

  }; // class graph

} // namespace claw

#include <claw/impl/graph.tpp>

#endif // __CLAW_GRAPH_HPP__