source: NonGTP/Boost/boost/graph/graph_concepts.hpp @ 857

Revision 857, 15.0 KB checked in by igarcia, 19 years ago (diff)
Line 
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
21namespace 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
155template <class T>
156typename 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 */
Note: See TracBrowser for help on using the repository browser.