williamr@2: //======================================================================= williamr@2: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek williamr@2: // williamr@2: // Distributed under the Boost Software License, Version 1.0. (See williamr@2: // accompanying file LICENSE_1_0.txt or copy at williamr@2: // http://www.boost.org/LICENSE_1_0.txt) williamr@2: //======================================================================= williamr@2: #ifndef BOOST_GRAPH_PROPERTIES_HPP williamr@2: #define BOOST_GRAPH_PROPERTIES_HPP williamr@2: williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: williamr@2: namespace boost { williamr@2: williamr@2: enum default_color_type { white_color, gray_color, green_color, red_color, black_color }; williamr@2: williamr@2: template williamr@2: struct color_traits { williamr@2: static default_color_type white() { return white_color; } williamr@2: static default_color_type gray() { return gray_color; } williamr@2: static default_color_type green() { return green_color; } williamr@2: static default_color_type red() { return red_color; } williamr@2: static default_color_type black() { return black_color; } williamr@2: }; williamr@2: williamr@2: // These functions are now obsolete, replaced by color_traits. williamr@2: inline default_color_type white(default_color_type) { return white_color; } williamr@2: inline default_color_type gray(default_color_type) { return gray_color; } williamr@2: inline default_color_type green(default_color_type) { return green_color; } williamr@2: inline default_color_type red(default_color_type) { return red_color; } williamr@2: inline default_color_type black(default_color_type) { return black_color; } williamr@2: williamr@2: #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION williamr@2: template <> williamr@2: struct property_traits { williamr@2: typedef default_color_type value_type; williamr@2: typedef std::ptrdiff_t key_type; williamr@2: typedef default_color_type& reference; williamr@2: typedef lvalue_property_map_tag category; williamr@2: }; williamr@2: // get/put already defined for T* williamr@2: #endif williamr@2: williamr@2: struct graph_property_tag { }; williamr@2: struct vertex_property_tag { }; williamr@2: struct edge_property_tag { }; williamr@2: williamr@2: #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION williamr@2: // See examples/edge_property.cpp for how to use this. williamr@2: #define BOOST_INSTALL_PROPERTY(KIND, NAME) \ williamr@2: template <> struct property_kind { \ williamr@2: typedef KIND##_property_tag type; \ williamr@2: } williamr@2: #else williamr@2: #define BOOST_INSTALL_PROPERTY(KIND, NAME) \ williamr@2: template <> struct property_kind { \ williamr@2: typedef KIND##_property_tag type; \ williamr@2: } williamr@2: #endif williamr@2: williamr@2: #define BOOST_DEF_PROPERTY(KIND, NAME) \ williamr@2: enum KIND##_##NAME##_t { KIND##_##NAME }; \ williamr@2: BOOST_INSTALL_PROPERTY(KIND, NAME) williamr@2: williamr@2: BOOST_DEF_PROPERTY(vertex, all); williamr@2: BOOST_DEF_PROPERTY(edge, all); williamr@2: BOOST_DEF_PROPERTY(graph, all); williamr@2: BOOST_DEF_PROPERTY(vertex, index); williamr@2: BOOST_DEF_PROPERTY(vertex, index1); williamr@2: BOOST_DEF_PROPERTY(vertex, index2); williamr@2: BOOST_DEF_PROPERTY(vertex, root); williamr@2: BOOST_DEF_PROPERTY(edge, index); williamr@2: BOOST_DEF_PROPERTY(edge, name); williamr@2: BOOST_DEF_PROPERTY(edge, weight); williamr@2: BOOST_DEF_PROPERTY(edge, weight2); williamr@2: BOOST_DEF_PROPERTY(edge, color); williamr@2: BOOST_DEF_PROPERTY(vertex, name); williamr@2: BOOST_DEF_PROPERTY(graph, name); williamr@2: BOOST_DEF_PROPERTY(vertex, distance); williamr@2: BOOST_DEF_PROPERTY(vertex, color); williamr@2: BOOST_DEF_PROPERTY(vertex, degree); williamr@2: BOOST_DEF_PROPERTY(vertex, in_degree); williamr@2: BOOST_DEF_PROPERTY(vertex, out_degree); williamr@2: BOOST_DEF_PROPERTY(vertex, current_degree); williamr@2: BOOST_DEF_PROPERTY(vertex, priority); williamr@2: BOOST_DEF_PROPERTY(vertex, discover_time); williamr@2: BOOST_DEF_PROPERTY(vertex, finish_time); williamr@2: BOOST_DEF_PROPERTY(vertex, predecessor); williamr@2: BOOST_DEF_PROPERTY(vertex, rank); williamr@2: BOOST_DEF_PROPERTY(vertex, centrality); williamr@2: BOOST_DEF_PROPERTY(vertex, lowpoint); williamr@2: BOOST_DEF_PROPERTY(edge, reverse); williamr@2: BOOST_DEF_PROPERTY(edge, capacity); williamr@2: BOOST_DEF_PROPERTY(edge, residual_capacity); williamr@2: BOOST_DEF_PROPERTY(edge, centrality); williamr@2: BOOST_DEF_PROPERTY(graph, visitor); williamr@2: williamr@2: // These tags are used for property bundles williamr@2: BOOST_DEF_PROPERTY(vertex, bundle); williamr@2: BOOST_DEF_PROPERTY(edge, bundle); williamr@2: williamr@2: #undef BOOST_DEF_PROPERTY williamr@2: williamr@2: namespace detail { williamr@2: williamr@2: struct dummy_edge_property_selector { williamr@2: template williamr@2: struct bind_ { williamr@2: typedef identity_property_map type; williamr@2: typedef identity_property_map const_type; williamr@2: }; williamr@2: }; williamr@2: struct dummy_vertex_property_selector { williamr@2: template williamr@2: struct bind_ { williamr@2: typedef identity_property_map type; williamr@2: typedef identity_property_map const_type; williamr@2: }; williamr@2: }; williamr@2: williamr@2: } // namespace detail williamr@2: williamr@2: // Graph classes can either partially specialize property_map williamr@2: // or they can specialize these two selector classes. williamr@2: template williamr@2: struct edge_property_selector { williamr@2: typedef detail::dummy_edge_property_selector type; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct vertex_property_selector { williamr@2: typedef detail::dummy_vertex_property_selector type; williamr@2: }; williamr@2: williamr@2: namespace detail { williamr@2: williamr@2: template williamr@2: struct edge_property_map { williamr@2: typedef typename Graph::edge_property_type Property; williamr@2: typedef typename Graph::graph_tag graph_tag; williamr@2: typedef typename edge_property_selector::type Selector; williamr@2: typedef typename Selector::template bind_ williamr@2: Bind; williamr@2: typedef typename Bind::type type; williamr@2: typedef typename Bind::const_type const_type; williamr@2: }; williamr@2: template williamr@2: class vertex_property_map { williamr@2: typedef typename Graph::vertex_property_type Property; williamr@2: typedef typename Graph::graph_tag graph_tag; williamr@2: typedef typename vertex_property_selector::type Selector; williamr@2: typedef typename Selector::template bind_ williamr@2: Bind; williamr@2: public: williamr@2: typedef typename Bind::type type; williamr@2: typedef typename Bind::const_type const_type; williamr@2: }; williamr@2: williamr@2: // This selects the kind of property map, whether is maps from williamr@2: // edges or from vertices. williamr@2: // williamr@2: // It is overly complicated because it's a workaround for williamr@2: // partial specialization. williamr@2: struct choose_vertex_property_map { williamr@2: template williamr@2: struct bind_ { williamr@2: typedef vertex_property_map type; williamr@2: }; williamr@2: }; williamr@2: struct choose_edge_property_map { williamr@2: template williamr@2: struct bind_ { williamr@2: typedef edge_property_map type; williamr@2: }; williamr@2: }; williamr@2: template williamr@2: struct property_map_kind_selector { williamr@2: // VC++ gets confused if this isn't defined, even though williamr@2: // this never gets used. williamr@2: typedef choose_vertex_property_map type; williamr@2: }; williamr@2: template <> struct property_map_kind_selector { williamr@2: typedef choose_vertex_property_map type; williamr@2: }; williamr@2: template <> struct property_map_kind_selector { williamr@2: typedef choose_edge_property_map type; williamr@2: }; williamr@2: } // namespace detail williamr@2: williamr@2: template williamr@2: struct property_map { williamr@2: private: williamr@2: typedef typename property_kind::type Kind; williamr@2: typedef typename detail::property_map_kind_selector::type Selector; williamr@2: typedef typename Selector::template bind_ Bind; williamr@2: typedef typename Bind::type Map; williamr@2: public: williamr@2: typedef typename Map::type type; williamr@2: typedef typename Map::const_type const_type; williamr@2: }; williamr@2: williamr@2: // shortcut for accessing the value type of the property map williamr@2: template williamr@2: class property_map_value { williamr@2: typedef typename property_map::const_type PMap; williamr@2: public: williamr@2: typedef typename property_traits::value_type type; williamr@2: }; williamr@2: williamr@2: template williamr@2: class graph_property { williamr@2: public: williamr@2: typedef typename property_value::type type; williamr@2: }; williamr@2: williamr@2: template williamr@2: class vertex_property { williamr@2: public: williamr@2: typedef typename Graph::vertex_property_type type; williamr@2: }; williamr@2: template williamr@2: class edge_property { williamr@2: public: williamr@2: typedef typename Graph::edge_property_type type; williamr@2: }; williamr@2: williamr@2: template williamr@2: class degree_property_map williamr@2: : public put_get_helper::degree_size_type, williamr@2: degree_property_map > williamr@2: { williamr@2: public: williamr@2: typedef typename graph_traits::vertex_descriptor key_type; williamr@2: typedef typename graph_traits::degree_size_type value_type; williamr@2: typedef value_type reference; williamr@2: typedef readable_property_map_tag category; williamr@2: degree_property_map(const Graph& g) : m_g(g) { } williamr@2: value_type operator[](const key_type& v) const { williamr@2: return degree(v, m_g); williamr@2: } williamr@2: private: williamr@2: const Graph& m_g; williamr@2: }; williamr@2: template williamr@2: inline degree_property_map williamr@2: make_degree_map(const Graph& g) { williamr@2: return degree_property_map(g); williamr@2: } williamr@2: williamr@2: //======================================================================== williamr@2: // Iterator Property Map Generating Functions contributed by williamr@2: // Kevin Vanhorn. (see also the property map generating functions williamr@2: // in boost/property_map.hpp) williamr@2: williamr@2: #if !defined(BOOST_NO_STD_ITERATOR_TRAITS) williamr@2: // A helper function for creating a vertex property map out of a williamr@2: // random access iterator and the internal vertex index map from a williamr@2: // graph. williamr@2: template williamr@2: inline williamr@2: iterator_property_map< williamr@2: RandomAccessIterator, williamr@2: typename property_map::type, williamr@2: typename std::iterator_traits::value_type, williamr@2: typename std::iterator_traits::reference williamr@2: > williamr@2: make_iterator_vertex_map(RandomAccessIterator iter, const PropertyGraph& g) williamr@2: { williamr@2: return make_iterator_property_map(iter, get(vertex_index, g)); williamr@2: } williamr@2: williamr@2: // Use this next function when vertex_descriptor is known to be an williamr@2: // integer type, with values ranging from 0 to num_vertices(g). williamr@2: // williamr@2: template williamr@2: inline williamr@2: iterator_property_map< williamr@2: RandomAccessIterator, williamr@2: identity_property_map, williamr@2: typename std::iterator_traits::value_type, williamr@2: typename std::iterator_traits::reference williamr@2: > williamr@2: make_iterator_vertex_map(RandomAccessIterator iter) williamr@2: { williamr@2: return make_iterator_property_map(iter, identity_property_map()); williamr@2: } williamr@2: #endif williamr@2: williamr@2: template williamr@2: inline williamr@2: iterator_property_map< williamr@2: typename RandomAccessContainer::iterator, williamr@2: typename property_map::type, williamr@2: typename RandomAccessContainer::value_type, williamr@2: typename RandomAccessContainer::reference williamr@2: > williamr@2: make_container_vertex_map(RandomAccessContainer& c, const PropertyGraph& g) williamr@2: { williamr@2: assert(c.size() >= num_vertices(g)); williamr@2: return make_iterator_vertex_map(c.begin(), g); williamr@2: } williamr@2: williamr@2: template inline williamr@2: iterator_property_map< williamr@2: typename RandomAccessContainer::iterator, williamr@2: identity_property_map, williamr@2: typename RandomAccessContainer::value_type, williamr@2: typename RandomAccessContainer::reference williamr@2: > williamr@2: make_container_vertex_map(RandomAccessContainer& c) williamr@2: { williamr@2: return make_iterator_vertex_map(c.begin()); williamr@2: } williamr@2: williamr@2: #if defined (BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) williamr@2: # define BOOST_GRAPH_NO_BUNDLED_PROPERTIES williamr@2: #endif williamr@2: williamr@2: #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES williamr@2: template williamr@2: struct bundle_property_map williamr@2: : put_get_helper > williamr@2: { williamr@2: typedef Descriptor key_type; williamr@2: typedef T value_type; williamr@2: typedef T& reference; williamr@2: typedef lvalue_property_map_tag category; williamr@2: williamr@2: bundle_property_map() { } williamr@2: bundle_property_map(Graph* g_, T Bundle::* pm_) : g(g_), pm(pm_) {} williamr@2: williamr@2: reference operator[](key_type k) const { return (*g)[k].*pm; } williamr@2: private: williamr@2: Graph* g; williamr@2: T Bundle::* pm; williamr@2: }; williamr@2: williamr@2: namespace detail { williamr@2: template williamr@2: struct is_vertex_bundle : is_convertible {}; williamr@2: } williamr@2: williamr@2: template williamr@2: struct property_map williamr@2: { williamr@2: private: williamr@2: typedef graph_traits traits; williamr@2: typedef typename Graph::vertex_bundled vertex_bundled; williamr@2: typedef typename Graph::edge_bundled edge_bundled; williamr@2: typedef typename ct_if<(detail::is_vertex_bundle::value), williamr@2: typename traits::vertex_descriptor, williamr@2: typename traits::edge_descriptor>::type williamr@2: descriptor; williamr@2: typedef typename ct_if<(detail::is_vertex_bundle::value), williamr@2: vertex_bundled, williamr@2: edge_bundled>::type williamr@2: actual_bundle; williamr@2: williamr@2: public: williamr@2: typedef bundle_property_map type; williamr@2: typedef bundle_property_map williamr@2: const_type; williamr@2: }; williamr@2: #endif williamr@2: williamr@2: } // namespace boost williamr@2: williamr@2: #endif /* BOOST_GRAPH_PROPERTIES_HPPA */