File indexing completed on 2025-01-18 09:37:35
0001
0002
0003
0004
0005
0006
0007
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
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
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
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
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
0123
0124 BOOST_INSTALL_PROPERTY(graph, bundle);
0125 BOOST_INSTALL_PROPERTY(vertex, bundle);
0126 BOOST_INSTALL_PROPERTY(edge, bundle);
0127
0128
0129
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 }
0184
0185
0186
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 }
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
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
0292
0293
0294
0295 #if !defined(BOOST_NO_STD_ITERATOR_TRAITS)
0296
0297
0298
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
0310
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
0343
0344
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
0355
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 }
0372
0373 #endif