1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 //=======================================================================
10 #ifndef BOOST_GRAPH_PROPERTIES_HPP
11 #define BOOST_GRAPH_PROPERTIES_HPP
13 #include <boost/config.hpp>
14 #include <boost/assert.hpp>
15 #include <boost/pending/property.hpp>
16 #include <boost/detail/workaround.hpp>
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>
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>
32 enum default_color_type { white_color, gray_color, green_color, red_color, black_color };
34 template <class ColorValue>
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; }
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; }
51 struct graph_property_tag { };
52 struct vertex_property_tag { };
53 struct edge_property_tag { };
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; \
61 #define BOOST_DEF_PROPERTY(KIND, NAME) \
62 enum KIND##_##NAME##_t { KIND##_##NAME }; \
63 BOOST_INSTALL_PROPERTY(KIND, NAME)
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);
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);
108 // These tags are used for property bundles
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);
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);
125 #undef BOOST_DEF_PROPERTY
129 template <typename G, typename Tag>
130 struct property_kind_from_graph: property_kind<Tag> {};
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>,
138 typename boost::mpl::if_<
139 boost::is_base_of<T, typename edge_bundle_type<G>::type>,
141 typename boost::mpl::if_<
142 boost::is_base_of<T, typename graph_bundle_type<G>::type>,
144 void>::type>::type>::type type;
148 struct dummy_edge_property_selector {
149 template <class Graph, class Property, class Tag>
151 typedef identity_property_map type;
152 typedef identity_property_map const_type;
155 struct dummy_vertex_property_selector {
156 template <class Graph, class Property, class Tag>
158 typedef identity_property_map type;
159 typedef identity_property_map const_type;
163 } // namespace detail
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;
172 template <class GraphTag>
173 struct vertex_property_selector {
174 typedef detail::dummy_vertex_property_selector type;
179 template <typename A> struct return_void {typedef void type;};
181 template <typename Graph, typename Enable = void>
182 struct graph_tag_or_void {
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;
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_<
197 typename edge_property_type<Graph>::type,
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_<
206 typename vertex_property_type<Graph>::type,
209 } // namespace detail
211 template <class Graph, class Property, class Enable = void>
214 is_same<typename detail::property_kind_from_graph<Graph, Property>::type, edge_property_tag>,
215 detail::edge_property_map<Graph, Property>,
216 detail::vertex_property_map<Graph, Property> >::type
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;
224 typedef typename property_traits<PMap>::value_type type;
227 template <class Graph, class Property>
228 class graph_property {
230 typedef typename property_value<
231 typename boost::graph_property_type<Graph>::type, Property
235 template <typename Graph> struct vertex_property: vertex_property_type<Graph> {};
236 template <typename Graph> struct edge_property: edge_property_type<Graph> {};
238 template <typename Graph>
239 class degree_property_map
240 : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
241 degree_property_map<Graph> >
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);
255 template <typename Graph>
256 inline degree_property_map<Graph>
257 make_degree_map(const Graph& g) {
258 return degree_property_map<Graph>(g);
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)
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
270 template <class PropertyGraph, class RandomAccessIterator>
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
278 make_iterator_vertex_map(RandomAccessIterator iter, const PropertyGraph& g)
280 return make_iterator_property_map(iter, get(vertex_index, g));
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).
286 template <class RandomAccessIterator>
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
294 make_iterator_vertex_map(RandomAccessIterator iter)
296 return make_iterator_property_map(iter, identity_property_map());
300 template <class PropertyGraph, class RandomAccessContainer>
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
308 make_container_vertex_map(RandomAccessContainer& c, const PropertyGraph& g)
310 BOOST_ASSERT(c.size() >= num_vertices(g));
311 return make_iterator_vertex_map(c.begin(), g);
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
321 make_container_vertex_map(RandomAccessContainer& c)
323 return make_iterator_vertex_map(c.begin());
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);
334 template<typename Graph, typename Tag>
335 typename graph_property<Graph, graph_bundle_t>::type const&
336 get_property(Graph const& g, Tag);
338 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
339 // NOTE: This operation is a simple adaptor over the overloaded get_property
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);
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);
356 #endif /* BOOST_GRAPH_PROPERTIES_HPP */