]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // |
2 | //======================================================================= | |
3 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
4 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek | |
5 | // | |
6 | // Copyright 2009, Andrew Sutton | |
7 | // | |
8 | // Distributed under the Boost Software License, Version 1.0. (See | |
9 | // accompanying file LICENSE_1_0.txt or copy at | |
10 | // http://www.boost.org/LICENSE_1_0.txt) | |
11 | //======================================================================= | |
12 | // | |
13 | #ifndef BOOST_GRAPH_CONCEPTS_HPP | |
14 | #define BOOST_GRAPH_CONCEPTS_HPP | |
15 | ||
16 | #include <boost/config.hpp> | |
17 | #include <boost/property_map/property_map.hpp> | |
18 | #include <boost/graph/graph_traits.hpp> | |
19 | #include <boost/graph/properties.hpp> | |
20 | #include <boost/graph/numeric_values.hpp> | |
21 | #include <boost/graph/buffer_concepts.hpp> | |
22 | #include <boost/concept_check.hpp> | |
23 | #include <boost/type_traits/is_same.hpp> | |
24 | #include <boost/mpl/not.hpp> | |
25 | #include <boost/static_assert.hpp> | |
26 | #include <boost/detail/workaround.hpp> | |
27 | #include <boost/concept/assert.hpp> | |
28 | ||
29 | #include <boost/concept/detail/concept_def.hpp> | |
30 | namespace boost | |
31 | { | |
32 | // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if | |
33 | // you want to use vector_as_graph, it is! I'm sure the graph | |
34 | // library leaves these out all over the place. Probably a | |
35 | // redesign involving specializing a template with a static | |
36 | // member function is in order :( | |
37 | // | |
38 | // It is needed in order to allow us to write using boost::vertices as | |
39 | // needed for ADL when using vector_as_graph below. | |
40 | #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) \ | |
41 | && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) | |
42 | # define BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK | |
43 | #endif | |
44 | ||
45 | #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK | |
46 | template <class T> | |
47 | typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&); | |
48 | #endif | |
49 | ||
50 | namespace concepts { | |
51 | BOOST_concept(MultiPassInputIterator,(T)) { | |
52 | BOOST_CONCEPT_USAGE(MultiPassInputIterator) { | |
53 | BOOST_CONCEPT_ASSERT((InputIterator<T>)); | |
54 | } | |
55 | }; | |
56 | ||
57 | BOOST_concept(Graph,(G)) | |
58 | { | |
59 | typedef typename graph_traits<G>::vertex_descriptor vertex_descriptor; | |
60 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; | |
61 | typedef typename graph_traits<G>::directed_category directed_category; | |
62 | typedef typename graph_traits<G>::edge_parallel_category edge_parallel_category; | |
63 | typedef typename graph_traits<G>::traversal_category traversal_category; | |
64 | ||
65 | BOOST_CONCEPT_USAGE(Graph) | |
66 | { | |
67 | BOOST_CONCEPT_ASSERT((DefaultConstructible<vertex_descriptor>)); | |
68 | BOOST_CONCEPT_ASSERT((EqualityComparable<vertex_descriptor>)); | |
69 | BOOST_CONCEPT_ASSERT((Assignable<vertex_descriptor>)); | |
70 | } | |
71 | G g; | |
72 | }; | |
73 | ||
74 | BOOST_concept(IncidenceGraph,(G)) | |
75 | : Graph<G> | |
76 | { | |
77 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; | |
78 | typedef typename graph_traits<G>::out_edge_iterator out_edge_iterator; | |
79 | typedef typename graph_traits<G>::degree_size_type degree_size_type; | |
80 | typedef typename graph_traits<G>::traversal_category traversal_category; | |
81 | ||
82 | BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<out_edge_iterator, void> >::value)); | |
83 | BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<degree_size_type, void> >::value)); | |
84 | ||
85 | BOOST_CONCEPT_USAGE(IncidenceGraph) { | |
86 | BOOST_CONCEPT_ASSERT((MultiPassInputIterator<out_edge_iterator>)); | |
87 | BOOST_CONCEPT_ASSERT((DefaultConstructible<edge_descriptor>)); | |
88 | BOOST_CONCEPT_ASSERT((EqualityComparable<edge_descriptor>)); | |
89 | BOOST_CONCEPT_ASSERT((Assignable<edge_descriptor>)); | |
90 | BOOST_CONCEPT_ASSERT((Convertible<traversal_category, | |
91 | incidence_graph_tag>)); | |
92 | ||
93 | p = out_edges(u, g); | |
94 | n = out_degree(u, g); | |
95 | e = *p.first; | |
96 | u = source(e, g); | |
97 | v = target(e, g); | |
98 | const_constraints(g); | |
99 | } | |
100 | void const_constraints(const G& cg) { | |
101 | p = out_edges(u, cg); | |
102 | n = out_degree(u, cg); | |
103 | e = *p.first; | |
104 | u = source(e, cg); | |
105 | v = target(e, cg); | |
106 | } | |
107 | std::pair<out_edge_iterator, out_edge_iterator> p; | |
108 | typename graph_traits<G>::vertex_descriptor u, v; | |
109 | typename graph_traits<G>::edge_descriptor e; | |
110 | typename graph_traits<G>::degree_size_type n; | |
111 | G g; | |
112 | }; | |
113 | ||
114 | BOOST_concept(BidirectionalGraph,(G)) | |
115 | : IncidenceGraph<G> | |
116 | { | |
117 | typedef typename graph_traits<G>::in_edge_iterator | |
118 | in_edge_iterator; | |
119 | typedef typename graph_traits<G>::traversal_category | |
120 | traversal_category; | |
121 | ||
122 | BOOST_CONCEPT_USAGE(BidirectionalGraph) { | |
123 | BOOST_CONCEPT_ASSERT((MultiPassInputIterator<in_edge_iterator>)); | |
124 | BOOST_CONCEPT_ASSERT((Convertible<traversal_category, | |
125 | bidirectional_graph_tag>)); | |
126 | ||
127 | BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<in_edge_iterator, void> >::value)); | |
128 | ||
129 | p = in_edges(v, g); | |
130 | n = in_degree(v, g); | |
131 | n = degree(v, g); | |
132 | e = *p.first; | |
133 | const_constraints(g); | |
134 | } | |
135 | void const_constraints(const G& cg) { | |
136 | p = in_edges(v, cg); | |
137 | n = in_degree(v, cg); | |
138 | n = degree(v, cg); | |
139 | e = *p.first; | |
140 | } | |
141 | std::pair<in_edge_iterator, in_edge_iterator> p; | |
142 | typename graph_traits<G>::vertex_descriptor v; | |
143 | typename graph_traits<G>::edge_descriptor e; | |
144 | typename graph_traits<G>::degree_size_type n; | |
145 | G g; | |
146 | }; | |
147 | ||
148 | BOOST_concept(AdjacencyGraph,(G)) | |
149 | : Graph<G> | |
150 | { | |
151 | typedef typename graph_traits<G>::adjacency_iterator | |
152 | adjacency_iterator; | |
153 | typedef typename graph_traits<G>::traversal_category | |
154 | traversal_category; | |
155 | ||
156 | BOOST_CONCEPT_USAGE(AdjacencyGraph) { | |
157 | BOOST_CONCEPT_ASSERT((MultiPassInputIterator<adjacency_iterator>)); | |
158 | BOOST_CONCEPT_ASSERT((Convertible<traversal_category, | |
159 | adjacency_graph_tag>)); | |
160 | ||
161 | BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<adjacency_iterator, void> >::value)); | |
162 | ||
163 | p = adjacent_vertices(v, g); | |
164 | v = *p.first; | |
165 | const_constraints(g); | |
166 | } | |
167 | void const_constraints(const G& cg) { | |
168 | p = adjacent_vertices(v, cg); | |
169 | } | |
170 | std::pair<adjacency_iterator,adjacency_iterator> p; | |
171 | typename graph_traits<G>::vertex_descriptor v; | |
172 | G g; | |
173 | }; | |
174 | ||
175 | BOOST_concept(VertexListGraph,(G)) | |
176 | : Graph<G> | |
177 | { | |
178 | typedef typename graph_traits<G>::vertex_iterator vertex_iterator; | |
179 | typedef typename graph_traits<G>::vertices_size_type vertices_size_type; | |
180 | typedef typename graph_traits<G>::traversal_category | |
181 | traversal_category; | |
182 | ||
183 | BOOST_CONCEPT_USAGE(VertexListGraph) { | |
184 | BOOST_CONCEPT_ASSERT((MultiPassInputIterator<vertex_iterator>)); | |
185 | BOOST_CONCEPT_ASSERT((Convertible<traversal_category, | |
186 | vertex_list_graph_tag>)); | |
187 | ||
188 | BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<vertex_iterator, void> >::value)); | |
189 | BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<vertices_size_type, void> >::value)); | |
190 | ||
191 | #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK | |
192 | // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if | |
193 | // you want to use vector_as_graph, it is! I'm sure the graph | |
194 | // library leaves these out all over the place. Probably a | |
195 | // redesign involving specializing a template with a static | |
196 | // member function is in order :( | |
197 | using boost::vertices; | |
198 | #endif | |
199 | p = vertices(g); | |
200 | v = *p.first; | |
201 | const_constraints(g); | |
202 | } | |
203 | void const_constraints(const G& cg) { | |
204 | #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK | |
205 | // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if | |
206 | // you want to use vector_as_graph, it is! I'm sure the graph | |
207 | // library leaves these out all over the place. Probably a | |
208 | // redesign involving specializing a template with a static | |
209 | // member function is in order :( | |
210 | using boost::vertices; | |
211 | #endif | |
212 | ||
213 | p = vertices(cg); | |
214 | v = *p.first; | |
215 | V = num_vertices(cg); | |
216 | } | |
217 | std::pair<vertex_iterator,vertex_iterator> p; | |
218 | typename graph_traits<G>::vertex_descriptor v; | |
219 | G g; | |
220 | vertices_size_type V; | |
221 | }; | |
222 | ||
223 | BOOST_concept(EdgeListGraph,(G)) | |
224 | : Graph<G> | |
225 | { | |
226 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; | |
227 | typedef typename graph_traits<G>::edge_iterator edge_iterator; | |
228 | typedef typename graph_traits<G>::edges_size_type edges_size_type; | |
229 | typedef typename graph_traits<G>::traversal_category | |
230 | traversal_category; | |
231 | ||
232 | BOOST_CONCEPT_USAGE(EdgeListGraph) { | |
233 | BOOST_CONCEPT_ASSERT((MultiPassInputIterator<edge_iterator>)); | |
234 | BOOST_CONCEPT_ASSERT((DefaultConstructible<edge_descriptor>)); | |
235 | BOOST_CONCEPT_ASSERT((EqualityComparable<edge_descriptor>)); | |
236 | BOOST_CONCEPT_ASSERT((Assignable<edge_descriptor>)); | |
237 | BOOST_CONCEPT_ASSERT((Convertible<traversal_category, | |
238 | edge_list_graph_tag>)); | |
239 | ||
240 | BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<edge_iterator, void> >::value)); | |
241 | BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<edges_size_type, void> >::value)); | |
242 | ||
243 | p = edges(g); | |
244 | e = *p.first; | |
245 | u = source(e, g); | |
246 | v = target(e, g); | |
247 | const_constraints(g); | |
248 | } | |
249 | void const_constraints(const G& cg) { | |
250 | p = edges(cg); | |
251 | E = num_edges(cg); | |
252 | e = *p.first; | |
253 | u = source(e, cg); | |
254 | v = target(e, cg); | |
255 | } | |
256 | std::pair<edge_iterator,edge_iterator> p; | |
257 | typename graph_traits<G>::vertex_descriptor u, v; | |
258 | typename graph_traits<G>::edge_descriptor e; | |
259 | edges_size_type E; | |
260 | G g; | |
261 | }; | |
262 | ||
263 | BOOST_concept(VertexAndEdgeListGraph,(G)) | |
264 | : VertexListGraph<G> | |
265 | , EdgeListGraph<G> | |
266 | { | |
267 | }; | |
268 | ||
269 | // Where to put the requirement for this constructor? | |
270 | // G g(n_vertices); | |
271 | // Not in mutable graph, then LEDA graph's can't be models of | |
272 | // MutableGraph. | |
273 | BOOST_concept(EdgeMutableGraph,(G)) | |
274 | { | |
275 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; | |
276 | ||
277 | BOOST_CONCEPT_USAGE(EdgeMutableGraph) { | |
278 | p = add_edge(u, v, g); | |
279 | remove_edge(u, v, g); | |
280 | remove_edge(e, g); | |
281 | clear_vertex(v, g); | |
282 | } | |
283 | G g; | |
284 | edge_descriptor e; | |
285 | std::pair<edge_descriptor, bool> p; | |
286 | typename graph_traits<G>::vertex_descriptor u, v; | |
287 | }; | |
288 | ||
289 | BOOST_concept(VertexMutableGraph,(G)) | |
290 | { | |
291 | ||
292 | BOOST_CONCEPT_USAGE(VertexMutableGraph) { | |
293 | v = add_vertex(g); | |
294 | remove_vertex(v, g); | |
295 | } | |
296 | G g; | |
297 | typename graph_traits<G>::vertex_descriptor u, v; | |
298 | }; | |
299 | ||
300 | BOOST_concept(MutableGraph,(G)) | |
301 | : EdgeMutableGraph<G> | |
302 | , VertexMutableGraph<G> | |
303 | { | |
304 | }; | |
305 | ||
306 | template <class edge_descriptor> | |
307 | struct dummy_edge_predicate { | |
308 | bool operator()(const edge_descriptor&) const { | |
309 | return false; | |
310 | } | |
311 | }; | |
312 | ||
313 | BOOST_concept(MutableIncidenceGraph,(G)) | |
314 | : MutableGraph<G> | |
315 | { | |
316 | BOOST_CONCEPT_USAGE(MutableIncidenceGraph) { | |
317 | remove_edge(iter, g); | |
318 | remove_out_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 | typename boost::graph_traits<G>::out_edge_iterator iter; | |
325 | }; | |
326 | ||
327 | BOOST_concept(MutableBidirectionalGraph,(G)) | |
328 | : MutableIncidenceGraph<G> | |
329 | { | |
330 | BOOST_CONCEPT_USAGE(MutableBidirectionalGraph) | |
331 | { | |
332 | remove_in_edge_if(u, p, g); | |
333 | } | |
334 | G g; | |
335 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; | |
336 | dummy_edge_predicate<edge_descriptor> p; | |
337 | typename boost::graph_traits<G>::vertex_descriptor u; | |
338 | }; | |
339 | ||
340 | BOOST_concept(MutableEdgeListGraph,(G)) | |
341 | : EdgeMutableGraph<G> | |
342 | { | |
343 | BOOST_CONCEPT_USAGE(MutableEdgeListGraph) { | |
344 | remove_edge_if(p, g); | |
345 | } | |
346 | G g; | |
347 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; | |
348 | dummy_edge_predicate<edge_descriptor> p; | |
349 | }; | |
350 | ||
351 | BOOST_concept(VertexMutablePropertyGraph,(G)) | |
352 | : VertexMutableGraph<G> | |
353 | { | |
354 | BOOST_CONCEPT_USAGE(VertexMutablePropertyGraph) { | |
355 | v = add_vertex(vp, g); | |
356 | } | |
357 | G g; | |
358 | typename graph_traits<G>::vertex_descriptor v; | |
359 | typename vertex_property_type<G>::type vp; | |
360 | }; | |
361 | ||
362 | BOOST_concept(EdgeMutablePropertyGraph,(G)) | |
363 | : EdgeMutableGraph<G> | |
364 | { | |
365 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; | |
366 | ||
367 | BOOST_CONCEPT_USAGE(EdgeMutablePropertyGraph) { | |
368 | p = add_edge(u, v, ep, g); | |
369 | } | |
370 | G g; | |
371 | std::pair<edge_descriptor, bool> p; | |
372 | typename graph_traits<G>::vertex_descriptor u, v; | |
373 | typename edge_property_type<G>::type ep; | |
374 | }; | |
375 | ||
376 | BOOST_concept(AdjacencyMatrix,(G)) | |
377 | : Graph<G> | |
378 | { | |
379 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; | |
380 | ||
381 | BOOST_CONCEPT_USAGE(AdjacencyMatrix) { | |
382 | p = edge(u, v, g); | |
383 | const_constraints(g); | |
384 | } | |
385 | void const_constraints(const G& cg) { | |
386 | p = edge(u, v, cg); | |
387 | } | |
388 | typename graph_traits<G>::vertex_descriptor u, v; | |
389 | std::pair<edge_descriptor, bool> p; | |
390 | G g; | |
391 | }; | |
392 | ||
393 | BOOST_concept(ReadablePropertyGraph,(G)(X)(Property)) | |
394 | : Graph<G> | |
395 | { | |
396 | typedef typename property_map<G, Property>::const_type const_Map; | |
397 | ||
398 | BOOST_CONCEPT_USAGE(ReadablePropertyGraph) | |
399 | { | |
400 | BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<const_Map, X>)); | |
401 | ||
402 | const_constraints(g); | |
403 | } | |
404 | void const_constraints(const G& cg) { | |
405 | const_Map pmap = get(Property(), cg); | |
406 | pval = get(Property(), cg, x); | |
407 | ignore_unused_variable_warning(pmap); | |
408 | } | |
409 | G g; | |
410 | X x; | |
411 | typename property_traits<const_Map>::value_type pval; | |
412 | }; | |
413 | ||
414 | BOOST_concept(PropertyGraph,(G)(X)(Property)) | |
415 | : ReadablePropertyGraph<G, X, Property> | |
416 | { | |
417 | typedef typename property_map<G, Property>::type Map; | |
418 | BOOST_CONCEPT_USAGE(PropertyGraph) { | |
419 | BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept<Map, X>)); | |
420 | ||
421 | Map pmap = get(Property(), g); | |
422 | pval = get(Property(), g, x); | |
423 | put(Property(), g, x, pval); | |
424 | ignore_unused_variable_warning(pmap); | |
425 | } | |
426 | G g; | |
427 | X x; | |
428 | typename property_traits<Map>::value_type pval; | |
429 | }; | |
430 | ||
431 | BOOST_concept(LvaluePropertyGraph,(G)(X)(Property)) | |
432 | : ReadablePropertyGraph<G, X, Property> | |
433 | { | |
434 | typedef typename property_map<G, Property>::type Map; | |
435 | typedef typename property_map<G, Property>::const_type const_Map; | |
436 | ||
437 | BOOST_CONCEPT_USAGE(LvaluePropertyGraph) { | |
438 | BOOST_CONCEPT_ASSERT((LvaluePropertyMapConcept<const_Map, X>)); | |
439 | ||
440 | pval = get(Property(), g, x); | |
441 | put(Property(), g, x, pval); | |
442 | } | |
443 | G g; | |
444 | X x; | |
445 | typename property_traits<Map>::value_type pval; | |
446 | }; | |
447 | ||
448 | // The *IndexGraph concepts are "semantic" graph concpepts. These can be | |
449 | // applied to describe any graph that has an index map that can be accessed | |
450 | // using the get(*_index, g) method. For example, adjacency lists with | |
451 | // VertexSet == vecS are implicitly models of this concept. | |
452 | // | |
453 | // NOTE: We could require an associated type vertex_index_type, but that | |
454 | // would mean propagating that type name into graph_traits and all of the | |
455 | // other graph implementations. Much easier to simply call it unsigned. | |
456 | ||
457 | BOOST_concept(VertexIndexGraph,(Graph)) | |
458 | { | |
459 | BOOST_CONCEPT_USAGE(VertexIndexGraph) | |
460 | { | |
461 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
462 | typedef typename property_map<Graph, vertex_index_t>::type Map; | |
463 | typedef unsigned Index; // This could be Graph::vertex_index_type | |
464 | Map m = get(vertex_index, g); | |
465 | Index x = get(vertex_index, g, Vertex()); | |
466 | ignore_unused_variable_warning(m); | |
467 | ignore_unused_variable_warning(x); | |
468 | ||
469 | // This is relaxed | |
470 | renumber_vertex_indices(g); | |
471 | ||
472 | const_constraints(g); | |
473 | } | |
474 | void const_constraints(const Graph& g_) | |
475 | { | |
476 | typedef typename property_map<Graph, vertex_index_t>::const_type Map; | |
477 | Map m = get(vertex_index, g_); | |
478 | ignore_unused_variable_warning(m); | |
479 | } | |
480 | private: | |
481 | Graph g; | |
482 | }; | |
483 | ||
484 | BOOST_concept(EdgeIndexGraph,(Graph)) | |
485 | { | |
486 | BOOST_CONCEPT_USAGE(EdgeIndexGraph) | |
487 | { | |
488 | typedef typename graph_traits<Graph>::edge_descriptor Edge; | |
489 | typedef typename property_map<Graph, edge_index_t>::type Map; | |
490 | typedef unsigned Index; // This could be Graph::vertex_index_type | |
491 | Map m = get(edge_index, g); | |
492 | Index x = get(edge_index, g, Edge()); | |
493 | ignore_unused_variable_warning(m); | |
494 | ignore_unused_variable_warning(x); | |
495 | ||
496 | // This is relaxed | |
497 | renumber_edge_indices(g); | |
498 | ||
499 | const_constraints(g); | |
500 | } | |
501 | void const_constraints(const Graph& g_) | |
502 | { | |
503 | typedef typename property_map<Graph, edge_index_t>::const_type Map; | |
504 | Map m = get(edge_index, g_); | |
505 | ignore_unused_variable_warning(m); | |
506 | } | |
507 | private: | |
508 | Graph g; | |
509 | }; | |
510 | ||
511 | BOOST_concept(ColorValue,(C)) | |
512 | : EqualityComparable<C> | |
513 | , DefaultConstructible<C> | |
514 | { | |
515 | BOOST_CONCEPT_USAGE(ColorValue) { | |
516 | c = color_traits<C>::white(); | |
517 | c = color_traits<C>::gray(); | |
518 | c = color_traits<C>::black(); | |
519 | } | |
520 | C c; | |
521 | }; | |
522 | ||
523 | BOOST_concept(BasicMatrix,(M)(I)(V)) | |
524 | { | |
525 | BOOST_CONCEPT_USAGE(BasicMatrix) { | |
526 | V& elt = A[i][j]; | |
527 | const_constraints(A); | |
528 | ignore_unused_variable_warning(elt); | |
529 | } | |
530 | void const_constraints(const M& cA) { | |
531 | const V& elt = cA[i][j]; | |
532 | ignore_unused_variable_warning(elt); | |
533 | } | |
534 | M A; | |
535 | I i, j; | |
536 | }; | |
537 | ||
538 | // The following concepts describe aspects of numberic values and measure | |
539 | // functions. We're extending the notion of numeric values to include | |
540 | // emulation for zero and infinity. | |
541 | ||
542 | BOOST_concept(NumericValue,(Numeric)) | |
543 | { | |
544 | BOOST_CONCEPT_USAGE(NumericValue) | |
545 | { | |
546 | BOOST_CONCEPT_ASSERT(( DefaultConstructible<Numeric> )); | |
547 | BOOST_CONCEPT_ASSERT(( CopyConstructible<Numeric> )); | |
548 | numeric_values<Numeric>::zero(); | |
549 | numeric_values<Numeric>::infinity(); | |
550 | } | |
551 | }; | |
552 | ||
553 | BOOST_concept(DegreeMeasure,(Measure)(Graph)) | |
554 | { | |
555 | BOOST_CONCEPT_USAGE(DegreeMeasure) | |
556 | { | |
557 | typedef typename Measure::degree_type Degree; | |
558 | typedef typename Measure::vertex_type Vertex; | |
559 | ||
560 | Degree d = m(Vertex(), g); | |
561 | ignore_unused_variable_warning(d); | |
562 | } | |
563 | private: | |
564 | Measure m; | |
565 | Graph g; | |
566 | }; | |
567 | ||
568 | BOOST_concept(DistanceMeasure,(Measure)(Graph)) | |
569 | { | |
570 | BOOST_CONCEPT_USAGE(DistanceMeasure) | |
571 | { | |
572 | typedef typename Measure::distance_type Distance; | |
573 | typedef typename Measure::result_type Result; | |
574 | Result r = m(Distance(), g); | |
575 | ignore_unused_variable_warning(r); | |
576 | } | |
577 | private: | |
578 | Measure m; | |
579 | Graph g; | |
580 | }; | |
581 | ||
582 | } /* namespace concepts */ | |
583 | ||
584 | using boost::concepts::MultiPassInputIteratorConcept; | |
585 | ||
586 | // Graph concepts | |
587 | using boost::concepts::GraphConcept; | |
588 | using boost::concepts::IncidenceGraphConcept; | |
589 | using boost::concepts::BidirectionalGraphConcept; | |
590 | using boost::concepts::AdjacencyGraphConcept; | |
591 | using boost::concepts::VertexListGraphConcept; | |
592 | using boost::concepts::EdgeListGraphConcept; | |
593 | using boost::concepts::VertexAndEdgeListGraphConcept; | |
594 | using boost::concepts::EdgeMutableGraphConcept; | |
595 | using boost::concepts::VertexMutableGraphConcept; | |
596 | using boost::concepts::MutableGraphConcept; | |
597 | using boost::concepts::MutableIncidenceGraphConcept; | |
598 | using boost::concepts::MutableBidirectionalGraphConcept; | |
599 | using boost::concepts::MutableEdgeListGraphConcept; | |
600 | using boost::concepts::VertexMutablePropertyGraphConcept; | |
601 | using boost::concepts::EdgeMutablePropertyGraphConcept; | |
602 | using boost::concepts::AdjacencyMatrixConcept; | |
603 | using boost::concepts::ReadablePropertyGraphConcept; | |
604 | using boost::concepts::PropertyGraphConcept; | |
605 | using boost::concepts::LvaluePropertyGraphConcept; | |
606 | using boost::concepts::VertexIndexGraphConcept; | |
607 | using boost::concepts::EdgeIndexGraphConcept; | |
608 | ||
609 | // Utility concepts | |
610 | using boost::concepts::ColorValueConcept; | |
611 | using boost::concepts::BasicMatrixConcept; | |
612 | using boost::concepts::NumericValueConcept; | |
613 | using boost::concepts::DistanceMeasureConcept; | |
614 | using boost::concepts::DegreeMeasureConcept; | |
615 | ||
616 | ||
617 | } /* namespace boost */ | |
618 | #include <boost/concept/detail/concept_undef.hpp> | |
619 | ||
620 | #endif /* BOOST_GRAPH_CONCEPTS_H */ |