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 { |
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; } |
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); |
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 |
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>, |
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> |
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 | } |
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); |
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 | #if BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x590)) && !defined (BOOST_GRAPH_NO_BUNDLED_PROPERTIES) |
328 | // This compiler cannot define a partial specialization based on a |
329 | // pointer-to-member type, as seen in boost/graph/subgraph.hpp line 985 (as of |
330 | // trunk r53912) |
331 | # define BOOST_GRAPH_NO_BUNDLED_PROPERTIES |
332 | #endif |
333 | |
334 | // NOTE: These functions are declared, but never defined since they need to |
335 | // be overloaded by graph implementations. However, we need them to be |
336 | // declared for the functions below. |
337 | template<typename Graph, typename Tag> |
338 | typename graph_property<Graph, graph_bundle_t>::type& |
339 | get_property(Graph& g, Tag); |
340 | |
341 | template<typename Graph, typename Tag> |
342 | typename graph_property<Graph, graph_bundle_t>::type const& |
343 | get_property(Graph const& g, Tag); |
344 | |
345 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES |
346 | // NOTE: This operation is a simple adaptor over the overloaded get_property |
347 | // operations. |
348 | template<typename Graph> |
349 | inline typename graph_property<Graph, graph_bundle_t>::type& |
350 | get_property(Graph& g) { |
351 | return get_property(g, graph_bundle); |
352 | } |
353 | |
354 | template<typename Graph> |
355 | inline typename graph_property<Graph, graph_bundle_t>::type const& |
356 | get_property(const Graph& g) { |
357 | return get_property(g, graph_bundle); |
358 | } |
359 | #endif |
360 | |
361 | } // namespace boost |
362 | |
363 | #endif /* BOOST_GRAPH_PROPERTIES_HPP */ |
364 | |