adjacency_matrix.hpp

support vector clustering for vc++

  // O(V)
  template <typename VP, typename EP, typename GP, typename A>
  void
  clear_vertex
    (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
     adjacency_matrix<directedS,VP,EP,GP,A>& g)
  {
    typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator 
      vi, vi_end;
    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
      remove_edge(u, *vi, g);
    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
      remove_edge(*vi, u, g);
  }

  // O(V)
  template <typename VP, typename EP, typename GP, typename A>
  void
  clear_vertex
    (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
     adjacency_matrix<undirectedS,VP,EP,GP,A>& g)
  {
    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_iterator
      vi, vi_end;
    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
      remove_edge(u, *vi, g);
  }

  //=========================================================================
  // Vertex Property Map
  
  template <typename GraphPtr, typename Vertex, typename T, typename R, 
    typename Tag> 
  class adj_matrix_vertex_property_map 
    : public put_get_helper<R,
         adj_matrix_vertex_property_map<GraphPtr, Vertex, T, R, Tag> >
  {
  public:
    typedef T value_type;
    typedef R reference;
    typedef Vertex key_type;
    typedef boost::lvalue_property_map_tag category;
    adj_matrix_vertex_property_map() { }
    adj_matrix_vertex_property_map(GraphPtr g) : m_g(g) { }
    inline reference operator[](key_type v) const {
      return get_property_value(m_g->m_vertex_properties[v], Tag());
    }
    GraphPtr m_g;
  };

  template <class Property, class Vertex>
  struct adj_matrix_vertex_id_map
    : public boost::put_get_helper<Vertex,
        adj_matrix_vertex_id_map<Property, Vertex> >
  {
    typedef Vertex value_type;
    typedef Vertex reference;
    typedef Vertex key_type;
    typedef boost::readable_property_map_tag category;
     adj_matrix_vertex_id_map() { }
    template <class Graph>
    inline adj_matrix_vertex_id_map(const Graph&) { }
    inline value_type operator[](key_type v) const { return v; }
  };

  namespace detail {

    struct adj_matrix_any_vertex_pa {
      template <class Tag, class Graph, class Property>
      struct bind_ {
        typedef typename property_value<Property,Tag>::type Value;
        typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
        
        typedef adj_matrix_vertex_property_map<Graph*, Vertex, Value, Value&,
          Tag> type;
        typedef adj_matrix_vertex_property_map<const Graph*, Vertex, Value, 
          const Value&, Tag> const_type;
      };
    };
    struct adj_matrix_id_vertex_pa {
      template <class Tag, class Graph, class Property>
      struct bind_ {
        typedef typename Graph::vertex_descriptor Vertex;
        typedef adj_matrix_vertex_id_map<Property, Vertex> type;
        typedef adj_matrix_vertex_id_map<Property, Vertex> const_type;
      };
    };

    template <class Tag>
    struct adj_matrix_choose_vertex_pa_helper {
      typedef adj_matrix_any_vertex_pa type;
    };
    template <>
    struct adj_matrix_choose_vertex_pa_helper<vertex_index_t> {
      typedef adj_matrix_id_vertex_pa type;
    };

    template <class Tag, class Graph, class Property>
    struct adj_matrix_choose_vertex_pa {
      typedef typename adj_matrix_choose_vertex_pa_helper<Tag>::type Helper;
      typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
      typedef typename Bind::type type;
      typedef typename Bind::const_type const_type;
    };

    struct adj_matrix_vertex_property_selector {
      template <class Graph, class Property, class Tag>
      struct bind_ {
        typedef adj_matrix_choose_vertex_pa<Tag,Graph,Property> Choice;
        typedef typename Choice::type type;
        typedef typename Choice::const_type const_type;
      };
    };

  } // namespace detail

  template <>
  struct vertex_property_selector<adjacency_matrix_class_tag> {
    typedef detail::adj_matrix_vertex_property_selector type;
  };
  
  //=========================================================================
  // Edge Property Map


  template <typename Directed, typename Property, typename Vertex, 
    typename T, typename R, typename Tag> 
  class adj_matrix_edge_property_map 
    : public put_get_helper<R,
         adj_matrix_edge_property_map<Directed, Property, Vertex, T, R, Tag> >
  {
  public:
    typedef T value_type;
    typedef R reference;
    typedef detail::matrix_edge_desc_impl<Directed, Vertex> key_type;
    typedef boost::lvalue_property_map_tag category;
    inline reference operator[](key_type e) const {
      Property& p = *(Property*)e.get_property();
      return get_property_value(p, Tag());
    }
  };
  struct adj_matrix_edge_property_selector {
    template <class Graph, class Property, class Tag>
    struct bind_ {
      typedef typename property_value<Property,Tag>::type T;
      typedef typename Graph::vertex_descriptor Vertex;
      typedef adj_matrix_edge_property_map<typename Graph::directed_category,
        Property, Vertex, T, T&, Tag> type;
      typedef adj_matrix_edge_property_map<typename Graph::directed_category,
        Property, Vertex, T, const T&, Tag> const_type;
    };
  };
  template <>
  struct edge_property_selector<adjacency_matrix_class_tag> {
    typedef adj_matrix_edge_property_selector type;
  };

  //=========================================================================
  // Functions required by PropertyGraph

  namespace detail {

    template <typename Property, typename D, typename VP, typename EP, 
              typename GP, typename A>
    typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
      Property>::type
    get_dispatch(adjacency_matrix<D,VP,EP,GP,A>& g, Property,
                 vertex_property_tag)
    {
      typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
      typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
        Property>::type PA;
      return PA(&g);
    }
    template <typename Property, typename D, typename VP, typename EP, 
              typename GP, typename A>
    typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
      Property>::type
    get_dispatch(adjacency_matrix<D,VP,EP,GP,A>&, Property,
                 edge_property_tag)
    {
      typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
        Property>::type PA;
      return PA();
    }
    template <typename Property, typename D, typename VP, typename EP, 
              typename GP, typename A>
    typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
      Property>::const_type
    get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>& g, Property,
                 vertex_property_tag)
    {
      typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
      typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
        Property>::const_type PA;
      return PA(&g);
    }
    template <typename Property, typename D, typename VP, typename EP, 
              typename GP, typename A>
    typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
      Property>::const_type
    get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>&, Property,
                 edge_property_tag)
    {
      typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, 
        Property>::const_type PA;
      return PA();
    }

  } // namespace detail

  template <typename Property, typename D, typename VP, typename EP, 
            typename GP, typename A>
  inline
  typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::type
  get(Property p, adjacency_matrix<D,VP,EP,GP,A>& g)
  {
    typedef typename property_kind<Property>::type Kind;
    return detail::get_dispatch(g, p, Kind());
  }

  template <typename Property, typename D, typename VP, typename EP, 
            typename GP, typename A>
  inline
  typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type
  get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g)
  {
    typedef typename property_kind<Property>::type Kind;
    return detail::get_dispatch(g, p, Kind());
  }

  template <typename Property, typename D, typename VP, typename EP, 
            typename GP, typename A, typename Key>
  inline
  typename property_traits<
    typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type
  >::value_type
  get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g,
      const Key& key)
  {
    return get(get(p, g), key);
  }

  template <typename Property, typename D, typename VP, typename EP, 
            typename GP, typename A, typename Key, typename Value>
  inline void
  put(Property p, adjacency_matrix<D,VP,EP,GP,A>& g,
      const Key& key, const Value& value)
  {
    typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
    typedef typename boost::property_map<Graph, Property>::type Map;
    Map pmap = get(p, g);
    put(pmap, key, value);
  }
  
  //=========================================================================
  // Other Functions

  template <typename D, typename VP, typename EP, typename GP, typename A>  
  typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
  vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n,
         const adjacency_matrix<D,VP,EP,GP,A>& g)
  {
    return n;
  }

  // Support for bundled properties
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
  template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
            typename Allocator, typename T, typename Bundle>
  inline
  typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
                        T Bundle::*>::type
  get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g)
  {
    typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
                                  T Bundle::*>::type
      result_type;
    return result_type(&g, p);
  }

  template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
            typename Allocator, typename T, typename Bundle>
  inline
  typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
                        T Bundle::*>::const_type
  get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g)
  {
    typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
                                  T Bundle::*>::const_type
      result_type;
    return result_type(&g, p);
  }
    
  template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
            typename Allocator, typename T, typename Bundle, typename Key>
  inline T
  get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g,
      const Key& key)
  {
    return get(get(p, g), key);
  }

  template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
            typename Allocator, typename T, typename Bundle, typename Key>
  inline void
  put(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g,
      const Key& key, const T& value)
  {
    put(get(p, g), key, value);
  }

#endif

} // namespace boost

#endif // BOOST_ADJACENCY_MATRIX_HPP