adjacency_matrix.hpp

来自「CGAL is a collaborative effort of severa」· HPP 代码 · 共 1,083 行 · 第 1/3 页

//=======================================================================
// Copyright 2001 University of Notre Dame.
// Author: Jeremy G. Siek
//
// This file is part of the Boost Graph Library
//
// You should have received a copy of the License Agreement for the
// Boost Graph Library along with the software; see the file LICENSE.
// If not, contact Office of Research, University of Notre Dame, Notre
// Dame, IN 46556.
//
// Permission to modify the code and to distribute modified code is
// granted, provided the text of this NOTICE is retained, a notice that
// the code was modified is included with the above COPYRIGHT NOTICE and
// with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
// file is distributed with the modified code.
//
// LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
// By way of example, but not limitation, Licensor MAKES NO
// REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
// PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
// OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
// OR OTHER RIGHTS.
//=======================================================================

#ifndef BOOST_ADJACENCY_MATRIX_HPP
#define BOOST_ADJACENCY_MATRIX_HPP

#include <boost/config.hpp>
#include <vector>
#include <memory>
#include <cassert>
#include <boost/limits.hpp>
#include <boost/iterator.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_selectors.hpp>
#include <boost/pending/ct_if.hpp>
#include <boost/graph/adjacency_iterator.hpp>
#include <boost/graph/detail/edge.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/iterator/filter_iterator.hpp>
#include <boost/pending/integer_range.hpp>
#include <boost/graph/properties.hpp>
#include <boost/tuple/tuple.hpp>

namespace boost {
  
  namespace detail {

    template <class Directed, class Vertex>
    class matrix_edge_desc_impl : public edge_desc_impl<Directed,Vertex>
    {
      typedef edge_desc_impl<Directed,Vertex> Base;
    public:
      matrix_edge_desc_impl() { }
      matrix_edge_desc_impl(bool exists, Vertex s, Vertex d, 
                            const void* ep = 0)
        : Base(s, d, ep), m_exists(exists) { }
      bool exists() const { return m_exists; }
    private:
      bool m_exists;
    };

    struct does_edge_exist {
      template <class Edge>
      bool operator()(const Edge& e) const { return e.exists(); }
    };

    template <typename EdgeProperty>
    bool get_edge_exists(const std::pair<bool, EdgeProperty>& stored_edge, int) {
      return stored_edge.first;
    }
    template <typename EdgeProperty>
    void set_edge_exists(
        std::pair<bool, EdgeProperty>& stored_edge, 
        bool flag,
        int
        ) {
      stored_edge.first = flag;
    }

    template <typename EdgeProxy>
    bool get_edge_exists(const EdgeProxy& edge_proxy, ...) {
      return edge_proxy;
    }
    template <typename EdgeProxy>
    EdgeProxy& set_edge_exists(EdgeProxy& edge_proxy, bool flag, ...) {
      edge_proxy = flag;
      return edge_proxy; // just to avoid never used warning
    }



    template <typename EdgeProperty>
    const EdgeProperty&
    get_property(const std::pair<bool, EdgeProperty>& stored_edge) {
      return stored_edge.second;
    }
    template <typename EdgeProperty>
    EdgeProperty&
    get_property(std::pair<bool, EdgeProperty>& stored_edge) {
      return stored_edge.second;
    }

    template <typename StoredEdgeProperty, typename EdgeProperty>
    inline void
    set_property(std::pair<bool, StoredEdgeProperty>& stored_edge, 
                 const EdgeProperty& ep, int) {
      stored_edge.second = ep;
    }

    inline const no_property& get_property(const char&) {
      static no_property s_prop;
      return s_prop;
    }
    inline no_property& get_property(char&) {
      static no_property s_prop;
      return s_prop;
    }
    template <typename EdgeProxy, typename EdgeProperty>
    inline void
    set_property(EdgeProxy, const EdgeProperty&, ...) {}
    
    //=======================================================================
    // Directed Out Edge Iterator

    template <
        typename VertexDescriptor, typename MatrixIter
      , typename VerticesSizeType, typename EdgeDescriptor
    >
    struct dir_adj_matrix_out_edge_iter
      : iterator_adaptor<
            dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
          , MatrixIter
          , EdgeDescriptor
          , use_default
          , EdgeDescriptor
          , std::ptrdiff_t
        >
    {
        typedef iterator_adaptor<
            dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
          , MatrixIter
          , EdgeDescriptor
          , use_default
          , EdgeDescriptor
          , std::ptrdiff_t
        > super_t;
        
        dir_adj_matrix_out_edge_iter() { }
        
        dir_adj_matrix_out_edge_iter(
            const MatrixIter& i
          , const VertexDescriptor& src
          , const VerticesSizeType& n
           )
            : super_t(i), m_src(src), m_targ(0), m_n(n)
        { }

        void increment() {
            ++this->base_reference();
            ++m_targ;
        }
        
        inline EdgeDescriptor
        dereference() const 
        {
            return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ, 
                                  &get_property(*this->base()));
        }
        VertexDescriptor m_src, m_targ;
        VerticesSizeType m_n;
    };

