Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / graph_concepts.hpp
1 //
2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
5 //
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
10 //
11 #ifndef BOOST_GRAPH_CONCEPTS_HPP
12 #define BOOST_GRAPH_CONCEPTS_HPP
13
14 #include <boost/config.hpp>
15 #include <boost/graph/graph_traits.hpp>
16 #include <boost/property_map.hpp>
17 #include <boost/graph/properties.hpp>
18 #include <boost/concept_check.hpp>
19 #include <boost/detail/workaround.hpp>
20
21 namespace boost {
22
23   template <class T>
24   struct MultiPassInputIteratorConcept {
25     void constraints() {
26       function_requires< InputIteratorConcept<T> >();
27     }
28   };
29
30   template <class G>
31   struct GraphConcept
32   {
33     typedef typename graph_traits<G>::vertex_descriptor vertex_descriptor;
34     typedef typename graph_traits<G>::directed_category directed_category;
35     typedef typename graph_traits<G>::edge_parallel_category
36       edge_parallel_category;
37     typedef typename graph_traits<G>::traversal_category
38       traversal_category;
39     void constraints() {
40       function_requires< DefaultConstructibleConcept<vertex_descriptor> >();
41       function_requires< EqualityComparableConcept<vertex_descriptor> >();
42       function_requires< AssignableConcept<vertex_descriptor> >();
43     }
44     G g;
45   };
46
47   template <class G>
48   struct IncidenceGraphConcept
49   {
50     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
51     typedef typename graph_traits<G>::out_edge_iterator
52       out_edge_iterator;
53     typedef typename graph_traits<G>::traversal_category
54       traversal_category;
55     void constraints() {
56       function_requires< GraphConcept<G> >();
57       function_requires< MultiPassInputIteratorConcept<out_edge_iterator> >();
58       function_requires< DefaultConstructibleConcept<edge_descriptor> >();
59       function_requires< EqualityComparableConcept<edge_descriptor> >();
60       function_requires< AssignableConcept<edge_descriptor> >();
61       function_requires< ConvertibleConcept<traversal_category,
62         incidence_graph_tag> >();
63
64       p = out_edges(u, g);
65       n = out_degree(u, g);
66       e = *p.first;
67       u = source(e, g);
68       v = target(e, g);
69       const_constraints(g);
70     }
71     void const_constraints(const G& cg) {
72       p = out_edges(u, cg);
73       n = out_degree(u, cg);
74       e = *p.first;
75       u = source(e, cg);
76       v = target(e, cg);
77     }
78     std::pair<out_edge_iterator, out_edge_iterator> p;
79     typename graph_traits<G>::vertex_descriptor u, v;
80     typename graph_traits<G>::edge_descriptor e;
81     typename graph_traits<G>::degree_size_type n;
82     G g;
83   };
84
85   template <class G>
86   struct BidirectionalGraphConcept
87   {
88     typedef typename graph_traits<G>::in_edge_iterator
89       in_edge_iterator;
90     typedef typename graph_traits<G>::traversal_category
91       traversal_category;
92     void constraints() {
93       function_requires< IncidenceGraphConcept<G> >();
94       function_requires< MultiPassInputIteratorConcept<in_edge_iterator> >();
95       function_requires< ConvertibleConcept<traversal_category,
96         bidirectional_graph_tag> >();
97
98       p = in_edges(v, g);
99       n = in_degree(v, g);
100       e = *p.first;
101       const_constraints(g);
102     }
103     void const_constraints(const G& cg) {
104       p = in_edges(v, cg);
105       n = in_degree(v, cg);
106       e = *p.first;
107     }
108     std::pair<in_edge_iterator, in_edge_iterator> p;
109     typename graph_traits<G>::vertex_descriptor v;
110     typename graph_traits<G>::edge_descriptor e;
111     typename graph_traits<G>::degree_size_type n;
112     G g;
113   };
114
115   template <class G>
116   struct AdjacencyGraphConcept
117   {
118     typedef typename graph_traits<G>::adjacency_iterator
119       adjacency_iterator;
120     typedef typename graph_traits<G>::traversal_category
121       traversal_category;
122     void constraints() {
123       function_requires< GraphConcept<G> >();
124       function_requires< MultiPassInputIteratorConcept<adjacency_iterator> >();
125       function_requires< ConvertibleConcept<traversal_category,
126         adjacency_graph_tag> >();
127
128       p = adjacent_vertices(v, g);
129       v = *p.first;
130       const_constraints(g);
131     }
132     void const_constraints(const G& cg) {
133       p = adjacent_vertices(v, cg);
134     }
135     std::pair<adjacency_iterator,adjacency_iterator> p;
136     typename graph_traits<G>::vertex_descriptor v;
137     G g;
138   };
139
140 // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
141 // you want to use vector_as_graph, it is!  I'm sure the graph
142 // library leaves these out all over the place.  Probably a
143 // redesign involving specializing a template with a static
144 // member function is in order :(
145 //
146 // It is needed in order to allow us to write using boost::vertices as
147 // needed for ADL when using vector_as_graph below.
148 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)            \
149  && !BOOST_WORKAROUND(__GNUC__, <= 2)                       \
150  && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
151 # define BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
152 #endif 
153
154 #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
155 template <class T>
156 typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&);
157 #endif      
158
159   template <class G>
160   struct VertexListGraphConcept
161   {
162     typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
163     typedef typename graph_traits<G>::vertices_size_type vertices_size_type;
164     typedef typename graph_traits<G>::traversal_category
165       traversal_category;
166     void constraints() {
167       function_requires< GraphConcept<G> >();
168       function_requires< MultiPassInputIteratorConcept<vertex_iterator> >();
169       function_requires< ConvertibleConcept<traversal_category,
170         vertex_list_graph_tag> >();
171
172 #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
173       // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
174       // you want to use vector_as_graph, it is!  I'm sure the graph
175       // library leaves these out all over the place.  Probably a
176       // redesign involving specializing a template with a static
177       // member function is in order :(
178       using boost::vertices;
179 #endif      
180       p = vertices(g);
181       v = *p.first;
182       const_constraints(g);
183     }
184     void const_constraints(const G& cg) {
185 #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
186       // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
187       // you want to use vector_as_graph, it is!  I'm sure the graph
188       // library leaves these out all over the place.  Probably a
189       // redesign involving specializing a template with a static
190       // member function is in order :(
191       using boost::vertices;
192 #endif 
193       
194       p = vertices(cg);
195       v = *p.first;
196       V = num_vertices(cg);
197     }
198     std::pair<vertex_iterator,vertex_iterator> p;
199     typename graph_traits<G>::vertex_descriptor v;
200     G g;
201     vertices_size_type V;
202   };
203
204   template <class G>
205   struct EdgeListGraphConcept
206   {
207     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
208     typedef typename graph_traits<G>::edge_iterator edge_iterator;
209     typedef typename graph_traits<G>::edges_size_type edges_size_type;
210     typedef typename graph_traits<G>::traversal_category
211       traversal_category;
212     void constraints() {
213       function_requires< GraphConcept<G> >();
214       function_requires< MultiPassInputIteratorConcept<edge_iterator> >();
215       function_requires< DefaultConstructibleConcept<edge_descriptor> >();
216       function_requires< EqualityComparableConcept<edge_descriptor> >();
217       function_requires< AssignableConcept<edge_descriptor> >();
218       function_requires< ConvertibleConcept<traversal_category,
219         edge_list_graph_tag> >();
220
221       p = edges(g);
222       e = *p.first;
223       u = source(e, g);
224       v = target(e, g);
225       const_constraints(g);
226     }
227     void const_constraints(const G& cg) {
228       p = edges(cg);
229       E = num_edges(cg);
230       e = *p.first;
231       u = source(e, cg);
232       v = target(e, cg);
233     }
234     std::pair<edge_iterator,edge_iterator> p;
235     typename graph_traits<G>::vertex_descriptor u, v;
236     typename graph_traits<G>::edge_descriptor e;
237     edges_size_type E;
238     G g;
239   };
240
241   template <class G>
242   struct VertexAndEdgeListGraphConcept
243   {
244     void constraints() {
245       function_requires< VertexListGraphConcept<G> >();    
246       function_requires< EdgeListGraphConcept<G> >();
247     }
248   };
249
250   // Where to put the requirement for this constructor?
251   //      G g(n_vertices);
252   // Not in mutable graph, then LEDA graph's can't be models of
253   // MutableGraph.
254
255   template <class G>
256   struct EdgeMutableGraphConcept
257   {
258     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
259     void constraints() {
260       p = add_edge(u, v, g);
261       remove_edge(u, v, g);
262       remove_edge(e, g);
263       clear_vertex(v, g);
264     }
265     G g;
266     edge_descriptor e;
267     std::pair<edge_descriptor, bool> p;
268     typename graph_traits<G>::vertex_descriptor u, v;
269   };
270
271   template <class G>
272   struct VertexMutableGraphConcept
273   {
274     void constraints() {
275       v = add_vertex(g);
276       remove_vertex(v, g);
277     }
278     G g;
279     typename graph_traits<G>::vertex_descriptor u, v;
280   };
281
282   template <class G>
283   struct MutableGraphConcept
284   {
285     void constraints() {
286       function_requires< EdgeMutableGraphConcept<G> >();
287       function_requires< VertexMutableGraphConcept<G> >();
288     }
289   };
290
291   template <class edge_descriptor>
292   struct dummy_edge_predicate {
293     bool operator()(const edge_descriptor&) const {
294       return false;
295     }
296   };
297
298   template <class G>
299   struct MutableIncidenceGraphConcept
300   {
301     void constraints() {
302       function_requires< MutableGraphConcept<G> >();
303       remove_edge(iter, g);
304       remove_out_edge_if(u, p, g);
305     }
306     G g;
307     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
308     dummy_edge_predicate<edge_descriptor> p;
309     typename boost::graph_traits<G>::vertex_descriptor u;
310     typename boost::graph_traits<G>::out_edge_iterator iter;
311   };
312
313   template <class G>
314   struct MutableBidirectionalGraphConcept
315   {
316     void constraints() {
317       function_requires< MutableIncidenceGraphConcept<G> >();
318       remove_in_edge_if(u, p, g);
319     }
320     G g;
321     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
322     dummy_edge_predicate<edge_descriptor> p;
323     typename boost::graph_traits<G>::vertex_descriptor u;
324   };
325
326   template <class G>
327   struct MutableEdgeListGraphConcept
328   {
329     void constraints() {
330       function_requires< EdgeMutableGraphConcept<G> >();
331       remove_edge_if(p, g);
332     }
333     G g;
334     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
335     dummy_edge_predicate<edge_descriptor> p;
336   };
337
338   template <class G>
339   struct VertexMutablePropertyGraphConcept
340   {
341     void constraints() {
342       function_requires< VertexMutableGraphConcept<G> >();
343       v = add_vertex(vp, g);
344     }
345     G g;
346     typename graph_traits<G>::vertex_descriptor v;
347     typename vertex_property<G>::type vp;
348   };
349
350   template <class G>
351   struct EdgeMutablePropertyGraphConcept
352   {
353     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
354     void constraints() {
355       function_requires< EdgeMutableGraphConcept<G> >();
356       p = add_edge(u, v, ep, g);
357     }
358     G g;
359     std::pair<edge_descriptor, bool> p;
360     typename graph_traits<G>::vertex_descriptor u, v;
361     typename edge_property<G>::type ep;
362   };
363
364   template <class G>
365   struct AdjacencyMatrixConcept
366   {
367     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
368     void constraints() {
369       function_requires< GraphConcept<G> >();
370       
371       p = edge(u, v, g);
372       const_constraints(g);
373     }
374     void const_constraints(const G& cg) {
375       p = edge(u, v, cg);
376     }
377     typename graph_traits<G>::vertex_descriptor u, v;
378     std::pair<edge_descriptor, bool> p;
379     G g;
380   };
381
382   template <class G, class X, class Property>
383   struct ReadablePropertyGraphConcept
384   {
385     typedef typename property_map<G, Property>::const_type const_Map;
386     void constraints() {
387       function_requires< GraphConcept<G> >();
388       function_requires< ReadablePropertyMapConcept<const_Map, X> >();
389
390       const_constraints(g);
391     }
392     void const_constraints(const G& cg) {
393       const_Map pmap = get(Property(), cg);
394       pval = get(Property(), cg, x);
395       ignore_unused_variable_warning(pmap);
396     }
397     G g;
398     X x;
399     typename property_traits<const_Map>::value_type pval;
400   };
401
402   template <class G, class X, class Property>
403   struct PropertyGraphConcept
404   {
405     typedef typename property_map<G, Property>::type Map;
406     void constraints() {
407       function_requires< ReadablePropertyGraphConcept<G, X, Property> >();
408       function_requires< ReadWritePropertyMapConcept<Map, X> >();
409
410       Map pmap = get(Property(), g);
411       pval = get(Property(), g, x);
412       put(Property(), g, x, pval);
413       ignore_unused_variable_warning(pmap);
414     }
415     G g;
416     X x;
417     typename property_traits<Map>::value_type pval;
418   };
419
420   template <class G, class X, class Property>
421   struct LvaluePropertyGraphConcept
422   {
423     typedef typename property_map<G, Property>::type Map;
424     typedef typename property_map<G, Property>::const_type const_Map;
425     void constraints() {
426       function_requires< ReadablePropertyGraphConcept<G, X, Property> >();
427       function_requires< LvaluePropertyMapConcept<const_Map, X> >();
428
429       pval = get(Property(), g, x);
430       put(Property(), g, x, pval);
431     }
432     G g;
433     X x;
434     typename property_traits<Map>::value_type pval;
435   };
436
437   // This needs to move out of the graph library
438   template <class B>
439   struct BufferConcept
440   {
441     void constraints() {
442       b.push(t);
443       b.pop();
444       typename B::value_type& v = b.top();
445       const_constraints(b);
446       ignore_unused_variable_warning(v);
447     }
448     void const_constraints(const B& cb) {
449       const typename B::value_type& v = cb.top();
450       n = cb.size();
451       bool e = cb.empty();
452       ignore_unused_variable_warning(v);
453       ignore_unused_variable_warning(e);
454     }
455     typename B::size_type n;
456     typename B::value_type t;
457     B b;
458   };
459
460   template <class C>
461   struct ColorValueConcept
462   {
463     void constraints() {
464       function_requires< EqualityComparableConcept<C> >();
465       function_requires< DefaultConstructibleConcept<C> >();
466
467       c = color_traits<C>::white();
468       c = color_traits<C>::gray();
469       c = color_traits<C>::black();
470     }
471     C c;
472   };
473
474   template <class M, class I, class V>
475   struct BasicMatrixConcept
476   {
477     void constraints() {
478       V& elt = A[i][j];
479       const_constraints(A);
480       ignore_unused_variable_warning(elt);      
481     }
482     void const_constraints(const M& cA) {
483       const V& elt = cA[i][j];
484       ignore_unused_variable_warning(elt);      
485     }
486     M A;
487     I i, j;
488   };
489
490 } // namespace boost
491
492 #endif /* BOOST_GRAPH_CONCEPTS_H */