]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
3 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek | |
4 | // | |
5 | // Distributed under the Boost Software License, Version 1.0. (See | |
6 | // accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | //======================================================================= | |
9 | ||
10 | #ifndef BOOST_FILTERED_GRAPH_HPP | |
11 | #define BOOST_FILTERED_GRAPH_HPP | |
12 | ||
13 | #include <boost/graph/graph_traits.hpp> | |
14 | #include <boost/graph/properties.hpp> | |
15 | #include <boost/graph/adjacency_iterator.hpp> | |
16 | #include <boost/graph/detail/set_adaptor.hpp> | |
17 | #include <boost/iterator/filter_iterator.hpp> | |
18 | ||
19 | namespace boost { | |
20 | ||
21 | //========================================================================= | |
22 | // Some predicate classes. | |
23 | ||
24 | struct keep_all { | |
25 | template <typename T> | |
26 | bool operator()(const T&) const { return true; } | |
27 | }; | |
28 | ||
29 | // Keep residual edges (used in maximum-flow algorithms). | |
30 | template <typename ResidualCapacityEdgeMap> | |
31 | struct is_residual_edge { | |
32 | is_residual_edge() { } | |
33 | is_residual_edge(ResidualCapacityEdgeMap rcap) : m_rcap(rcap) { } | |
34 | template <typename Edge> | |
35 | bool operator()(const Edge& e) const { | |
36 | return 0 < get(m_rcap, e); | |
37 | } | |
38 | ResidualCapacityEdgeMap m_rcap; | |
39 | }; | |
40 | ||
41 | template <typename Set> | |
42 | struct is_in_subset { | |
43 | is_in_subset() : m_s(0) { } | |
44 | is_in_subset(const Set& s) : m_s(&s) { } | |
45 | ||
46 | template <typename Elt> | |
47 | bool operator()(const Elt& x) const { | |
48 | return set_contains(*m_s, x); | |
49 | } | |
50 | const Set* m_s; | |
51 | }; | |
52 | ||
53 | template <typename Set> | |
54 | struct is_not_in_subset { | |
55 | is_not_in_subset() : m_s(0) { } | |
56 | is_not_in_subset(const Set& s) : m_s(&s) { } | |
57 | ||
58 | template <typename Elt> | |
59 | bool operator()(const Elt& x) const { | |
60 | return !set_contains(*m_s, x); | |
61 | } | |
62 | const Set* m_s; | |
63 | }; | |
64 | ||
65 | namespace detail { | |
66 | ||
67 | template <typename EdgePredicate, typename VertexPredicate, typename Graph> | |
68 | struct out_edge_predicate { | |
69 | out_edge_predicate() { } | |
70 | out_edge_predicate(EdgePredicate ep, VertexPredicate vp, | |
71 | const Graph& g) | |
72 | : m_edge_pred(ep), m_vertex_pred(vp), m_g(&g) { } | |
73 | ||
74 | template <typename Edge> | |
75 | bool operator()(const Edge& e) const { | |
76 | return m_edge_pred(e) && m_vertex_pred(target(e, *m_g)); | |
77 | } | |
78 | EdgePredicate m_edge_pred; | |
79 | VertexPredicate m_vertex_pred; | |
80 | const Graph* m_g; | |
81 | }; | |
82 | ||
83 | template <typename EdgePredicate, typename VertexPredicate, typename Graph> | |
84 | struct in_edge_predicate { | |
85 | in_edge_predicate() { } | |
86 | in_edge_predicate(EdgePredicate ep, VertexPredicate vp, | |
87 | const Graph& g) | |
88 | : m_edge_pred(ep), m_vertex_pred(vp), m_g(&g) { } | |
89 | ||
90 | template <typename Edge> | |
91 | bool operator()(const Edge& e) const { | |
92 | return m_edge_pred(e) && m_vertex_pred(source(e, *m_g)); | |
93 | } | |
94 | EdgePredicate m_edge_pred; | |
95 | VertexPredicate m_vertex_pred; | |
96 | const Graph* m_g; | |
97 | }; | |
98 | ||
99 | template <typename EdgePredicate, typename VertexPredicate, typename Graph> | |
100 | struct edge_predicate { | |
101 | edge_predicate() { } | |
102 | edge_predicate(EdgePredicate ep, VertexPredicate vp, | |
103 | const Graph& g) | |
104 | : m_edge_pred(ep), m_vertex_pred(vp), m_g(&g) { } | |
105 | ||
106 | template <typename Edge> | |
107 | bool operator()(const Edge& e) const { | |
108 | return m_edge_pred(e) | |
109 | && m_vertex_pred(source(e, *m_g)) && m_vertex_pred(target(e, *m_g)); | |
110 | } | |
111 | EdgePredicate m_edge_pred; | |
112 | VertexPredicate m_vertex_pred; | |
113 | const Graph* m_g; | |
114 | }; | |
115 | ||
116 | } // namespace detail | |
117 | ||
118 | ||
119 | //=========================================================================== | |
120 | // Filtered Graph | |
121 | ||
122 | struct filtered_graph_tag { }; | |
123 | ||
124 | // This base class is a stupid hack to change overload resolution | |
125 | // rules for the source and target functions so that they are a | |
126 | // worse match than the source and target functions defined for | |
127 | // pairs in graph_traits.hpp. I feel dirty. -JGS | |
128 | template <class G> | |
129 | struct filtered_graph_base { | |
130 | typedef graph_traits<G> Traits; | |
131 | typedef typename Traits::vertex_descriptor vertex_descriptor; | |
132 | typedef typename Traits::edge_descriptor edge_descriptor; | |
133 | filtered_graph_base(const G& g) : m_g(g) { } | |
134 | //protected: | |
135 | const G& m_g; | |
136 | }; | |
137 | ||
138 | template <typename Graph, | |
139 | typename EdgePredicate, | |
140 | typename VertexPredicate = keep_all> | |
141 | class filtered_graph : public filtered_graph_base<Graph> { | |
142 | typedef filtered_graph_base<Graph> Base; | |
143 | typedef graph_traits<Graph> Traits; | |
144 | typedef filtered_graph self; | |
145 | public: | |
146 | typedef Graph graph_type; | |
147 | typedef detail::out_edge_predicate<EdgePredicate, | |
148 | VertexPredicate, self> OutEdgePred; | |
149 | typedef detail::in_edge_predicate<EdgePredicate, | |
150 | VertexPredicate, self> InEdgePred; | |
151 | typedef detail::edge_predicate<EdgePredicate, | |
152 | VertexPredicate, self> EdgePred; | |
153 | ||
154 | // Constructors | |
155 | filtered_graph(const Graph& g, EdgePredicate ep) | |
156 | : Base(g), m_edge_pred(ep) { } | |
157 | ||
158 | filtered_graph(const Graph& g, EdgePredicate ep, VertexPredicate vp) | |
159 | : Base(g), m_edge_pred(ep), m_vertex_pred(vp) { } | |
160 | ||
161 | // Graph requirements | |
162 | typedef typename Traits::vertex_descriptor vertex_descriptor; | |
163 | typedef typename Traits::edge_descriptor edge_descriptor; | |
164 | typedef typename Traits::directed_category directed_category; | |
165 | typedef typename Traits::edge_parallel_category edge_parallel_category; | |
166 | typedef typename Traits::traversal_category traversal_category; | |
167 | ||
168 | // IncidenceGraph requirements | |
169 | typedef filter_iterator< | |
170 | OutEdgePred, typename Traits::out_edge_iterator | |
171 | > out_edge_iterator; | |
172 | ||
173 | typedef typename Traits::degree_size_type degree_size_type; | |
174 | ||
175 | // AdjacencyGraph requirements | |
176 | typedef typename adjacency_iterator_generator<self, | |
177 | vertex_descriptor, out_edge_iterator>::type adjacency_iterator; | |
178 | ||
179 | // BidirectionalGraph requirements | |
180 | typedef filter_iterator< | |
181 | InEdgePred, typename Traits::in_edge_iterator | |
182 | > in_edge_iterator; | |
183 | ||
184 | // VertexListGraph requirements | |
185 | typedef filter_iterator< | |
186 | VertexPredicate, typename Traits::vertex_iterator | |
187 | > vertex_iterator; | |
188 | typedef typename Traits::vertices_size_type vertices_size_type; | |
189 | ||
190 | // EdgeListGraph requirements | |
191 | typedef filter_iterator< | |
192 | EdgePred, typename Traits::edge_iterator | |
193 | > edge_iterator; | |
194 | typedef typename Traits::edges_size_type edges_size_type; | |
195 | ||
196 | typedef filtered_graph_tag graph_tag; | |
197 | ||
198 | // Bundled properties support | |
199 | template<typename Descriptor> | |
200 | typename graph::detail::bundled_result<Graph, Descriptor>::type& | |
201 | operator[](Descriptor x) | |
202 | { return const_cast<Graph&>(this->m_g)[x]; } | |
203 | ||
204 | template<typename Descriptor> | |
205 | typename graph::detail::bundled_result<Graph, Descriptor>::type const& | |
206 | operator[](Descriptor x) const | |
207 | { return this->m_g[x]; } | |
208 | ||
209 | static vertex_descriptor null_vertex() | |
210 | { | |
211 | return Traits::null_vertex(); | |
212 | } | |
213 | ||
214 | //private: | |
215 | EdgePredicate m_edge_pred; | |
216 | VertexPredicate m_vertex_pred; | |
217 | }; | |
218 | ||
219 | // Do not instantiate these unless needed | |
220 | template <typename Graph, | |
221 | typename EdgePredicate, | |
222 | typename VertexPredicate> | |
223 | struct vertex_property_type<filtered_graph<Graph, EdgePredicate, VertexPredicate> >: | |
224 | vertex_property_type<Graph> {}; | |
225 | ||
226 | template <typename Graph, | |
227 | typename EdgePredicate, | |
228 | typename VertexPredicate> | |
229 | struct edge_property_type<filtered_graph<Graph, EdgePredicate, VertexPredicate> >: | |
230 | edge_property_type<Graph> {}; | |
231 | ||
232 | template <typename Graph, | |
233 | typename EdgePredicate, | |
234 | typename VertexPredicate> | |
235 | struct graph_property_type<filtered_graph<Graph, EdgePredicate, VertexPredicate> >: | |
236 | graph_property_type<Graph> {}; | |
237 | ||
238 | template<typename Graph, typename EdgePredicate, typename VertexPredicate> | |
239 | struct vertex_bundle_type<filtered_graph<Graph, EdgePredicate, | |
240 | VertexPredicate> > | |
241 | : vertex_bundle_type<Graph> { }; | |
242 | ||
243 | template<typename Graph, typename EdgePredicate, typename VertexPredicate> | |
244 | struct edge_bundle_type<filtered_graph<Graph, EdgePredicate, | |
245 | VertexPredicate> > | |
246 | : edge_bundle_type<Graph> { }; | |
247 | ||
248 | template<typename Graph, typename EdgePredicate, typename VertexPredicate> | |
249 | struct graph_bundle_type<filtered_graph<Graph, EdgePredicate, | |
250 | VertexPredicate> > | |
251 | : graph_bundle_type<Graph> { }; | |
252 | ||
253 | //=========================================================================== | |
254 | // Non-member functions for the Filtered Edge Graph | |
255 | ||
256 | // Helper functions | |
257 | template <typename Graph, typename EdgePredicate> | |
258 | inline filtered_graph<Graph, EdgePredicate> | |
259 | make_filtered_graph(Graph& g, EdgePredicate ep) { | |
260 | return filtered_graph<Graph, EdgePredicate>(g, ep); | |
261 | } | |
262 | template <typename Graph, typename EdgePredicate, typename VertexPredicate> | |
263 | inline filtered_graph<Graph, EdgePredicate, VertexPredicate> | |
264 | make_filtered_graph(Graph& g, EdgePredicate ep, VertexPredicate vp) { | |
265 | return filtered_graph<Graph, EdgePredicate, VertexPredicate>(g, ep, vp); | |
266 | } | |
267 | ||
268 | template <typename Graph, typename EdgePredicate> | |
269 | inline filtered_graph<const Graph, EdgePredicate> | |
270 | make_filtered_graph(const Graph& g, EdgePredicate ep) { | |
271 | return filtered_graph<const Graph, EdgePredicate>(g, ep); | |
272 | } | |
273 | template <typename Graph, typename EdgePredicate, typename VertexPredicate> | |
274 | inline filtered_graph<const Graph, EdgePredicate, VertexPredicate> | |
275 | make_filtered_graph(const Graph& g, EdgePredicate ep, VertexPredicate vp) { | |
276 | return filtered_graph<const Graph, EdgePredicate, VertexPredicate>(g, ep, vp); | |
277 | } | |
278 | ||
279 | template <typename G, typename EP, typename VP> | |
280 | std::pair<typename filtered_graph<G, EP, VP>::vertex_iterator, | |
281 | typename filtered_graph<G, EP, VP>::vertex_iterator> | |
282 | vertices(const filtered_graph<G, EP, VP>& g) | |
283 | { | |
284 | typedef filtered_graph<G, EP, VP> Graph; | |
285 | typename graph_traits<G>::vertex_iterator f, l; | |
286 | boost::tie(f, l) = vertices(g.m_g); | |
287 | typedef typename Graph::vertex_iterator iter; | |
288 | return std::make_pair(iter(g.m_vertex_pred, f, l), | |
289 | iter(g.m_vertex_pred, l, l)); | |
290 | } | |
291 | ||
292 | template <typename G, typename EP, typename VP> | |
293 | std::pair<typename filtered_graph<G, EP, VP>::edge_iterator, | |
294 | typename filtered_graph<G, EP, VP>::edge_iterator> | |
295 | edges(const filtered_graph<G, EP, VP>& g) | |
296 | { | |
297 | typedef filtered_graph<G, EP, VP> Graph; | |
298 | typename Graph::EdgePred pred(g.m_edge_pred, g.m_vertex_pred, g); | |
299 | typename graph_traits<G>::edge_iterator f, l; | |
300 | boost::tie(f, l) = edges(g.m_g); | |
301 | typedef typename Graph::edge_iterator iter; | |
302 | return std::make_pair(iter(pred, f, l), iter(pred, l, l)); | |
303 | } | |
304 | ||
305 | // An alternative for num_vertices() and num_edges() would be to | |
306 | // count the number in the filtered graph. This is problematic | |
307 | // because of the interaction with the vertex indices... they would | |
308 | // no longer go from 0 to num_vertices(), which would cause trouble | |
309 | // for algorithms allocating property storage in an array. We could | |
310 | // try to create a mapping to new recalibrated indices, but I don't | |
311 | // see an efficient way to do this. | |
312 | // | |
313 | // However, the current solution is still unsatisfactory because | |
314 | // the following semantic constraints no longer hold: | |
315 | // boost::tie(vi, viend) = vertices(g); | |
316 | // assert(std::distance(vi, viend) == num_vertices(g)); | |
317 | ||
318 | template <typename G, typename EP, typename VP> | |
319 | typename filtered_graph<G, EP, VP>::vertices_size_type | |
320 | num_vertices(const filtered_graph<G, EP, VP>& g) { | |
321 | return num_vertices(g.m_g); | |
322 | } | |
323 | ||
324 | template <typename G, typename EP, typename VP> | |
325 | typename filtered_graph<G, EP, VP>::edges_size_type | |
326 | num_edges(const filtered_graph<G, EP, VP>& g) { | |
327 | return num_edges(g.m_g); | |
328 | } | |
329 | ||
330 | template <typename G> | |
331 | typename filtered_graph_base<G>::vertex_descriptor | |
332 | source(typename filtered_graph_base<G>::edge_descriptor e, | |
333 | const filtered_graph_base<G>& g) | |
334 | { | |
335 | return source(e, g.m_g); | |
336 | } | |
337 | ||
338 | template <typename G> | |
339 | typename filtered_graph_base<G>::vertex_descriptor | |
340 | target(typename filtered_graph_base<G>::edge_descriptor e, | |
341 | const filtered_graph_base<G>& g) | |
342 | { | |
343 | return target(e, g.m_g); | |
344 | } | |
345 | ||
346 | template <typename G, typename EP, typename VP> | |
347 | std::pair<typename filtered_graph<G, EP, VP>::out_edge_iterator, | |
348 | typename filtered_graph<G, EP, VP>::out_edge_iterator> | |
349 | out_edges(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
350 | const filtered_graph<G, EP, VP>& g) | |
351 | { | |
352 | typedef filtered_graph<G, EP, VP> Graph; | |
353 | typename Graph::OutEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g); | |
354 | typedef typename Graph::out_edge_iterator iter; | |
355 | typename graph_traits<G>::out_edge_iterator f, l; | |
356 | boost::tie(f, l) = out_edges(u, g.m_g); | |
357 | return std::make_pair(iter(pred, f, l), iter(pred, l, l)); | |
358 | } | |
359 | ||
360 | template <typename G, typename EP, typename VP> | |
361 | typename filtered_graph<G, EP, VP>::degree_size_type | |
362 | out_degree(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
363 | const filtered_graph<G, EP, VP>& g) | |
364 | { | |
365 | typename filtered_graph<G, EP, VP>::degree_size_type n = 0; | |
366 | typename filtered_graph<G, EP, VP>::out_edge_iterator f, l; | |
367 | for (boost::tie(f, l) = out_edges(u, g); f != l; ++f) | |
368 | ++n; | |
369 | return n; | |
370 | } | |
371 | ||
372 | template <typename G, typename EP, typename VP> | |
373 | std::pair<typename filtered_graph<G, EP, VP>::adjacency_iterator, | |
374 | typename filtered_graph<G, EP, VP>::adjacency_iterator> | |
375 | adjacent_vertices(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
376 | const filtered_graph<G, EP, VP>& g) | |
377 | { | |
378 | typedef filtered_graph<G, EP, VP> Graph; | |
379 | typedef typename Graph::adjacency_iterator adjacency_iterator; | |
380 | typename Graph::out_edge_iterator f, l; | |
381 | boost::tie(f, l) = out_edges(u, g); | |
382 | return std::make_pair(adjacency_iterator(f, const_cast<Graph*>(&g)), | |
383 | adjacency_iterator(l, const_cast<Graph*>(&g))); | |
384 | } | |
385 | ||
386 | template <typename G, typename EP, typename VP> | |
387 | std::pair<typename filtered_graph<G, EP, VP>::in_edge_iterator, | |
388 | typename filtered_graph<G, EP, VP>::in_edge_iterator> | |
389 | in_edges(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
390 | const filtered_graph<G, EP, VP>& g) | |
391 | { | |
392 | typedef filtered_graph<G, EP, VP> Graph; | |
393 | typename Graph::InEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g); | |
394 | typedef typename Graph::in_edge_iterator iter; | |
395 | typename graph_traits<G>::in_edge_iterator f, l; | |
396 | boost::tie(f, l) = in_edges(u, g.m_g); | |
397 | return std::make_pair(iter(pred, f, l), iter(pred, l, l)); | |
398 | } | |
399 | ||
400 | template <typename G, typename EP, typename VP> | |
401 | typename filtered_graph<G, EP, VP>::degree_size_type | |
402 | in_degree(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
403 | const filtered_graph<G, EP, VP>& g) | |
404 | { | |
405 | typename filtered_graph<G, EP, VP>::degree_size_type n = 0; | |
406 | typename filtered_graph<G, EP, VP>::in_edge_iterator f, l; | |
407 | for (boost::tie(f, l) = in_edges(u, g); f != l; ++f) | |
408 | ++n; | |
409 | return n; | |
410 | } | |
411 | ||
412 | template <typename G, typename EP, typename VP> | |
413 | typename enable_if<typename is_directed_graph<G>::type, | |
414 | typename filtered_graph<G, EP, VP>::degree_size_type | |
415 | >::type | |
416 | degree(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
417 | const filtered_graph<G, EP, VP>& g) | |
418 | { | |
419 | return out_degree(u, g) + in_degree(u, g); | |
420 | } | |
421 | ||
422 | template <typename G, typename EP, typename VP> | |
423 | typename disable_if<typename is_directed_graph<G>::type, | |
424 | typename filtered_graph<G, EP, VP>::degree_size_type | |
425 | >::type | |
426 | degree(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
427 | const filtered_graph<G, EP, VP>& g) | |
428 | { | |
429 | return out_degree(u, g); | |
430 | } | |
431 | ||
432 | template <typename G, typename EP, typename VP> | |
433 | std::pair<typename filtered_graph<G, EP, VP>::edge_descriptor, bool> | |
434 | edge(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
435 | typename filtered_graph<G, EP, VP>::vertex_descriptor v, | |
436 | const filtered_graph<G, EP, VP>& g) | |
437 | { | |
438 | typename graph_traits<G>::edge_descriptor e; | |
439 | bool exists; | |
440 | boost::tie(e, exists) = edge(u, v, g.m_g); | |
441 | return std::make_pair(e, exists && g.m_edge_pred(e)); | |
442 | } | |
443 | ||
444 | template <typename G, typename EP, typename VP> | |
445 | std::pair<typename filtered_graph<G, EP, VP>::out_edge_iterator, | |
446 | typename filtered_graph<G, EP, VP>::out_edge_iterator> | |
447 | edge_range(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
448 | typename filtered_graph<G, EP, VP>::vertex_descriptor v, | |
449 | const filtered_graph<G, EP, VP>& g) | |
450 | { | |
451 | typedef filtered_graph<G, EP, VP> Graph; | |
452 | typename Graph::OutEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g); | |
453 | typedef typename Graph::out_edge_iterator iter; | |
454 | typename graph_traits<G>::out_edge_iterator f, l; | |
455 | boost::tie(f, l) = edge_range(u, v, g.m_g); | |
456 | return std::make_pair(iter(pred, f, l), iter(pred, l, l)); | |
457 | } | |
458 | ||
459 | ||
460 | //=========================================================================== | |
461 | // Property map | |
462 | ||
463 | template <typename G, typename EP, typename VP, typename Property> | |
464 | struct property_map<filtered_graph<G, EP, VP>, Property> | |
465 | : property_map<G, Property> {}; | |
466 | ||
467 | template <typename G, typename EP, typename VP, typename Property> | |
468 | typename property_map<G, Property>::type | |
469 | get(Property p, filtered_graph<G, EP, VP>& g) | |
470 | { | |
471 | return get(p, const_cast<G&>(g.m_g)); | |
472 | } | |
473 | ||
474 | template <typename G, typename EP, typename VP,typename Property> | |
475 | typename property_map<G, Property>::const_type | |
476 | get(Property p, const filtered_graph<G, EP, VP>& g) | |
477 | { | |
478 | return get(p, (const G&)g.m_g); | |
479 | } | |
480 | ||
481 | template <typename G, typename EP, typename VP, typename Property, | |
482 | typename Key> | |
483 | typename property_map_value<G, Property>::type | |
484 | get(Property p, const filtered_graph<G, EP, VP>& g, const Key& k) | |
485 | { | |
486 | return get(p, (const G&)g.m_g, k); | |
487 | } | |
488 | ||
489 | template <typename G, typename EP, typename VP, typename Property, | |
490 | typename Key, typename Value> | |
491 | void | |
492 | put(Property p, const filtered_graph<G, EP, VP>& g, const Key& k, | |
493 | const Value& val) | |
494 | { | |
495 | put(p, const_cast<G&>(g.m_g), k, val); | |
496 | } | |
497 | ||
498 | //=========================================================================== | |
499 | // Some filtered subgraph specializations | |
500 | ||
501 | template <typename Graph, typename Set> | |
502 | struct vertex_subset_filter { | |
503 | typedef filtered_graph<Graph, keep_all, is_in_subset<Set> > type; | |
504 | }; | |
505 | template <typename Graph, typename Set> | |
506 | inline typename vertex_subset_filter<Graph, Set>::type | |
507 | make_vertex_subset_filter(Graph& g, const Set& s) { | |
508 | typedef typename vertex_subset_filter<Graph, Set>::type Filter; | |
509 | is_in_subset<Set> p(s); | |
510 | return Filter(g, keep_all(), p); | |
511 | } | |
512 | ||
513 | // This is misspelled, but present for backwards compatibility; new code | |
514 | // should use the version below that has the correct spelling. | |
515 | template <typename Graph, typename Set> | |
516 | struct vertex_subset_compliment_filter { | |
517 | typedef filtered_graph<Graph, keep_all, is_not_in_subset<Set> > type; | |
518 | }; | |
519 | template <typename Graph, typename Set> | |
520 | inline typename vertex_subset_compliment_filter<Graph, Set>::type | |
521 | make_vertex_subset_compliment_filter(Graph& g, const Set& s) { | |
522 | typedef typename vertex_subset_compliment_filter<Graph, Set>::type Filter; | |
523 | is_not_in_subset<Set> p(s); | |
524 | return Filter(g, keep_all(), p); | |
525 | } | |
526 | ||
527 | template <typename Graph, typename Set> | |
528 | struct vertex_subset_complement_filter { | |
529 | typedef filtered_graph<Graph, keep_all, is_not_in_subset<Set> > type; | |
530 | }; | |
531 | template <typename Graph, typename Set> | |
532 | inline typename vertex_subset_complement_filter<Graph, Set>::type | |
533 | make_vertex_subset_complement_filter(Graph& g, const Set& s) { | |
534 | typedef typename vertex_subset_complement_filter<Graph, Set>::type Filter; | |
535 | is_not_in_subset<Set> p(s); | |
536 | return Filter(g, keep_all(), p); | |
537 | } | |
538 | ||
539 | // Filter that uses a property map whose value_type is a boolean | |
540 | template <typename PropertyMap> | |
541 | struct property_map_filter { | |
542 | ||
543 | property_map_filter() { } | |
544 | ||
545 | property_map_filter(const PropertyMap& property_map) : | |
546 | m_property_map(property_map) { } | |
547 | ||
548 | template <typename Key> | |
549 | bool operator()(const Key& key) const { | |
550 | return (get(m_property_map, key)); | |
551 | } | |
552 | ||
553 | private : | |
554 | PropertyMap m_property_map; | |
555 | }; | |
556 | ||
557 | } // namespace boost | |
558 | ||
559 | ||
560 | #endif // BOOST_FILTERED_GRAPH_HPP |