    //=======================================================================
    // Undirected Out Edge Iterator

    template <
        typename VertexDescriptor, typename MatrixIter
      , typename VerticesSizeType, typename EdgeDescriptor
    >
    struct undir_adj_matrix_out_edge_iter 
      : iterator_adaptor<
            undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
          , MatrixIter
          , EdgeDescriptor
          , use_default
          , EdgeDescriptor
          , std::ptrdiff_t
        >
    {
        typedef iterator_adaptor<
            undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
          , MatrixIter
          , EdgeDescriptor
          , use_default
          , EdgeDescriptor
          , std::ptrdiff_t
        > super_t;
        
        undir_adj_matrix_out_edge_iter() { }
        
        undir_adj_matrix_out_edge_iter(
            const MatrixIter& i
          , const VertexDescriptor& src
          , const VerticesSizeType& n
        )
          : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n)
        {}

        void increment()
        {
            if (m_targ < m_src)     // first half
            {
                ++this->base_reference();
            }
            else if (m_targ < m_n - 1)
            {                  // second half
                ++m_inc;
                this->base_reference() += m_inc;
            }
            else
            {                  // past-the-end
                this->base_reference() += m_n - m_src;
            }
            ++m_targ;
        }
        
        inline EdgeDescriptor
        dereference() const 
        {
            return EdgeDescriptor(
                get_edge_exists(*this->base(), 0), m_src, m_targ
              , &get_property(*this->base())
            );
        }
        
        VertexDescriptor m_src, m_inc, m_targ;
        VerticesSizeType m_n;
    };

    //=======================================================================
    // Edge Iterator

    template <typename Directed, typename MatrixIter, 
              typename VerticesSizeType, typename EdgeDescriptor>
    struct adj_matrix_edge_iter
      : iterator_adaptor<
            adj_matrix_edge_iter<Directed, MatrixIter,  VerticesSizeType, EdgeDescriptor>
          , MatrixIter
          , EdgeDescriptor
          , use_default
          , EdgeDescriptor
          , std::ptrdiff_t
        >
    {
        typedef iterator_adaptor<
            adj_matrix_edge_iter<Directed, MatrixIter,  VerticesSizeType, EdgeDescriptor>
          , MatrixIter
          , EdgeDescriptor
          , use_default
          , EdgeDescriptor
          , std::ptrdiff_t
        > super_t;
        
        adj_matrix_edge_iter() { }
        
        adj_matrix_edge_iter(const MatrixIter& i, const MatrixIter& start, const VerticesSizeType& n) 
            : super_t(i), m_start(start), m_src(0), m_targ(0), m_n(n) { }

        void increment()
        {
            increment_dispatch(this->base_reference(), Directed());
        }
        
        void increment_dispatch(MatrixIter& i, directedS)
        {
            ++i;
            if (m_targ == m_n - 1)
            {
                m_targ = 0;
                ++m_src;
            }
            else
            {
                ++m_targ;
            }
        }
        
        void increment_dispatch(MatrixIter& i, undirectedS)
        {
            ++i;
            if (m_targ == m_src)
            {
                m_targ = 0;
                ++m_src;
            }
            else
            {
                ++m_targ;
            }
        }

        inline EdgeDescriptor
        dereference() const 
        {
            return EdgeDescriptor(
                get_edge_exists(
                    *this->base(), 0), m_src, m_targ, &get_property(*this->base())
            );
        }
      
        MatrixIter m_start;
        VerticesSizeType m_src, m_targ, m_n;
    };

  } // namespace detail

  //=========================================================================
  // Adjacency Matrix Traits
  template <typename Directed = directedS>
  class adjacency_matrix_traits {
    typedef typename Directed::is_bidir_t is_bidir;
    typedef typename Directed::is_directed_t is_directed;
  public:
    typedef typename boost::ct_if_t<is_bidir,
      bidirectional_tag,
      typename boost::ct_if_t<is_directed,
        directed_tag, undirected_tag
      >::type
    >::type directed_category;
    
    typedef disallow_parallel_edge_tag edge_parallel_category;
    
    typedef std::size_t vertex_descriptor;

    typedef detail::matrix_edge_desc_impl<directed_category,
      vertex_descriptor> edge_descriptor;
  };

  struct adjacency_matrix_class_tag { };

  struct adj_matrix_traversal_tag :
    public virtual adjacency_matrix_tag,
    public virtual vertex_list_graph_tag,
    public virtual incidence_graph_tag,
    public virtual adjacency_graph_tag,
    public virtual edge_list_graph_tag { };
  
  //=========================================================================
  // Adjacency Matrix Class
  template <typename Directed = directedS,
            typename VertexProperty = no_property,
            typename EdgeProperty = no_property,
            typename GraphProperty = no_property,
            typename Allocator = std::allocator<bool> >
  class adjacency_matrix {
    typedef adjacency_matrix self;
    typedef adjacency_matrix_traits<Directed> Traits;
    
    struct no_vertex_bundle {};