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
19namespace 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 std::pair<typename filtered_graph<G, EP, VP>::edge_descriptor, bool>
414 edge(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
415 typename filtered_graph<G, EP, VP>::vertex_descriptor v,
416 const filtered_graph<G, EP, VP>& g)
417 {
418 typename graph_traits<G>::edge_descriptor e;
419 bool exists;
420 boost::tie(e, exists) = edge(u, v, g.m_g);
421 return std::make_pair(e, exists && g.m_edge_pred(e));
422 }
423
424 template <typename G, typename EP, typename VP>
425 std::pair<typename filtered_graph<G, EP, VP>::out_edge_iterator,
426 typename filtered_graph<G, EP, VP>::out_edge_iterator>
427 edge_range(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
428 typename filtered_graph<G, EP, VP>::vertex_descriptor v,
429 const filtered_graph<G, EP, VP>& g)
430 {
431 typedef filtered_graph<G, EP, VP> Graph;
432 typename Graph::OutEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g);
433 typedef typename Graph::out_edge_iterator iter;
434 typename graph_traits<G>::out_edge_iterator f, l;
435 boost::tie(f, l) = edge_range(u, v, g.m_g);
436 return std::make_pair(iter(pred, f, l), iter(pred, l, l));
437 }
438
439
440 //===========================================================================
441 // Property map
442
443 template <typename G, typename EP, typename VP, typename Property>
444 struct property_map<filtered_graph<G, EP, VP>, Property>
445 : property_map<G, Property> {};
446
447 template <typename G, typename EP, typename VP, typename Property>
448 typename property_map<G, Property>::type
449 get(Property p, filtered_graph<G, EP, VP>& g)
450 {
451 return get(p, const_cast<G&>(g.m_g));
452 }
453
454 template <typename G, typename EP, typename VP,typename Property>
455 typename property_map<G, Property>::const_type
456 get(Property p, const filtered_graph<G, EP, VP>& g)
457 {
458 return get(p, (const G&)g.m_g);
459 }
460
461 template <typename G, typename EP, typename VP, typename Property,
462 typename Key>
463 typename property_map_value<G, Property>::type
464 get(Property p, const filtered_graph<G, EP, VP>& g, const Key& k)
465 {
466 return get(p, (const G&)g.m_g, k);
467 }
468
469 template <typename G, typename EP, typename VP, typename Property,
470 typename Key, typename Value>
471 void
472 put(Property p, const filtered_graph<G, EP, VP>& g, const Key& k,
473 const Value& val)
474 {
475 put(p, const_cast<G&>(g.m_g), k, val);
476 }
477
478 //===========================================================================
479 // Some filtered subgraph specializations
480
481 template <typename Graph, typename Set>
482 struct vertex_subset_filter {
483 typedef filtered_graph<Graph, keep_all, is_in_subset<Set> > type;
484 };
485 template <typename Graph, typename Set>
486 inline typename vertex_subset_filter<Graph, Set>::type
487 make_vertex_subset_filter(Graph& g, const Set& s) {
488 typedef typename vertex_subset_filter<Graph, Set>::type Filter;
489 is_in_subset<Set> p(s);
490 return Filter(g, keep_all(), p);
491 }
492
493 // This is misspelled, but present for backwards compatibility; new code
494 // should use the version below that has the correct spelling.
495 template <typename Graph, typename Set>
496 struct vertex_subset_compliment_filter {
497 typedef filtered_graph<Graph, keep_all, is_not_in_subset<Set> > type;
498 };
499 template <typename Graph, typename Set>
500 inline typename vertex_subset_compliment_filter<Graph, Set>::type
501 make_vertex_subset_compliment_filter(Graph& g, const Set& s) {
502 typedef typename vertex_subset_compliment_filter<Graph, Set>::type Filter;
503 is_not_in_subset<Set> p(s);
504 return Filter(g, keep_all(), p);
505 }
506
507 template <typename Graph, typename Set>
508 struct vertex_subset_complement_filter {
509 typedef filtered_graph<Graph, keep_all, is_not_in_subset<Set> > type;
510 };
511 template <typename Graph, typename Set>
512 inline typename vertex_subset_complement_filter<Graph, Set>::type
513 make_vertex_subset_complement_filter(Graph& g, const Set& s) {
514 typedef typename vertex_subset_complement_filter<Graph, Set>::type Filter;
515 is_not_in_subset<Set> p(s);
516 return Filter(g, keep_all(), p);
517 }
518
519 // Filter that uses a property map whose value_type is a boolean
520 template <typename PropertyMap>
521 struct property_map_filter {
522
523 property_map_filter() { }
524
525 property_map_filter(const PropertyMap& property_map) :
526 m_property_map(property_map) { }
527
528 template <typename Key>
529 bool operator()(const Key& key) const {
530 return (get(m_property_map, key));
531 }
532
533 private :
534 PropertyMap m_property_map;
535 };
536
537} // namespace boost
538
539
540#endif // BOOST_FILTERED_GRAPH_HPP
541

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