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(cg: 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 | e = *p.first; |
132 | const_constraints(cg: g); |
133 | } |
134 | void const_constraints(const G& cg) { |
135 | p = in_edges(v, cg); |
136 | n = in_degree(v, cg); |
137 | e = *p.first; |
138 | } |
139 | std::pair<in_edge_iterator, in_edge_iterator> p; |
140 | typename graph_traits<G>::vertex_descriptor v; |
141 | typename graph_traits<G>::edge_descriptor e; |
142 | typename graph_traits<G>::degree_size_type n; |
143 | G g; |
144 | }; |
145 | |
146 | BOOST_concept(AdjacencyGraph,(G)) |
147 | : Graph<G> |
148 | { |
149 | typedef typename graph_traits<G>::adjacency_iterator |
150 | adjacency_iterator; |
151 | typedef typename graph_traits<G>::traversal_category |
152 | traversal_category; |
153 | |
154 | BOOST_CONCEPT_USAGE(AdjacencyGraph) { |
155 | BOOST_CONCEPT_ASSERT((MultiPassInputIterator<adjacency_iterator>)); |
156 | BOOST_CONCEPT_ASSERT((Convertible<traversal_category, |
157 | adjacency_graph_tag>)); |
158 | |
159 | BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<adjacency_iterator, void> >::value)); |
160 | |
161 | p = adjacent_vertices(v, g); |
162 | v = *p.first; |
163 | const_constraints(cg: g); |
164 | } |
165 | void const_constraints(const G& cg) { |
166 | p = adjacent_vertices(v, cg); |
167 | } |
168 | std::pair<adjacency_iterator,adjacency_iterator> p; |
169 | typename graph_traits<G>::vertex_descriptor v; |
170 | G g; |
171 | }; |
172 | |
173 | BOOST_concept(VertexListGraph,(G)) |
174 | : Graph<G> |
175 | { |
176 | typedef typename graph_traits<G>::vertex_iterator vertex_iterator; |
177 | typedef typename graph_traits<G>::vertices_size_type vertices_size_type; |
178 | typedef typename graph_traits<G>::traversal_category |
179 | traversal_category; |
180 | |
181 | BOOST_CONCEPT_USAGE(VertexListGraph) { |
182 | BOOST_CONCEPT_ASSERT((MultiPassInputIterator<vertex_iterator>)); |
183 | BOOST_CONCEPT_ASSERT((Convertible<traversal_category, |
184 | vertex_list_graph_tag>)); |
185 | |
186 | BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<vertex_iterator, void> >::value)); |
187 | BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<vertices_size_type, void> >::value)); |
188 | |
189 | #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK |
190 | // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if |
191 | // you want to use vector_as_graph, it is! I'm sure the graph |
192 | // library leaves these out all over the place. Probably a |
193 | // redesign involving specializing a template with a static |
194 | // member function is in order :( |
195 | using boost::vertices; |
196 | #endif |
197 | p = vertices(g); |
198 | v = *p.first; |
199 | const_constraints(cg: g); |
200 | } |
201 | void const_constraints(const G& cg) { |
202 | #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK |
203 | // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if |
204 | // you want to use vector_as_graph, it is! I'm sure the graph |
205 | // library leaves these out all over the place. Probably a |
206 | // redesign involving specializing a template with a static |
207 | // member function is in order :( |
208 | using boost::vertices; |
209 | #endif |
210 | |
211 | p = vertices(cg); |
212 | v = *p.first; |
213 | V = num_vertices(cg); |
214 | } |
215 | std::pair<vertex_iterator,vertex_iterator> p; |
216 | typename graph_traits<G>::vertex_descriptor v; |
217 | G g; |
218 | vertices_size_type V; |
219 | }; |
220 | |
221 | BOOST_concept(EdgeListGraph,(G)) |
222 | : Graph<G> |
223 | { |
224 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; |
225 | typedef typename graph_traits<G>::edge_iterator edge_iterator; |
226 | typedef typename graph_traits<G>::edges_size_type edges_size_type; |
227 | typedef typename graph_traits<G>::traversal_category |
228 | traversal_category; |
229 | |
230 | BOOST_CONCEPT_USAGE(EdgeListGraph) { |
231 | BOOST_CONCEPT_ASSERT((MultiPassInputIterator<edge_iterator>)); |
232 | BOOST_CONCEPT_ASSERT((DefaultConstructible<edge_descriptor>)); |
233 | BOOST_CONCEPT_ASSERT((EqualityComparable<edge_descriptor>)); |
234 | BOOST_CONCEPT_ASSERT((Assignable<edge_descriptor>)); |
235 | BOOST_CONCEPT_ASSERT((Convertible<traversal_category, |
236 | edge_list_graph_tag>)); |
237 | |
238 | BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<edge_iterator, void> >::value)); |
239 | BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<edges_size_type, void> >::value)); |
240 | |
241 | p = edges(g); |
242 | e = *p.first; |
243 | u = source(e, g); |
244 | v = target(e, g); |
245 | const_constraints(cg: g); |
246 | } |
247 | void const_constraints(const G& cg) { |
248 | p = edges(cg); |
249 | E = num_edges(cg); |
250 | e = *p.first; |
251 | u = source(e, cg); |
252 | v = target(e, cg); |
253 | } |
254 | std::pair<edge_iterator,edge_iterator> p; |
255 | typename graph_traits<G>::vertex_descriptor u, v; |
256 | typename graph_traits<G>::edge_descriptor e; |
257 | edges_size_type E; |
258 | G g; |
259 | }; |
260 | |
261 | BOOST_concept(VertexAndEdgeListGraph,(G)) |
262 | : VertexListGraph<G> |
263 | , EdgeListGraph<G> |
264 | { |
265 | }; |
266 | |
267 | // Where to put the requirement for this constructor? |
268 | // G g(n_vertices); |
269 | // Not in mutable graph, then LEDA graph's can't be models of |
270 | // MutableGraph. |
271 | BOOST_concept(EdgeMutableGraph,(G)) |
272 | { |
273 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; |
274 | |
275 | BOOST_CONCEPT_USAGE(EdgeMutableGraph) { |
276 | p = add_edge(u, v, g); |
277 | remove_edge(u, v, g); |
278 | remove_edge(e, g); |
279 | clear_vertex(v, g); |
280 | } |
281 | G g; |
282 | edge_descriptor e; |
283 | std::pair<edge_descriptor, bool> p; |
284 | typename graph_traits<G>::vertex_descriptor u, v; |
285 | }; |
286 | |
287 | BOOST_concept(VertexMutableGraph,(G)) |
288 | { |
289 | |
290 | BOOST_CONCEPT_USAGE(VertexMutableGraph) { |
291 | v = add_vertex(g); |
292 | remove_vertex(v, g); |
293 | } |
294 | G g; |
295 | typename graph_traits<G>::vertex_descriptor u, v; |
296 | }; |
297 | |
298 | BOOST_concept(MutableGraph,(G)) |
299 | : EdgeMutableGraph<G> |
300 | , VertexMutableGraph<G> |
301 | { |
302 | }; |
303 | |
304 | template <class edge_descriptor> |
305 | struct dummy_edge_predicate { |
306 | bool operator()(const edge_descriptor&) const { |
307 | return false; |
308 | } |
309 | }; |
310 | |
311 | BOOST_concept(MutableIncidenceGraph,(G)) |
312 | : MutableGraph<G> |
313 | { |
314 | BOOST_CONCEPT_USAGE(MutableIncidenceGraph) { |
315 | remove_edge(iter, g); |
316 | remove_out_edge_if(u, p, g); |
317 | } |
318 | G g; |
319 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; |
320 | dummy_edge_predicate<edge_descriptor> p; |
321 | typename boost::graph_traits<G>::vertex_descriptor u; |
322 | typename boost::graph_traits<G>::out_edge_iterator iter; |
323 | }; |
324 | |
325 | BOOST_concept(MutableBidirectionalGraph,(G)) |
326 | : MutableIncidenceGraph<G> |
327 | { |
328 | BOOST_CONCEPT_USAGE(MutableBidirectionalGraph) |
329 | { |
330 | remove_in_edge_if(u, p, g); |
331 | } |
332 | G g; |
333 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; |
334 | dummy_edge_predicate<edge_descriptor> p; |
335 | typename boost::graph_traits<G>::vertex_descriptor u; |
336 | }; |
337 | |
338 | BOOST_concept(MutableEdgeListGraph,(G)) |
339 | : EdgeMutableGraph<G> |
340 | { |
341 | BOOST_CONCEPT_USAGE(MutableEdgeListGraph) { |
342 | remove_edge_if(p, g); |
343 | } |
344 | G g; |
345 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; |
346 | dummy_edge_predicate<edge_descriptor> p; |
347 | }; |
348 | |
349 | BOOST_concept(VertexMutablePropertyGraph,(G)) |
350 | : VertexMutableGraph<G> |
351 | { |
352 | BOOST_CONCEPT_USAGE(VertexMutablePropertyGraph) { |
353 | v = add_vertex(vp, g); |
354 | } |
355 | G g; |
356 | typename graph_traits<G>::vertex_descriptor v; |
357 | typename vertex_property_type<G>::type vp; |
358 | }; |
359 | |
360 | BOOST_concept(EdgeMutablePropertyGraph,(G)) |
361 | : EdgeMutableGraph<G> |
362 | { |
363 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; |
364 | |
365 | BOOST_CONCEPT_USAGE(EdgeMutablePropertyGraph) { |
366 | p = add_edge(u, v, ep, g); |
367 | } |
368 | G g; |
369 | std::pair<edge_descriptor, bool> p; |
370 | typename graph_traits<G>::vertex_descriptor u, v; |
371 | typename edge_property_type<G>::type ep; |
372 | }; |
373 | |
374 | BOOST_concept(AdjacencyMatrix,(G)) |
375 | : Graph<G> |
376 | { |
377 | typedef typename graph_traits<G>::edge_descriptor edge_descriptor; |
378 | |
379 | BOOST_CONCEPT_USAGE(AdjacencyMatrix) { |
380 | p = edge(u, v, g); |
381 | const_constraints(cg: g); |
382 | } |
383 | void const_constraints(const G& cg) { |
384 | p = edge(u, v, cg); |
385 | } |
386 | typename graph_traits<G>::vertex_descriptor u, v; |
387 | std::pair<edge_descriptor, bool> p; |
388 | G g; |
389 | }; |
390 | |
391 | BOOST_concept(ReadablePropertyGraph,(G)(X)(Property)) |
392 | : Graph<G> |
393 | { |
394 | typedef typename property_map<G, Property>::const_type const_Map; |
395 | |
396 | BOOST_CONCEPT_USAGE(ReadablePropertyGraph) |
397 | { |
398 | BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<const_Map, X>)); |
399 | |
400 | const_constraints(cg: g); |
401 | } |
402 | void const_constraints(const G& cg) { |
403 | const_Map pmap = get(Property(), cg); |
404 | pval = get(Property(), cg, x); |
405 | ignore_unused_variable_warning(pmap); |
406 | } |
407 | G g; |
408 | X x; |
409 | typename property_traits<const_Map>::value_type pval; |
410 | }; |
411 | |
412 | BOOST_concept(PropertyGraph,(G)(X)(Property)) |
413 | : ReadablePropertyGraph<G, X, Property> |
414 | { |
415 | typedef typename property_map<G, Property>::type Map; |
416 | BOOST_CONCEPT_USAGE(PropertyGraph) { |
417 | BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept<Map, X>)); |
418 | |
419 | Map pmap = get(Property(), g); |
420 | pval = get(Property(), g, x); |
421 | put(Property(), g, x, pval); |
422 | ignore_unused_variable_warning(pmap); |
423 | } |
424 | G g; |
425 | X x; |
426 | typename property_traits<Map>::value_type pval; |
427 | }; |
428 | |
429 | BOOST_concept(LvaluePropertyGraph,(G)(X)(Property)) |
430 | : ReadablePropertyGraph<G, X, Property> |
431 | { |
432 | typedef typename property_map<G, Property>::type Map; |
433 | typedef typename property_map<G, Property>::const_type const_Map; |
434 | |
435 | BOOST_CONCEPT_USAGE(LvaluePropertyGraph) { |
436 | BOOST_CONCEPT_ASSERT((LvaluePropertyMapConcept<const_Map, X>)); |
437 | |
438 | pval = get(Property(), g, x); |
439 | put(Property(), g, x, pval); |
440 | } |
441 | G g; |
442 | X x; |
443 | typename property_traits<Map>::value_type pval; |
444 | }; |
445 | |
446 | // The *IndexGraph concepts are "semantic" graph concpepts. These can be |
447 | // applied to describe any graph that has an index map that can be accessed |
448 | // using the get(*_index, g) method. For example, adjacency lists with |
449 | // VertexSet == vecS are implicitly models of this concept. |
450 | // |
451 | // NOTE: We could require an associated type vertex_index_type, but that |
452 | // would mean propagating that type name into graph_traits and all of the |
453 | // other graph implementations. Much easier to simply call it unsigned. |
454 | |
455 | BOOST_concept(VertexIndexGraph,(Graph)) |
456 | { |
457 | BOOST_CONCEPT_USAGE(VertexIndexGraph) |
458 | { |
459 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
460 | typedef typename property_map<Graph, vertex_index_t>::type Map; |
461 | typedef unsigned Index; // This could be Graph::vertex_index_type |
462 | Map m = get(vertex_index, g); |
463 | Index x = get(vertex_index, g, Vertex()); |
464 | ignore_unused_variable_warning(m); |
465 | ignore_unused_variable_warning(x); |
466 | |
467 | // This is relaxed |
468 | renumber_vertex_indices(g); |
469 | |
470 | const_constraints(g_: g); |
471 | } |
472 | void const_constraints(const Graph& g_) |
473 | { |
474 | typedef typename property_map<Graph, vertex_index_t>::const_type Map; |
475 | Map m = get(vertex_index, g_); |
476 | ignore_unused_variable_warning(m); |
477 | } |
478 | private: |
479 | Graph g; |
480 | }; |
481 | |
482 | BOOST_concept(EdgeIndexGraph,(Graph)) |
483 | { |
484 | BOOST_CONCEPT_USAGE(EdgeIndexGraph) |
485 | { |
486 | typedef typename graph_traits<Graph>::edge_descriptor Edge; |
487 | typedef typename property_map<Graph, edge_index_t>::type Map; |
488 | typedef unsigned Index; // This could be Graph::vertex_index_type |
489 | Map m = get(edge_index, g); |
490 | Index x = get(edge_index, g, Edge()); |
491 | ignore_unused_variable_warning(m); |
492 | ignore_unused_variable_warning(x); |
493 | |
494 | // This is relaxed |
495 | renumber_edge_indices(g); |
496 | |
497 | const_constraints(g_: g); |
498 | } |
499 | void const_constraints(const Graph& g_) |
500 | { |
501 | typedef typename property_map<Graph, edge_index_t>::const_type Map; |
502 | Map m = get(edge_index, g_); |
503 | ignore_unused_variable_warning(m); |
504 | } |
505 | private: |
506 | Graph g; |
507 | }; |
508 | |
509 | BOOST_concept(ColorValue,(C)) |
510 | : EqualityComparable<C> |
511 | , DefaultConstructible<C> |
512 | { |
513 | BOOST_CONCEPT_USAGE(ColorValue) { |
514 | c = color_traits<C>::white(); |
515 | c = color_traits<C>::gray(); |
516 | c = color_traits<C>::black(); |
517 | } |
518 | C c; |
519 | }; |
520 | |
521 | BOOST_concept(BasicMatrix,(M)(I)(V)) |
522 | { |
523 | BOOST_CONCEPT_USAGE(BasicMatrix) { |
524 | V& elt = A[i][j]; |
525 | const_constraints(cA: A); |
526 | ignore_unused_variable_warning(elt); |
527 | } |
528 | void const_constraints(const M& cA) { |
529 | const V& elt = cA[i][j]; |
530 | ignore_unused_variable_warning(elt); |
531 | } |
532 | M A; |
533 | I i, j; |
534 | }; |
535 | |
536 | // The following concepts describe aspects of numberic values and measure |
537 | // functions. We're extending the notion of numeric values to include |
538 | // emulation for zero and infinity. |
539 | |
540 | BOOST_concept(NumericValue,(Numeric)) |
541 | { |
542 | BOOST_CONCEPT_USAGE(NumericValue) |
543 | { |
544 | BOOST_CONCEPT_ASSERT(( DefaultConstructible<Numeric> )); |
545 | BOOST_CONCEPT_ASSERT(( CopyConstructible<Numeric> )); |
546 | numeric_values<Numeric>::zero(); |
547 | numeric_values<Numeric>::infinity(); |
548 | } |
549 | }; |
550 | |
551 | BOOST_concept(DegreeMeasure,(Measure)(Graph)) |
552 | { |
553 | BOOST_CONCEPT_USAGE(DegreeMeasure) |
554 | { |
555 | typedef typename Measure::degree_type Degree; |
556 | typedef typename Measure::vertex_type Vertex; |
557 | |
558 | Degree d = m(Vertex(), g); |
559 | ignore_unused_variable_warning(d); |
560 | } |
561 | private: |
562 | Measure m; |
563 | Graph g; |
564 | }; |
565 | |
566 | BOOST_concept(DistanceMeasure,(Measure)(Graph)) |
567 | { |
568 | BOOST_CONCEPT_USAGE(DistanceMeasure) |
569 | { |
570 | typedef typename Measure::distance_type Distance; |
571 | typedef typename Measure::result_type Result; |
572 | Result r = m(Distance(), g); |
573 | ignore_unused_variable_warning(r); |
574 | } |
575 | private: |
576 | Measure m; |
577 | Graph g; |
578 | }; |
579 | |
580 | } /* namespace concepts */ |
581 | |
582 | using boost::concepts::MultiPassInputIteratorConcept; |
583 | |
584 | // Graph concepts |
585 | using boost::concepts::GraphConcept; |
586 | using boost::concepts::IncidenceGraphConcept; |
587 | using boost::concepts::BidirectionalGraphConcept; |
588 | using boost::concepts::AdjacencyGraphConcept; |
589 | using boost::concepts::VertexListGraphConcept; |
590 | using boost::concepts::EdgeListGraphConcept; |
591 | using boost::concepts::VertexAndEdgeListGraphConcept; |
592 | using boost::concepts::EdgeMutableGraphConcept; |
593 | using boost::concepts::VertexMutableGraphConcept; |
594 | using boost::concepts::MutableGraphConcept; |
595 | using boost::concepts::MutableIncidenceGraphConcept; |
596 | using boost::concepts::MutableBidirectionalGraphConcept; |
597 | using boost::concepts::MutableEdgeListGraphConcept; |
598 | using boost::concepts::VertexMutablePropertyGraphConcept; |
599 | using boost::concepts::EdgeMutablePropertyGraphConcept; |
600 | using boost::concepts::AdjacencyMatrixConcept; |
601 | using boost::concepts::ReadablePropertyGraphConcept; |
602 | using boost::concepts::PropertyGraphConcept; |
603 | using boost::concepts::LvaluePropertyGraphConcept; |
604 | using boost::concepts::VertexIndexGraphConcept; |
605 | using boost::concepts::EdgeIndexGraphConcept; |
606 | |
607 | // Utility concepts |
608 | using boost::concepts::ColorValueConcept; |
609 | using boost::concepts::BasicMatrixConcept; |
610 | using boost::concepts::NumericValueConcept; |
611 | using boost::concepts::DistanceMeasureConcept; |
612 | using boost::concepts::DegreeMeasureConcept; |
613 | |
614 | |
615 | } /* namespace boost */ |
616 | #include <boost/concept/detail/concept_undef.hpp> |
617 | |
618 | #endif /* BOOST_GRAPH_CONCEPTS_H */ |
619 | |