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>
30namespace 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
46template <class T>
47typename 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
582using boost::concepts::MultiPassInputIteratorConcept;
583
584// Graph concepts
585using boost::concepts::GraphConcept;
586using boost::concepts::IncidenceGraphConcept;
587using boost::concepts::BidirectionalGraphConcept;
588using boost::concepts::AdjacencyGraphConcept;
589using boost::concepts::VertexListGraphConcept;
590using boost::concepts::EdgeListGraphConcept;
591using boost::concepts::VertexAndEdgeListGraphConcept;
592using boost::concepts::EdgeMutableGraphConcept;
593using boost::concepts::VertexMutableGraphConcept;
594using boost::concepts::MutableGraphConcept;
595using boost::concepts::MutableIncidenceGraphConcept;
596using boost::concepts::MutableBidirectionalGraphConcept;
597using boost::concepts::MutableEdgeListGraphConcept;
598using boost::concepts::VertexMutablePropertyGraphConcept;
599using boost::concepts::EdgeMutablePropertyGraphConcept;
600using boost::concepts::AdjacencyMatrixConcept;
601using boost::concepts::ReadablePropertyGraphConcept;
602using boost::concepts::PropertyGraphConcept;
603using boost::concepts::LvaluePropertyGraphConcept;
604using boost::concepts::VertexIndexGraphConcept;
605using boost::concepts::EdgeIndexGraphConcept;
606
607// Utility concepts
608using boost::concepts::ColorValueConcept;
609using boost::concepts::BasicMatrixConcept;
610using boost::concepts::NumericValueConcept;
611using boost::concepts::DistanceMeasureConcept;
612using boost::concepts::DegreeMeasureConcept;
613
614
615} /* namespace boost */
616#include <boost/concept/detail/concept_undef.hpp>
617
618#endif /* BOOST_GRAPH_CONCEPTS_H */
619

source code of boost/boost/graph/graph_concepts.hpp