source: NonGTP/Boost/boost/graph/filtered_graph.hpp @ 857

Revision 857, 18.0 KB checked in by igarcia, 18 years ago (diff)
Line 
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
18namespace 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    //private:
213    EdgePredicate m_edge_pred;
214    VertexPredicate m_vertex_pred;
215  };
216
217#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
218  template<typename Graph, typename EdgePredicate, typename VertexPredicate>
219  struct vertex_bundle_type<filtered_graph<Graph, EdgePredicate,
220                                           VertexPredicate> >
221    : vertex_bundle_type<Graph> { };
222
223  template<typename Graph, typename EdgePredicate, typename VertexPredicate>
224  struct edge_bundle_type<filtered_graph<Graph, EdgePredicate,
225                                         VertexPredicate> >
226    : edge_bundle_type<Graph> { };
227#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
228
229  //===========================================================================
230  // Non-member functions for the Filtered Edge Graph
231
232  // Helper functions
233  template <typename Graph, typename EdgePredicate>
234  inline filtered_graph<Graph, EdgePredicate>
235  make_filtered_graph(Graph& g, EdgePredicate ep) {
236    return filtered_graph<Graph, EdgePredicate>(g, ep);
237  }
238  template <typename Graph, typename EdgePredicate, typename VertexPredicate>
239  inline filtered_graph<Graph, EdgePredicate, VertexPredicate>
240  make_filtered_graph(Graph& g, EdgePredicate ep, VertexPredicate vp) {
241    return filtered_graph<Graph, EdgePredicate, VertexPredicate>(g, ep, vp);
242  }
243
244  template <typename G, typename EP, typename VP>
245  std::pair<typename filtered_graph<G, EP, VP>::vertex_iterator,
246            typename filtered_graph<G, EP, VP>::vertex_iterator>
247  vertices(const filtered_graph<G, EP, VP>& g)
248  {
249    typedef filtered_graph<G, EP, VP> Graph;   
250    typename graph_traits<G>::vertex_iterator f, l;
251    tie(f, l) = vertices(g.m_g);
252    typedef typename Graph::vertex_iterator iter;
253    return std::make_pair(iter(g.m_vertex_pred, f, l),
254                          iter(g.m_vertex_pred, l, l));
255  }
256
257  template <typename G, typename EP, typename VP>
258  std::pair<typename filtered_graph<G, EP, VP>::edge_iterator,
259            typename filtered_graph<G, EP, VP>::edge_iterator>
260  edges(const filtered_graph<G, EP, VP>& g)
261  {
262    typedef filtered_graph<G, EP, VP> Graph;
263    typename Graph::EdgePred pred(g.m_edge_pred, g.m_vertex_pred, g);
264    typename graph_traits<G>::edge_iterator f, l;
265    tie(f, l) = edges(g.m_g);
266    typedef typename Graph::edge_iterator iter;
267    return std::make_pair(iter(pred, f, l), iter(pred, l, l));
268  }
269
270  // An alternative for num_vertices() and num_edges() would be to
271  // count the number in the filtered graph. This is problematic
272  // because of the interaction with the vertex indices...  they would
273  // no longer go from 0 to num_vertices(), which would cause trouble
274  // for algorithms allocating property storage in an array. We could
275  // try to create a mapping to new recalibrated indices, but I don't
276  // see an efficient way to do this.
277  //
278  // However, the current solution is still unsatisfactory because
279  // the following semantic constraints no longer hold:
280  // tie(vi, viend) = vertices(g);
281  // assert(std::distance(vi, viend) == num_vertices(g));
282
283  template <typename G, typename EP, typename VP> 
284  typename filtered_graph<G, EP, VP>::vertices_size_type
285  num_vertices(const filtered_graph<G, EP, VP>& g) {
286    return num_vertices(g.m_g);
287  }
288
289  template <typename G, typename EP, typename VP> 
290  typename filtered_graph<G, EP, VP>::edges_size_type
291  num_edges(const filtered_graph<G, EP, VP>& g) {
292    return num_edges(g.m_g);
293  }
294 
295  template <typename G>
296  typename filtered_graph_base<G>::vertex_descriptor
297  source(typename filtered_graph_base<G>::edge_descriptor e,
298         const filtered_graph_base<G>& g)
299  {
300    return source(e, g.m_g);
301  }
302
303  template <typename G>
304  typename filtered_graph_base<G>::vertex_descriptor
305  target(typename filtered_graph_base<G>::edge_descriptor e,
306         const filtered_graph_base<G>& g)
307  {
308    return target(e, g.m_g);
309  }
310
311  template <typename G, typename EP, typename VP>
312  std::pair<typename filtered_graph<G, EP, VP>::out_edge_iterator,
313            typename filtered_graph<G, EP, VP>::out_edge_iterator>
314  out_edges(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
315            const filtered_graph<G, EP, VP>& g)
316  {
317    typedef filtered_graph<G, EP, VP> Graph;
318    typename Graph::OutEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g);
319    typedef typename Graph::out_edge_iterator iter;
320    typename graph_traits<G>::out_edge_iterator f, l;
321    tie(f, l) = out_edges(u, g.m_g);
322    return std::make_pair(iter(pred, f, l), iter(pred, l, l));
323  }
324
325  template <typename G, typename EP, typename VP>
326  typename filtered_graph<G, EP, VP>::degree_size_type
327  out_degree(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
328             const filtered_graph<G, EP, VP>& g)
329  {
330    typename filtered_graph<G, EP, VP>::degree_size_type n = 0;
331    typename filtered_graph<G, EP, VP>::out_edge_iterator f, l;
332    for (tie(f, l) = out_edges(u, g); f != l; ++f)
333      ++n;
334    return n;
335  }
336
337  template <typename G, typename EP, typename VP>
338  std::pair<typename filtered_graph<G, EP, VP>::adjacency_iterator,
339            typename filtered_graph<G, EP, VP>::adjacency_iterator>
340  adjacent_vertices(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
341                    const filtered_graph<G, EP, VP>& g)
342  {
343    typedef filtered_graph<G, EP, VP> Graph;
344    typedef typename Graph::adjacency_iterator adjacency_iterator;
345    typename Graph::out_edge_iterator f, l;
346    tie(f, l) = out_edges(u, g);
347    return std::make_pair(adjacency_iterator(f, const_cast<Graph*>(&g)),
348                          adjacency_iterator(l, const_cast<Graph*>(&g)));
349  }
350 
351  template <typename G, typename EP, typename VP>
352  std::pair<typename filtered_graph<G, EP, VP>::in_edge_iterator,
353            typename filtered_graph<G, EP, VP>::in_edge_iterator>
354  in_edges(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
355            const filtered_graph<G, EP, VP>& g)
356  {
357    typedef filtered_graph<G, EP, VP> Graph;
358    typename Graph::InEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g);
359    typedef typename Graph::in_edge_iterator iter;
360    typename graph_traits<G>::in_edge_iterator f, l;
361    tie(f, l) = in_edges(u, g.m_g);
362    return std::make_pair(iter(pred, f, l), iter(pred, l, l));
363  }
364
365  template <typename G, typename EP, typename VP>
366  typename filtered_graph<G, EP, VP>::degree_size_type
367  in_degree(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
368             const filtered_graph<G, EP, VP>& g)
369  {
370    typename filtered_graph<G, EP, VP>::degree_size_type n = 0;
371    typename filtered_graph<G, EP, VP>::in_edge_iterator f, l;
372    for (tie(f, l) = in_edges(u, g); f != l; ++f)
373      ++n;
374    return n;
375  }
376
377  template <typename G, typename EP, typename VP>
378  std::pair<typename filtered_graph<G, EP, VP>::edge_descriptor, bool>
379  edge(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
380       typename filtered_graph<G, EP, VP>::vertex_descriptor v,
381       const filtered_graph<G, EP, VP>& g)
382  {
383    typename graph_traits<G>::edge_descriptor e;
384    bool exists;
385    tie(e, exists) = edge(u, v, g.m_g);
386    return std::make_pair(e, exists && g.m_edge_pred(e));
387  }
388
389  template <typename G, typename EP, typename VP>
390  std::pair<typename filtered_graph<G, EP, VP>::out_edge_iterator,
391            typename filtered_graph<G, EP, VP>::out_edge_iterator>
392  edge_range(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
393             typename filtered_graph<G, EP, VP>::vertex_descriptor v,
394             const filtered_graph<G, EP, VP>& g)
395  {
396    typedef filtered_graph<G, EP, VP> Graph;
397    typename Graph::OutEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g);
398    typedef typename Graph::out_edge_iterator iter;
399    typename graph_traits<G>::out_edge_iterator f, l;
400    tie(f, l) = edge_range(u, v, g.m_g);
401    return std::make_pair(iter(pred, f, l), iter(pred, l, l));
402  }
403
404
405  //===========================================================================
406  // Property map
407
408  namespace detail {
409    struct filtered_graph_property_selector {
410      template <class FilteredGraph, class Property, class Tag>
411      struct bind_ {
412        typedef typename FilteredGraph::graph_type Graph;
413        typedef property_map<Graph, Tag> Map;
414        typedef typename Map::type type;
415        typedef typename Map::const_type const_type;
416      };
417    };   
418  } // namespace detail
419
420  template <> 
421  struct vertex_property_selector<filtered_graph_tag> {
422    typedef detail::filtered_graph_property_selector type;
423  };
424  template <> 
425  struct edge_property_selector<filtered_graph_tag> {
426    typedef detail::filtered_graph_property_selector type;
427  };
428
429  template <typename G, typename EP, typename VP, typename Property>
430  typename property_map<G, Property>::type
431  get(Property p, filtered_graph<G, EP, VP>& g)
432  {
433    return get(p, const_cast<G&>(g.m_g));
434  }
435
436  template <typename G, typename EP, typename VP,typename Property>
437  typename property_map<G, Property>::const_type
438  get(Property p, const filtered_graph<G, EP, VP>& g)
439  {
440    return get(p, (const G&)g.m_g);
441  }
442
443  template <typename G, typename EP, typename VP, typename Property,
444            typename Key>
445  typename property_map_value<G, Property>::type
446  get(Property p, const filtered_graph<G, EP, VP>& g, const Key& k)
447  {
448    return get(p, (const G&)g.m_g, k);
449  }
450
451  template <typename G, typename EP, typename VP, typename Property,
452            typename Key, typename Value>
453  void
454  put(Property p, const filtered_graph<G, EP, VP>& g, const Key& k,
455      const Value& val)
456  {
457    put(p, const_cast<G&>(g.m_g), k, val);
458  }
459
460  //===========================================================================
461  // Some filtered subgraph specializations
462
463  template <typename Graph, typename Set>
464  struct vertex_subset_filter {
465    typedef filtered_graph<Graph, keep_all, is_in_subset<Set> > type;
466  };
467  template <typename Graph, typename Set>
468  inline typename vertex_subset_filter<Graph, Set>::type
469  make_vertex_subset_filter(Graph& g, const Set& s) {
470    typedef typename vertex_subset_filter<Graph, Set>::type Filter;
471    is_in_subset<Set> p(s);
472    return Filter(g, keep_all(), p);
473  }
474
475  template <typename Graph, typename Set>
476  struct vertex_subset_compliment_filter {
477    typedef filtered_graph<Graph, keep_all, is_not_in_subset<Set> > type;
478  };
479  template <typename Graph, typename Set>
480  inline typename vertex_subset_compliment_filter<Graph, Set>::type
481  make_vertex_subset_compliment_filter(Graph& g, const Set& s) {
482    typedef typename vertex_subset_compliment_filter<Graph, Set>::type Filter;
483    is_not_in_subset<Set> p(s);
484    return Filter(g, keep_all(), p);
485  }
486
487
488} // namespace boost
489
490
491#endif // BOOST_FILTERED_GRAPH_HPP
Note: See TracBrowser for help on using the repository browser.