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 10 #ifndef BOOST_GRAPH_PROPERTIES_HPP 11 #define BOOST_GRAPH_PROPERTIES_HPP 12 13 #include <boost/config.hpp> 14 #include <boost/assert.hpp> 15 #include <boost/pending/property.hpp> 16 #include <boost/detail/workaround.hpp> 17 18 // Include the property map library and extensions in the BGL. 19 #include <boost/property_map/property_map.hpp> 20 #include <boost/graph/property_maps/constant_property_map.hpp> 21 #include <boost/graph/property_maps/null_property_map.hpp> 22 23 #include <boost/graph/graph_traits.hpp> 24 #include <boost/type_traits.hpp> 25 #include <boost/limits.hpp> 26 #include <boost/mpl/and.hpp> 27 #include <boost/mpl/not.hpp> 28 #include <boost/mpl/if.hpp> 29 30 namespace boost { 31 32 enum default_color_type { white_color, gray_color, green_color, red_color, black_color }; 33 34 template <class ColorValue> 35 struct color_traits { is_reg(void)36 static default_color_type white() { return white_color; } 37 static default_color_type gray() { return gray_color; } 38 static default_color_type green() { return green_color; } 39 static default_color_type red() { return red_color; } 40 static default_color_type black() { return black_color; } 41 }; 42 43 // These functions are now obsolete, replaced by color_traits. 44 inline default_color_type white(default_color_type) { return white_color; } 45 inline default_color_type gray(default_color_type) { return gray_color; } 46 inline default_color_type green(default_color_type) { return green_color; } 47 inline default_color_type red(default_color_type) { return red_color; } 48 inline default_color_type black(default_color_type) { return black_color; } type_to_mode(ftype3 ftype)49 50 51 struct graph_property_tag { }; 52 struct vertex_property_tag { }; 53 struct edge_property_tag { }; 54 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 61 #define BOOST_DEF_PROPERTY(KIND, NAME) \ 62 enum KIND##_##NAME##_t { KIND##_##NAME }; \ 63 BOOST_INSTALL_PROPERTY(KIND, NAME) 64 65 // These three are defined in boost/pending/property.hpp 66 BOOST_INSTALL_PROPERTY(vertex, all); 67 BOOST_INSTALL_PROPERTY(edge, all); 68 BOOST_INSTALL_PROPERTY(graph, all); 69 BOOST_DEF_PROPERTY(vertex, index); 70 BOOST_DEF_PROPERTY(vertex, index1); 71 BOOST_DEF_PROPERTY(vertex, index2); 72 BOOST_DEF_PROPERTY(vertex, root); 73 BOOST_DEF_PROPERTY(edge, index); 74 BOOST_DEF_PROPERTY(edge, name); 75 BOOST_DEF_PROPERTY(edge, weight); 76 BOOST_DEF_PROPERTY(edge, weight2); 77 BOOST_DEF_PROPERTY(edge, color); 78 BOOST_DEF_PROPERTY(vertex, name); 79 BOOST_DEF_PROPERTY(graph, name); 80 BOOST_DEF_PROPERTY(vertex, distance); 81 BOOST_DEF_PROPERTY(vertex, distance2); 82 BOOST_DEF_PROPERTY(vertex, color); 83 BOOST_DEF_PROPERTY(vertex, degree); 84 BOOST_DEF_PROPERTY(vertex, in_degree); 85 BOOST_DEF_PROPERTY(vertex, out_degree); get_pre_cached(void)86 BOOST_DEF_PROPERTY(vertex, current_degree); 87 BOOST_DEF_PROPERTY(vertex, priority); 88 BOOST_DEF_PROPERTY(vertex, discover_time); 89 BOOST_DEF_PROPERTY(vertex, finish_time); 90 BOOST_DEF_PROPERTY(vertex, predecessor); 91 BOOST_DEF_PROPERTY(vertex, rank); 92 BOOST_DEF_PROPERTY(vertex, centrality); 93 BOOST_DEF_PROPERTY(vertex, lowpoint); 94 BOOST_DEF_PROPERTY(vertex, potential); 95 BOOST_DEF_PROPERTY(vertex, update); 96 BOOST_DEF_PROPERTY(vertex, underlying); 97 BOOST_DEF_PROPERTY(edge, reverse); 98 BOOST_DEF_PROPERTY(edge, capacity); 99 BOOST_DEF_PROPERTY(edge, flow); 100 BOOST_DEF_PROPERTY(edge, residual_capacity); 101 BOOST_DEF_PROPERTY(edge, centrality); 102 BOOST_DEF_PROPERTY(edge, discover_time); 103 BOOST_DEF_PROPERTY(edge, update); 104 BOOST_DEF_PROPERTY(edge, finished); 105 BOOST_DEF_PROPERTY(edge, underlying); 106 BOOST_DEF_PROPERTY(graph, visitor); 107 108 // These tags are used for property bundles get_post_buf(backend_statstruct buf,struct svc_req * req)109 // These three are defined in boost/pending/property.hpp 110 BOOST_INSTALL_PROPERTY(graph, bundle); 111 BOOST_INSTALL_PROPERTY(vertex, bundle); 112 BOOST_INSTALL_PROPERTY(edge, bundle); 113 114 // These tags are used to denote the owners and local descriptors 115 // for the vertices and edges of a distributed graph. 116 BOOST_DEF_PROPERTY(vertex, global); 117 BOOST_DEF_PROPERTY(vertex, owner); 118 BOOST_DEF_PROPERTY(vertex, local); 119 BOOST_DEF_PROPERTY(edge, global); 120 BOOST_DEF_PROPERTY(edge, owner); 121 BOOST_DEF_PROPERTY(edge, local); 122 BOOST_DEF_PROPERTY(vertex, local_index); 123 BOOST_DEF_PROPERTY(edge, local_index); 124 125 #undef BOOST_DEF_PROPERTY 126 127 namespace detail { 128 129 template <typename G, typename Tag> 130 struct property_kind_from_graph: property_kind<Tag> {}; 131 132 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES 133 template <typename G, typename R, typename T> 134 struct property_kind_from_graph<G, R T::*> { 135 typedef typename boost::mpl::if_< 136 boost::is_base_of<T, typename vertex_bundle_type<G>::type>, 137 vertex_property_tag, 138 typename boost::mpl::if_< 139 boost::is_base_of<T, typename edge_bundle_type<G>::type>, 140 edge_property_tag, 141 typename boost::mpl::if_< 142 boost::is_base_of<T, typename graph_bundle_type<G>::type>, 143 graph_property_tag, 144 void>::type>::type>::type type; 145 }; 146 #endif 147 148 struct dummy_edge_property_selector { 149 template <class Graph, class Property, class Tag> 150 struct bind_ { 151 typedef identity_property_map type; 152 typedef identity_property_map const_type; 153 }; 154 }; 155 struct dummy_vertex_property_selector { 156 template <class Graph, class Property, class Tag> 157 struct bind_ { 158 typedef identity_property_map type; 159 typedef identity_property_map const_type; 160 }; 161 }; 162 163 } // namespace detail 164 165 // Graph classes can either partially specialize property_map 166 // or they can specialize these two selector classes. 167 template <class GraphTag> 168 struct edge_property_selector { 169 typedef detail::dummy_edge_property_selector type; 170 }; 171 172 template <class GraphTag> 173 struct vertex_property_selector { 174 typedef detail::dummy_vertex_property_selector type; 175 }; 176 177 namespace detail { 178 179 template <typename A> struct return_void {typedef void type;}; 180 181 template <typename Graph, typename Enable = void> 182 struct graph_tag_or_void { 183 typedef void type; 184 }; 185 186 template <typename Graph> 187 struct graph_tag_or_void<Graph, typename return_void<typename Graph::graph_tag>::type> { 188 typedef typename Graph::graph_tag type; 189 }; 190 191 template <class Graph, class PropertyTag> 192 struct edge_property_map 193 : edge_property_selector< 194 typename graph_tag_or_void<Graph>::type 195 >::type::template bind_< 196 Graph, 197 typename edge_property_type<Graph>::type, 198 PropertyTag> 199 {}; 200 template <class Graph, class PropertyTag> 201 struct vertex_property_map 202 : vertex_property_selector< 203 typename graph_tag_or_void<Graph>::type 204 >::type::template bind_< 205 Graph, 206 typename vertex_property_type<Graph>::type, 207 PropertyTag> 208 {}; 209 } // namespace detail 210 211 template <class Graph, class Property, class Enable = void> 212 struct property_map: 213 mpl::if_< 214 is_same<typename detail::property_kind_from_graph<Graph, Property>::type, edge_property_tag>, 215 detail::edge_property_map<Graph, Property>, get_post_ll(const char * path,uint32 dev,uint64 ino,struct svc_req * req)216 detail::vertex_property_map<Graph, Property> >::type 217 {}; 218 219 // shortcut for accessing the value type of the property map 220 template <class Graph, class Property> 221 class property_map_value { 222 typedef typename property_map<Graph, Property>::const_type PMap; 223 public: 224 typedef typename property_traits<PMap>::value_type type; 225 }; 226 227 template <class Graph, class Property> 228 class graph_property { 229 public: 230 typedef typename property_value< 231 typename boost::graph_property_type<Graph>::type, Property 232 >::type type; 233 }; 234 235 template <typename Graph> struct vertex_property: vertex_property_type<Graph> {}; 236 template <typename Graph> struct edge_property: edge_property_type<Graph> {}; 237 238 template <typename Graph> get_post_attr(const char * path,nfs_fh3 nfh,struct svc_req * req)239 class degree_property_map 240 : public put_get_helper<typename graph_traits<Graph>::degree_size_type, 241 degree_property_map<Graph> > 242 { 243 public: 244 typedef typename graph_traits<Graph>::vertex_descriptor key_type; 245 typedef typename graph_traits<Graph>::degree_size_type value_type; 246 typedef value_type reference; 247 typedef readable_property_map_tag category; 248 degree_property_map(const Graph& g) : m_g(g) { } 249 value_type operator[](const key_type& v) const { 250 return degree(v, m_g); 251 } 252 private: 253 const Graph& m_g; 254 }; 255 template <typename Graph> 256 inline degree_property_map<Graph> 257 make_degree_map(const Graph& g) { 258 return degree_property_map<Graph>(g); 259 } get_post_cached(struct svc_req * req)260 261 //======================================================================== 262 // Iterator Property Map Generating Functions contributed by 263 // Kevin Vanhorn. (see also the property map generating functions 264 // in boost/property_map/property_map.hpp) 265 266 #if !defined(BOOST_NO_STD_ITERATOR_TRAITS) 267 // A helper function for creating a vertex property map out of a 268 // random access iterator and the internal vertex index map from a 269 // graph. 270 template <class PropertyGraph, class RandomAccessIterator> 271 inline 272 iterator_property_map< 273 RandomAccessIterator, 274 typename property_map<PropertyGraph, vertex_index_t>::type, 275 typename std::iterator_traits<RandomAccessIterator>::value_type, 276 typename std::iterator_traits<RandomAccessIterator>::reference 277 > 278 make_iterator_vertex_map(RandomAccessIterator iter, const PropertyGraph& g) 279 { 280 return make_iterator_property_map(iter, get(vertex_index, g)); 281 } 282 283 // Use this next function when vertex_descriptor is known to be an 284 // integer type, with values ranging from 0 to num_vertices(g). 285 // 286 template <class RandomAccessIterator> 287 inline 288 iterator_property_map< 289 RandomAccessIterator, 290 identity_property_map, 291 typename std::iterator_traits<RandomAccessIterator>::value_type, 292 typename std::iterator_traits<RandomAccessIterator>::reference 293 > 294 make_iterator_vertex_map(RandomAccessIterator iter) 295 { 296 return make_iterator_property_map(iter, identity_property_map()); 297 } 298 #endif 299 300 template <class PropertyGraph, class RandomAccessContainer> 301 inline 302 iterator_property_map< 303 typename RandomAccessContainer::iterator, 304 typename property_map<PropertyGraph, vertex_index_t>::type, 305 typename RandomAccessContainer::value_type, 306 typename RandomAccessContainer::reference 307 > 308 make_container_vertex_map(RandomAccessContainer& c, const PropertyGraph& g) 309 { 310 BOOST_ASSERT(c.size() >= num_vertices(g)); 311 return make_iterator_vertex_map(c.begin(), g); set_attr_unsafe(const char * path,nfs_fh3 nfh,sattr3 new)312 } 313 314 template <class RandomAccessContainer> inline 315 iterator_property_map< 316 typename RandomAccessContainer::iterator, 317 identity_property_map, 318 typename RandomAccessContainer::value_type, 319 typename RandomAccessContainer::reference 320 > 321 make_container_vertex_map(RandomAccessContainer& c) 322 { 323 return make_iterator_vertex_map(c.begin()); 324 } 325 326 327 // NOTE: These functions are declared, but never defined since they need to 328 // be overloaded by graph implementations. However, we need them to be 329 // declared for the functions below. 330 template<typename Graph, typename Tag> 331 typename graph_property<Graph, graph_bundle_t>::type& 332 get_property(Graph& g, Tag); 333 334 template<typename Graph, typename Tag> 335 typename graph_property<Graph, graph_bundle_t>::type const& 336 get_property(Graph const& g, Tag); 337 338 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES 339 // NOTE: This operation is a simple adaptor over the overloaded get_property 340 // operations. 341 template<typename Graph> 342 inline typename graph_property<Graph, graph_bundle_t>::type& 343 get_property(Graph& g) { 344 return get_property(g, graph_bundle); 345 } 346 347 template<typename Graph> 348 inline typename graph_property<Graph, graph_bundle_t>::type const& 349 get_property(const Graph& g) { 350 return get_property(g, graph_bundle); 351 } 352 #endif 353 354 } // namespace boost 355 356 #endif /* BOOST_GRAPH_PROPERTIES_HPP */ 357