]>
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 | ||
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 | // 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 */ |