git.sesse.net Git - casparcg/blob - dependencies64/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/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   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