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 //=======================================================================
9 #ifndef BOOST_GRAPH_PROPERTIES_HPP
10 #define BOOST_GRAPH_PROPERTIES_HPP
12 #include <boost/config.hpp>
14 #include <boost/pending/property.hpp>
15 #include <boost/property_map.hpp>
16 #include <boost/graph/graph_traits.hpp>
17 #include <boost/type_traits/is_convertible.hpp>
21 enum default_color_type { white_color, gray_color, green_color, red_color, black_color };
23 template <class ColorValue>
25 static default_color_type white() { return white_color; }
26 static default_color_type gray() { return gray_color; }
27 static default_color_type green() { return green_color; }
28 static default_color_type red() { return red_color; }
29 static default_color_type black() { return black_color; }
32 // These functions are now obsolete, replaced by color_traits.
33 inline default_color_type white(default_color_type) { return white_color; }
34 inline default_color_type gray(default_color_type) { return gray_color; }
35 inline default_color_type green(default_color_type) { return green_color; }
36 inline default_color_type red(default_color_type) { return red_color; }
37 inline default_color_type black(default_color_type) { return black_color; }
39 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
41 struct property_traits<default_color_type*> {
42 typedef default_color_type value_type;
43 typedef std::ptrdiff_t key_type;
44 typedef default_color_type& reference;
45 typedef lvalue_property_map_tag category;
47 // get/put already defined for T*
50 struct graph_property_tag { };
51 struct vertex_property_tag { };
52 struct edge_property_tag { };
54 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
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_INSTALL_PROPERTY(KIND, NAME) \
62 template <> struct property_kind<KIND##_##NAME##_t> { \
63 typedef KIND##_property_tag type; \
67 #define BOOST_DEF_PROPERTY(KIND, NAME) \
68 enum KIND##_##NAME##_t { KIND##_##NAME }; \
69 BOOST_INSTALL_PROPERTY(KIND, NAME)
71 BOOST_DEF_PROPERTY(vertex, all);
72 BOOST_DEF_PROPERTY(edge, all);
73 BOOST_DEF_PROPERTY(graph, all);
74 BOOST_DEF_PROPERTY(vertex, index);
75 BOOST_DEF_PROPERTY(vertex, index1);
76 BOOST_DEF_PROPERTY(vertex, index2);
77 BOOST_DEF_PROPERTY(vertex, root);
78 BOOST_DEF_PROPERTY(edge, index);
79 BOOST_DEF_PROPERTY(edge, name);
80 BOOST_DEF_PROPERTY(edge, weight);
81 BOOST_DEF_PROPERTY(edge, weight2);
82 BOOST_DEF_PROPERTY(edge, color);
83 BOOST_DEF_PROPERTY(vertex, name);
84 BOOST_DEF_PROPERTY(graph, name);
85 BOOST_DEF_PROPERTY(vertex, distance);
86 BOOST_DEF_PROPERTY(vertex, color);
87 BOOST_DEF_PROPERTY(vertex, degree);
88 BOOST_DEF_PROPERTY(vertex, in_degree);
89 BOOST_DEF_PROPERTY(vertex, out_degree);
90 BOOST_DEF_PROPERTY(vertex, current_degree);
91 BOOST_DEF_PROPERTY(vertex, priority);
92 BOOST_DEF_PROPERTY(vertex, discover_time);
93 BOOST_DEF_PROPERTY(vertex, finish_time);
94 BOOST_DEF_PROPERTY(vertex, predecessor);
95 BOOST_DEF_PROPERTY(vertex, rank);
96 BOOST_DEF_PROPERTY(vertex, centrality);
97 BOOST_DEF_PROPERTY(vertex, lowpoint);
98 BOOST_DEF_PROPERTY(edge, reverse);
99 BOOST_DEF_PROPERTY(edge, capacity);
100 BOOST_DEF_PROPERTY(edge, residual_capacity);
101 BOOST_DEF_PROPERTY(edge, centrality);
102 BOOST_DEF_PROPERTY(graph, visitor);
104 // These tags are used for property bundles
105 BOOST_DEF_PROPERTY(vertex, bundle);
106 BOOST_DEF_PROPERTY(edge, bundle);
108 #undef BOOST_DEF_PROPERTY
112 struct dummy_edge_property_selector {
113 template <class Graph, class Property, class Tag>
115 typedef identity_property_map type;
116 typedef identity_property_map const_type;
119 struct dummy_vertex_property_selector {
120 template <class Graph, class Property, class Tag>
122 typedef identity_property_map type;
123 typedef identity_property_map const_type;
127 } // namespace detail
129 // Graph classes can either partially specialize property_map
130 // or they can specialize these two selector classes.
131 template <class GraphTag>
132 struct edge_property_selector {
133 typedef detail::dummy_edge_property_selector type;
136 template <class GraphTag>
137 struct vertex_property_selector {
138 typedef detail::dummy_vertex_property_selector type;
143 template <class Graph, class PropertyTag>
144 struct edge_property_map {
145 typedef typename Graph::edge_property_type Property;
146 typedef typename Graph::graph_tag graph_tag;
147 typedef typename edge_property_selector<graph_tag>::type Selector;
148 typedef typename Selector::template bind_<Graph,Property,PropertyTag>
150 typedef typename Bind::type type;
151 typedef typename Bind::const_type const_type;
153 template <class Graph, class PropertyTag>
154 class vertex_property_map {
155 typedef typename Graph::vertex_property_type Property;
156 typedef typename Graph::graph_tag graph_tag;
157 typedef typename vertex_property_selector<graph_tag>::type Selector;
158 typedef typename Selector::template bind_<Graph,Property,PropertyTag>
161 typedef typename Bind::type type;
162 typedef typename Bind::const_type const_type;
165 // This selects the kind of property map, whether is maps from
166 // edges or from vertices.
168 // It is overly complicated because it's a workaround for
169 // partial specialization.
170 struct choose_vertex_property_map {
171 template <class Graph, class Property>
173 typedef vertex_property_map<Graph, Property> type;
176 struct choose_edge_property_map {
177 template <class Graph, class Property>
179 typedef edge_property_map<Graph, Property> type;
182 template <class Kind>
183 struct property_map_kind_selector {
184 // VC++ gets confused if this isn't defined, even though
185 // this never gets used.
186 typedef choose_vertex_property_map type;
188 template <> struct property_map_kind_selector<vertex_property_tag> {
189 typedef choose_vertex_property_map type;
191 template <> struct property_map_kind_selector<edge_property_tag> {
192 typedef choose_edge_property_map type;
194 } // namespace detail
196 template <class Graph, class Property>
197 struct property_map {
199 typedef typename property_kind<Property>::type Kind;
200 typedef typename detail::property_map_kind_selector<Kind>::type Selector;
201 typedef typename Selector::template bind_<Graph, Property> Bind;
202 typedef typename Bind::type Map;
204 typedef typename Map::type type;
205 typedef typename Map::const_type const_type;
208 // shortcut for accessing the value type of the property map
209 template <class Graph, class Property>
210 class property_map_value {
211 typedef typename property_map<Graph, Property>::const_type PMap;
213 typedef typename property_traits<PMap>::value_type type;
216 template <class Graph, class Property>
217 class graph_property {
219 typedef typename property_value<typename Graph::graph_property_type,
220 Property>::type type;
223 template <class Graph>
224 class vertex_property {
226 typedef typename Graph::vertex_property_type type;
228 template <class Graph>
229 class edge_property {
231 typedef typename Graph::edge_property_type type;
234 template <typename Graph>
235 class degree_property_map
236 : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
237 degree_property_map<Graph> >
240 typedef typename graph_traits<Graph>::vertex_descriptor key_type;
241 typedef typename graph_traits<Graph>::degree_size_type value_type;
242 typedef value_type reference;
243 typedef readable_property_map_tag category;
244 degree_property_map(const Graph& g) : m_g(g) { }
245 value_type operator[](const key_type& v) const {
246 return degree(v, m_g);
251 template <typename Graph>
252 inline degree_property_map<Graph>
253 make_degree_map(const Graph& g) {
254 return degree_property_map<Graph>(g);
257 //========================================================================
258 // Iterator Property Map Generating Functions contributed by
259 // Kevin Vanhorn. (see also the property map generating functions
260 // in boost/property_map.hpp)
262 #if !defined(BOOST_NO_STD_ITERATOR_TRAITS)
263 // A helper function for creating a vertex property map out of a
264 // random access iterator and the internal vertex index map from a
266 template <class PropertyGraph, class RandomAccessIterator>
268 iterator_property_map<
269 RandomAccessIterator,
270 typename property_map<PropertyGraph, vertex_index_t>::type,
271 typename std::iterator_traits<RandomAccessIterator>::value_type,
272 typename std::iterator_traits<RandomAccessIterator>::reference
274 make_iterator_vertex_map(RandomAccessIterator iter, const PropertyGraph& g)
276 return make_iterator_property_map(iter, get(vertex_index, g));
279 // Use this next function when vertex_descriptor is known to be an
280 // integer type, with values ranging from 0 to num_vertices(g).
282 template <class RandomAccessIterator>
284 iterator_property_map<
285 RandomAccessIterator,
286 identity_property_map,
287 typename std::iterator_traits<RandomAccessIterator>::value_type,
288 typename std::iterator_traits<RandomAccessIterator>::reference
290 make_iterator_vertex_map(RandomAccessIterator iter)
292 return make_iterator_property_map(iter, identity_property_map());
296 template <class PropertyGraph, class RandomAccessContainer>
298 iterator_property_map<
299 typename RandomAccessContainer::iterator,
300 typename property_map<PropertyGraph, vertex_index_t>::type,
301 typename RandomAccessContainer::value_type,
302 typename RandomAccessContainer::reference
304 make_container_vertex_map(RandomAccessContainer& c, const PropertyGraph& g)
306 assert(c.size() >= num_vertices(g));
307 return make_iterator_vertex_map(c.begin(), g);
310 template <class RandomAccessContainer> inline
311 iterator_property_map<
312 typename RandomAccessContainer::iterator,
313 identity_property_map,
314 typename RandomAccessContainer::value_type,
315 typename RandomAccessContainer::reference
317 make_container_vertex_map(RandomAccessContainer& c)
319 return make_iterator_vertex_map(c.begin());
322 #if defined (BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
323 # define BOOST_GRAPH_NO_BUNDLED_PROPERTIES
326 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
327 template<typename Graph, typename Descriptor, typename Bundle, typename T>
328 struct bundle_property_map
329 : put_get_helper<T&, bundle_property_map<Graph, Descriptor, Bundle, T> >
331 typedef Descriptor key_type;
332 typedef T value_type;
333 typedef T& reference;
334 typedef lvalue_property_map_tag category;
336 bundle_property_map() { }
337 bundle_property_map(Graph* g_, T Bundle::* pm_) : g(g_), pm(pm_) {}
339 reference operator[](key_type k) const { return (*g)[k].*pm; }
346 template<typename VertexBundle, typename EdgeBundle, typename Bundle>
347 struct is_vertex_bundle : is_convertible<VertexBundle*, Bundle*> {};
350 template <typename Graph, typename T, typename Bundle>
351 struct property_map<Graph, T Bundle::*>
354 typedef graph_traits<Graph> traits;
355 typedef typename Graph::vertex_bundled vertex_bundled;
356 typedef typename Graph::edge_bundled edge_bundled;
357 typedef typename ct_if<(detail::is_vertex_bundle<vertex_bundled, edge_bundled, Bundle>::value),
358 typename traits::vertex_descriptor,
359 typename traits::edge_descriptor>::type
361 typedef typename ct_if<(detail::is_vertex_bundle<vertex_bundled, edge_bundled, Bundle>::value),
367 typedef bundle_property_map<Graph, descriptor, actual_bundle, T> type;
368 typedef bundle_property_map<const Graph, descriptor, actual_bundle, const T>
375 #endif /* BOOST_GRAPH_PROPERTIES_HPPA */