]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
f67539c2 TL |
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 | { | |
7c673cae FG |
44 | static default_color_type white() { return white_color; } |
45 | static default_color_type gray() { return gray_color; } | |
46 | static default_color_type green() { return green_color; } | |
47 | static default_color_type red() { return red_color; } | |
48 | static default_color_type black() { return black_color; } | |
f67539c2 TL |
49 | }; |
50 | ||
51 | // These functions are now obsolete, replaced by color_traits. | |
52 | inline default_color_type white(default_color_type) { return white_color; } | |
53 | inline default_color_type gray(default_color_type) { return gray_color; } | |
54 | inline default_color_type green(default_color_type) { return green_color; } | |
55 | inline default_color_type red(default_color_type) { return red_color; } | |
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); | |
7c673cae FG |
138 | |
139 | #undef BOOST_DEF_PROPERTY | |
140 | ||
f67539c2 TL |
141 | namespace detail |
142 | { | |
7c673cae | 143 | |
f67539c2 TL |
144 | template < typename G, typename Tag > |
145 | struct property_kind_from_graph : property_kind< Tag > | |
146 | { | |
147 | }; | |
7c673cae FG |
148 | |
149 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES | |
f67539c2 TL |
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, | |
7c673cae | 159 | typename boost::mpl::if_< |
f67539c2 TL |
160 | boost::is_base_of< T, |
161 | typename graph_bundle_type< G >::type >, | |
162 | graph_property_tag, void >::type >::type >::type type; | |
7c673cae FG |
163 | }; |
164 | #endif | |
165 | ||
f67539c2 TL |
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 | }; | |
7c673cae | 173 | }; |
f67539c2 TL |
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 | }; | |
7c673cae FG |
181 | }; |
182 | ||
f67539c2 | 183 | } // namespace detail |
7c673cae | 184 | |
f67539c2 TL |
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 | { | |
7c673cae | 189 | typedef detail::dummy_edge_property_selector type; |
f67539c2 | 190 | }; |
7c673cae | 191 | |
f67539c2 TL |
192 | template < class GraphTag > struct vertex_property_selector |
193 | { | |
7c673cae | 194 | typedef detail::dummy_vertex_property_selector type; |
f67539c2 | 195 | }; |
7c673cae | 196 | |
f67539c2 TL |
197 | namespace detail |
198 | { | |
7c673cae | 199 | |
f67539c2 TL |
200 | template < typename A > struct return_void |
201 | { | |
202 | typedef void type; | |
203 | }; | |
7c673cae | 204 | |
f67539c2 TL |
205 | template < typename Graph, typename Enable = void > struct graph_tag_or_void |
206 | { | |
207 | typedef void type; | |
7c673cae FG |
208 | }; |
209 | ||
f67539c2 TL |
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; | |
7c673cae FG |
215 | }; |
216 | ||
f67539c2 | 217 | template < class Graph, class PropertyTag > |
7c673cae | 218 | struct edge_property_map |
f67539c2 TL |
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 > | |
7c673cae | 225 | struct vertex_property_map |
f67539c2 TL |
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: | |
7c673cae | 255 | typedef typename property_value< |
f67539c2 TL |
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; | |
7c673cae FG |
276 | typedef value_type reference; |
277 | typedef readable_property_map_tag category; | |
f67539c2 TL |
278 | degree_property_map(const Graph& g) : m_g(g) {} |
279 | value_type operator[](const key_type& v) const { return degree(v, m_g); } | |
280 | ||
281 | private: | |
7c673cae | 282 | const Graph& m_g; |
f67539c2 TL |
283 | }; |
284 | template < typename Graph > | |
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) | |
7c673cae FG |
294 | |
295 | #if !defined(BOOST_NO_STD_ITERATOR_TRAITS) | |
f67539c2 TL |
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 > | |
304 | make_iterator_vertex_map(RandomAccessIterator iter, const PropertyGraph& g) | |
305 | { | |
7c673cae | 306 | return make_iterator_property_map(iter, get(vertex_index, g)); |
f67539c2 TL |
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 > | |
316 | make_iterator_vertex_map(RandomAccessIterator iter) | |
317 | { | |
7c673cae | 318 | return make_iterator_property_map(iter, identity_property_map()); |
f67539c2 | 319 | } |
7c673cae FG |
320 | #endif |
321 | ||
f67539c2 TL |
322 | template < class PropertyGraph, class RandomAccessContainer > |
323 | inline iterator_property_map< typename RandomAccessContainer::iterator, | |
324 | typename property_map< PropertyGraph, vertex_index_t >::type, | |
7c673cae | 325 | typename RandomAccessContainer::value_type, |
f67539c2 TL |
326 | typename RandomAccessContainer::reference > |
327 | make_container_vertex_map(RandomAccessContainer& c, const PropertyGraph& g) | |
328 | { | |
7c673cae FG |
329 | BOOST_ASSERT(c.size() >= num_vertices(g)); |
330 | return make_iterator_vertex_map(c.begin(), g); | |
f67539c2 | 331 | } |
7c673cae | 332 | |
f67539c2 TL |
333 | template < class RandomAccessContainer > |
334 | inline iterator_property_map< typename RandomAccessContainer::iterator, | |
335 | identity_property_map, typename RandomAccessContainer::value_type, | |
336 | typename RandomAccessContainer::reference > | |
337 | make_container_vertex_map(RandomAccessContainer& c) | |
338 | { | |
7c673cae | 339 | return make_iterator_vertex_map(c.begin()); |
f67539c2 | 340 | } |
7c673cae FG |
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. | |
f67539c2 TL |
345 | template < typename Graph, typename Tag > |
346 | typename graph_property< Graph, graph_bundle_t >::type& get_property( | |
347 | Graph& g, Tag); | |
7c673cae | 348 | |
f67539c2 TL |
349 | template < typename Graph, typename Tag > |
350 | typename graph_property< Graph, graph_bundle_t >::type const& get_property( | |
351 | Graph const& g, Tag); | |
7c673cae FG |
352 | |
353 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES | |
354 | // NOTE: This operation is a simple adaptor over the overloaded get_property | |
355 | // operations. | |
f67539c2 TL |
356 | template < typename Graph > |
357 | inline typename graph_property< Graph, graph_bundle_t >::type& get_property( | |
358 | Graph& g) | |
359 | { | |
360 | return get_property(g, graph_bundle); | |
7c673cae FG |
361 | } |
362 | ||
f67539c2 TL |
363 | template < typename Graph > |
364 | inline typename graph_property< Graph, graph_bundle_t >::type const& | |
365 | get_property(const Graph& g) | |
366 | { | |
367 | return get_property(g, graph_bundle); | |
7c673cae FG |
368 | } |
369 | #endif | |
370 | ||
371 | } // namespace boost | |
372 | ||
373 | #endif /* BOOST_GRAPH_PROPERTIES_HPP */ |