1 //=======================================================================

     2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

     3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

     4 //

     5 // Distributed under the Boost Software License, Version 1.0. (See

     6 // accompanying file LICENSE_1_0.txt or copy at

     7 // http://www.boost.org/LICENSE_1_0.txt)

     8 //=======================================================================

     9 #ifndef BOOST_GRAPH_PROPERTIES_HPP

    10 #define BOOST_GRAPH_PROPERTIES_HPP

    11 

    12 #include <boost/config.hpp>

    13 #include <cassert>

    14 #include <boost/pending/property.hpp>

    15 #include <boost/property_map.hpp>

    16 #include <boost/graph/graph_traits.hpp>

    17 #include <boost/type_traits/is_convertible.hpp>

    18 

    19 namespace boost {

    20 

    21   enum default_color_type { white_color, gray_color, green_color, red_color, black_color };

    22 

    23   template <class ColorValue>

    24   struct color_traits {

    25     static default_color_type white() { return white_color; }

    26     static default_color_type gray() { return gray_color; }

    27     static default_color_type green() { return green_color; }

    28     static default_color_type red() { return red_color; }

    29     static default_color_type black() { return black_color; }

    30   };

    31   

    32   // These functions are now obsolete, replaced by color_traits.

    33   inline default_color_type white(default_color_type) { return white_color; }

    34   inline default_color_type gray(default_color_type) { return gray_color; }

    35   inline default_color_type green(default_color_type) { return green_color; }

    36   inline default_color_type red(default_color_type) { return red_color; } 

    37   inline default_color_type black(default_color_type) { return black_color; }

    38 

    39 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

    40   template <>

    41   struct property_traits<default_color_type*> {

    42     typedef default_color_type value_type;

    43     typedef std::ptrdiff_t key_type;

    44     typedef default_color_type& reference;

    45     typedef lvalue_property_map_tag category;

    46   };

    47   // get/put already defined for T*

    48 #endif

    49 

    50   struct graph_property_tag { };

    51   struct vertex_property_tag { };

    52   struct edge_property_tag { };

    53 

    54 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

    55   // See examples/edge_property.cpp for how to use this.

    56 #define BOOST_INSTALL_PROPERTY(KIND, NAME) \

    57   template <> struct property_kind<KIND##_##NAME##_t> { \

    58     typedef KIND##_property_tag type; \

    59   }

    60 #else

    61 #define BOOST_INSTALL_PROPERTY(KIND, NAME) \

    62   template <> struct property_kind<KIND##_##NAME##_t> { \

    63     typedef KIND##_property_tag type; \

    64   }

    65 #endif

    66 

    67 #define BOOST_DEF_PROPERTY(KIND, NAME) \

    68   enum KIND##_##NAME##_t { KIND##_##NAME }; \

    69   BOOST_INSTALL_PROPERTY(KIND, NAME)

    70 

    71   BOOST_DEF_PROPERTY(vertex, all);

    72   BOOST_DEF_PROPERTY(edge, all);

    73   BOOST_DEF_PROPERTY(graph, all);

    74   BOOST_DEF_PROPERTY(vertex, index);

    75   BOOST_DEF_PROPERTY(vertex, index1);

    76   BOOST_DEF_PROPERTY(vertex, index2);

    77   BOOST_DEF_PROPERTY(vertex, root);

    78   BOOST_DEF_PROPERTY(edge, index);

    79   BOOST_DEF_PROPERTY(edge, name);

    80   BOOST_DEF_PROPERTY(edge, weight);

    81   BOOST_DEF_PROPERTY(edge, weight2);

    82   BOOST_DEF_PROPERTY(edge, color);

    83   BOOST_DEF_PROPERTY(vertex, name);

    84   BOOST_DEF_PROPERTY(graph, name);

    85   BOOST_DEF_PROPERTY(vertex, distance);

    86   BOOST_DEF_PROPERTY(vertex, color);

    87   BOOST_DEF_PROPERTY(vertex, degree);

    88   BOOST_DEF_PROPERTY(vertex, in_degree);

    89   BOOST_DEF_PROPERTY(vertex, out_degree);

    90   BOOST_DEF_PROPERTY(vertex, current_degree);

    91   BOOST_DEF_PROPERTY(vertex, priority); 

    92   BOOST_DEF_PROPERTY(vertex, discover_time);

    93   BOOST_DEF_PROPERTY(vertex, finish_time);

    94   BOOST_DEF_PROPERTY(vertex, predecessor);

    95   BOOST_DEF_PROPERTY(vertex, rank);

    96   BOOST_DEF_PROPERTY(vertex, centrality);

    97   BOOST_DEF_PROPERTY(vertex, lowpoint);

    98   BOOST_DEF_PROPERTY(edge, reverse);

    99   BOOST_DEF_PROPERTY(edge, capacity);

   100   BOOST_DEF_PROPERTY(edge, residual_capacity);

   101   BOOST_DEF_PROPERTY(edge, centrality);

   102   BOOST_DEF_PROPERTY(graph, visitor);

   103 

   104   // These tags are used for property bundles

   105   BOOST_DEF_PROPERTY(vertex, bundle);

   106   BOOST_DEF_PROPERTY(edge, bundle);

   107 

   108 #undef BOOST_DEF_PROPERTY

   109 

   110   namespace detail {

   111 

   112     struct dummy_edge_property_selector {

   113       template <class Graph, class Property, class Tag>

   114       struct bind_ {

   115         typedef identity_property_map type;

   116         typedef identity_property_map const_type;

   117       };

   118     };

   119     struct dummy_vertex_property_selector {

   120       template <class Graph, class Property, class Tag>

   121       struct bind_ {

   122         typedef identity_property_map type;

   123         typedef identity_property_map const_type;

   124       };

   125     };

   126 

   127   } // namespace detail

   128 

   129   // Graph classes can either partially specialize property_map

   130   // or they can specialize these two selector classes.

   131   template <class GraphTag>

   132   struct edge_property_selector {

   133     typedef detail::dummy_edge_property_selector type;

   134   };

   135 

   136   template <class GraphTag>

   137   struct vertex_property_selector {

   138     typedef detail::dummy_vertex_property_selector type;

   139   };

   140 

   141   namespace detail {

   142 

   143     template <class Graph, class PropertyTag>

   144     struct edge_property_map {

   145       typedef typename Graph::edge_property_type Property;

   146       typedef typename Graph::graph_tag graph_tag;

   147       typedef typename edge_property_selector<graph_tag>::type Selector;

   148       typedef typename Selector::template bind_<Graph,Property,PropertyTag>

   149         Bind;

   150       typedef typename Bind::type type;

   151       typedef typename Bind::const_type const_type;

   152     };

   153     template <class Graph, class PropertyTag>

   154     class vertex_property_map {

   155       typedef typename Graph::vertex_property_type Property;

   156       typedef typename Graph::graph_tag graph_tag;

   157       typedef typename vertex_property_selector<graph_tag>::type Selector;

   158       typedef typename Selector::template bind_<Graph,Property,PropertyTag>

   159         Bind;

   160     public:

   161       typedef typename Bind::type type;

   162       typedef typename Bind::const_type const_type;

   163     };

   164 

   165     // This selects the kind of property map, whether is maps from

   166     // edges or from vertices.

   167     //

   168     // It is overly complicated because it's a workaround for

   169     // partial specialization.

   170     struct choose_vertex_property_map {

   171       template <class Graph, class Property>

   172       struct bind_ {

   173         typedef vertex_property_map<Graph, Property> type;

   174       };

   175     };

   176     struct choose_edge_property_map {

   177       template <class Graph, class Property>

   178       struct bind_ {

   179         typedef edge_property_map<Graph, Property> type;

   180       };

   181     };

   182     template <class Kind>

   183     struct property_map_kind_selector {

   184       // VC++ gets confused if this isn't defined, even though

   185       // this never gets used.

   186       typedef choose_vertex_property_map type;

   187     };

   188     template <> struct property_map_kind_selector<vertex_property_tag> {

   189       typedef choose_vertex_property_map type;

   190     };

   191     template <> struct property_map_kind_selector<edge_property_tag> {

   192       typedef choose_edge_property_map type;

   193     };

   194   } // namespace detail

   195 

   196   template <class Graph, class Property>

   197   struct property_map {

   198   private:

   199     typedef typename property_kind<Property>::type Kind;

   200     typedef typename detail::property_map_kind_selector<Kind>::type Selector;

   201     typedef typename Selector::template bind_<Graph, Property> Bind;

   202     typedef typename Bind::type Map;

   203   public:

   204     typedef typename Map::type type;

   205     typedef typename Map::const_type const_type;

   206   };

   207 

   208   // shortcut for accessing the value type of the property map

   209   template <class Graph, class Property>

   210   class property_map_value {

   211     typedef typename property_map<Graph, Property>::const_type PMap;

   212   public:

   213     typedef typename property_traits<PMap>::value_type type;

   214   };

   215 

   216   template <class Graph, class Property>

   217   class graph_property {

   218   public:

   219     typedef typename property_value<typename Graph::graph_property_type, 

   220       Property>::type type;

   221   };

   222 

   223   template <class Graph>

   224   class vertex_property {

   225   public:

   226     typedef typename Graph::vertex_property_type type;

   227   };

   228   template <class Graph>

   229   class edge_property {

   230   public:

   231     typedef typename Graph::edge_property_type type;

   232   };

   233 

   234   template <typename Graph>

   235   class degree_property_map 

   236     : public put_get_helper<typename graph_traits<Graph>::degree_size_type,

   237                             degree_property_map<Graph> >                  

   238   {

   239   public:

   240     typedef typename graph_traits<Graph>::vertex_descriptor key_type;

   241     typedef typename graph_traits<Graph>::degree_size_type value_type;

   242     typedef value_type reference;

   243     typedef readable_property_map_tag category;

   244     degree_property_map(const Graph& g) : m_g(g) { }

   245     value_type operator[](const key_type& v) const {

   246       return degree(v, m_g);

   247     }

   248   private:

   249     const Graph& m_g;

   250   };

   251   template <typename Graph>

   252   inline degree_property_map<Graph>

   253   make_degree_map(const Graph& g) {

   254     return degree_property_map<Graph>(g);

   255   }

   256 

   257   //========================================================================

   258   // Iterator Property Map Generating Functions contributed by 

   259   // Kevin Vanhorn. (see also the property map generating functions

   260   // in boost/property_map.hpp)

   261 

   262 #if !defined(BOOST_NO_STD_ITERATOR_TRAITS)

   263   // A helper function for creating a vertex property map out of a

   264   // random access iterator and the internal vertex index map from a

   265   // graph.

   266   template <class PropertyGraph, class RandomAccessIterator>

   267   inline

   268   iterator_property_map<

   269     RandomAccessIterator,

   270     typename property_map<PropertyGraph, vertex_index_t>::type,

   271     typename std::iterator_traits<RandomAccessIterator>::value_type,

   272     typename std::iterator_traits<RandomAccessIterator>::reference

   273   >

   274   make_iterator_vertex_map(RandomAccessIterator iter, const PropertyGraph& g)

   275   {

   276     return make_iterator_property_map(iter, get(vertex_index, g));

   277   }  

   278   

   279   // Use this next function when vertex_descriptor is known to be an

   280   // integer type, with values ranging from 0 to num_vertices(g).

   281   //

   282   template <class RandomAccessIterator>

   283   inline

   284   iterator_property_map<

   285     RandomAccessIterator,

   286     identity_property_map,

   287     typename std::iterator_traits<RandomAccessIterator>::value_type,

   288     typename std::iterator_traits<RandomAccessIterator>::reference

   289   >

   290   make_iterator_vertex_map(RandomAccessIterator iter)

   291   {

   292     return make_iterator_property_map(iter, identity_property_map());

   293   }      

   294 #endif

   295 

   296   template <class PropertyGraph, class RandomAccessContainer>

   297   inline

   298   iterator_property_map<

   299     typename RandomAccessContainer::iterator,

   300     typename property_map<PropertyGraph, vertex_index_t>::type,

   301     typename RandomAccessContainer::value_type,

   302     typename RandomAccessContainer::reference

   303   >

   304   make_container_vertex_map(RandomAccessContainer& c, const PropertyGraph& g)

   305   {

   306     assert(c.size() >= num_vertices(g));

   307     return make_iterator_vertex_map(c.begin(), g);

   308   }   

   309 

   310   template <class RandomAccessContainer> inline

   311   iterator_property_map<

   312     typename RandomAccessContainer::iterator,

   313     identity_property_map,

   314     typename RandomAccessContainer::value_type,

   315     typename RandomAccessContainer::reference

   316   >

   317   make_container_vertex_map(RandomAccessContainer& c)

   318   {

   319     return make_iterator_vertex_map(c.begin());

   320   }

   321 

   322 #if defined (BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)

   323 #  define BOOST_GRAPH_NO_BUNDLED_PROPERTIES

   324 #endif

   325 

   326 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES

   327   template<typename Graph, typename Descriptor, typename Bundle, typename T>

   328   struct bundle_property_map

   329     : put_get_helper<T&, bundle_property_map<Graph, Descriptor, Bundle, T> >

   330   {

   331     typedef Descriptor key_type;

   332     typedef T value_type;

   333     typedef T& reference;

   334     typedef lvalue_property_map_tag category;

   335  

   336     bundle_property_map() { }

   337     bundle_property_map(Graph* g_, T Bundle::* pm_) : g(g_), pm(pm_) {}

   338 

   339     reference operator[](key_type k) const { return (*g)[k].*pm; }

   340   private:

   341     Graph* g;

   342     T Bundle::* pm;

   343   };

   344 

   345   namespace detail {

   346     template<typename VertexBundle, typename EdgeBundle, typename Bundle>

   347       struct is_vertex_bundle : is_convertible<VertexBundle*, Bundle*> {};

   348   }

   349   

   350   template <typename Graph, typename T, typename Bundle>

   351   struct property_map<Graph, T Bundle::*>  

   352   {

   353   private:

   354     typedef graph_traits<Graph> traits;

   355     typedef typename Graph::vertex_bundled vertex_bundled;

   356     typedef typename Graph::edge_bundled edge_bundled;

   357     typedef typename ct_if<(detail::is_vertex_bundle<vertex_bundled, edge_bundled, Bundle>::value),

   358                        typename traits::vertex_descriptor,

   359                        typename traits::edge_descriptor>::type

   360       descriptor;

   361     typedef typename ct_if<(detail::is_vertex_bundle<vertex_bundled, edge_bundled, Bundle>::value),

   362                        vertex_bundled,

   363                        edge_bundled>::type

   364       actual_bundle;

   365     

   366   public:

   367     typedef bundle_property_map<Graph, descriptor, actual_bundle, T> type;

   368     typedef bundle_property_map<const Graph, descriptor, actual_bundle, const T>

   369       const_type;

   370   };

   371 #endif

   372 

   373 } // namespace boost

   374 

   375 #endif /* BOOST_GRAPH_PROPERTIES_HPPA */