Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / properties.hpp
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 #ifndef BOOST_GRAPH_PROPERTIES_HPP
10 #define BOOST_GRAPH_PROPERTIES_HPP
11
12 #include <boost/config.hpp>
13 #include <cassert>
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>
18
19 namespace boost {
20
21   enum default_color_type { white_color, gray_color, green_color, red_color, black_color };
22
23   template <class ColorValue>
24   struct color_traits {
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; }
30   };
31   
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; }
38
39 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
40   template <>
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;
46   };
47   // get/put already defined for T*
48 #endif
49
50   struct graph_property_tag { };
51   struct vertex_property_tag { };
52   struct edge_property_tag { };
53
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; \
59   }
60 #else
61 #define BOOST_INSTALL_PROPERTY(KIND, NAME) \
62   template <> struct property_kind<KIND##_##NAME##_t> { \
63     typedef KIND##_property_tag type; \
64   }
65 #endif
66
67 #define BOOST_DEF_PROPERTY(KIND, NAME) \
68   enum KIND##_##NAME##_t { KIND##_##NAME }; \
69   BOOST_INSTALL_PROPERTY(KIND, NAME)
70
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(edge, reverse);
98   BOOST_DEF_PROPERTY(edge, capacity);
99   BOOST_DEF_PROPERTY(edge, residual_capacity);
100   BOOST_DEF_PROPERTY(edge, centrality);
101   BOOST_DEF_PROPERTY(graph, visitor);
102
103   // These tags are used for property bundles
104   BOOST_DEF_PROPERTY(vertex, bundle);
105   BOOST_DEF_PROPERTY(edge, bundle);
106
107 #undef BOOST_DEF_PROPERTY
108
109   namespace detail {
110
111     struct dummy_edge_property_selector {
112       template <class Graph, class Property, class Tag>
113       struct bind_ {
114         typedef identity_property_map type;
115         typedef identity_property_map const_type;
116       };
117     };
118     struct dummy_vertex_property_selector {
119       template <class Graph, class Property, class Tag>
120       struct bind_ {
121         typedef identity_property_map type;
122         typedef identity_property_map const_type;
123       };
124     };
125
126   } // namespace detail
127
128   // Graph classes can either partially specialize property_map
129   // or they can specialize these two selector classes.
130   template <class GraphTag>
131   struct edge_property_selector {
132     typedef detail::dummy_edge_property_selector type;
133   };
134
135   template <class GraphTag>
136   struct vertex_property_selector {
137     typedef detail::dummy_vertex_property_selector type;
138   };
139
140   namespace detail {
141
142     template <class Graph, class PropertyTag>
143     struct edge_property_map {
144       typedef typename Graph::edge_property_type Property;
145       typedef typename Graph::graph_tag graph_tag;
146       typedef typename edge_property_selector<graph_tag>::type Selector;
147       typedef typename Selector::template bind_<Graph,Property,PropertyTag>
148         Bind;
149       typedef typename Bind::type type;
150       typedef typename Bind::const_type const_type;
151     };
152     template <class Graph, class PropertyTag>
153     class vertex_property_map {
154       typedef typename Graph::vertex_property_type Property;
155       typedef typename Graph::graph_tag graph_tag;
156       typedef typename vertex_property_selector<graph_tag>::type Selector;
157       typedef typename Selector::template bind_<Graph,Property,PropertyTag>
158         Bind;
159     public:
160       typedef typename Bind::type type;
161       typedef typename Bind::const_type const_type;
162     };
163
164     // This selects the kind of property map, whether is maps from
165     // edges or from vertices.
166     //
167     // It is overly complicated because it's a workaround for
168     // partial specialization.
169     struct choose_vertex_property_map {
170       template <class Graph, class Property>
171       struct bind_ {
172         typedef vertex_property_map<Graph, Property> type;
173       };
174     };
175     struct choose_edge_property_map {
176       template <class Graph, class Property>
177       struct bind_ {
178         typedef edge_property_map<Graph, Property> type;
179       };
180     };
181     template <class Kind>
182     struct property_map_kind_selector {
183       // VC++ gets confused if this isn't defined, even though
184       // this never gets used.
185       typedef choose_vertex_property_map type;
186     };
187     template <> struct property_map_kind_selector<vertex_property_tag> {
188       typedef choose_vertex_property_map type;
189     };
190     template <> struct property_map_kind_selector<edge_property_tag> {
191       typedef choose_edge_property_map type;
192     };
193   } // namespace detail
194
195   template <class Graph, class Property>
196   struct property_map {
197   private:
198     typedef typename property_kind<Property>::type Kind;
199     typedef typename detail::property_map_kind_selector<Kind>::type Selector;
200     typedef typename Selector::template bind_<Graph, Property> Bind;
201     typedef typename Bind::type Map;
202   public:
203     typedef typename Map::type type;
204     typedef typename Map::const_type const_type;
205   };
206
207   // shortcut for accessing the value type of the property map
208   template <class Graph, class Property>
209   class property_map_value {
210     typedef typename property_map<Graph, Property>::const_type PMap;
211   public:
212     typedef typename property_traits<PMap>::value_type type;
213   };
214
215   template <class Graph, class Property>
216   class graph_property {
217   public:
218     typedef typename property_value<typename Graph::graph_property_type, 
219       Property>::type type;
220   };
221
222   template <class Graph>
223   class vertex_property {
224   public:
225     typedef typename Graph::vertex_property_type type;
226   };
227   template <class Graph>
228   class edge_property {
229   public:
230     typedef typename Graph::edge_property_type type;
231   };
232
233   template <typename Graph>
234   class degree_property_map 
235     : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
236                             degree_property_map<Graph> >                  
237   {
238   public:
239     typedef typename graph_traits<Graph>::vertex_descriptor key_type;
240     typedef typename graph_traits<Graph>::degree_size_type value_type;
241     typedef value_type reference;
242     typedef readable_property_map_tag category;
243     degree_property_map(const Graph& g) : m_g(g) { }
244     value_type operator[](const key_type& v) const {
245       return degree(v, m_g);
246     }
247   private:
248     const Graph& m_g;
249   };
250   template <typename Graph>
251   inline degree_property_map<Graph>
252   make_degree_map(const Graph& g) {
253     return degree_property_map<Graph>(g);
254   }
255
256   //========================================================================
257   // Iterator Property Map Generating Functions contributed by 
258   // Kevin Vanhorn. (see also the property map generating functions
259   // in boost/property_map.hpp)
260
261 #if !defined(BOOST_NO_STD_ITERATOR_TRAITS)
262   // A helper function for creating a vertex property map out of a
263   // random access iterator and the internal vertex index map from a
264   // graph.
265   template <class PropertyGraph, class RandomAccessIterator>
266   inline
267   iterator_property_map<
268     RandomAccessIterator,
269     typename property_map<PropertyGraph, vertex_index_t>::type,
270     typename std::iterator_traits<RandomAccessIterator>::value_type,
271     typename std::iterator_traits<RandomAccessIterator>::reference
272   >
273   make_iterator_vertex_map(RandomAccessIterator iter, const PropertyGraph& g)
274   {
275     return make_iterator_property_map(iter, get(vertex_index, g));
276   }  
277   
278   // Use this next function when vertex_descriptor is known to be an
279   // integer type, with values ranging from 0 to num_vertices(g).
280   //
281   template <class RandomAccessIterator>
282   inline
283   iterator_property_map<
284     RandomAccessIterator,
285     identity_property_map,
286     typename std::iterator_traits<RandomAccessIterator>::value_type,
287     typename std::iterator_traits<RandomAccessIterator>::reference
288   >
289   make_iterator_vertex_map(RandomAccessIterator iter)
290   {
291     return make_iterator_property_map(iter, identity_property_map());
292   }      
293 #endif
294
295   template <class PropertyGraph, class RandomAccessContainer>
296   inline
297   iterator_property_map<
298     typename RandomAccessContainer::iterator,
299     typename property_map<PropertyGraph, vertex_index_t>::type,
300     typename RandomAccessContainer::value_type,
301     typename RandomAccessContainer::reference
302   >
303   make_container_vertex_map(RandomAccessContainer& c, const PropertyGraph& g)
304   {
305     assert(c.size() >= num_vertices(g));
306     return make_iterator_vertex_map(c.begin(), g);
307   }   
308
309   template <class RandomAccessContainer> inline
310   iterator_property_map<
311     typename RandomAccessContainer::iterator,
312     identity_property_map,
313     typename RandomAccessContainer::value_type,
314     typename RandomAccessContainer::reference
315   >
316   make_container_vertex_map(RandomAccessContainer& c)
317   {
318     return make_iterator_vertex_map(c.begin());
319   }
320
321 #if defined (BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
322 #  define BOOST_GRAPH_NO_BUNDLED_PROPERTIES
323 #endif
324
325 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
326   template<typename Graph, typename Descriptor, typename Bundle, typename T>
327   struct bundle_property_map
328     : put_get_helper<T&, bundle_property_map<Graph, Descriptor, Bundle, T> >
329   {
330     typedef Descriptor key_type;
331     typedef T value_type;
332     typedef T& reference;
333     typedef lvalue_property_map_tag category;
334
335     bundle_property_map(Graph* g_, T Bundle::* pm_) : g(g_), pm(pm_) {}
336
337     reference operator[](key_type k) const { return (*g)[k].*pm; }
338   private:
339     Graph* g;
340     T Bundle::* pm;
341   };
342
343   namespace detail {
344     template<typename VertexBundle, typename EdgeBundle, typename Bundle>
345       struct is_vertex_bundle : is_convertible<Bundle*, VertexBundle*> {};
346   }
347   
348   template <typename Graph, typename T, typename Bundle>
349   struct property_map<Graph, T Bundle::*>  
350   {
351   private:
352     typedef graph_traits<Graph> traits;
353     typedef typename Graph::vertex_bundled vertex_bundled;
354     typedef typename Graph::edge_bundled edge_bundled;
355     typedef typename ct_if<(detail::is_vertex_bundle<vertex_bundled, edge_bundled, Bundle>::value),
356                        typename traits::vertex_descriptor,
357                        typename traits::edge_descriptor>::type
358       descriptor;
359     
360   public:
361     typedef bundle_property_map<Graph, descriptor, Bundle, T> type;
362     typedef bundle_property_map<const Graph, descriptor, Bundle, const T> const_type;
363   };
364 #endif
365
366 } // namespace boost
367
368 #endif /* BOOST_GRAPH_PROPERTIES_HPPA */