adjacency_matrix.hpp

support vector clustering for vc++

        return m_matrix[u * (u + 1)/2 + v];
      }
    }

    Matrix m_matrix;
    VertexList m_vertex_set;
    std::vector<vertex_property_type> m_vertex_properties;
    size_type m_num_edges;
  };
  
  //=========================================================================
  // Functions required by the AdjacencyMatrix concept 

  template <typename D, typename VP, typename EP, typename GP, typename A>
  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor,
            bool>
  edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
       typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
       const adjacency_matrix<D,VP,EP,GP,A>& g)
  {
    bool exists = detail::get_edge_exists(g.get_edge(u,v), 0);
    typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
      e(exists, u, v, &detail::get_property(g.get_edge(u,v)));
    return std::make_pair(e, exists);
  }

  //=========================================================================
  // Functions required by the IncidenceGraph concept 

  // O(1)
  template <typename VP, typename EP, typename GP, typename A>
  std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator,
            typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator>
  out_edges
    (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
     const adjacency_matrix<directedS,VP,EP,GP,A>& g_)
  {
    typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;
    Graph& g = const_cast<Graph&>(g_);
    typename Graph::vertices_size_type offset = u * g.m_vertex_set.size();
    typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
    typename Graph::MatrixIter l = f + g.m_vertex_set.size();
    typename Graph::unfiltered_out_edge_iter
          first(f, u, g.m_vertex_set.size())
        , last(l, u, g.m_vertex_set.size());
    detail::does_edge_exist pred;
    typedef typename Graph::out_edge_iterator out_edge_iterator;
    return std::make_pair(out_edge_iterator(pred, first, last), 
                          out_edge_iterator(pred, last, last));
  }

  // O(1)
  template <typename VP, typename EP, typename GP, typename A>
  std::pair<
    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator,
    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator>
  out_edges
    (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
     const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)
  {
    typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;
    Graph& g = const_cast<Graph&>(g_);
    typename Graph::vertices_size_type offset = u * (u + 1) / 2;
    typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
    typename Graph::MatrixIter l = g.m_matrix.end();

    typename Graph::unfiltered_out_edge_iter
        first(f, u, g.m_vertex_set.size())
      , last(l, u, g.m_vertex_set.size());
    
    detail::does_edge_exist pred;
    typedef typename Graph::out_edge_iterator out_edge_iterator;
    return std::make_pair(out_edge_iterator(pred, first, last), 
                          out_edge_iterator(pred, last, last));
  }
  
  // O(N)
  template <typename D, typename VP, typename EP, typename GP, typename A>  
  typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type
  out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
             const adjacency_matrix<D,VP,EP,GP,A>& g)
  {
    typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;
    typename adjacency_matrix<D,VP,EP,GP,A>::out_edge_iterator f, l;
    for (tie(f, l) = out_edges(u, g); f != l; ++f)
      ++n;
    return n;
  }

  // O(1)
  template <typename D, typename VP, typename EP, typename GP, typename A,
    typename Dir, typename Vertex>  
  typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
  source(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
         const adjacency_matrix<D,VP,EP,GP,A>&)
  {
    return e.m_source;
  }

  // O(1)
  template <typename D, typename VP, typename EP, typename GP, typename A,
    typename Dir, typename Vertex>  
  typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
  target(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
         const adjacency_matrix<D,VP,EP,GP,A>&)
  {
    return e.m_target;
  }

  //=========================================================================
  // Functions required by the BidirectionalGraph concept 

  // O(1)
  template <typename VP, typename EP, typename GP, typename A>
  std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator,
            typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator>
  in_edges
    (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
     const adjacency_matrix<directedS,VP,EP,GP,A>& g_)
  {
    typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;
    Graph& g = const_cast<Graph&>(g_);
    typename Graph::MatrixIter f = g.m_matrix.begin() + u;
    typename Graph::MatrixIter l = g.m_matrix.end();
    typename Graph::unfiltered_in_edge_iter
        first(f, l, u, g.m_vertex_set.size())
      , last(l, l, u, g.m_vertex_set.size());
    detail::does_edge_exist pred;
    typedef typename Graph::in_edge_iterator in_edge_iterator;
    return std::make_pair(in_edge_iterator(pred, first, last), 
                          in_edge_iterator(pred, last, last));
  }

  // O(1)
  template <typename VP, typename EP, typename GP, typename A>
  std::pair<
    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator,
    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator>
  in_edges
    (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
     const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)
  {
    typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;
    Graph& g = const_cast<Graph&>(g_);
    typename Graph::vertices_size_type offset = u * (u + 1) / 2;
    typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
    typename Graph::MatrixIter l = g.m_matrix.end();

    typename Graph::unfiltered_in_edge_iter
        first(f, u, g.m_vertex_set.size())
      , last(l, u, g.m_vertex_set.size());
    
    detail::does_edge_exist pred;
    typedef typename Graph::in_edge_iterator in_edge_iterator;
    return std::make_pair(in_edge_iterator(pred, first, last), 
                          in_edge_iterator(pred, last, last));
  }
  
  // O(N)
  template <typename D, typename VP, typename EP, typename GP, typename A>  
  typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type
  in_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
             const adjacency_matrix<D,VP,EP,GP,A>& g)
  {
    typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;
    typename adjacency_matrix<D,VP,EP,GP,A>::in_edge_iterator f, l;
    for (tie(f, l) = in_edges(u, g); f != l; ++f)
      ++n;
    return n;
  }

  //=========================================================================
  // Functions required by the AdjacencyGraph concept 

  template <typename D, typename VP, typename EP, typename GP, typename A>
  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator,
            typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator>
  adjacent_vertices
    (typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
     const adjacency_matrix<D,VP,EP,GP,A>& g_)
  {
      typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
      const Graph& cg = static_cast<const Graph&>(g_);
      Graph& g = const_cast<Graph&>(cg);
      typedef typename Graph::adjacency_iterator adjacency_iterator;
      typename Graph::out_edge_iterator first, last;
      boost::tie(first, last) = out_edges(u, g);
      return std::make_pair(adjacency_iterator(first, &g),
                            adjacency_iterator(last, &g));
  }

  //=========================================================================
  // Functions required by the VertexListGraph concept 

  template <typename D, typename VP, typename EP, typename GP, typename A>
  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator,
            typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator>
  vertices(const adjacency_matrix<D,VP,EP,GP,A>& g_) {
    typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
    Graph& g = const_cast<Graph&>(g_);
    return std::make_pair(g.m_vertex_set.begin(), g.m_vertex_set.end());
  }

  template <typename D, typename VP, typename EP, typename GP, typename A>
  typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type
  num_vertices(const adjacency_matrix<D,VP,EP,GP,A>& g) {
    return g.m_vertex_set.size();
  }
  
  //=========================================================================
  // Functions required by the EdgeListGraph concept 
  
  template <typename D, typename VP, typename EP, typename GP, typename A>
  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator,
            typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator>
  edges(const adjacency_matrix<D,VP,EP,GP,A>& g_)
  {
    typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
    Graph& g = const_cast<Graph&>(g_);
    
    typename Graph::unfiltered_edge_iter
      first(g.m_matrix.begin(), g.m_matrix.begin(), 
                                    g.m_vertex_set.size()),
      last(g.m_matrix.end(), g.m_matrix.begin(), 
                                    g.m_vertex_set.size());
    detail::does_edge_exist pred;
    typedef typename Graph::edge_iterator edge_iterator;
    return std::make_pair(edge_iterator(pred, first, last),
                          edge_iterator(pred, last, last));
  }

  // O(1)
  template <typename D, typename VP, typename EP, typename GP, typename A>
  typename adjacency_matrix<D,VP,EP,GP,A>::edges_size_type
  num_edges(const adjacency_matrix<D,VP,EP,GP,A>& g)
  {
    return g.m_num_edges;
  }
  
  //=========================================================================
  // Functions required by the MutableGraph concept 

  // O(1)
  template <typename D, typename VP, typename EP, typename GP, typename A>
  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
  add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
           typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
           const EP& ep,
           adjacency_matrix<D,VP,EP,GP,A>& g)
  {
    typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor 
      edge_descriptor;
    if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) {
      ++(g.m_num_edges);
      detail::set_property(g.get_edge(u,v), ep, 0);
      detail::set_edge_exists(g.get_edge(u,v), true, 0);
      return std::make_pair
        (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))), 
         true);
    } else
      return std::make_pair
        (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),
         false);
  }
  // O(1)
  template <typename D, typename VP, typename EP, typename GP, typename A>
  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
  add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
           typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
           adjacency_matrix<D,VP,EP,GP,A>& g)
  {
    EP ep;
    return add_edge(u, v, ep, g);
  }

  // O(1)  
  template <typename D, typename VP, typename EP, typename GP, typename A>
  void
  remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
              typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
              adjacency_matrix<D,VP,EP,GP,A>& g)
  {
    --(g.m_num_edges);
    detail::set_edge_exists(g.get_edge(u,v), false, 0);
  }

  // O(1)
  template <typename D, typename VP, typename EP, typename GP, typename A>
  void
  remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e,
              adjacency_matrix<D,VP,EP,GP,A>& g)
  {
    remove_edge(source(e, g), target(e, g), g);
  }

  
  template <typename D, typename VP, typename EP, typename GP, typename A>
  inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
  add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) {
    // UNDER CONSTRUCTION
    assert(false);
    return *vertices(g).first;
  }

  template <typename D, typename VP, typename EP, typename GP, typename A>
  inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
  add_vertex(const VP& vp, adjacency_matrix<D,VP,EP,GP,A>& g) {
    // UNDER CONSTRUCTION
    assert(false);
    return *vertices(g).first;
  }

  template <typename D, typename VP, typename EP, typename GP, typename A>
  inline void
  remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
                adjacency_matrix<D,VP,EP,GP,A>& g)
  {
    // UNDER CONSTRUCTION
    assert(false);
  }