]>
Commit | Line | Data |
---|---|---|
1 | // (C) Copyright 2007-2009 Andrew Sutton | |
2 | // | |
3 | // Use, modification and distribution are subject to the | |
4 | // Boost Software License, Version 1.0 (See accompanying file | |
5 | // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | #ifndef BOOST_GRAPH_UNDIRECTED_GRAPH_HPP | |
8 | #define BOOST_GRAPH_UNDIRECTED_GRAPH_HPP | |
9 | ||
10 | #include <boost/graph/adjacency_list.hpp> | |
11 | #include <boost/graph/properties.hpp> | |
12 | #include <boost/pending/property.hpp> | |
13 | #include <boost/property_map/transform_value_property_map.hpp> | |
14 | #include <boost/type_traits.hpp> | |
15 | #include <boost/mpl/if.hpp> | |
16 | ||
17 | namespace boost | |
18 | { | |
19 | struct undirected_graph_tag | |
20 | { | |
21 | }; | |
22 | ||
23 | /** | |
24 | * The undirected_graph class template is a simplified version of the BGL | |
25 | * adjacency list. This class is provided for ease of use, but may not | |
26 | * perform as well as custom-defined adjacency list classes. Instances of | |
27 | * this template model the VertexIndexGraph, and EdgeIndexGraph concepts. The | |
28 | * graph is also fully mutable, supporting both insertions and removals of | |
29 | * vertices and edges. | |
30 | * | |
31 | * @note Special care must be taken when removing vertices or edges since | |
32 | * those operations can invalidate the numbering of vertices. | |
33 | */ | |
34 | template < typename VertexProp = no_property, typename EdgeProp = no_property, | |
35 | typename GraphProp = no_property > | |
36 | class undirected_graph | |
37 | { | |
38 | public: | |
39 | typedef GraphProp graph_property_type; | |
40 | typedef VertexProp vertex_property_type; | |
41 | typedef EdgeProp edge_property_type; | |
42 | typedef typename lookup_one_property< GraphProp, graph_bundle_t >::type | |
43 | graph_bundled; | |
44 | typedef typename lookup_one_property< VertexProp, vertex_bundle_t >::type | |
45 | vertex_bundled; | |
46 | typedef typename lookup_one_property< EdgeProp, edge_bundle_t >::type | |
47 | edge_bundled; | |
48 | ||
49 | public: | |
50 | // Embed indices into the vertex type. | |
51 | typedef property< vertex_index_t, unsigned, vertex_property_type > | |
52 | internal_vertex_property; | |
53 | typedef property< edge_index_t, unsigned, edge_property_type > | |
54 | internal_edge_property; | |
55 | ||
56 | public: | |
57 | typedef adjacency_list< listS, listS, undirectedS, internal_vertex_property, | |
58 | internal_edge_property, GraphProp, listS > | |
59 | graph_type; | |
60 | ||
61 | private: | |
62 | // storage selectors | |
63 | typedef typename graph_type::vertex_list_selector vertex_list_selector; | |
64 | typedef typename graph_type::edge_list_selector edge_list_selector; | |
65 | typedef typename graph_type::out_edge_list_selector out_edge_list_selector; | |
66 | typedef typename graph_type::directed_selector directed_selector; | |
67 | ||
68 | public: | |
69 | // more commonly used graph types | |
70 | typedef typename graph_type::stored_vertex stored_vertex; | |
71 | typedef typename graph_type::vertices_size_type vertices_size_type; | |
72 | typedef typename graph_type::edges_size_type edges_size_type; | |
73 | typedef typename graph_type::degree_size_type degree_size_type; | |
74 | typedef typename graph_type::vertex_descriptor vertex_descriptor; | |
75 | typedef typename graph_type::edge_descriptor edge_descriptor; | |
76 | ||
77 | // iterator types | |
78 | typedef typename graph_type::vertex_iterator vertex_iterator; | |
79 | typedef typename graph_type::edge_iterator edge_iterator; | |
80 | typedef typename graph_type::out_edge_iterator out_edge_iterator; | |
81 | typedef typename graph_type::in_edge_iterator in_edge_iterator; | |
82 | typedef typename graph_type::adjacency_iterator adjacency_iterator; | |
83 | ||
84 | // miscellaneous types | |
85 | typedef undirected_graph_tag graph_tag; | |
86 | typedef typename graph_type::directed_category directed_category; | |
87 | typedef typename graph_type::edge_parallel_category edge_parallel_category; | |
88 | typedef typename graph_type::traversal_category traversal_category; | |
89 | ||
90 | typedef std::size_t vertex_index_type; | |
91 | typedef std::size_t edge_index_type; | |
92 | ||
93 | inline undirected_graph(GraphProp const& p = GraphProp()) | |
94 | : m_graph(p) | |
95 | , m_num_vertices(0) | |
96 | , m_num_edges(0) | |
97 | , m_max_vertex_index(0) | |
98 | , m_max_edge_index(0) | |
99 | { | |
100 | } | |
101 | ||
102 | inline undirected_graph(undirected_graph const& x) | |
103 | : m_graph(x.m_graph) | |
104 | , m_num_vertices(x.m_num_vertices) | |
105 | , m_num_edges(x.m_num_edges) | |
106 | , m_max_vertex_index(x.m_max_vertex_index) | |
107 | , m_max_edge_index(x.m_max_edge_index) | |
108 | { | |
109 | } | |
110 | ||
111 | inline undirected_graph( | |
112 | vertices_size_type n, GraphProp const& p = GraphProp()) | |
113 | : m_graph(n, p) | |
114 | , m_num_vertices(n) | |
115 | , m_num_edges(0) | |
116 | , m_max_vertex_index(n) | |
117 | , m_max_edge_index(0) | |
118 | { | |
119 | renumber_vertex_indices(); | |
120 | } | |
121 | ||
122 | template < typename EdgeIterator > | |
123 | inline undirected_graph(EdgeIterator f, EdgeIterator l, | |
124 | vertices_size_type n, edges_size_type m = 0, | |
125 | GraphProp const& p = GraphProp()) | |
126 | : m_graph(f, l, n, m, p) | |
127 | , m_num_vertices(n) | |
128 | , m_num_edges(0) | |
129 | , m_max_vertex_index(n) | |
130 | , m_max_edge_index(0) | |
131 | { | |
132 | // Unfortunately, we have to renumber to ensure correct indexing. | |
133 | renumber_indices(); | |
134 | ||
135 | // Can't always guarantee that the number of edges is actually | |
136 | // m if distance(f, l) != m (or is undefined). | |
137 | m_num_edges = m_max_edge_index = boost::num_edges(m_graph); | |
138 | } | |
139 | ||
140 | undirected_graph& operator=(undirected_graph const& g) | |
141 | { | |
142 | if (&g != this) | |
143 | { | |
144 | m_graph = g.m_graph; | |
145 | m_num_vertices = g.m_num_vertices; | |
146 | m_num_edges = g.m_num_edges; | |
147 | m_max_vertex_index = g.m_max_vertex_index; | |
148 | } | |
149 | return *this; | |
150 | } | |
151 | ||
152 | // The impl_() methods are not part of the public interface. | |
153 | graph_type& impl() { return m_graph; } | |
154 | ||
155 | graph_type const& impl() const { return m_graph; } | |
156 | ||
157 | // The following methods are not part of the public interface | |
158 | vertices_size_type num_vertices() const { return m_num_vertices; } | |
159 | ||
160 | private: | |
161 | // This helper function manages the attribution of vertex indices. | |
162 | vertex_descriptor make_index(vertex_descriptor v) | |
163 | { | |
164 | boost::put(vertex_index, m_graph, v, m_max_vertex_index); | |
165 | m_num_vertices++; | |
166 | m_max_vertex_index++; | |
167 | return v; | |
168 | } | |
169 | ||
170 | public: | |
171 | vertex_descriptor add_vertex() | |
172 | { | |
173 | return make_index(boost::add_vertex(m_graph)); | |
174 | } | |
175 | ||
176 | vertex_descriptor add_vertex(vertex_property_type const& p) | |
177 | { | |
178 | return make_index( | |
179 | boost::add_vertex(internal_vertex_property(0u, p), m_graph)); | |
180 | } | |
181 | ||
182 | void clear_vertex(vertex_descriptor v) | |
183 | { | |
184 | std::pair< out_edge_iterator, out_edge_iterator > p | |
185 | = boost::out_edges(v, m_graph); | |
186 | m_num_edges -= std::distance(p.first, p.second); | |
187 | boost::clear_vertex(v, m_graph); | |
188 | } | |
189 | ||
190 | void remove_vertex(vertex_descriptor v) | |
191 | { | |
192 | boost::remove_vertex(v, m_graph); | |
193 | --m_num_vertices; | |
194 | } | |
195 | ||
196 | edges_size_type num_edges() const { return m_num_edges; } | |
197 | ||
198 | private: | |
199 | // A helper fucntion for managing edge index attributes. | |
200 | std::pair< edge_descriptor, bool > const& make_index( | |
201 | std::pair< edge_descriptor, bool > const& x) | |
202 | { | |
203 | if (x.second) | |
204 | { | |
205 | boost::put(edge_index, m_graph, x.first, m_max_edge_index); | |
206 | ++m_num_edges; | |
207 | ++m_max_edge_index; | |
208 | } | |
209 | return x; | |
210 | } | |
211 | ||
212 | public: | |
213 | std::pair< edge_descriptor, bool > add_edge( | |
214 | vertex_descriptor u, vertex_descriptor v) | |
215 | { | |
216 | return make_index(boost::add_edge(u, v, m_graph)); | |
217 | } | |
218 | ||
219 | std::pair< edge_descriptor, bool > add_edge( | |
220 | vertex_descriptor u, vertex_descriptor v, edge_property_type const& p) | |
221 | { | |
222 | return make_index( | |
223 | boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); | |
224 | } | |
225 | ||
226 | void remove_edge(vertex_descriptor u, vertex_descriptor v) | |
227 | { | |
228 | // find all edges, (u, v) | |
229 | std::vector< edge_descriptor > edges; | |
230 | out_edge_iterator i, i_end; | |
231 | for (boost::tie(i, i_end) = boost::out_edges(u, m_graph); i != i_end; | |
232 | ++i) | |
233 | { | |
234 | if (boost::target(*i, m_graph) == v) | |
235 | { | |
236 | edges.push_back(*i); | |
237 | } | |
238 | } | |
239 | // remove all edges, (u, v) | |
240 | typename std::vector< edge_descriptor >::iterator j = edges.begin(), | |
241 | j_end = edges.end(); | |
242 | for (; j != j_end; ++j) | |
243 | { | |
244 | remove_edge(*j); | |
245 | } | |
246 | } | |
247 | ||
248 | void remove_edge(edge_iterator i) { remove_edge(*i); } | |
249 | ||
250 | void remove_edge(edge_descriptor e) | |
251 | { | |
252 | boost::remove_edge(e, m_graph); | |
253 | --m_num_edges; | |
254 | } | |
255 | ||
256 | vertex_index_type max_vertex_index() const { return m_max_vertex_index; } | |
257 | ||
258 | void renumber_vertex_indices() | |
259 | { | |
260 | vertex_iterator i, i_end; | |
261 | boost::tie(i, i_end) = vertices(m_graph); | |
262 | m_max_vertex_index = renumber_vertex_indices(i, i_end, 0); | |
263 | } | |
264 | ||
265 | void remove_vertex_and_renumber_indices(vertex_iterator i) | |
266 | { | |
267 | vertex_iterator j = next(i), end = vertices(m_graph).second; | |
268 | vertex_index_type n = get(vertex_index, m_graph, *i); | |
269 | ||
270 | // remove the offending vertex and renumber everything after | |
271 | remove_vertex(*i); | |
272 | m_max_vertex_index = renumber_vertex_indices(j, end, n); | |
273 | } | |
274 | ||
275 | edge_index_type max_edge_index() const { return m_max_edge_index; } | |
276 | ||
277 | void renumber_edge_indices() | |
278 | { | |
279 | edge_iterator i, end; | |
280 | boost::tie(i, end) = edges(m_graph); | |
281 | m_max_edge_index = renumber_edge_indices(i, end, 0); | |
282 | } | |
283 | ||
284 | void remove_edge_and_renumber_indices(edge_iterator i) | |
285 | { | |
286 | edge_iterator j = next(i), end = edges(m_graph.second); | |
287 | edge_index_type n = get(edge_index, m_graph, *i); | |
288 | ||
289 | // remove the edge and renumber everything after it | |
290 | remove_edge(*i); | |
291 | m_max_edge_index = renumber_edge_indices(j, end, n); | |
292 | } | |
293 | ||
294 | void renumber_indices() | |
295 | { | |
296 | renumber_vertex_indices(); | |
297 | renumber_edge_indices(); | |
298 | } | |
299 | ||
300 | // bundled property support | |
301 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES | |
302 | vertex_bundled& operator[](vertex_descriptor v) { return m_graph[v]; } | |
303 | ||
304 | vertex_bundled const& operator[](vertex_descriptor v) const | |
305 | { | |
306 | return m_graph[v]; | |
307 | } | |
308 | ||
309 | edge_bundled& operator[](edge_descriptor e) { return m_graph[e]; } | |
310 | ||
311 | edge_bundled const& operator[](edge_descriptor e) const | |
312 | { | |
313 | return m_graph[e]; | |
314 | } | |
315 | ||
316 | graph_bundled& operator[](graph_bundle_t) { return get_property(*this); } | |
317 | ||
318 | graph_bundled const& operator[](graph_bundle_t) const | |
319 | { | |
320 | return get_property(*this); | |
321 | } | |
322 | #endif | |
323 | ||
324 | // Graph concepts | |
325 | static vertex_descriptor null_vertex() { return graph_type::null_vertex(); } | |
326 | ||
327 | void clear() | |
328 | { | |
329 | m_graph.clear(); | |
330 | m_num_vertices = m_max_vertex_index = 0; | |
331 | m_num_edges = m_max_edge_index = 0; | |
332 | } | |
333 | ||
334 | void swap(undirected_graph& g) | |
335 | { | |
336 | m_graph.swap(g.m_graph); | |
337 | std::swap(m_num_vertices, g.m_num_vertices); | |
338 | std::swap(m_max_vertex_index, g.m_max_vertex_index); | |
339 | std::swap(m_num_edges, g.m_num_edges); | |
340 | std::swap(m_max_edge_index, g.m_max_edge_index); | |
341 | } | |
342 | ||
343 | private: | |
344 | vertices_size_type renumber_vertex_indices( | |
345 | vertex_iterator i, vertex_iterator end, vertices_size_type n) | |
346 | { | |
347 | typedef | |
348 | typename property_map< graph_type, vertex_index_t >::type IndexMap; | |
349 | IndexMap indices = get(vertex_index, m_graph); | |
350 | for (; i != end; ++i) | |
351 | { | |
352 | indices[*i] = n++; | |
353 | } | |
354 | return n; | |
355 | } | |
356 | ||
357 | edges_size_type renumber_edge_indices( | |
358 | edge_iterator i, edge_iterator end, edges_size_type n) | |
359 | { | |
360 | typedef | |
361 | typename property_map< graph_type, edge_index_t >::type IndexMap; | |
362 | IndexMap indices = get(edge_index, m_graph); | |
363 | for (; i != end; ++i) | |
364 | { | |
365 | indices[*i] = n++; | |
366 | } | |
367 | return n; | |
368 | } | |
369 | ||
370 | graph_type m_graph; | |
371 | vertices_size_type m_num_vertices; | |
372 | edges_size_type m_num_edges; | |
373 | vertex_index_type m_max_vertex_index; | |
374 | edge_index_type m_max_edge_index; | |
375 | }; | |
376 | ||
377 | #define UNDIRECTED_GRAPH_PARAMS typename VP, typename EP, typename GP | |
378 | #define UNDIRECTED_GRAPH undirected_graph< VP, EP, GP > | |
379 | ||
380 | // IncidenceGraph concepts | |
381 | template < UNDIRECTED_GRAPH_PARAMS > | |
382 | inline typename UNDIRECTED_GRAPH::vertex_descriptor source( | |
383 | typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH const& g) | |
384 | { | |
385 | return source(e, g.impl()); | |
386 | } | |
387 | ||
388 | template < UNDIRECTED_GRAPH_PARAMS > | |
389 | inline typename UNDIRECTED_GRAPH::vertex_descriptor target( | |
390 | typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH const& g) | |
391 | { | |
392 | return target(e, g.impl()); | |
393 | } | |
394 | ||
395 | template < UNDIRECTED_GRAPH_PARAMS > | |
396 | inline typename UNDIRECTED_GRAPH::degree_size_type out_degree( | |
397 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) | |
398 | { | |
399 | return out_degree(v, g.impl()); | |
400 | } | |
401 | ||
402 | template < UNDIRECTED_GRAPH_PARAMS > | |
403 | inline std::pair< typename UNDIRECTED_GRAPH::out_edge_iterator, | |
404 | typename UNDIRECTED_GRAPH::out_edge_iterator > | |
405 | out_edges( | |
406 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) | |
407 | { | |
408 | return out_edges(v, g.impl()); | |
409 | } | |
410 | ||
411 | // BidirectionalGraph concepts | |
412 | template < UNDIRECTED_GRAPH_PARAMS > | |
413 | inline typename UNDIRECTED_GRAPH::degree_size_type in_degree( | |
414 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) | |
415 | { | |
416 | return in_degree(v, g.impl()); | |
417 | } | |
418 | ||
419 | template < UNDIRECTED_GRAPH_PARAMS > | |
420 | inline std::pair< typename UNDIRECTED_GRAPH::in_edge_iterator, | |
421 | typename UNDIRECTED_GRAPH::in_edge_iterator > | |
422 | in_edges( | |
423 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) | |
424 | { | |
425 | return in_edges(v, g.impl()); | |
426 | } | |
427 | ||
428 | template < UNDIRECTED_GRAPH_PARAMS > | |
429 | inline std::pair< typename UNDIRECTED_GRAPH::out_edge_iterator, | |
430 | typename UNDIRECTED_GRAPH::out_edge_iterator > | |
431 | incident_edges( | |
432 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) | |
433 | { | |
434 | return out_edges(v, g.impl()); | |
435 | } | |
436 | ||
437 | template < UNDIRECTED_GRAPH_PARAMS > | |
438 | inline typename UNDIRECTED_GRAPH::degree_size_type degree( | |
439 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) | |
440 | { | |
441 | return degree(v, g.impl()); | |
442 | } | |
443 | ||
444 | // AdjacencyGraph concepts | |
445 | template < UNDIRECTED_GRAPH_PARAMS > | |
446 | inline std::pair< typename UNDIRECTED_GRAPH::adjacency_iterator, | |
447 | typename UNDIRECTED_GRAPH::adjacency_iterator > | |
448 | adjacent_vertices( | |
449 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) | |
450 | { | |
451 | return adjacent_vertices(v, g.impl()); | |
452 | } | |
453 | ||
454 | template < UNDIRECTED_GRAPH_PARAMS > | |
455 | typename UNDIRECTED_GRAPH::vertex_descriptor vertex( | |
456 | typename UNDIRECTED_GRAPH::vertices_size_type n, UNDIRECTED_GRAPH const& g) | |
457 | { | |
458 | return vertex(n, g.impl()); | |
459 | } | |
460 | ||
461 | template < UNDIRECTED_GRAPH_PARAMS > | |
462 | std::pair< typename UNDIRECTED_GRAPH::edge_descriptor, bool > edge( | |
463 | typename UNDIRECTED_GRAPH::vertex_descriptor u, | |
464 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) | |
465 | { | |
466 | return edge(u, v, g.impl()); | |
467 | } | |
468 | ||
469 | // VertexListGraph concepts | |
470 | template < UNDIRECTED_GRAPH_PARAMS > | |
471 | inline typename UNDIRECTED_GRAPH::vertices_size_type num_vertices( | |
472 | UNDIRECTED_GRAPH const& g) | |
473 | { | |
474 | return g.num_vertices(); | |
475 | } | |
476 | ||
477 | template < UNDIRECTED_GRAPH_PARAMS > | |
478 | inline std::pair< typename UNDIRECTED_GRAPH::vertex_iterator, | |
479 | typename UNDIRECTED_GRAPH::vertex_iterator > | |
480 | vertices(UNDIRECTED_GRAPH const& g) | |
481 | { | |
482 | return vertices(g.impl()); | |
483 | } | |
484 | ||
485 | // EdgeListGraph concepts | |
486 | template < UNDIRECTED_GRAPH_PARAMS > | |
487 | inline typename UNDIRECTED_GRAPH::edges_size_type num_edges( | |
488 | UNDIRECTED_GRAPH const& g) | |
489 | { | |
490 | return g.num_edges(); | |
491 | } | |
492 | ||
493 | template < UNDIRECTED_GRAPH_PARAMS > | |
494 | inline std::pair< typename UNDIRECTED_GRAPH::edge_iterator, | |
495 | typename UNDIRECTED_GRAPH::edge_iterator > | |
496 | edges(UNDIRECTED_GRAPH const& g) | |
497 | { | |
498 | return edges(g.impl()); | |
499 | } | |
500 | ||
501 | // MutableGraph concepts | |
502 | template < UNDIRECTED_GRAPH_PARAMS > | |
503 | inline typename UNDIRECTED_GRAPH::vertex_descriptor add_vertex( | |
504 | UNDIRECTED_GRAPH& g) | |
505 | { | |
506 | return g.add_vertex(); | |
507 | } | |
508 | ||
509 | template < UNDIRECTED_GRAPH_PARAMS > | |
510 | inline typename UNDIRECTED_GRAPH::vertex_descriptor add_vertex( | |
511 | typename UNDIRECTED_GRAPH::vertex_property_type const& p, | |
512 | UNDIRECTED_GRAPH& g) | |
513 | { | |
514 | return g.add_vertex(p); | |
515 | } | |
516 | ||
517 | template < UNDIRECTED_GRAPH_PARAMS > | |
518 | inline void clear_vertex( | |
519 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g) | |
520 | { | |
521 | return g.clear_vertex(v); | |
522 | } | |
523 | ||
524 | template < UNDIRECTED_GRAPH_PARAMS > | |
525 | inline void remove_vertex( | |
526 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g) | |
527 | { | |
528 | return g.remove_vertex(v); | |
529 | } | |
530 | ||
531 | template < UNDIRECTED_GRAPH_PARAMS > | |
532 | inline std::pair< typename UNDIRECTED_GRAPH::edge_descriptor, bool > add_edge( | |
533 | typename UNDIRECTED_GRAPH::vertex_descriptor u, | |
534 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g) | |
535 | { | |
536 | return g.add_edge(u, v); | |
537 | } | |
538 | ||
539 | template < UNDIRECTED_GRAPH_PARAMS > | |
540 | inline std::pair< typename UNDIRECTED_GRAPH::edge_descriptor, bool > add_edge( | |
541 | typename UNDIRECTED_GRAPH::vertex_descriptor u, | |
542 | typename UNDIRECTED_GRAPH::vertex_descriptor v, | |
543 | typename UNDIRECTED_GRAPH::edge_property_type const& p, UNDIRECTED_GRAPH& g) | |
544 | { | |
545 | return g.add_edge(u, v, p); | |
546 | } | |
547 | ||
548 | template < UNDIRECTED_GRAPH_PARAMS > | |
549 | inline void remove_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u, | |
550 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g) | |
551 | { | |
552 | return g.remove_edge(u, v); | |
553 | } | |
554 | ||
555 | template < UNDIRECTED_GRAPH_PARAMS > | |
556 | inline void remove_edge( | |
557 | typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH& g) | |
558 | { | |
559 | return g.remove_edge(e); | |
560 | } | |
561 | ||
562 | template < UNDIRECTED_GRAPH_PARAMS > | |
563 | inline void remove_edge( | |
564 | typename UNDIRECTED_GRAPH::edge_iterator i, UNDIRECTED_GRAPH& g) | |
565 | { | |
566 | return g.remove_edge(i); | |
567 | } | |
568 | ||
569 | template < UNDIRECTED_GRAPH_PARAMS, class Predicate > | |
570 | inline void remove_edge_if(Predicate pred, UNDIRECTED_GRAPH& g) | |
571 | { | |
572 | return remove_edge_if(pred, g.impl()); | |
573 | } | |
574 | ||
575 | template < UNDIRECTED_GRAPH_PARAMS, class Predicate > | |
576 | inline void remove_incident_edge_if( | |
577 | typename UNDIRECTED_GRAPH::vertex_descriptor v, Predicate pred, | |
578 | UNDIRECTED_GRAPH& g) | |
579 | { | |
580 | return remove_out_edge_if(v, pred, g.impl()); | |
581 | } | |
582 | ||
583 | template < UNDIRECTED_GRAPH_PARAMS, class Predicate > | |
584 | inline void remove_out_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v, | |
585 | Predicate pred, UNDIRECTED_GRAPH& g) | |
586 | { | |
587 | return remove_out_edge_if(v, pred, g.impl()); | |
588 | } | |
589 | ||
590 | template < UNDIRECTED_GRAPH_PARAMS, class Predicate > | |
591 | inline void remove_in_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v, | |
592 | Predicate pred, UNDIRECTED_GRAPH& g) | |
593 | { | |
594 | return remove_in_edge_if(v, pred, g.impl()); | |
595 | } | |
596 | ||
597 | template < UNDIRECTED_GRAPH_PARAMS, typename Property > | |
598 | struct property_map< UNDIRECTED_GRAPH, Property > | |
599 | : property_map< typename UNDIRECTED_GRAPH::graph_type, Property > | |
600 | { | |
601 | }; | |
602 | ||
603 | template < UNDIRECTED_GRAPH_PARAMS > | |
604 | struct property_map< UNDIRECTED_GRAPH, vertex_all_t > | |
605 | { | |
606 | typedef transform_value_property_map< detail::remove_first_property, | |
607 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, | |
608 | vertex_all_t >::const_type > | |
609 | const_type; | |
610 | typedef transform_value_property_map< detail::remove_first_property, | |
611 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, | |
612 | vertex_all_t >::type > | |
613 | type; | |
614 | }; | |
615 | ||
616 | template < UNDIRECTED_GRAPH_PARAMS > | |
617 | struct property_map< UNDIRECTED_GRAPH, edge_all_t > | |
618 | { | |
619 | typedef transform_value_property_map< detail::remove_first_property, | |
620 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, | |
621 | edge_all_t >::const_type > | |
622 | const_type; | |
623 | typedef transform_value_property_map< detail::remove_first_property, | |
624 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, | |
625 | edge_all_t >::type > | |
626 | type; | |
627 | }; | |
628 | ||
629 | // PropertyGraph concepts | |
630 | template < UNDIRECTED_GRAPH_PARAMS, typename Property > | |
631 | inline typename property_map< UNDIRECTED_GRAPH, Property >::type get( | |
632 | Property p, UNDIRECTED_GRAPH& g) | |
633 | { | |
634 | return get(p, g.impl()); | |
635 | } | |
636 | ||
637 | template < UNDIRECTED_GRAPH_PARAMS, typename Property > | |
638 | inline typename property_map< UNDIRECTED_GRAPH, Property >::const_type get( | |
639 | Property p, UNDIRECTED_GRAPH const& g) | |
640 | { | |
641 | return get(p, g.impl()); | |
642 | } | |
643 | ||
644 | template < UNDIRECTED_GRAPH_PARAMS > | |
645 | inline typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::type get( | |
646 | vertex_all_t, UNDIRECTED_GRAPH& g) | |
647 | { | |
648 | return typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::type( | |
649 | detail::remove_first_property(), get(vertex_all, g.impl())); | |
650 | } | |
651 | ||
652 | template < UNDIRECTED_GRAPH_PARAMS > | |
653 | inline typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::const_type get( | |
654 | vertex_all_t, UNDIRECTED_GRAPH const& g) | |
655 | { | |
656 | return typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::const_type( | |
657 | detail::remove_first_property(), get(vertex_all, g.impl())); | |
658 | } | |
659 | ||
660 | template < UNDIRECTED_GRAPH_PARAMS > | |
661 | inline typename property_map< UNDIRECTED_GRAPH, edge_all_t >::type get( | |
662 | edge_all_t, UNDIRECTED_GRAPH& g) | |
663 | { | |
664 | return typename property_map< UNDIRECTED_GRAPH, edge_all_t >::type( | |
665 | detail::remove_first_property(), get(edge_all, g.impl())); | |
666 | } | |
667 | ||
668 | template < UNDIRECTED_GRAPH_PARAMS > | |
669 | inline typename property_map< UNDIRECTED_GRAPH, edge_all_t >::const_type get( | |
670 | edge_all_t, UNDIRECTED_GRAPH const& g) | |
671 | { | |
672 | return typename property_map< UNDIRECTED_GRAPH, edge_all_t >::const_type( | |
673 | detail::remove_first_property(), get(edge_all, g.impl())); | |
674 | } | |
675 | ||
676 | template < UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key > | |
677 | inline typename property_traits< typename property_map< | |
678 | typename UNDIRECTED_GRAPH::graph_type, Property >::const_type >::value_type | |
679 | get(Property p, UNDIRECTED_GRAPH const& g, Key const& k) | |
680 | { | |
681 | return get(p, g.impl(), k); | |
682 | } | |
683 | ||
684 | template < UNDIRECTED_GRAPH_PARAMS, typename Key > | |
685 | inline typename property_traits< | |
686 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, | |
687 | vertex_all_t >::const_type >::value_type | |
688 | get(vertex_all_t, UNDIRECTED_GRAPH const& g, Key const& k) | |
689 | { | |
690 | return get(vertex_all, g.impl(), k).m_base; | |
691 | } | |
692 | ||
693 | template < UNDIRECTED_GRAPH_PARAMS, typename Key > | |
694 | inline typename property_traits< | |
695 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, | |
696 | edge_all_t >::const_type >::value_type | |
697 | get(edge_all_t, UNDIRECTED_GRAPH const& g, Key const& k) | |
698 | { | |
699 | return get(edge_all, g.impl(), k).m_base; | |
700 | } | |
701 | ||
702 | template < UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key, | |
703 | typename Value > | |
704 | inline void put(Property p, UNDIRECTED_GRAPH& g, Key const& k, Value const& v) | |
705 | { | |
706 | put(p, g.impl(), k, v); | |
707 | } | |
708 | ||
709 | template < UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value > | |
710 | inline void put(vertex_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v) | |
711 | { | |
712 | put(vertex_all, g.impl(), k, | |
713 | typename UNDIRECTED_GRAPH::internal_vertex_property( | |
714 | get(vertex_index, g.impl(), k), v)); | |
715 | } | |
716 | ||
717 | template < UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value > | |
718 | inline void put(edge_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v) | |
719 | { | |
720 | put(edge_all, g.impl(), k, | |
721 | typename UNDIRECTED_GRAPH::internal_vertex_property( | |
722 | get(edge_index, g.impl(), k), v)); | |
723 | } | |
724 | ||
725 | template < UNDIRECTED_GRAPH_PARAMS, class Property > | |
726 | inline typename graph_property< UNDIRECTED_GRAPH, Property >::type& | |
727 | get_property(UNDIRECTED_GRAPH& g, Property p) | |
728 | { | |
729 | return get_property(g.impl(), p); | |
730 | } | |
731 | ||
732 | template < UNDIRECTED_GRAPH_PARAMS, class Property > | |
733 | inline typename graph_property< UNDIRECTED_GRAPH, Property >::type const& | |
734 | get_property(UNDIRECTED_GRAPH const& g, Property p) | |
735 | { | |
736 | return get_property(g.impl(), p); | |
737 | } | |
738 | ||
739 | template < UNDIRECTED_GRAPH_PARAMS, class Property, class Value > | |
740 | inline void set_property(UNDIRECTED_GRAPH& g, Property p, Value v) | |
741 | { | |
742 | return set_property(g.impl(), p, v); | |
743 | } | |
744 | ||
745 | // Indexed Vertex graph | |
746 | ||
747 | template < UNDIRECTED_GRAPH_PARAMS > | |
748 | inline typename UNDIRECTED_GRAPH::vertex_index_type get_vertex_index( | |
749 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) | |
750 | { | |
751 | return get(vertex_index, g, v); | |
752 | } | |
753 | ||
754 | template < UNDIRECTED_GRAPH_PARAMS > | |
755 | typename UNDIRECTED_GRAPH::vertex_index_type max_vertex_index( | |
756 | UNDIRECTED_GRAPH const& g) | |
757 | { | |
758 | return g.max_vertex_index(); | |
759 | } | |
760 | ||
761 | template < UNDIRECTED_GRAPH_PARAMS > | |
762 | inline void renumber_vertex_indices(UNDIRECTED_GRAPH& g) | |
763 | { | |
764 | g.renumber_vertex_indices(); | |
765 | } | |
766 | ||
767 | template < UNDIRECTED_GRAPH_PARAMS > | |
768 | inline void remove_vertex_and_renumber_indices( | |
769 | typename UNDIRECTED_GRAPH::vertex_iterator i, UNDIRECTED_GRAPH& g) | |
770 | { | |
771 | g.remove_vertex_and_renumber_indices(i); | |
772 | } | |
773 | ||
774 | // Edge index management | |
775 | ||
776 | template < UNDIRECTED_GRAPH_PARAMS > | |
777 | inline typename UNDIRECTED_GRAPH::edge_index_type get_edge_index( | |
778 | typename UNDIRECTED_GRAPH::edge_descriptor v, UNDIRECTED_GRAPH const& g) | |
779 | { | |
780 | return get(edge_index, g, v); | |
781 | } | |
782 | ||
783 | template < UNDIRECTED_GRAPH_PARAMS > | |
784 | typename UNDIRECTED_GRAPH::edge_index_type max_edge_index( | |
785 | UNDIRECTED_GRAPH const& g) | |
786 | { | |
787 | return g.max_edge_index(); | |
788 | } | |
789 | ||
790 | template < UNDIRECTED_GRAPH_PARAMS > | |
791 | inline void renumber_edge_indices(UNDIRECTED_GRAPH& g) | |
792 | { | |
793 | g.renumber_edge_indices(); | |
794 | } | |
795 | ||
796 | template < UNDIRECTED_GRAPH_PARAMS > | |
797 | inline void remove_edge_and_renumber_indices( | |
798 | typename UNDIRECTED_GRAPH::edge_iterator i, UNDIRECTED_GRAPH& g) | |
799 | { | |
800 | g.remove_edge_and_renumber_indices(i); | |
801 | } | |
802 | ||
803 | // Index management | |
804 | template < UNDIRECTED_GRAPH_PARAMS > | |
805 | inline void renumber_indices(UNDIRECTED_GRAPH& g) | |
806 | { | |
807 | g.renumber_indices(); | |
808 | } | |
809 | ||
810 | // Mutability Traits | |
811 | template < UNDIRECTED_GRAPH_PARAMS > | |
812 | struct graph_mutability_traits< UNDIRECTED_GRAPH > | |
813 | { | |
814 | typedef mutable_property_graph_tag category; | |
815 | }; | |
816 | ||
817 | #undef UNDIRECTED_GRAPH_PARAMS | |
818 | #undef UNDIRECTED_GRAPH | |
819 | ||
820 | } /* namespace boost */ | |
821 | ||
822 | #endif |