Chris@16: //=======================================================================
Chris@16: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
Chris@16: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_PROPERTIES_HPP
Chris@16: #define BOOST_GRAPH_PROPERTIES_HPP
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/pending/property.hpp>
Chris@16: #include <boost/detail/workaround.hpp>
Chris@16: 
Chris@16: // Include the property map library and extensions in the BGL.
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/graph/property_maps/constant_property_map.hpp>
Chris@16: #include <boost/graph/property_maps/null_property_map.hpp>
Chris@16: 
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/type_traits.hpp>
Chris@16: #include <boost/limits.hpp>
Chris@16: #include <boost/mpl/and.hpp>
Chris@16: #include <boost/mpl/not.hpp>
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   enum default_color_type { white_color, gray_color, green_color, red_color, black_color };
Chris@16: 
Chris@16:   template <class ColorValue>
Chris@16:   struct color_traits {
Chris@16:     static default_color_type white() { return white_color; }
Chris@16:     static default_color_type gray() { return gray_color; }
Chris@16:     static default_color_type green() { return green_color; }
Chris@16:     static default_color_type red() { return red_color; }
Chris@16:     static default_color_type black() { return black_color; }
Chris@16:   };
Chris@16: 
Chris@16:   // These functions are now obsolete, replaced by color_traits.
Chris@16:   inline default_color_type white(default_color_type) { return white_color; }
Chris@16:   inline default_color_type gray(default_color_type) { return gray_color; }
Chris@16:   inline default_color_type green(default_color_type) { return green_color; }
Chris@16:   inline default_color_type red(default_color_type) { return red_color; }
Chris@16:   inline default_color_type black(default_color_type) { return black_color; }
Chris@16: 
Chris@16: 
Chris@16:   struct graph_property_tag { };
Chris@16:   struct vertex_property_tag { };
Chris@16:   struct edge_property_tag { };
Chris@16: 
Chris@16:   // See examples/edge_property.cpp for how to use this.
Chris@16: #define BOOST_INSTALL_PROPERTY(KIND, NAME) \
Chris@16:   template <> struct property_kind<KIND##_##NAME##_t> { \
Chris@16:     typedef KIND##_property_tag type; \
Chris@16:   }
Chris@16: 
Chris@16: #define BOOST_DEF_PROPERTY(KIND, NAME) \
Chris@16:   enum KIND##_##NAME##_t { KIND##_##NAME }; \
Chris@16:   BOOST_INSTALL_PROPERTY(KIND, NAME)
Chris@16: 
Chris@16:   // These three are defined in boost/pending/property.hpp
Chris@16:   BOOST_INSTALL_PROPERTY(vertex, all);
Chris@16:   BOOST_INSTALL_PROPERTY(edge, all);
Chris@16:   BOOST_INSTALL_PROPERTY(graph, all);
Chris@16:   BOOST_DEF_PROPERTY(vertex, index);
Chris@16:   BOOST_DEF_PROPERTY(vertex, index1);
Chris@16:   BOOST_DEF_PROPERTY(vertex, index2);
Chris@16:   BOOST_DEF_PROPERTY(vertex, root);
Chris@16:   BOOST_DEF_PROPERTY(edge, index);
Chris@16:   BOOST_DEF_PROPERTY(edge, name);
Chris@16:   BOOST_DEF_PROPERTY(edge, weight);
Chris@16:   BOOST_DEF_PROPERTY(edge, weight2);
Chris@16:   BOOST_DEF_PROPERTY(edge, color);
Chris@16:   BOOST_DEF_PROPERTY(vertex, name);
Chris@16:   BOOST_DEF_PROPERTY(graph, name);
Chris@16:   BOOST_DEF_PROPERTY(vertex, distance);
Chris@16:   BOOST_DEF_PROPERTY(vertex, distance2);
Chris@16:   BOOST_DEF_PROPERTY(vertex, color);
Chris@16:   BOOST_DEF_PROPERTY(vertex, degree);
Chris@16:   BOOST_DEF_PROPERTY(vertex, in_degree);
Chris@16:   BOOST_DEF_PROPERTY(vertex, out_degree);
Chris@16:   BOOST_DEF_PROPERTY(vertex, current_degree);
Chris@16:   BOOST_DEF_PROPERTY(vertex, priority);
Chris@16:   BOOST_DEF_PROPERTY(vertex, discover_time);
Chris@16:   BOOST_DEF_PROPERTY(vertex, finish_time);
Chris@16:   BOOST_DEF_PROPERTY(vertex, predecessor);
Chris@16:   BOOST_DEF_PROPERTY(vertex, rank);
Chris@16:   BOOST_DEF_PROPERTY(vertex, centrality);
Chris@16:   BOOST_DEF_PROPERTY(vertex, lowpoint);
Chris@16:   BOOST_DEF_PROPERTY(vertex, potential);
Chris@16:   BOOST_DEF_PROPERTY(vertex, update);
Chris@16:   BOOST_DEF_PROPERTY(vertex, underlying);
Chris@16:   BOOST_DEF_PROPERTY(edge, reverse);
Chris@16:   BOOST_DEF_PROPERTY(edge, capacity);
Chris@16:   BOOST_DEF_PROPERTY(edge, flow);
Chris@16:   BOOST_DEF_PROPERTY(edge, residual_capacity);
Chris@16:   BOOST_DEF_PROPERTY(edge, centrality);
Chris@16:   BOOST_DEF_PROPERTY(edge, discover_time);
Chris@16:   BOOST_DEF_PROPERTY(edge, update);
Chris@16:   BOOST_DEF_PROPERTY(edge, finished);
Chris@16:   BOOST_DEF_PROPERTY(edge, underlying);
Chris@16:   BOOST_DEF_PROPERTY(graph, visitor);
Chris@16: 
Chris@16:   // These tags are used for property bundles
Chris@16:   // These three are defined in boost/pending/property.hpp
Chris@16:   BOOST_INSTALL_PROPERTY(graph, bundle);
Chris@16:   BOOST_INSTALL_PROPERTY(vertex, bundle);
Chris@16:   BOOST_INSTALL_PROPERTY(edge, bundle);
Chris@16: 
Chris@16:   // These tags are used to denote the owners and local descriptors
Chris@16:   // for the vertices and edges of a distributed graph.
Chris@16:   BOOST_DEF_PROPERTY(vertex, global);
Chris@16:   BOOST_DEF_PROPERTY(vertex, owner);
Chris@16:   BOOST_DEF_PROPERTY(vertex, local);
Chris@16:   BOOST_DEF_PROPERTY(edge, global);
Chris@16:   BOOST_DEF_PROPERTY(edge, owner);
Chris@16:   BOOST_DEF_PROPERTY(edge, local);
Chris@16:   BOOST_DEF_PROPERTY(vertex, local_index);
Chris@16:   BOOST_DEF_PROPERTY(edge, local_index);
Chris@16: 
Chris@16: #undef BOOST_DEF_PROPERTY
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     template <typename G, typename Tag>
Chris@16:     struct property_kind_from_graph: property_kind<Tag> {};
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
Chris@16:     template <typename G, typename R, typename T>
Chris@16:     struct property_kind_from_graph<G, R T::*> {
Chris@16:       typedef typename boost::mpl::if_<
Chris@16:                 boost::is_base_of<T, typename vertex_bundle_type<G>::type>,
Chris@16:                 vertex_property_tag,
Chris@16:                 typename boost::mpl::if_<
Chris@16:                   boost::is_base_of<T, typename edge_bundle_type<G>::type>,
Chris@16:                   edge_property_tag,
Chris@16:                   typename boost::mpl::if_<
Chris@16:                     boost::is_base_of<T, typename graph_bundle_type<G>::type>,
Chris@16:                     graph_property_tag,
Chris@16:                     void>::type>::type>::type type;
Chris@16:     };
Chris@16: #endif
Chris@16: 
Chris@16:     struct dummy_edge_property_selector {
Chris@16:       template <class Graph, class Property, class Tag>
Chris@16:       struct bind_ {
Chris@16:         typedef identity_property_map type;
Chris@16:         typedef identity_property_map const_type;
Chris@16:       };
Chris@16:     };
Chris@16:     struct dummy_vertex_property_selector {
Chris@16:       template <class Graph, class Property, class Tag>
Chris@16:       struct bind_ {
Chris@16:         typedef identity_property_map type;
Chris@16:         typedef identity_property_map const_type;
Chris@16:       };
Chris@16:     };
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   // Graph classes can either partially specialize property_map
Chris@16:   // or they can specialize these two selector classes.
Chris@16:   template <class GraphTag>
Chris@16:   struct edge_property_selector {
Chris@16:     typedef detail::dummy_edge_property_selector type;
Chris@16:   };
Chris@16: 
Chris@16:   template <class GraphTag>
Chris@16:   struct vertex_property_selector {
Chris@16:     typedef detail::dummy_vertex_property_selector type;
Chris@16:   };
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     template <typename A> struct return_void {typedef void type;};
Chris@16: 
Chris@16:     template <typename Graph, typename Enable = void>
Chris@16:     struct graph_tag_or_void {
Chris@16:       typedef void type;
Chris@16:     };
Chris@16: 
Chris@16:     template <typename Graph>
Chris@16:     struct graph_tag_or_void<Graph, typename return_void<typename Graph::graph_tag>::type> {
Chris@16:       typedef typename Graph::graph_tag type;
Chris@16:     };
Chris@16: 
Chris@16:     template <class Graph, class PropertyTag>
Chris@16:     struct edge_property_map
Chris@16:       : edge_property_selector<
Chris@16:           typename graph_tag_or_void<Graph>::type
Chris@16:         >::type::template bind_<
Chris@16:                             Graph,
Chris@16:                             typename edge_property_type<Graph>::type,
Chris@16:                             PropertyTag>
Chris@16:       {};
Chris@16:     template <class Graph, class PropertyTag>
Chris@16:     struct vertex_property_map
Chris@16:       : vertex_property_selector<
Chris@16:           typename graph_tag_or_void<Graph>::type
Chris@16:         >::type::template bind_<
Chris@16:                             Graph,
Chris@16:                             typename vertex_property_type<Graph>::type,
Chris@16:                             PropertyTag>
Chris@16:       {};
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   template <class Graph, class Property, class Enable = void>
Chris@16:   struct property_map:
Chris@16:     mpl::if_<
Chris@16:       is_same<typename detail::property_kind_from_graph<Graph, Property>::type, edge_property_tag>,
Chris@16:       detail::edge_property_map<Graph, Property>,
Chris@16:       detail::vertex_property_map<Graph, Property> >::type
Chris@16:   {};
Chris@16: 
Chris@16:   // shortcut for accessing the value type of the property map
Chris@16:   template <class Graph, class Property>
Chris@16:   class property_map_value {
Chris@16:     typedef typename property_map<Graph, Property>::const_type PMap;
Chris@16:   public:
Chris@16:     typedef typename property_traits<PMap>::value_type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <class Graph, class Property>
Chris@16:   class graph_property {
Chris@16:   public:
Chris@16:     typedef typename property_value<
Chris@16:       typename boost::graph_property_type<Graph>::type, Property
Chris@16:     >::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename Graph> struct vertex_property: vertex_property_type<Graph> {};
Chris@16:   template <typename Graph> struct edge_property: edge_property_type<Graph> {};
Chris@16: 
Chris@16:   template <typename Graph>
Chris@16:   class degree_property_map
Chris@16:     : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
Chris@16:                             degree_property_map<Graph> >
Chris@16:   {
Chris@16:   public:
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor key_type;
Chris@16:     typedef typename graph_traits<Graph>::degree_size_type value_type;
Chris@16:     typedef value_type reference;
Chris@16:     typedef readable_property_map_tag category;
Chris@16:     degree_property_map(const Graph& g) : m_g(g) { }
Chris@16:     value_type operator[](const key_type& v) const {
Chris@16:       return degree(v, m_g);
Chris@16:     }
Chris@16:   private:
Chris@16:     const Graph& m_g;
Chris@16:   };
Chris@16:   template <typename Graph>
Chris@16:   inline degree_property_map<Graph>
Chris@16:   make_degree_map(const Graph& g) {
Chris@16:     return degree_property_map<Graph>(g);
Chris@16:   }
Chris@16: 
Chris@16:   //========================================================================
Chris@16:   // Iterator Property Map Generating Functions contributed by
Chris@16:   // Kevin Vanhorn. (see also the property map generating functions
Chris@16:   // in boost/property_map/property_map.hpp)
Chris@16: 
Chris@16: #if !defined(BOOST_NO_STD_ITERATOR_TRAITS)
Chris@16:   // A helper function for creating a vertex property map out of a
Chris@16:   // random access iterator and the internal vertex index map from a
Chris@16:   // graph.
Chris@16:   template <class PropertyGraph, class RandomAccessIterator>
Chris@16:   inline
Chris@16:   iterator_property_map<
Chris@16:     RandomAccessIterator,
Chris@16:     typename property_map<PropertyGraph, vertex_index_t>::type,
Chris@16:     typename std::iterator_traits<RandomAccessIterator>::value_type,
Chris@16:     typename std::iterator_traits<RandomAccessIterator>::reference
Chris@16:   >
Chris@16:   make_iterator_vertex_map(RandomAccessIterator iter, const PropertyGraph& g)
Chris@16:   {
Chris@16:     return make_iterator_property_map(iter, get(vertex_index, g));
Chris@16:   }
Chris@16: 
Chris@16:   // Use this next function when vertex_descriptor is known to be an
Chris@16:   // integer type, with values ranging from 0 to num_vertices(g).
Chris@16:   //
Chris@16:   template <class RandomAccessIterator>
Chris@16:   inline
Chris@16:   iterator_property_map<
Chris@16:     RandomAccessIterator,
Chris@16:     identity_property_map,
Chris@16:     typename std::iterator_traits<RandomAccessIterator>::value_type,
Chris@16:     typename std::iterator_traits<RandomAccessIterator>::reference
Chris@16:   >
Chris@16:   make_iterator_vertex_map(RandomAccessIterator iter)
Chris@16:   {
Chris@16:     return make_iterator_property_map(iter, identity_property_map());
Chris@16:   }
Chris@16: #endif
Chris@16: 
Chris@16:   template <class PropertyGraph, class RandomAccessContainer>
Chris@16:   inline
Chris@16:   iterator_property_map<
Chris@16:     typename RandomAccessContainer::iterator,
Chris@16:     typename property_map<PropertyGraph, vertex_index_t>::type,
Chris@16:     typename RandomAccessContainer::value_type,
Chris@16:     typename RandomAccessContainer::reference
Chris@16:   >
Chris@16:   make_container_vertex_map(RandomAccessContainer& c, const PropertyGraph& g)
Chris@16:   {
Chris@16:     BOOST_ASSERT(c.size() >= num_vertices(g));
Chris@16:     return make_iterator_vertex_map(c.begin(), g);
Chris@16:   }
Chris@16: 
Chris@16:   template <class RandomAccessContainer> inline
Chris@16:   iterator_property_map<
Chris@16:     typename RandomAccessContainer::iterator,
Chris@16:     identity_property_map,
Chris@16:     typename RandomAccessContainer::value_type,
Chris@16:     typename RandomAccessContainer::reference
Chris@16:   >
Chris@16:   make_container_vertex_map(RandomAccessContainer& c)
Chris@16:   {
Chris@16:     return make_iterator_vertex_map(c.begin());
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16: #if BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x590)) && !defined (BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
Chris@16: // This compiler cannot define a partial specialization based on a
Chris@16: // pointer-to-member type, as seen in boost/graph/subgraph.hpp line 985 (as of
Chris@16: // trunk r53912)
Chris@16: #  define BOOST_GRAPH_NO_BUNDLED_PROPERTIES
Chris@16: #endif
Chris@16: 
Chris@16: // NOTE: These functions are declared, but never defined since they need to
Chris@16: // be overloaded by graph implementations. However, we need them to be
Chris@16: // declared for the functions below.
Chris@16: template<typename Graph, typename Tag>
Chris@16: typename graph_property<Graph, graph_bundle_t>::type&
Chris@16: get_property(Graph& g, Tag);
Chris@16: 
Chris@16: template<typename Graph, typename Tag>
Chris@16: typename graph_property<Graph, graph_bundle_t>::type const&
Chris@16: get_property(Graph const& g, Tag);
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
Chris@16: // NOTE: This operation is a simple adaptor over the overloaded get_property
Chris@16: // operations.
Chris@16: template<typename Graph>
Chris@16: inline typename graph_property<Graph, graph_bundle_t>::type&
Chris@16: get_property(Graph& g) {
Chris@16:   return get_property(g, graph_bundle);
Chris@16: }
Chris@16: 
Chris@16: template<typename Graph>
Chris@16: inline typename graph_property<Graph, graph_bundle_t>::type const&
Chris@16: get_property(const Graph& g) {
Chris@16:   return get_property(g, graph_bundle);
Chris@16: }
Chris@16: #endif
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif /* BOOST_GRAPH_PROPERTIES_HPP */