adjacency_matrix.hpp

support vector clustering for vc++

//=======================================================================
// Copyright 2001 University of Notre Dame.
// Copyright 2006 Trustees of Indiana University
// Authors: Jeremy G. Siek and Douglas Gregor <[e-mail]>
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

#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>
#include <boost/static_assert.hpp>
#include <boost/type_traits/ice.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;
    };

    //=======================================================================
    // Directed In Edge Iterator

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

        void increment() {
          if (VerticesSizeType(m_last - this->base_reference()) >= m_n) {
            this->base_reference() += m_n;
            ++m_src;
          } else {
            this->base_reference() = m_last;
          }
        }
        
        inline EdgeDescriptor
        dereference() const 
        {
            return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ, 
                                  &get_property(*this->base()));
        }
        MatrixIter m_last;
        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;
    };

    //=======================================================================
    // Undirected In Edge Iterator

    template <
        typename VertexDescriptor, typename MatrixIter
      , typename VerticesSizeType, typename EdgeDescriptor
    >
    struct undir_adj_matrix_in_edge_iter 
      : iterator_adaptor<
            undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
          , MatrixIter
          , EdgeDescriptor
          , use_default
          , EdgeDescriptor
          , std::ptrdiff_t
        >
    {
        typedef iterator_adaptor<
            undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
          , MatrixIter
          , EdgeDescriptor
          , use_default
          , EdgeDescriptor
          , std::ptrdiff_t
        > super_t;
        
        undir_adj_matrix_in_edge_iter() { }
        
        undir_adj_matrix_in_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)
        {}