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