Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-01-18 09:37:35

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009 
0010 #ifndef BOOST_GRAPH_PROPERTIES_HPP
0011 #define BOOST_GRAPH_PROPERTIES_HPP
0012 
0013 #include <boost/config.hpp>
0014 #include <boost/assert.hpp>
0015 #include <boost/pending/property.hpp>
0016 #include <boost/detail/workaround.hpp>
0017 
0018 // Include the property map library and extensions in the BGL.
0019 #include <boost/property_map/property_map.hpp>
0020 #include <boost/graph/property_maps/constant_property_map.hpp>
0021 #include <boost/graph/property_maps/null_property_map.hpp>
0022 
0023 #include <boost/graph/graph_traits.hpp>
0024 #include <boost/type_traits.hpp>
0025 #include <boost/limits.hpp>
0026 #include <boost/mpl/and.hpp>
0027 #include <boost/mpl/not.hpp>
0028 #include <boost/mpl/if.hpp>
0029 
0030 namespace boost
0031 {
0032 
0033 enum default_color_type
0034 {
0035     white_color,
0036     gray_color,
0037     green_color,
0038     red_color,
0039     black_color
0040 };
0041 
0042 template < class ColorValue > struct color_traits
0043 {
0044     static default_color_type white() { return white_color; }
0045     static default_color_type gray() { return gray_color; }
0046     static default_color_type green() { return green_color; }
0047     static default_color_type red() { return red_color; }
0048     static default_color_type black() { return black_color; }
0049 };
0050 
0051 // These functions are now obsolete, replaced by color_traits.
0052 inline default_color_type white(default_color_type) { return white_color; }
0053 inline default_color_type gray(default_color_type) { return gray_color; }
0054 inline default_color_type green(default_color_type) { return green_color; }
0055 inline default_color_type red(default_color_type) { return red_color; }
0056 inline default_color_type black(default_color_type) { return black_color; }
0057 
0058 struct graph_property_tag
0059 {
0060 };
0061 struct vertex_property_tag
0062 {
0063 };
0064 struct edge_property_tag
0065 {
0066 };
0067 
0068 // See examples/edge_property.cpp for how to use this.
0069 #define BOOST_INSTALL_PROPERTY(KIND, NAME)                \
0070     template <> struct property_kind< KIND##_##NAME##_t > \
0071     {                                                     \
0072         typedef KIND##_property_tag type;                 \
0073     }
0074 
0075 #define BOOST_DEF_PROPERTY(KIND, NAME)        \
0076     enum KIND##_##NAME##_t { KIND##_##NAME }; \
0077     BOOST_INSTALL_PROPERTY(KIND, NAME)
0078 
0079 // These three are defined in boost/pending/property.hpp
0080 BOOST_INSTALL_PROPERTY(vertex, all);
0081 BOOST_INSTALL_PROPERTY(edge, all);
0082 BOOST_INSTALL_PROPERTY(graph, all);
0083 BOOST_DEF_PROPERTY(vertex, index);
0084 BOOST_DEF_PROPERTY(vertex, index1);
0085 BOOST_DEF_PROPERTY(vertex, index2);
0086 BOOST_DEF_PROPERTY(vertex, root);
0087 BOOST_DEF_PROPERTY(edge, index);
0088 BOOST_DEF_PROPERTY(edge, name);
0089 BOOST_DEF_PROPERTY(edge, weight);
0090 BOOST_DEF_PROPERTY(edge, weight2);
0091 BOOST_DEF_PROPERTY(edge, color);
0092 BOOST_DEF_PROPERTY(vertex, name);
0093 BOOST_DEF_PROPERTY(graph, name);
0094 BOOST_DEF_PROPERTY(vertex, distance);
0095 BOOST_DEF_PROPERTY(vertex, distance2);
0096 BOOST_DEF_PROPERTY(vertex, color);
0097 BOOST_DEF_PROPERTY(vertex, degree);
0098 BOOST_DEF_PROPERTY(vertex, in_degree);
0099 BOOST_DEF_PROPERTY(vertex, out_degree);
0100 BOOST_DEF_PROPERTY(vertex, current_degree);
0101 BOOST_DEF_PROPERTY(vertex, priority);
0102 BOOST_DEF_PROPERTY(vertex, discover_time);
0103 BOOST_DEF_PROPERTY(vertex, finish_time);
0104 BOOST_DEF_PROPERTY(vertex, predecessor);
0105 BOOST_DEF_PROPERTY(vertex, rank);
0106 BOOST_DEF_PROPERTY(vertex, centrality);
0107 BOOST_DEF_PROPERTY(vertex, lowpoint);
0108 BOOST_DEF_PROPERTY(vertex, potential);
0109 BOOST_DEF_PROPERTY(vertex, update);
0110 BOOST_DEF_PROPERTY(vertex, underlying);
0111 BOOST_DEF_PROPERTY(edge, reverse);
0112 BOOST_DEF_PROPERTY(edge, capacity);
0113 BOOST_DEF_PROPERTY(edge, flow);
0114 BOOST_DEF_PROPERTY(edge, residual_capacity);
0115 BOOST_DEF_PROPERTY(edge, centrality);
0116 BOOST_DEF_PROPERTY(edge, discover_time);
0117 BOOST_DEF_PROPERTY(edge, update);
0118 BOOST_DEF_PROPERTY(edge, finished);
0119 BOOST_DEF_PROPERTY(edge, underlying);
0120 BOOST_DEF_PROPERTY(graph, visitor);
0121 
0122 // These tags are used for property bundles
0123 // These three are defined in boost/pending/property.hpp
0124 BOOST_INSTALL_PROPERTY(graph, bundle);
0125 BOOST_INSTALL_PROPERTY(vertex, bundle);
0126 BOOST_INSTALL_PROPERTY(edge, bundle);
0127 
0128 // These tags are used to denote the owners and local descriptors
0129 // for the vertices and edges of a distributed graph.
0130 BOOST_DEF_PROPERTY(vertex, global);
0131 BOOST_DEF_PROPERTY(vertex, owner);
0132 BOOST_DEF_PROPERTY(vertex, local);
0133 BOOST_DEF_PROPERTY(edge, global);
0134 BOOST_DEF_PROPERTY(edge, owner);
0135 BOOST_DEF_PROPERTY(edge, local);
0136 BOOST_DEF_PROPERTY(vertex, local_index);
0137 BOOST_DEF_PROPERTY(edge, local_index);
0138 
0139 #undef BOOST_DEF_PROPERTY
0140 
0141 namespace detail
0142 {
0143 
0144     template < typename G, typename Tag >
0145     struct property_kind_from_graph : property_kind< Tag >
0146     {
0147     };
0148 
0149 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
0150     template < typename G, typename R, typename T >
0151     struct property_kind_from_graph< G, R T::* >
0152     {
0153         typedef typename boost::mpl::if_<
0154             boost::is_base_of< T, typename vertex_bundle_type< G >::type >,
0155             vertex_property_tag,
0156             typename boost::mpl::if_<
0157                 boost::is_base_of< T, typename edge_bundle_type< G >::type >,
0158                 edge_property_tag,
0159                 typename boost::mpl::if_<
0160                     boost::is_base_of< T,
0161                         typename graph_bundle_type< G >::type >,
0162                     graph_property_tag, void >::type >::type >::type type;
0163     };
0164 #endif
0165 
0166     struct dummy_edge_property_selector
0167     {
0168         template < class Graph, class Property, class Tag > struct bind_
0169         {
0170             typedef identity_property_map type;
0171             typedef identity_property_map const_type;
0172         };
0173     };
0174     struct dummy_vertex_property_selector
0175     {
0176         template < class Graph, class Property, class Tag > struct bind_
0177         {
0178             typedef identity_property_map type;
0179             typedef identity_property_map const_type;
0180         };
0181     };
0182 
0183 } // namespace detail
0184 
0185 // Graph classes can either partially specialize property_map
0186 // or they can specialize these two selector classes.
0187 template < class GraphTag > struct edge_property_selector
0188 {
0189     typedef detail::dummy_edge_property_selector type;
0190 };
0191 
0192 template < class GraphTag > struct vertex_property_selector
0193 {
0194     typedef detail::dummy_vertex_property_selector type;
0195 };
0196 
0197 namespace detail
0198 {
0199 
0200     template < typename A > struct return_void
0201     {
0202         typedef void type;
0203     };
0204 
0205     template < typename Graph, typename Enable = void > struct graph_tag_or_void
0206     {
0207         typedef void type;
0208     };
0209 
0210     template < typename Graph >
0211     struct graph_tag_or_void< Graph,
0212         typename return_void< typename Graph::graph_tag >::type >
0213     {
0214         typedef typename Graph::graph_tag type;
0215     };
0216 
0217     template < class Graph, class PropertyTag >
0218     struct edge_property_map
0219     : edge_property_selector< typename graph_tag_or_void< Graph >::type >::
0220           type::template bind_< Graph,
0221               typename edge_property_type< Graph >::type, PropertyTag >
0222     {
0223     };
0224     template < class Graph, class PropertyTag >
0225     struct vertex_property_map
0226     : vertex_property_selector< typename graph_tag_or_void< Graph >::type >::
0227           type::template bind_< Graph,
0228               typename vertex_property_type< Graph >::type, PropertyTag >
0229     {
0230     };
0231 } // namespace detail
0232 
0233 template < class Graph, class Property, class Enable = void >
0234 struct property_map
0235 : mpl::if_< is_same< typename detail::property_kind_from_graph< Graph,
0236                          Property >::type,
0237                 edge_property_tag >,
0238       detail::edge_property_map< Graph, Property >,
0239       detail::vertex_property_map< Graph, Property > >::type
0240 {
0241 };
0242 
0243 // shortcut for accessing the value type of the property map
0244 template < class Graph, class Property > class property_map_value
0245 {
0246     typedef typename property_map< Graph, Property >::const_type PMap;
0247 
0248 public:
0249     typedef typename property_traits< PMap >::value_type type;
0250 };
0251 
0252 template < class Graph, class Property > class graph_property
0253 {
0254 public:
0255     typedef typename property_value<
0256         typename boost::graph_property_type< Graph >::type, Property >::type
0257         type;
0258 };
0259 
0260 template < typename Graph >
0261 struct vertex_property : vertex_property_type< Graph >
0262 {
0263 };
0264 template < typename Graph > struct edge_property : edge_property_type< Graph >
0265 {
0266 };
0267 
0268 template < typename Graph >
0269 class degree_property_map
0270 : public put_get_helper< typename graph_traits< Graph >::degree_size_type,
0271       degree_property_map< Graph > >
0272 {
0273 public:
0274     typedef typename graph_traits< Graph >::vertex_descriptor key_type;
0275     typedef typename graph_traits< Graph >::degree_size_type value_type;
0276     typedef value_type reference;
0277     typedef readable_property_map_tag category;
0278     degree_property_map(const Graph& g) : m_g(g) {}
0279     value_type operator[](const key_type& v) const { return degree(v, m_g); }
0280 
0281 private:
0282     const Graph& m_g;
0283 };
0284 template < typename Graph >
0285 inline degree_property_map< Graph > make_degree_map(const Graph& g)
0286 {
0287     return degree_property_map< Graph >(g);
0288 }
0289 
0290 //========================================================================
0291 // Iterator Property Map Generating Functions contributed by
0292 // Kevin Vanhorn. (see also the property map generating functions
0293 // in boost/property_map/property_map.hpp)
0294 
0295 #if !defined(BOOST_NO_STD_ITERATOR_TRAITS)
0296 // A helper function for creating a vertex property map out of a
0297 // random access iterator and the internal vertex index map from a
0298 // graph.
0299 template < class PropertyGraph, class RandomAccessIterator >
0300 inline iterator_property_map< RandomAccessIterator,
0301     typename property_map< PropertyGraph, vertex_index_t >::type,
0302     typename std::iterator_traits< RandomAccessIterator >::value_type,
0303     typename std::iterator_traits< RandomAccessIterator >::reference >
0304 make_iterator_vertex_map(RandomAccessIterator iter, const PropertyGraph& g)
0305 {
0306     return make_iterator_property_map(iter, get(vertex_index, g));
0307 }
0308 
0309 // Use this next function when vertex_descriptor is known to be an
0310 // integer type, with values ranging from 0 to num_vertices(g).
0311 //
0312 template < class RandomAccessIterator >
0313 inline iterator_property_map< RandomAccessIterator, identity_property_map,
0314     typename std::iterator_traits< RandomAccessIterator >::value_type,
0315     typename std::iterator_traits< RandomAccessIterator >::reference >
0316 make_iterator_vertex_map(RandomAccessIterator iter)
0317 {
0318     return make_iterator_property_map(iter, identity_property_map());
0319 }
0320 #endif
0321 
0322 template < class PropertyGraph, class RandomAccessContainer >
0323 inline iterator_property_map< typename RandomAccessContainer::iterator,
0324     typename property_map< PropertyGraph, vertex_index_t >::type,
0325     typename RandomAccessContainer::value_type,
0326     typename RandomAccessContainer::reference >
0327 make_container_vertex_map(RandomAccessContainer& c, const PropertyGraph& g)
0328 {
0329     BOOST_ASSERT(c.size() >= num_vertices(g));
0330     return make_iterator_vertex_map(c.begin(), g);
0331 }
0332 
0333 template < class RandomAccessContainer >
0334 inline iterator_property_map< typename RandomAccessContainer::iterator,
0335     identity_property_map, typename RandomAccessContainer::value_type,
0336     typename RandomAccessContainer::reference >
0337 make_container_vertex_map(RandomAccessContainer& c)
0338 {
0339     return make_iterator_vertex_map(c.begin());
0340 }
0341 
0342 // NOTE: These functions are declared, but never defined since they need to
0343 // be overloaded by graph implementations. However, we need them to be
0344 // declared for the functions below.
0345 template < typename Graph, typename Tag >
0346 typename graph_property< Graph, graph_bundle_t >::type& get_property(
0347     Graph& g, Tag);
0348 
0349 template < typename Graph, typename Tag >
0350 typename graph_property< Graph, graph_bundle_t >::type const& get_property(
0351     Graph const& g, Tag);
0352 
0353 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
0354 // NOTE: This operation is a simple adaptor over the overloaded get_property
0355 // operations.
0356 template < typename Graph >
0357 inline typename graph_property< Graph, graph_bundle_t >::type& get_property(
0358     Graph& g)
0359 {
0360     return get_property(g, graph_bundle);
0361 }
0362 
0363 template < typename Graph >
0364 inline typename graph_property< Graph, graph_bundle_t >::type const&
0365 get_property(const Graph& g)
0366 {
0367     return get_property(g, graph_bundle);
0368 }
0369 #endif
0370 
0371 } // namespace boost
0372 
0373 #endif /* BOOST_GRAPH_PROPERTIES_HPP */