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