← Back to branch summary

~twpol/dcplusplus/trunk

« back to all changes in this revision

Viewing changes to boost/boost/graph/filtered_graph.hpp

  • Committer: James Ross
  • Date: 2010-07-05 00:03:18 UTC
  • mfrom: (1524.1.650 dcplusplus)
  • Revision ID: silver@warwickcompsoc.co.uk-20100705000318-awwqm8ocpp5m47yz
Merged to trunk.

Show diffs side-by-side

added added

removed removed

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