]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | { | |
f67539c2 TL |
19 | struct undirected_graph_tag |
20 | { | |
21 | }; | |
7c673cae FG |
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 | */ | |
f67539c2 TL |
34 | template < typename VertexProp = no_property, typename EdgeProp = no_property, |
35 | typename GraphProp = no_property > | |
7c673cae FG |
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; | |
f67539c2 TL |
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; | |
7c673cae FG |
48 | |
49 | public: | |
50 | // Embed indices into the vertex type. | |
f67539c2 TL |
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 | ||
7c673cae | 56 | public: |
f67539c2 TL |
57 | typedef adjacency_list< listS, listS, undirectedS, internal_vertex_property, |
58 | internal_edge_property, GraphProp, listS > | |
59 | graph_type; | |
60 | ||
7c673cae FG |
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()) | |
f67539c2 TL |
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 | } | |
7c673cae FG |
101 | |
102 | inline undirected_graph(undirected_graph const& x) | |
f67539c2 TL |
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) | |
7c673cae FG |
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 | ||
f67539c2 TL |
140 | undirected_graph& operator=(undirected_graph const& g) |
141 | { | |
142 | if (&g != this) | |
143 | { | |
7c673cae FG |
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. | |
f67539c2 | 153 | graph_type& impl() { return m_graph; } |
7c673cae | 154 | |
f67539c2 | 155 | graph_type const& impl() const { return m_graph; } |
7c673cae FG |
156 | |
157 | // The following methods are not part of the public interface | |
f67539c2 | 158 | vertices_size_type num_vertices() const { return m_num_vertices; } |
7c673cae FG |
159 | |
160 | private: | |
161 | // This helper function manages the attribution of vertex indices. | |
f67539c2 TL |
162 | vertex_descriptor make_index(vertex_descriptor v) |
163 | { | |
7c673cae FG |
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 | } | |
f67539c2 | 169 | |
7c673cae FG |
170 | public: |
171 | vertex_descriptor add_vertex() | |
f67539c2 TL |
172 | { |
173 | return make_index(boost::add_vertex(m_graph)); | |
174 | } | |
7c673cae FG |
175 | |
176 | vertex_descriptor add_vertex(vertex_property_type const& p) | |
f67539c2 TL |
177 | { |
178 | return make_index( | |
179 | boost::add_vertex(internal_vertex_property(0u, p), m_graph)); | |
180 | } | |
7c673cae | 181 | |
f67539c2 TL |
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); | |
7c673cae FG |
186 | m_num_edges -= std::distance(p.first, p.second); |
187 | boost::clear_vertex(v, m_graph); | |
188 | } | |
189 | ||
f67539c2 TL |
190 | void remove_vertex(vertex_descriptor v) |
191 | { | |
7c673cae FG |
192 | boost::remove_vertex(v, m_graph); |
193 | --m_num_vertices; | |
194 | } | |
195 | ||
f67539c2 | 196 | edges_size_type num_edges() const { return m_num_edges; } |
7c673cae FG |
197 | |
198 | private: | |
199 | // A helper fucntion for managing edge index attributes. | |
f67539c2 TL |
200 | std::pair< edge_descriptor, bool > const& make_index( |
201 | std::pair< edge_descriptor, bool > const& x) | |
7c673cae | 202 | { |
f67539c2 TL |
203 | if (x.second) |
204 | { | |
7c673cae FG |
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 | } | |
f67539c2 | 211 | |
7c673cae | 212 | public: |
f67539c2 TL |
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 | } | |
7c673cae | 218 | |
f67539c2 TL |
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 | } | |
7c673cae | 225 | |
f67539c2 TL |
226 | void remove_edge(vertex_descriptor u, vertex_descriptor v) |
227 | { | |
7c673cae | 228 | // find all edges, (u, v) |
f67539c2 | 229 | std::vector< edge_descriptor > edges; |
7c673cae | 230 | out_edge_iterator i, i_end; |
f67539c2 TL |
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 | { | |
7c673cae FG |
236 | edges.push_back(*i); |
237 | } | |
238 | } | |
239 | // remove all edges, (u, v) | |
f67539c2 TL |
240 | typename std::vector< edge_descriptor >::iterator j = edges.begin(), |
241 | j_end = edges.end(); | |
242 | for (; j != j_end; ++j) | |
243 | { | |
7c673cae FG |
244 | remove_edge(*j); |
245 | } | |
246 | } | |
247 | ||
f67539c2 | 248 | void remove_edge(edge_iterator i) { remove_edge(*i); } |
7c673cae | 249 | |
f67539c2 TL |
250 | void remove_edge(edge_descriptor e) |
251 | { | |
7c673cae FG |
252 | boost::remove_edge(e, m_graph); |
253 | --m_num_edges; | |
254 | } | |
255 | ||
f67539c2 | 256 | vertex_index_type max_vertex_index() const { return m_max_vertex_index; } |
7c673cae | 257 | |
f67539c2 TL |
258 | void renumber_vertex_indices() |
259 | { | |
7c673cae FG |
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 | ||
f67539c2 TL |
265 | void remove_vertex_and_renumber_indices(vertex_iterator i) |
266 | { | |
7c673cae FG |
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 | ||
f67539c2 | 275 | edge_index_type max_edge_index() const { return m_max_edge_index; } |
7c673cae | 276 | |
f67539c2 TL |
277 | void renumber_edge_indices() |
278 | { | |
7c673cae FG |
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 | ||
f67539c2 TL |
284 | void remove_edge_and_renumber_indices(edge_iterator i) |
285 | { | |
7c673cae FG |
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 | ||
f67539c2 TL |
294 | void renumber_indices() |
295 | { | |
7c673cae FG |
296 | renumber_vertex_indices(); |
297 | renumber_edge_indices(); | |
298 | } | |
299 | ||
300 | // bundled property support | |
301 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES | |
f67539c2 | 302 | vertex_bundled& operator[](vertex_descriptor v) { return m_graph[v]; } |
7c673cae FG |
303 | |
304 | vertex_bundled const& operator[](vertex_descriptor v) const | |
f67539c2 TL |
305 | { |
306 | return m_graph[v]; | |
307 | } | |
7c673cae | 308 | |
f67539c2 | 309 | edge_bundled& operator[](edge_descriptor e) { return m_graph[e]; } |
7c673cae FG |
310 | |
311 | edge_bundled const& operator[](edge_descriptor e) const | |
f67539c2 TL |
312 | { |
313 | return m_graph[e]; | |
314 | } | |
7c673cae | 315 | |
f67539c2 | 316 | graph_bundled& operator[](graph_bundle_t) { return get_property(*this); } |
7c673cae FG |
317 | |
318 | graph_bundled const& operator[](graph_bundle_t) const | |
f67539c2 TL |
319 | { |
320 | return get_property(*this); | |
321 | } | |
7c673cae FG |
322 | #endif |
323 | ||
324 | // Graph concepts | |
f67539c2 | 325 | static vertex_descriptor null_vertex() { return graph_type::null_vertex(); } |
7c673cae | 326 | |
f67539c2 TL |
327 | void clear() |
328 | { | |
7c673cae FG |
329 | m_graph.clear(); |
330 | m_num_vertices = m_max_vertex_index = 0; | |
331 | m_num_edges = m_max_edge_index = 0; | |
332 | } | |
333 | ||
f67539c2 TL |
334 | void swap(undirected_graph& g) |
335 | { | |
7c673cae FG |
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: | |
f67539c2 TL |
344 | vertices_size_type renumber_vertex_indices( |
345 | vertex_iterator i, vertex_iterator end, vertices_size_type n) | |
7c673cae | 346 | { |
f67539c2 TL |
347 | typedef |
348 | typename property_map< graph_type, vertex_index_t >::type IndexMap; | |
7c673cae | 349 | IndexMap indices = get(vertex_index, m_graph); |
f67539c2 TL |
350 | for (; i != end; ++i) |
351 | { | |
7c673cae FG |
352 | indices[*i] = n++; |
353 | } | |
354 | return n; | |
355 | } | |
356 | ||
f67539c2 TL |
357 | edges_size_type renumber_edge_indices( |
358 | edge_iterator i, edge_iterator end, edges_size_type n) | |
7c673cae | 359 | { |
f67539c2 TL |
360 | typedef |
361 | typename property_map< graph_type, edge_index_t >::type IndexMap; | |
7c673cae | 362 | IndexMap indices = get(edge_index, m_graph); |
f67539c2 TL |
363 | for (; i != end; ++i) |
364 | { | |
7c673cae FG |
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 | |
f67539c2 | 378 | #define UNDIRECTED_GRAPH undirected_graph< VP, EP, GP > |
7c673cae FG |
379 | |
380 | // IncidenceGraph concepts | |
f67539c2 TL |
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 | } | |
7c673cae FG |
410 | |
411 | // BidirectionalGraph concepts | |
f67539c2 TL |
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 | } | |
7c673cae FG |
443 | |
444 | // AdjacencyGraph concepts | |
f67539c2 TL |
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 | } | |
7c673cae FG |
468 | |
469 | // VertexListGraph concepts | |
f67539c2 TL |
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 > | |
7c673cae | 480 | vertices(UNDIRECTED_GRAPH const& g) |
f67539c2 TL |
481 | { |
482 | return vertices(g.impl()); | |
483 | } | |
7c673cae FG |
484 | |
485 | // EdgeListGraph concepts | |
f67539c2 TL |
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 > | |
7c673cae | 496 | edges(UNDIRECTED_GRAPH const& g) |
f67539c2 TL |
497 | { |
498 | return edges(g.impl()); | |
499 | } | |
7c673cae FG |
500 | |
501 | // MutableGraph concepts | |
f67539c2 TL |
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 > | |
7c673cae | 570 | inline void remove_edge_if(Predicate pred, UNDIRECTED_GRAPH& g) |
f67539c2 TL |
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; | |
7c673cae FG |
614 | }; |
615 | ||
f67539c2 TL |
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; | |
7c673cae FG |
627 | }; |
628 | ||
629 | // PropertyGraph concepts | |
f67539c2 TL |
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 | |
7c673cae | 679 | get(Property p, UNDIRECTED_GRAPH const& g, Key const& k) |
f67539c2 TL |
680 | { |
681 | return get(p, g.impl(), k); | |
682 | } | |
7c673cae | 683 | |
f67539c2 | 684 | template < UNDIRECTED_GRAPH_PARAMS, typename Key > |
7c673cae | 685 | inline typename property_traits< |
f67539c2 TL |
686 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, |
687 | vertex_all_t >::const_type >::value_type | |
7c673cae | 688 | get(vertex_all_t, UNDIRECTED_GRAPH const& g, Key const& k) |
f67539c2 TL |
689 | { |
690 | return get(vertex_all, g.impl(), k).m_base; | |
691 | } | |
7c673cae | 692 | |
f67539c2 | 693 | template < UNDIRECTED_GRAPH_PARAMS, typename Key > |
7c673cae | 694 | inline typename property_traits< |
f67539c2 TL |
695 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, |
696 | edge_all_t >::const_type >::value_type | |
7c673cae | 697 | get(edge_all_t, UNDIRECTED_GRAPH const& g, Key const& k) |
f67539c2 TL |
698 | { |
699 | return get(edge_all, g.impl(), k).m_base; | |
700 | } | |
7c673cae | 701 | |
f67539c2 TL |
702 | template < UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key, |
703 | typename Value > | |
7c673cae | 704 | inline void put(Property p, UNDIRECTED_GRAPH& g, Key const& k, Value const& v) |
f67539c2 TL |
705 | { |
706 | put(p, g.impl(), k, v); | |
707 | } | |
7c673cae | 708 | |
f67539c2 | 709 | template < UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value > |
7c673cae | 710 | inline void put(vertex_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v) |
f67539c2 TL |
711 | { |
712 | put(vertex_all, g.impl(), k, | |
713 | typename UNDIRECTED_GRAPH::internal_vertex_property( | |
714 | get(vertex_index, g.impl(), k), v)); | |
7c673cae FG |
715 | } |
716 | ||
f67539c2 | 717 | template < UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value > |
7c673cae | 718 | inline void put(edge_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v) |
f67539c2 TL |
719 | { |
720 | put(edge_all, g.impl(), k, | |
721 | typename UNDIRECTED_GRAPH::internal_vertex_property( | |
722 | get(edge_index, g.impl(), k), v)); | |
7c673cae FG |
723 | } |
724 | ||
f67539c2 TL |
725 | template < UNDIRECTED_GRAPH_PARAMS, class Property > |
726 | inline typename graph_property< UNDIRECTED_GRAPH, Property >::type& | |
7c673cae | 727 | get_property(UNDIRECTED_GRAPH& g, Property p) |
f67539c2 TL |
728 | { |
729 | return get_property(g.impl(), p); | |
730 | } | |
7c673cae | 731 | |
f67539c2 TL |
732 | template < UNDIRECTED_GRAPH_PARAMS, class Property > |
733 | inline typename graph_property< UNDIRECTED_GRAPH, Property >::type const& | |
7c673cae | 734 | get_property(UNDIRECTED_GRAPH const& g, Property p) |
f67539c2 TL |
735 | { |
736 | return get_property(g.impl(), p); | |
737 | } | |
7c673cae | 738 | |
f67539c2 | 739 | template < UNDIRECTED_GRAPH_PARAMS, class Property, class Value > |
7c673cae | 740 | inline void set_property(UNDIRECTED_GRAPH& g, Property p, Value v) |
f67539c2 TL |
741 | { |
742 | return set_property(g.impl(), p, v); | |
743 | } | |
7c673cae FG |
744 | |
745 | // Indexed Vertex graph | |
746 | ||
f67539c2 TL |
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 | } | |
7c673cae | 753 | |
f67539c2 TL |
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 | } | |
7c673cae | 760 | |
f67539c2 TL |
761 | template < UNDIRECTED_GRAPH_PARAMS > |
762 | inline void renumber_vertex_indices(UNDIRECTED_GRAPH& g) | |
763 | { | |
764 | g.renumber_vertex_indices(); | |
765 | } | |
7c673cae | 766 | |
f67539c2 TL |
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 | } | |
7c673cae FG |
773 | |
774 | // Edge index management | |
775 | ||
f67539c2 TL |
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 | } | |
7c673cae | 782 | |
f67539c2 TL |
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 | } | |
7c673cae | 789 | |
f67539c2 TL |
790 | template < UNDIRECTED_GRAPH_PARAMS > |
791 | inline void renumber_edge_indices(UNDIRECTED_GRAPH& g) | |
792 | { | |
793 | g.renumber_edge_indices(); | |
794 | } | |
7c673cae | 795 | |
f67539c2 TL |
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 | } | |
7c673cae FG |
802 | |
803 | // Index management | |
f67539c2 TL |
804 | template < UNDIRECTED_GRAPH_PARAMS > |
805 | inline void renumber_indices(UNDIRECTED_GRAPH& g) | |
806 | { | |
807 | g.renumber_indices(); | |
808 | } | |
7c673cae FG |
809 | |
810 | // Mutability Traits | |
f67539c2 TL |
811 | template < UNDIRECTED_GRAPH_PARAMS > |
812 | struct graph_mutability_traits< UNDIRECTED_GRAPH > | |
813 | { | |
7c673cae FG |
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 |