]>
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. | |
f67539c2 | 40 | #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) \ |
20effc67 | 41 | && !BOOST_WORKAROUND(BOOST_BORLANDC, BOOST_TESTED_AT(0x564)) |
f67539c2 | 42 | #define BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK |
7c673cae FG |
43 | #endif |
44 | ||
45 | #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK | |
f67539c2 | 46 | template < class T > |
7c673cae FG |
47 | typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&); |
48 | #endif | |
49 | ||
f67539c2 TL |
50 | namespace concepts |
51 | { | |
52 | BOOST_concept(MultiPassInputIterator, (T)) { BOOST_CONCEPT_USAGE( | |
53 | MultiPassInputIterator) { BOOST_CONCEPT_ASSERT((InputIterator< T >)); | |
54 | } | |
55 | }; | |
7c673cae | 56 | |
f67539c2 TL |
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 | |
63 | edge_parallel_category; | |
64 | typedef typename graph_traits< G >::traversal_category traversal_category; | |
65 | ||
66 | BOOST_CONCEPT_USAGE(Graph) | |
7c673cae | 67 | { |
f67539c2 TL |
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 | ||
75 | BOOST_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) | |
7c673cae | 88 | { |
f67539c2 TL |
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(g); | |
102 | } | |
103 | void const_constraints(const G& cg) | |
7c673cae | 104 | { |
f67539c2 TL |
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 | ||
118 | BOOST_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; | |
7c673cae | 122 | |
f67539c2 TL |
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 >)); | |
7c673cae | 128 | |
f67539c2 TL |
129 | BOOST_STATIC_ASSERT((boost::mpl::not_< |
130 | boost::is_same< in_edge_iterator, void > >::value)); | |
7c673cae FG |
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(g); | |
f67539c2 TL |
137 | } |
138 | void const_constraints(const G& cg) | |
139 | { | |
7c673cae FG |
140 | p = in_edges(v, cg); |
141 | n = in_degree(v, cg); | |
142 | n = degree(v, cg); | |
143 | e = *p.first; | |
f67539c2 TL |
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 | ||
152 | BOOST_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; | |
7c673cae | 156 | |
f67539c2 TL |
157 | BOOST_CONCEPT_USAGE(AdjacencyGraph) |
158 | { | |
159 | BOOST_CONCEPT_ASSERT((MultiPassInputIterator< adjacency_iterator >)); | |
160 | BOOST_CONCEPT_ASSERT( | |
161 | (Convertible< traversal_category, adjacency_graph_tag >)); | |
7c673cae | 162 | |
f67539c2 TL |
163 | BOOST_STATIC_ASSERT((boost::mpl::not_< |
164 | boost::is_same< adjacency_iterator, void > >::value)); | |
7c673cae FG |
165 | |
166 | p = adjacent_vertices(v, g); | |
167 | v = *p.first; | |
168 | const_constraints(g); | |
f67539c2 TL |
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 | ||
176 | BOOST_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; | |
7c673cae | 181 | |
f67539c2 TL |
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 >)); | |
7c673cae | 187 | |
f67539c2 TL |
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)); | |
7c673cae FG |
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(g); | |
f67539c2 TL |
204 | } |
205 | void const_constraints(const G& cg) | |
206 | { | |
7c673cae FG |
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); | |
f67539c2 TL |
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 | ||
226 | BOOST_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) | |
7c673cae | 234 | { |
f67539c2 TL |
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)); | |
7c673cae FG |
246 | |
247 | p = edges(g); | |
248 | e = *p.first; | |
249 | u = source(e, g); | |
250 | v = target(e, g); | |
251 | const_constraints(g); | |
f67539c2 TL |
252 | } |
253 | void const_constraints(const G& cg) | |
254 | { | |
7c673cae FG |
255 | p = edges(cg); |
256 | E = num_edges(cg); | |
257 | e = *p.first; | |
258 | u = source(e, cg); | |
259 | v = target(e, cg); | |
f67539c2 TL |
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 | ||
268 | BOOST_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. | |
275 | BOOST_concept(EdgeMutableGraph, (G)) | |
276 | { | |
277 | typedef typename graph_traits< G >::edge_descriptor edge_descriptor; | |
7c673cae | 278 | |
f67539c2 | 279 | BOOST_CONCEPT_USAGE(EdgeMutableGraph) |
7c673cae | 280 | { |
7c673cae FG |
281 | p = add_edge(u, v, g); |
282 | remove_edge(u, v, g); | |
283 | remove_edge(e, g); | |
284 | clear_vertex(v, g); | |
f67539c2 TL |
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 | ||
292 | BOOST_concept(VertexMutableGraph, (G)) | |
293 | { | |
7c673cae | 294 | |
f67539c2 TL |
295 | BOOST_CONCEPT_USAGE(VertexMutableGraph) |
296 | { | |
7c673cae FG |
297 | v = add_vertex(g); |
298 | remove_vertex(v, g); | |
f67539c2 TL |
299 | } |
300 | G g; | |
301 | typename graph_traits< G >::vertex_descriptor u, v; | |
302 | }; | |
7c673cae | 303 | |
f67539c2 TL |
304 | BOOST_concept(MutableGraph, (G)) |
305 | : EdgeMutableGraph< G >, VertexMutableGraph< G > {}; | |
306 | ||
307 | template < class edge_descriptor > struct dummy_edge_predicate | |
308 | { | |
309 | bool operator()(const edge_descriptor&) const { return false; } | |
310 | }; | |
7c673cae | 311 | |
f67539c2 TL |
312 | BOOST_concept(MutableIncidenceGraph, (G)) : MutableGraph< G > |
313 | { | |
314 | BOOST_CONCEPT_USAGE(MutableIncidenceGraph) | |
7c673cae | 315 | { |
7c673cae FG |
316 | remove_edge(iter, g); |
317 | remove_out_edge_if(u, p, g); | |
f67539c2 TL |
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 | ||
326 | BOOST_concept(MutableBidirectionalGraph, (G)) : MutableIncidenceGraph< G > | |
327 | { | |
328 | BOOST_CONCEPT_USAGE(MutableBidirectionalGraph) | |
7c673cae | 329 | { |
f67539c2 TL |
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)) : 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 | ||
346 | BOOST_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 | ||
354 | BOOST_concept(EdgeMutablePropertyGraph, (G)) : EdgeMutableGraph< G > | |
355 | { | |
356 | typedef typename graph_traits< G >::edge_descriptor edge_descriptor; | |
7c673cae | 357 | |
f67539c2 TL |
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 | ||
365 | BOOST_concept(AdjacencyMatrix, (G)) : Graph< G > | |
366 | { | |
367 | typedef typename graph_traits< G >::edge_descriptor edge_descriptor; | |
368 | ||
369 | BOOST_CONCEPT_USAGE(AdjacencyMatrix) | |
370 | { | |
7c673cae FG |
371 | p = edge(u, v, g); |
372 | const_constraints(g); | |
f67539c2 TL |
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 | ||
380 | BOOST_concept(ReadablePropertyGraph, (G)(X)(Property)) : Graph< G > | |
381 | { | |
382 | typedef typename property_map< G, Property >::const_type const_Map; | |
7c673cae | 383 | |
f67539c2 TL |
384 | BOOST_CONCEPT_USAGE(ReadablePropertyGraph) |
385 | { | |
386 | BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< const_Map, X >)); | |
7c673cae FG |
387 | |
388 | const_constraints(g); | |
f67539c2 TL |
389 | } |
390 | void const_constraints(const G& cg) | |
391 | { | |
7c673cae FG |
392 | const_Map pmap = get(Property(), cg); |
393 | pval = get(Property(), cg, x); | |
394 | ignore_unused_variable_warning(pmap); | |
f67539c2 TL |
395 | } |
396 | G g; | |
397 | X x; | |
398 | typename property_traits< const_Map >::value_type pval; | |
399 | }; | |
400 | ||
401 | BOOST_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) | |
7c673cae | 406 | { |
f67539c2 | 407 | BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< Map, X >)); |
7c673cae FG |
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); | |
f67539c2 TL |
413 | } |
414 | G g; | |
415 | X x; | |
416 | typename property_traits< Map >::value_type pval; | |
417 | }; | |
418 | ||
419 | BOOST_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; | |
7c673cae | 424 | |
f67539c2 TL |
425 | BOOST_CONCEPT_USAGE(LvaluePropertyGraph) |
426 | { | |
427 | BOOST_CONCEPT_ASSERT((LvaluePropertyMapConcept< const_Map, X >)); | |
7c673cae FG |
428 | |
429 | pval = get(Property(), g, x); | |
430 | put(Property(), g, x, pval); | |
f67539c2 TL |
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 | ||
446 | BOOST_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); | |
462 | } | |
463 | void const_constraints(const Graph& g_) | |
7c673cae | 464 | { |
f67539c2 TL |
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 | ||
470 | private: | |
471 | Graph g; | |
472 | }; | |
473 | ||
474 | BOOST_concept(EdgeIndexGraph, (Graph)) | |
475 | { | |
476 | BOOST_CONCEPT_USAGE(EdgeIndexGraph) | |
7c673cae | 477 | { |
f67539c2 TL |
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); | |
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 | ||
498 | private: | |
499 | Graph g; | |
500 | }; | |
501 | ||
502 | BOOST_concept(ColorValue, (C)) | |
503 | : EqualityComparable< C >, DefaultConstructible< C > | |
504 | { | |
505 | BOOST_CONCEPT_USAGE(ColorValue) | |
7c673cae | 506 | { |
f67539c2 TL |
507 | c = color_traits< C >::white(); |
508 | c = color_traits< C >::gray(); | |
509 | c = color_traits< C >::black(); | |
510 | } | |
511 | C c; | |
512 | }; | |
513 | ||
514 | BOOST_concept(BasicMatrix, (M)(I)(V)) | |
515 | { | |
516 | BOOST_CONCEPT_USAGE(BasicMatrix) | |
7c673cae | 517 | { |
7c673cae FG |
518 | V& elt = A[i][j]; |
519 | const_constraints(A); | |
520 | ignore_unused_variable_warning(elt); | |
f67539c2 TL |
521 | } |
522 | void const_constraints(const M& cA) | |
523 | { | |
7c673cae FG |
524 | const V& elt = cA[i][j]; |
525 | ignore_unused_variable_warning(elt); | |
f67539c2 TL |
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 | ||
535 | BOOST_concept(NumericValue, (Numeric)) { BOOST_CONCEPT_USAGE(NumericValue) { | |
536 | BOOST_CONCEPT_ASSERT((DefaultConstructible< Numeric >)); | |
537 | BOOST_CONCEPT_ASSERT((CopyConstructible< Numeric >)); | |
538 | numeric_values< Numeric >::zero(); | |
539 | numeric_values< Numeric >::infinity(); | |
540 | } | |
541 | } | |
542 | ; | |
543 | ||
544 | BOOST_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; | |
7c673cae | 550 | |
f67539c2 TL |
551 | Degree d = m(Vertex(), g); |
552 | ignore_unused_variable_warning(d); | |
553 | } | |
7c673cae | 554 | |
f67539c2 TL |
555 | private: |
556 | Measure m; | |
557 | Graph g; | |
558 | }; | |
559 | ||
560 | BOOST_concept(DistanceMeasure, (Measure)(Graph)) | |
561 | { | |
562 | BOOST_CONCEPT_USAGE(DistanceMeasure) | |
7c673cae | 563 | { |
f67539c2 TL |
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 | ||
570 | private: | |
571 | Measure m; | |
572 | Graph g; | |
573 | }; | |
7c673cae FG |
574 | |
575 | } /* namespace concepts */ | |
576 | ||
577 | using boost::concepts::MultiPassInputIteratorConcept; | |
578 | ||
579 | // Graph concepts | |
7c673cae | 580 | using boost::concepts::AdjacencyGraphConcept; |
f67539c2 TL |
581 | using boost::concepts::AdjacencyMatrixConcept; |
582 | using boost::concepts::BidirectionalGraphConcept; | |
583 | using boost::concepts::EdgeIndexGraphConcept; | |
7c673cae | 584 | using boost::concepts::EdgeListGraphConcept; |
7c673cae | 585 | using boost::concepts::EdgeMutableGraphConcept; |
f67539c2 TL |
586 | using boost::concepts::EdgeMutablePropertyGraphConcept; |
587 | using boost::concepts::GraphConcept; | |
588 | using boost::concepts::IncidenceGraphConcept; | |
589 | using boost::concepts::LvaluePropertyGraphConcept; | |
7c673cae FG |
590 | using boost::concepts::MutableBidirectionalGraphConcept; |
591 | using boost::concepts::MutableEdgeListGraphConcept; | |
f67539c2 TL |
592 | using boost::concepts::MutableGraphConcept; |
593 | using boost::concepts::MutableIncidenceGraphConcept; | |
7c673cae | 594 | using boost::concepts::PropertyGraphConcept; |
f67539c2 TL |
595 | using boost::concepts::ReadablePropertyGraphConcept; |
596 | using boost::concepts::VertexAndEdgeListGraphConcept; | |
7c673cae | 597 | using boost::concepts::VertexIndexGraphConcept; |
f67539c2 TL |
598 | using boost::concepts::VertexListGraphConcept; |
599 | using boost::concepts::VertexMutableGraphConcept; | |
600 | using boost::concepts::VertexMutablePropertyGraphConcept; | |
7c673cae FG |
601 | |
602 | // Utility concepts | |
7c673cae | 603 | using boost::concepts::BasicMatrixConcept; |
f67539c2 | 604 | using boost::concepts::ColorValueConcept; |
7c673cae | 605 | using boost::concepts::DegreeMeasureConcept; |
f67539c2 TL |
606 | using boost::concepts::DistanceMeasureConcept; |
607 | using boost::concepts::NumericValueConcept; | |
7c673cae FG |
608 | |
609 | } /* namespace boost */ | |
610 | #include <boost/concept/detail/concept_undef.hpp> | |
611 | ||
612 | #endif /* BOOST_GRAPH_CONCEPTS_H */ |