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