adjacency_matrix.hpp

support vector clustering for vc++

        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_targ, m_src
              , &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_directed_t is_directed;
  public:
    // The bidirectionalS tag is not allowed with the adjacency_matrix
    // graph type. Instead, use directedS, which also provides the
    // functionality required for a Bidirectional Graph (in_edges,
    // in_degree, etc.).
#if !defined(_MSC_VER) || _MSC_VER > 1300
    BOOST_STATIC_ASSERT(type_traits::ice_not<(is_same<Directed, bidirectionalS>::value)>::value);
#endif

    typedef typename boost::ct_if_t<is_directed,
                                    bidirectional_tag, undirected_tag>::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;
    
  public:
#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
    // The bidirectionalS tag is not allowed with the adjacency_matrix
    // graph type. Instead, use directedS, which also provides the
    // functionality required for a Bidirectional Graph (in_edges,
    // in_degree, etc.).
    BOOST_STATIC_ASSERT(!(is_same<Directed, bidirectionalS>::value));
#endif

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
    typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::type
      vertex_property_type;
    typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type
      edge_property_type;
      
  private:
    typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::retagged
      maybe_vertex_bundled;

    typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::retagged
      maybe_edge_bundled;
    
  public:
    // The types that are actually bundled
    typedef typename ct_if<(is_same<maybe_vertex_bundled, no_property>::value),
                           no_vertex_bundle,
                           maybe_vertex_bundled>::type vertex_bundled;
    typedef typename ct_if<(is_same<maybe_edge_bundled, no_property>::value),
                           no_edge_bundle,
                           maybe_edge_bundled>::type edge_bundled;
#else
    typedef EdgeProperty     edge_property_type;
    typedef VertexProperty   vertex_property_type;
    typedef no_vertex_bundle vertex_bundled;
    typedef no_edge_bundle   edge_bundled;
#endif

  public: // should be private
    typedef typename ct_if_t<typename has_property<edge_property_type>::type,
      std::pair<bool, edge_property_type>, char>::type StoredEdge;
#if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) || defined(BOOST_NO_STD_ALLOCATOR)
    typedef std::vector<StoredEdge> Matrix;
#else
    // This causes internal compiler error for MSVC
    typedef typename Allocator::template rebind<StoredEdge>::other Alloc;
    typedef std::vector<StoredEdge, Alloc> Matrix;
#endif
    typedef typename Matrix::iterator MatrixIter;
    typedef typename Matrix::size_type size_type;
  public:
    // Graph concept required types
    typedef typename Traits::vertex_descriptor vertex_descriptor;
    typedef typename Traits::edge_descriptor edge_descriptor;
    typedef typename Traits::directed_category directed_category;
    typedef typename Traits::edge_parallel_category edge_parallel_category;
    typedef adj_matrix_traversal_tag traversal_category;

    static vertex_descriptor null_vertex()
    {
      return (std::numeric_limits<vertex_descriptor>::max)();
    }
      
    //private: if friends worked, these would be private

    typedef detail::dir_adj_matrix_out_edge_iter<
        vertex_descriptor, MatrixIter, size_type, edge_descriptor
    > DirOutEdgeIter;

    typedef detail::undir_adj_matrix_out_edge_iter<
        vertex_descriptor, MatrixIter, size_type, edge_descriptor
    > UnDirOutEdgeIter;

    typedef typename ct_if_t<
        typename Directed::is_directed_t, DirOutEdgeIter, UnDirOutEdgeIter
    >::type unfiltered_out_edge_iter;

    typedef detail::dir_adj_matrix_in_edge_iter<
        vertex_descriptor, MatrixIter, size_type, edge_descriptor
    > DirInEdgeIter;

    typedef detail::undir_adj_matrix_in_edge_iter<
        vertex_descriptor, MatrixIter, size_type, edge_descriptor
    > UnDirInEdgeIter;

    typedef typename ct_if_t<
        typename Directed::is_directed_t, DirInEdgeIter, UnDirInEdgeIter
    >::type unfiltered_in_edge_iter;
    
    typedef detail::adj_matrix_edge_iter<
        Directed, MatrixIter, size_type, edge_descriptor
    > unfiltered_edge_iter;
    
  public:

    // IncidenceGraph concept required types
    typedef filter_iterator<detail::does_edge_exist, unfiltered_out_edge_iter>
      out_edge_iterator;

    typedef size_type degree_size_type;

    // BidirectionalGraph required types
    typedef filter_iterator<detail::does_edge_exist, unfiltered_in_edge_iter>
      in_edge_iterator;

    // AdjacencyGraph required types
     typedef typename adjacency_iterator_generator<self,
       vertex_descriptor, out_edge_iterator>::type adjacency_iterator;

    // VertexListGraph required types
    typedef size_type vertices_size_type;
    typedef integer_range<vertex_descriptor> VertexList;
    typedef typename VertexList::iterator vertex_iterator;

    // EdgeListGraph required types
    typedef size_type edges_size_type;
    typedef filter_iterator<
        detail::does_edge_exist, unfiltered_edge_iter
    > edge_iterator;

    // PropertyGraph required types
    typedef adjacency_matrix_class_tag graph_tag;

    // Constructor required by MutableGraph
    adjacency_matrix(vertices_size_type n_vertices) 
      : m_matrix(Directed::is_directed ? 
                 (n_vertices * n_vertices)
                 : (n_vertices * (n_vertices + 1) / 2)),
      m_vertex_set(0, n_vertices),
      m_vertex_properties(n_vertices),
      m_num_edges(0) { }

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
    // Directly access a vertex or edge bundle
    vertex_bundled& operator[](vertex_descriptor v)
    { return get(vertex_bundle, *this)[v]; }

    const vertex_bundled& operator[](vertex_descriptor v) const
    { return get(vertex_bundle, *this)[v]; }

    edge_bundled& operator[](edge_descriptor e)
    { return get(edge_bundle, *this)[e]; }

    const edge_bundled& operator[](edge_descriptor e) const
    { return get(edge_bundle, *this)[e]; }
#endif
    
    //private: if friends worked, these would be private

    typename Matrix::const_reference
    get_edge(vertex_descriptor u, vertex_descriptor v) const {
      if (Directed::is_directed)
        return m_matrix[u * m_vertex_set.size() + v];
      else {
        if (v > u)
          std::swap(u, v);
        return m_matrix[u * (u + 1)/2 + v];
      }
    }
    typename Matrix::reference
    get_edge(vertex_descriptor u, vertex_descriptor v) {
      if (Directed::is_directed)
        return m_matrix[u * m_vertex_set.size() + v];
      else {
        if (v > u)
          std::swap(u, v);