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/utility.hpp>
11 #include <boost/graph/adjacency_list.hpp>
12 #include <boost/graph/properties.hpp>
13
14 // NOTE: The retag_property_list is used to "normalize" a proeprty such that
15 // any non-property conforming parameter is wrapped in a vertex_bundle
16 // property. For example (with bad syntax) retag<property<X>> -> property<X>,
17 // but retag<foo> -> property<vertex_bundle_t, foo>.
18
19 namespace boost
20 {
21 struct undirected_graph_tag { };
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 <
35 typename VertexProp = no_property,
36 typename EdgeProp = no_property,
37 typename GraphProp = no_property>
38 class undirected_graph
39 {
40 public:
41 typedef typename graph_detail::graph_prop<GraphProp>::property graph_property_type;
42 typedef typename graph_detail::graph_prop<GraphProp>::bundle graph_bundled;
43
44 typedef typename graph_detail::vertex_prop<VertexProp>::property vertex_property_type;
45 typedef typename graph_detail::vertex_prop<VertexProp>::bundle vertex_bundled;
46
47 typedef typename graph_detail::edge_prop<EdgeProp>::property edge_property_type;
48 typedef typename graph_detail::edge_prop<EdgeProp>::bundle edge_bundled;
49
50 private:
51 // Embed indices into the vertex type.
52 typedef property<vertex_index_t, unsigned, vertex_property_type> vertex_property;
53 typedef property<edge_index_t, unsigned, edge_property_type> edge_property;
54 public:
55 typedef adjacency_list<listS,
56 listS,
57 undirectedS,
58 vertex_property,
59 edge_property,
60 GraphProp,
61 listS> graph_type;
62 private:
63 // storage selectors
64 typedef typename graph_type::vertex_list_selector vertex_list_selector;
65 typedef typename graph_type::edge_list_selector edge_list_selector;
66 typedef typename graph_type::out_edge_list_selector out_edge_list_selector;
67 typedef typename graph_type::directed_selector directed_selector;
68
69 public:
70 // more commonly used graph types
71 typedef typename graph_type::stored_vertex stored_vertex;
72 typedef typename graph_type::vertices_size_type vertices_size_type;
73 typedef typename graph_type::edges_size_type edges_size_type;
74 typedef typename graph_type::degree_size_type degree_size_type;
75 typedef typename graph_type::vertex_descriptor vertex_descriptor;
76 typedef typename graph_type::edge_descriptor edge_descriptor;
77
78 // iterator types
79 typedef typename graph_type::vertex_iterator vertex_iterator;
80 typedef typename graph_type::edge_iterator edge_iterator;
81 typedef typename graph_type::out_edge_iterator out_edge_iterator;
82 typedef typename graph_type::in_edge_iterator in_edge_iterator;
83 typedef typename graph_type::adjacency_iterator adjacency_iterator;
84
85 // miscellaneous types
86 typedef undirected_graph_tag graph_tag;
87 typedef typename graph_type::directed_category directed_category;
88 typedef typename graph_type::edge_parallel_category edge_parallel_category;
89 typedef typename graph_type::traversal_category traversal_category;
90
91 typedef std::size_t vertex_index_type;
92 typedef std::size_t edge_index_type;
93
undirected_graph(GraphProp const & p=GraphProp ())94 inline undirected_graph(GraphProp const& p = GraphProp())
95 : m_graph(p), m_num_vertices(0), m_num_edges(0), m_max_vertex_index(0)
96 , m_max_edge_index(0)
97 { }
98
undirected_graph(undirected_graph const & x)99 inline undirected_graph(undirected_graph const& x)
100 : m_graph(x.m_graph), m_num_vertices(x.m_num_vertices), m_num_edges(x.m_num_edges)
101 , m_max_vertex_index(x.m_max_vertex_index), m_max_edge_index(x.m_max_edge_index)
102 { }
103
undirected_graph(vertices_size_type n,GraphProp const & p=GraphProp ())104 inline undirected_graph(vertices_size_type n,
105 GraphProp const& p = GraphProp())
106 : m_graph(n, p), m_num_vertices(n), m_num_edges(0), m_max_vertex_index(n)
107 , m_max_edge_index(0)
108 { renumber_vertex_indices(); }
109
110 template <typename EdgeIterator>
undirected_graph(EdgeIterator f,EdgeIterator l,vertices_size_type n,edges_size_type m=0,GraphProp const & p=GraphProp ())111 inline undirected_graph(EdgeIterator f,
112 EdgeIterator l,
113 vertices_size_type n,
114 edges_size_type m = 0,
115 GraphProp const& p = GraphProp())
116 : m_graph(f, l, n, m, p), m_num_vertices(n), m_num_edges(0)
117 , m_max_vertex_index(n), m_max_edge_index(0)
118 {
119 // Unfortunately, we have to renumber to ensure correct indexing.
120 renumber_indices();
121
122 // Can't always guarantee that the number of edges is actually
123 // m if distance(f, l) != m (or is undefined).
124 m_num_edges = m_max_edge_index = boost::num_edges(m_graph);
125 }
126
operator =(undirected_graph const & g)127 undirected_graph& operator =(undirected_graph const& g) {
128 if(&g != this) {
129 m_graph = g.m_graph;
130 m_num_vertices = g.m_num_vertices;
131 m_num_edges = g.m_num_edges;
132 m_max_vertex_index = g.m_max_vertex_index;
133 }
134 return *this;
135 }
136
137 // The impl_() methods are not part of the public interface.
impl()138 graph_type& impl()
139 { return m_graph; }
140
impl() const141 graph_type const& impl() const
142 { return m_graph; }
143
144 // The following methods are not part of the public interface
num_vertices() const145 vertices_size_type num_vertices() const
146 { return m_num_vertices; }
147
148
149 private:
150 // This helper function manages the attribution of vertex indices.
make_index(vertex_descriptor v)151 vertex_descriptor make_index(vertex_descriptor v) {
152 boost::put(vertex_index, m_graph, v, m_max_vertex_index);
153 m_num_vertices++;
154 m_max_vertex_index++;
155 return v;
156 }
157 public:
add_vertex()158 vertex_descriptor add_vertex()
159 { return make_index(boost::add_vertex(m_graph)); }
160
add_vertex(vertex_property_type const & p)161 vertex_descriptor add_vertex(vertex_property_type const& p)
162 { return make_index(boost::add_vertex(vertex_property(0u, p), m_graph)); }
163
clear_vertex(vertex_descriptor v)164 void clear_vertex(vertex_descriptor v) {
165 std::pair<out_edge_iterator, out_edge_iterator>
166 p = boost::out_edges(v, m_graph);
167 m_num_edges -= std::distance(p.first, p.second);
168 boost::clear_vertex(v, m_graph);
169 }
170
remove_vertex(vertex_descriptor v)171 void remove_vertex(vertex_descriptor v) {
172 boost::remove_vertex(v, m_graph);
173 --m_num_vertices;
174 }
175
num_edges() const176 edges_size_type num_edges() const
177 { return m_num_edges; }
178
179 private:
180 // A helper fucntion for managing edge index attributes.
181 std::pair<edge_descriptor, bool> const&
make_index(std::pair<edge_descriptor,bool> const & x)182 make_index(std::pair<edge_descriptor, bool> const& x)
183 {
184 if(x.second) {
185 boost::put(edge_index, m_graph, x.first, m_max_edge_index);
186 ++m_num_edges;
187 ++m_max_edge_index;
188 }
189 return x;
190 }
191 public:
192 std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u,vertex_descriptor v)193 add_edge(vertex_descriptor u, vertex_descriptor v)
194 { return make_index(boost::add_edge(u, v, m_graph)); }
195
196 std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u,vertex_descriptor v,edge_property_type const & p)197 add_edge(vertex_descriptor u, vertex_descriptor v,
198 edge_property_type const& p)
199 { return make_index(boost::add_edge(u, v, edge_property(0u, p), m_graph)); }
200
remove_edge(vertex_descriptor u,vertex_descriptor v)201 void remove_edge(vertex_descriptor u, vertex_descriptor v) {
202 // find all edges, (u, v)
203 std::vector<edge_descriptor> edges;
204 out_edge_iterator i, i_end;
205 for(boost::tie(i, i_end) = boost::out_edges(u, m_graph); i != i_end; ++i) {
206 if(boost::target(*i, m_graph) == v) {
207 edges.push_back(*i);
208 }
209 }
210 // remove all edges, (u, v)
211 typename std::vector<edge_descriptor>::iterator
212 j = edges.begin(), j_end = edges.end();
213 for( ; j != j_end; ++j) {
214 remove_edge(*j);
215 }
216 }
217
remove_edge(edge_iterator i)218 void remove_edge(edge_iterator i) {
219 remove_edge(*i);
220 }
221
remove_edge(edge_descriptor e)222 void remove_edge(edge_descriptor e) {
223 boost::remove_edge(e, m_graph);
224 --m_num_edges;
225 }
226
max_vertex_index() const227 vertex_index_type max_vertex_index() const
228 { return m_max_vertex_index; }
229
renumber_vertex_indices()230 void renumber_vertex_indices() {
231 vertex_iterator i, i_end;
232 boost::tie(i, i_end) = vertices(m_graph);
233 m_max_vertex_index = renumber_vertex_indices(i, i_end, 0);
234 }
235
remove_vertex_and_renumber_indices(vertex_iterator i)236 void remove_vertex_and_renumber_indices(vertex_iterator i) {
237 vertex_iterator j = next(i), end = vertices(m_graph).second;
238 vertex_index_type n = get(vertex_index, m_graph, *i);
239
240 // remove the offending vertex and renumber everything after
241 remove_vertex(*i);
242 m_max_vertex_index = renumber_vertex_indices(j, end, n);
243 }
244
245
max_edge_index() const246 edge_index_type max_edge_index() const
247 { return m_max_edge_index; }
248
renumber_edge_indices()249 void renumber_edge_indices() {
250 edge_iterator i, end;
251 boost::tie(i, end) = edges(m_graph);
252 m_max_edge_index = renumber_edge_indices(i, end, 0);
253 }
254
remove_edge_and_renumber_indices(edge_iterator i)255 void remove_edge_and_renumber_indices(edge_iterator i) {
256 edge_iterator j = next(i), end = edges(m_graph.second);
257 edge_index_type n = get(edge_index, m_graph, *i);
258
259 // remove the edge and renumber everything after it
260 remove_edge(*i);
261 m_max_edge_index = renumber_edge_indices(j, end, n);
262 }
263
renumber_indices()264 void renumber_indices() {
265 renumber_vertex_indices();
266 renumber_edge_indices();
267 }
268
269 // bundled property support
270 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
operator [](vertex_descriptor v)271 vertex_bundled& operator[](vertex_descriptor v)
272 { return m_graph[v]; }
273
operator [](vertex_descriptor v) const274 vertex_bundled const& operator[](vertex_descriptor v) const
275 { return m_graph[v]; }
276
operator [](edge_descriptor e)277 edge_bundled& operator[](edge_descriptor e)
278 { return m_graph[e]; }
279
operator [](edge_descriptor e) const280 edge_bundled const& operator[](edge_descriptor e) const
281 { return m_graph[e]; }
282
operator [](graph_bundle_t)283 graph_bundled& operator[](graph_bundle_t)
284 { return get_property(*this); }
285
operator [](graph_bundle_t) const286 graph_bundled const& operator[](graph_bundle_t) const
287 { return get_property(*this); }
288 #endif
289
290 // Graph concepts
null_vertex()291 static vertex_descriptor null_vertex()
292 { return graph_type::null_vertex(); }
293
clear()294 void clear() {
295 m_graph.clear();
296 m_num_vertices = m_max_vertex_index = 0;
297 m_num_edges = m_max_edge_index = 0;
298 }
299
swap(undirected_graph & g)300 void swap(undirected_graph& g) {
301 m_graph.swap(g);
302 std::swap(m_num_vertices, g.m_num_vertices);
303 std::swap(m_max_vertex_index, g.m_max_vertex_index);
304 std::swap(m_num_edges, g.m_num_edges);
305 std::swap(m_max_edge_index, g.m_max_edge_index);
306 }
307
308 private:
renumber_vertex_indices(vertex_iterator i,vertex_iterator end,vertices_size_type n)309 vertices_size_type renumber_vertex_indices(vertex_iterator i,
310 vertex_iterator end,
311 vertices_size_type n)
312 {
313 typedef typename property_map<graph_type, vertex_index_t>::type IndexMap;
314 IndexMap indices = get(vertex_index, m_graph);
315 for( ; i != end; ++i) {
316 indices[*i] = n++;
317 }
318 return n;
319 }
320
renumber_edge_indices(edge_iterator i,edge_iterator end,edges_size_type n)321 edges_size_type renumber_edge_indices(edge_iterator i,
322 edge_iterator end,
323 edges_size_type n)
324 {
325 typedef typename property_map<graph_type, edge_index_t>::type IndexMap;
326 IndexMap indices = get(edge_index, m_graph);
327 for( ; i != end; ++i) {
328 indices[*i] = n++;
329 }
330 return n;
331 }
332
333 graph_type m_graph;
334 vertices_size_type m_num_vertices;
335 edges_size_type m_num_edges;
336 vertex_index_type m_max_vertex_index;
337 edge_index_type m_max_edge_index;
338 };
339
340 #define UNDIRECTED_GRAPH_PARAMS typename VP, typename EP, typename GP
341 #define UNDIRECTED_GRAPH undirected_graph<VP,EP,GP>
342
343 // IncidenceGraph concepts
344 template <UNDIRECTED_GRAPH_PARAMS>
345 inline typename UNDIRECTED_GRAPH::vertex_descriptor
source(typename UNDIRECTED_GRAPH::edge_descriptor e,UNDIRECTED_GRAPH const & g)346 source(typename UNDIRECTED_GRAPH::edge_descriptor e,
347 UNDIRECTED_GRAPH const& g)
348 { return source(e, g.impl()); }
349
350 template <UNDIRECTED_GRAPH_PARAMS>
351 inline typename UNDIRECTED_GRAPH::vertex_descriptor
target(typename UNDIRECTED_GRAPH::edge_descriptor e,UNDIRECTED_GRAPH const & g)352 target(typename UNDIRECTED_GRAPH::edge_descriptor e,
353 UNDIRECTED_GRAPH const& g)
354 { return target(e, g.impl()); }
355
356 template <UNDIRECTED_GRAPH_PARAMS>
357 inline typename UNDIRECTED_GRAPH::degree_size_type
out_degree(typename UNDIRECTED_GRAPH::vertex_descriptor v,UNDIRECTED_GRAPH const & g)358 out_degree(typename UNDIRECTED_GRAPH::vertex_descriptor v,
359 UNDIRECTED_GRAPH const& g)
360 { return out_degree(v, g.impl()); }
361
362 template <UNDIRECTED_GRAPH_PARAMS>
363 inline std::pair<
364 typename UNDIRECTED_GRAPH::out_edge_iterator,
365 typename UNDIRECTED_GRAPH::out_edge_iterator
366 >
out_edges(typename UNDIRECTED_GRAPH::vertex_descriptor v,UNDIRECTED_GRAPH const & g)367 out_edges(typename UNDIRECTED_GRAPH::vertex_descriptor v,
368 UNDIRECTED_GRAPH const& g)
369 { return out_edges(v, g.impl()); }
370
371 // BidirectionalGraph concepts
372 template <UNDIRECTED_GRAPH_PARAMS>
373 inline typename UNDIRECTED_GRAPH::degree_size_type
in_degree(typename UNDIRECTED_GRAPH::vertex_descriptor v,UNDIRECTED_GRAPH const & g)374 in_degree(typename UNDIRECTED_GRAPH::vertex_descriptor v,
375 UNDIRECTED_GRAPH const& g)
376 { return in_degree(v, g.impl()); }
377
378 template <UNDIRECTED_GRAPH_PARAMS>
379 inline std::pair<
380 typename UNDIRECTED_GRAPH::in_edge_iterator,
381 typename UNDIRECTED_GRAPH::in_edge_iterator
382 >
in_edges(typename UNDIRECTED_GRAPH::vertex_descriptor v,UNDIRECTED_GRAPH const & g)383 in_edges(typename UNDIRECTED_GRAPH::vertex_descriptor v,
384 UNDIRECTED_GRAPH const& g)
385 { return in_edges(v, g.impl()); }
386
387 template <UNDIRECTED_GRAPH_PARAMS>
388 inline std::pair<
389 typename UNDIRECTED_GRAPH::out_edge_iterator,
390 typename UNDIRECTED_GRAPH::out_edge_iterator
391 >
incident_edges(typename UNDIRECTED_GRAPH::vertex_descriptor v,UNDIRECTED_GRAPH const & g)392 incident_edges(typename UNDIRECTED_GRAPH::vertex_descriptor v,
393 UNDIRECTED_GRAPH const& g)
394 { return out_edges(v, g.impl()); }
395
396 template <UNDIRECTED_GRAPH_PARAMS>
397 inline typename UNDIRECTED_GRAPH::degree_size_type
degree(typename UNDIRECTED_GRAPH::vertex_descriptor v,UNDIRECTED_GRAPH const & g)398 degree(typename UNDIRECTED_GRAPH::vertex_descriptor v,
399 UNDIRECTED_GRAPH const& g)
400 { return degree(v, g.impl()); }
401
402 // AdjacencyGraph concepts
403 template <UNDIRECTED_GRAPH_PARAMS>
404 inline std::pair<
405 typename UNDIRECTED_GRAPH::adjacency_iterator,
406 typename UNDIRECTED_GRAPH::adjacency_iterator
407 >
adjacent_vertices(typename UNDIRECTED_GRAPH::vertex_descriptor v,UNDIRECTED_GRAPH const & g)408 adjacent_vertices(typename UNDIRECTED_GRAPH::vertex_descriptor v,
409 UNDIRECTED_GRAPH const& g)
410 { return adjacent_vertices(v, g.impl()); }
411
412 template <UNDIRECTED_GRAPH_PARAMS>
413 typename UNDIRECTED_GRAPH::vertex_descriptor
vertex(typename UNDIRECTED_GRAPH::vertices_size_type n,UNDIRECTED_GRAPH const & g)414 vertex(typename UNDIRECTED_GRAPH::vertices_size_type n,
415 UNDIRECTED_GRAPH const& g)
416 { return vertex(g.impl()); }
417
418 template <UNDIRECTED_GRAPH_PARAMS>
419 std::pair<typename UNDIRECTED_GRAPH::edge_descriptor, bool>
edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,typename UNDIRECTED_GRAPH::vertex_descriptor v,UNDIRECTED_GRAPH const & g)420 edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,
421 typename UNDIRECTED_GRAPH::vertex_descriptor v,
422 UNDIRECTED_GRAPH const& g)
423 { return edge(u, v, g.impl()); }
424
425 // VertexListGraph concepts
426 template <UNDIRECTED_GRAPH_PARAMS>
427 inline typename UNDIRECTED_GRAPH::vertices_size_type
num_vertices(UNDIRECTED_GRAPH const & g)428 num_vertices(UNDIRECTED_GRAPH const& g)
429 { return g.num_vertices(); }
430
431 template <UNDIRECTED_GRAPH_PARAMS>
432 inline std::pair<
433 typename UNDIRECTED_GRAPH::vertex_iterator,
434 typename UNDIRECTED_GRAPH::vertex_iterator
435 >
vertices(UNDIRECTED_GRAPH const & g)436 vertices(UNDIRECTED_GRAPH const& g)
437 { return vertices(g.impl()); }
438
439 // EdgeListGraph concepts
440 template <UNDIRECTED_GRAPH_PARAMS>
441 inline typename UNDIRECTED_GRAPH::edges_size_type
num_edges(UNDIRECTED_GRAPH const & g)442 num_edges(UNDIRECTED_GRAPH const& g)
443 { return g.num_edges(); }
444
445 template <UNDIRECTED_GRAPH_PARAMS>
446 inline std::pair<
447 typename UNDIRECTED_GRAPH::edge_iterator,
448 typename UNDIRECTED_GRAPH::edge_iterator
449 >
edges(UNDIRECTED_GRAPH const & g)450 edges(UNDIRECTED_GRAPH const& g)
451 { return edges(g.impl()); }
452
453 // MutableGraph concepts
454 template <UNDIRECTED_GRAPH_PARAMS>
455 inline typename UNDIRECTED_GRAPH::vertex_descriptor
add_vertex(UNDIRECTED_GRAPH & g)456 add_vertex(UNDIRECTED_GRAPH& g)
457 { return g.add_vertex(); }
458
459 template <UNDIRECTED_GRAPH_PARAMS>
460 inline typename UNDIRECTED_GRAPH::vertex_descriptor
add_vertex(typename UNDIRECTED_GRAPH::vertex_property_type const & p,UNDIRECTED_GRAPH & g)461 add_vertex(typename UNDIRECTED_GRAPH::vertex_property_type const& p,
462 UNDIRECTED_GRAPH& g)
463 { return g.add_vertex(p); }
464
465 template <UNDIRECTED_GRAPH_PARAMS>
466 inline void
clear_vertex(typename UNDIRECTED_GRAPH::vertex_descriptor v,UNDIRECTED_GRAPH & g)467 clear_vertex(typename UNDIRECTED_GRAPH::vertex_descriptor v,
468 UNDIRECTED_GRAPH& g)
469 { return g.clear_vertex(v); }
470
471 template <UNDIRECTED_GRAPH_PARAMS>
472 inline void
remove_vertex(typename UNDIRECTED_GRAPH::vertex_descriptor v,UNDIRECTED_GRAPH & g)473 remove_vertex(typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g)
474 { return g.remove_vertex(v); }
475
476 template <UNDIRECTED_GRAPH_PARAMS>
477 inline std::pair<typename UNDIRECTED_GRAPH::edge_descriptor, bool>
add_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,typename UNDIRECTED_GRAPH::vertex_descriptor v,UNDIRECTED_GRAPH & g)478 add_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,
479 typename UNDIRECTED_GRAPH::vertex_descriptor v,
480 UNDIRECTED_GRAPH& g)
481 { return g.add_edge(u, v); }
482
483 template <UNDIRECTED_GRAPH_PARAMS>
484 inline std::pair<typename UNDIRECTED_GRAPH::edge_descriptor, bool>
add_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,typename UNDIRECTED_GRAPH::vertex_descriptor v,typename UNDIRECTED_GRAPH::edge_property_type const & p,UNDIRECTED_GRAPH & g)485 add_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,
486 typename UNDIRECTED_GRAPH::vertex_descriptor v,
487 typename UNDIRECTED_GRAPH::edge_property_type const& p,
488 UNDIRECTED_GRAPH& g)
489 { return g.add_edge(u, v, p); }
490
491 template <UNDIRECTED_GRAPH_PARAMS>
492 inline void
remove_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,typename UNDIRECTED_GRAPH::vertex_descriptor v,UNDIRECTED_GRAPH & g)493 remove_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,
494 typename UNDIRECTED_GRAPH::vertex_descriptor v,
495 UNDIRECTED_GRAPH& g)
496 { return g.remove_edge(u, v); }
497
498 template <UNDIRECTED_GRAPH_PARAMS>
499 inline void
remove_edge(typename UNDIRECTED_GRAPH::edge_descriptor e,UNDIRECTED_GRAPH & g)500 remove_edge(typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH& g)
501 { return g.remove_edge(e); }
502
503 template <UNDIRECTED_GRAPH_PARAMS>
504 inline void
remove_edge(typename UNDIRECTED_GRAPH::edge_iterator i,UNDIRECTED_GRAPH & g)505 remove_edge(typename UNDIRECTED_GRAPH::edge_iterator i, UNDIRECTED_GRAPH& g)
506 { return g.remove_edge(i); }
507
508 template <UNDIRECTED_GRAPH_PARAMS, class Predicate>
remove_edge_if(Predicate pred,UNDIRECTED_GRAPH & g)509 inline void remove_edge_if(Predicate pred, UNDIRECTED_GRAPH& g)
510 { return remove_edge_if(pred, g.impl()); }
511
512 template <UNDIRECTED_GRAPH_PARAMS, class Predicate>
513 inline void
remove_incident_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,Predicate pred,UNDIRECTED_GRAPH & g)514 remove_incident_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,
515 Predicate pred,
516 UNDIRECTED_GRAPH& g)
517 { return remove_out_edge_if(v, pred, g.impl()); }
518
519 template <UNDIRECTED_GRAPH_PARAMS, class Predicate>
520 inline void
remove_out_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,Predicate pred,UNDIRECTED_GRAPH & g)521 remove_out_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,
522 Predicate pred,
523 UNDIRECTED_GRAPH& g)
524 { return remove_out_edge_if(v, pred, g.impl()); }
525
526 template <UNDIRECTED_GRAPH_PARAMS, class Predicate>
527 inline void
remove_in_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,Predicate pred,UNDIRECTED_GRAPH & g)528 remove_in_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,
529 Predicate pred,
530 UNDIRECTED_GRAPH& g)
531 { return remove_in_edge_if(v, pred, g.impl()); }
532
533 // Helper code for working with property maps
534 namespace detail {
535 struct undirected_graph_vertex_property_selector {
536 template <class UndirectedGraph, class Property, class Tag>
537 struct bind_ {
538 typedef typename UndirectedGraph::graph_type Graph;
539 typedef property_map<Graph, Tag> PropertyMap;
540 typedef typename PropertyMap::type type;
541 typedef typename PropertyMap::const_type const_type;
542 };
543 };
544
545 struct undirected_graph_edge_property_selector {
546 template <class UndirectedGraph, class Property, class Tag>
547 struct bind_ {
548 typedef typename UndirectedGraph::graph_type Graph;
549 typedef property_map<Graph, Tag> PropertyMap;
550 typedef typename PropertyMap::type type;
551 typedef typename PropertyMap::const_type const_type;
552 };
553 };
554 } // namespace detail
555
556 template <>
557 struct vertex_property_selector<undirected_graph_tag>
558 { typedef detail::undirected_graph_vertex_property_selector type; };
559
560 template <>
561 struct edge_property_selector<undirected_graph_tag>
562 { typedef detail::undirected_graph_edge_property_selector type; };
563
564 // PropertyGraph concepts
565 template <UNDIRECTED_GRAPH_PARAMS, typename Property>
566 inline typename property_map<UNDIRECTED_GRAPH, Property>::type
get(Property p,UNDIRECTED_GRAPH & g)567 get(Property p, UNDIRECTED_GRAPH& g)
568 { return get(p, g.impl()); }
569
570 template <UNDIRECTED_GRAPH_PARAMS, typename Property>
571 inline typename property_map<UNDIRECTED_GRAPH, Property>::const_type
get(Property p,UNDIRECTED_GRAPH const & g)572 get(Property p, UNDIRECTED_GRAPH const& g)
573 { return get(p, g.impl()); }
574
575 template <UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key>
576 inline typename property_traits<
577 typename property_map<
578 typename UNDIRECTED_GRAPH::graph_type, Property
579 >::const_type
580 >::value_type
get(Property p,UNDIRECTED_GRAPH const & g,Key const & k)581 get(Property p, UNDIRECTED_GRAPH const& g, Key const& k)
582 { return get(p, g.impl(), k); }
583
584 template <UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key, typename Value>
put(Property p,UNDIRECTED_GRAPH & g,Key const & k,Value const & v)585 inline void put(Property p, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
586 { put(p, g.impl(), k, v); }
587
588 template <UNDIRECTED_GRAPH_PARAMS, class Property>
589 inline typename graph_property<UNDIRECTED_GRAPH, Property>::type&
get_property(UNDIRECTED_GRAPH & g,Property p)590 get_property(UNDIRECTED_GRAPH& g, Property p)
591 { return get_property(g.impl(), p); }
592
593 template <UNDIRECTED_GRAPH_PARAMS, class Property>
594 inline typename graph_property<UNDIRECTED_GRAPH, Property>::type const&
get_property(UNDIRECTED_GRAPH const & g,Property p)595 get_property(UNDIRECTED_GRAPH const& g, Property p)
596 { return get_property(g.impl(), p); }
597
598 template <UNDIRECTED_GRAPH_PARAMS, class Property, class Value>
set_property(UNDIRECTED_GRAPH & g,Property p,Value v)599 inline void set_property(UNDIRECTED_GRAPH& g, Property p, Value v)
600 { return set_property(g.impl(), p, v); }
601
602 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
603 template <UNDIRECTED_GRAPH_PARAMS, typename Type, typename Bundle>
604 inline typename property_map<UNDIRECTED_GRAPH, Type Bundle::*>::type
get(Type Bundle::* p,UNDIRECTED_GRAPH & g)605 get(Type Bundle::* p, UNDIRECTED_GRAPH& g) {
606 typedef typename property_map<
607 UNDIRECTED_GRAPH, Type Bundle::*
608 >::type return_type;
609 return return_type(&g, p);
610 }
611
612 template <UNDIRECTED_GRAPH_PARAMS, typename Type, typename Bundle>
613 inline typename property_map<UNDIRECTED_GRAPH, Type Bundle::*>::const_type
get(Type Bundle::* p,UNDIRECTED_GRAPH const & g)614 get(Type Bundle::* p, UNDIRECTED_GRAPH const& g) {
615 typedef typename property_map<
616 UNDIRECTED_GRAPH, Type Bundle::*
617 >::const_type return_type;
618 return return_type(&g, p);
619 }
620
621 template <UNDIRECTED_GRAPH_PARAMS, typename Type, typename Bundle, typename Key>
622 inline Type
get(Type Bundle::* p,UNDIRECTED_GRAPH const & g,Key const & k)623 get(Type Bundle::* p, UNDIRECTED_GRAPH const& g, Key const& k)
624 { return get(p, g.impl(), k); }
625
626 template <UNDIRECTED_GRAPH_PARAMS, typename Type, typename Bundle, typename Key, typename Value>
627 inline void
put(Type Bundle::* p,UNDIRECTED_GRAPH & g,Key const & k,Value const & v)628 put(Type Bundle::* p, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
629 { put(p, g.impl(), k, v); }
630 #endif
631
632 // Indexed Vertex graph
633
634 template <UNDIRECTED_GRAPH_PARAMS>
635 inline typename UNDIRECTED_GRAPH::vertex_index_type
get_vertex_index(typename UNDIRECTED_GRAPH::vertex_descriptor v,UNDIRECTED_GRAPH const & g)636 get_vertex_index(typename UNDIRECTED_GRAPH::vertex_descriptor v,
637 UNDIRECTED_GRAPH const& g)
638 { return get(vertex_index, g, v); }
639
640 template <UNDIRECTED_GRAPH_PARAMS>
641 typename UNDIRECTED_GRAPH::vertex_index_type
max_vertex_index(UNDIRECTED_GRAPH const & g)642 max_vertex_index(UNDIRECTED_GRAPH const& g)
643 { return g.max_vertex_index(); }
644
645 template <UNDIRECTED_GRAPH_PARAMS>
646 inline void
renumber_vertex_indices(UNDIRECTED_GRAPH & g)647 renumber_vertex_indices(UNDIRECTED_GRAPH& g)
648 { g.renumber_vertex_indices(); }
649
650 template <UNDIRECTED_GRAPH_PARAMS>
651 inline void
remove_vertex_and_renumber_indices(typename UNDIRECTED_GRAPH::vertex_iterator i,UNDIRECTED_GRAPH & g)652 remove_vertex_and_renumber_indices(typename UNDIRECTED_GRAPH::vertex_iterator i,
653 UNDIRECTED_GRAPH& g)
654 { g.remove_vertex_and_renumber_indices(i); }
655
656
657 // Edge index management
658
659 template <UNDIRECTED_GRAPH_PARAMS>
660 inline typename UNDIRECTED_GRAPH::edge_index_type
get_edge_index(typename UNDIRECTED_GRAPH::edge_descriptor v,UNDIRECTED_GRAPH const & g)661 get_edge_index(typename UNDIRECTED_GRAPH::edge_descriptor v,
662 UNDIRECTED_GRAPH const& g)
663 { return get(edge_index, g, v); }
664
665 template <UNDIRECTED_GRAPH_PARAMS>
666 typename UNDIRECTED_GRAPH::edge_index_type
max_edge_index(UNDIRECTED_GRAPH const & g)667 max_edge_index(UNDIRECTED_GRAPH const& g)
668 { return g.max_edge_index(); }
669
670 template <UNDIRECTED_GRAPH_PARAMS>
671 inline void
renumber_edge_indices(UNDIRECTED_GRAPH & g)672 renumber_edge_indices(UNDIRECTED_GRAPH& g)
673 { g.renumber_edge_indices(); }
674
675 template <UNDIRECTED_GRAPH_PARAMS>
676 inline void
remove_edge_and_renumber_indices(typename UNDIRECTED_GRAPH::edge_iterator i,UNDIRECTED_GRAPH & g)677 remove_edge_and_renumber_indices(typename UNDIRECTED_GRAPH::edge_iterator i,
678 UNDIRECTED_GRAPH& g)
679 { g.remove_edge_and_renumber_indices(i); }
680
681 // Index management
682 template <UNDIRECTED_GRAPH_PARAMS>
683 inline void
renumber_indices(UNDIRECTED_GRAPH & g)684 renumber_indices(UNDIRECTED_GRAPH& g)
685 { g.renumber_indices(); }
686
687 // Mutability Traits
688 template <UNDIRECTED_GRAPH_PARAMS>
689 struct graph_mutability_traits<UNDIRECTED_GRAPH> {
690 typedef mutable_property_graph_tag category;
691 };
692
693 #undef UNDIRECTED_GRAPH_PARAMS
694 #undef UNDIRECTED_GRAPH
695
696 } /* namespace boost */
697
698 #endif
699