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

source code of boost/boost/graph/undirected_graph.hpp