boost/graph/filtered_graph.hpp

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009
0010 #ifndef BOOST_FILTERED_GRAPH_HPP
0011 #define BOOST_FILTERED_GRAPH_HPP
0012
0013 #include <boost/graph/graph_traits.hpp>
0014 #include <boost/graph/properties.hpp>
0015 #include <boost/graph/adjacency_iterator.hpp>
0016 #include <boost/graph/detail/set_adaptor.hpp>
0017 #include <boost/iterator/filter_iterator.hpp>
0018
0019 namespace boost
0020 {
0021
0022 //=========================================================================
0023 // Some predicate classes.
0024
0025 struct keep_all
0026 {
0027     template < typename T > bool operator()(const T&) const { return true; }
0028 };
0029
0030 // Keep residual edges (used in maximum-flow algorithms).
0031 template < typename ResidualCapacityEdgeMap > struct is_residual_edge
0032 {
0033     is_residual_edge() {}
0034     is_residual_edge(ResidualCapacityEdgeMap rcap) : m_rcap(rcap) {}
0035     template < typename Edge > bool operator()(const Edge& e) const
0036     {
0037         return 0 < get(m_rcap, e);
0038     }
0039     ResidualCapacityEdgeMap m_rcap;
0040 };
0041
0042 template < typename Set > struct is_in_subset
0043 {
0044     is_in_subset() : m_s(0) {}
0045     is_in_subset(const Set& s) : m_s(&s) {}
0046
0047     template < typename Elt > bool operator()(const Elt& x) const
0048     {
0049         return set_contains(*m_s, x);
0050     }
0051     const Set* m_s;
0052 };
0053
0054 template < typename Set > struct is_not_in_subset
0055 {
0056     is_not_in_subset() : m_s(0) {}
0057     is_not_in_subset(const Set& s) : m_s(&s) {}
0058
0059     template < typename Elt > bool operator()(const Elt& x) const
0060     {
0061         return !set_contains(*m_s, x);
0062     }
0063     const Set* m_s;
0064 };
0065
0066 namespace detail
0067 {
0068
0069     template < typename EdgePredicate, typename VertexPredicate,
0070         typename Graph >
0071     struct out_edge_predicate
0072     {
0073         out_edge_predicate() {}
0074         out_edge_predicate(EdgePredicate ep, VertexPredicate vp, const Graph& g)
0075         : m_edge_pred(ep), m_vertex_pred(vp), m_g(&g)
0076         {
0077         }
0078
0079         template < typename Edge > bool operator()(const Edge& e) const
0080         {
0081             return m_edge_pred(e) && m_vertex_pred(target(e, *m_g));
0082         }
0083         EdgePredicate m_edge_pred;
0084         VertexPredicate m_vertex_pred;
0085         const Graph* m_g;
0086     };
0087
0088     template < typename EdgePredicate, typename VertexPredicate,
0089         typename Graph >
0090     struct in_edge_predicate
0091     {
0092         in_edge_predicate() {}
0093         in_edge_predicate(EdgePredicate ep, VertexPredicate vp, const Graph& g)
0094         : m_edge_pred(ep), m_vertex_pred(vp), m_g(&g)
0095         {
0096         }
0097
0098         template < typename Edge > bool operator()(const Edge& e) const
0099         {
0100             return m_edge_pred(e) && m_vertex_pred(source(e, *m_g));
0101         }
0102         EdgePredicate m_edge_pred;
0103         VertexPredicate m_vertex_pred;
0104         const Graph* m_g;
0105     };
0106
0107     template < typename EdgePredicate, typename VertexPredicate,
0108         typename Graph >
0109     struct edge_predicate
0110     {
0111         edge_predicate() {}
0112         edge_predicate(EdgePredicate ep, VertexPredicate vp, const Graph& g)
0113         : m_edge_pred(ep), m_vertex_pred(vp), m_g(&g)
0114         {
0115         }
0116
0117         template < typename Edge > bool operator()(const Edge& e) const
0118         {
0119             return m_edge_pred(e) && m_vertex_pred(source(e, *m_g))
0120                 && m_vertex_pred(target(e, *m_g));
0121         }
0122         EdgePredicate m_edge_pred;
0123         VertexPredicate m_vertex_pred;
0124         const Graph* m_g;
0125     };
0126
0127 } // namespace detail
0128
0129 //===========================================================================
0130 // Filtered Graph
0131
0132 struct filtered_graph_tag
0133 {
0134 };
0135
0136 // This base class is a stupid hack to change overload resolution
0137 // rules for the source and target functions so that they are a
0138 // worse match than the source and target functions defined for
0139 // pairs in graph_traits.hpp. I feel dirty. -JGS
0140 template < class G > struct filtered_graph_base
0141 {
0142     typedef graph_traits< G > Traits;
0143     typedef typename Traits::vertex_descriptor vertex_descriptor;
0144     typedef typename Traits::edge_descriptor edge_descriptor;
0145     filtered_graph_base(const G& g) : m_g(g) {}
0146     // protected:
0147     const G& m_g;
0148 };
0149
0150 template < typename Graph, typename EdgePredicate,
0151     typename VertexPredicate = keep_all >
0152 class filtered_graph : public filtered_graph_base< Graph >
0153 {
0154     typedef filtered_graph_base< Graph > Base;
0155     typedef graph_traits< Graph > Traits;
0156     typedef filtered_graph self;
0157
0158 public:
0159     typedef Graph graph_type;
0160     typedef detail::out_edge_predicate< EdgePredicate, VertexPredicate, self >
0161         OutEdgePred;
0162     typedef detail::in_edge_predicate< EdgePredicate, VertexPredicate, self >
0163         InEdgePred;
0164     typedef detail::edge_predicate< EdgePredicate, VertexPredicate, self >
0165         EdgePred;
0166
0167     // Constructors
0168     filtered_graph(const Graph& g, EdgePredicate ep) : Base(g), m_edge_pred(ep)
0169     {
0170     }
0171
0172     filtered_graph(const Graph& g, EdgePredicate ep, VertexPredicate vp)
0173     : Base(g), m_edge_pred(ep), m_vertex_pred(vp)
0174     {
0175     }
0176
0177     // Graph requirements
0178     typedef typename Traits::vertex_descriptor vertex_descriptor;
0179     typedef typename Traits::edge_descriptor edge_descriptor;
0180     typedef typename Traits::directed_category directed_category;
0181     typedef typename Traits::edge_parallel_category edge_parallel_category;
0182     typedef typename Traits::traversal_category traversal_category;
0183
0184     // IncidenceGraph requirements
0185     typedef filter_iterator< OutEdgePred, typename Traits::out_edge_iterator >
0186         out_edge_iterator;
0187
0188     typedef typename Traits::degree_size_type degree_size_type;
0189
0190     // AdjacencyGraph requirements
0191     typedef typename adjacency_iterator_generator< self, vertex_descriptor,
0192         out_edge_iterator >::type adjacency_iterator;
0193
0194     // BidirectionalGraph requirements
0195     typedef filter_iterator< InEdgePred, typename Traits::in_edge_iterator >
0196         in_edge_iterator;
0197
0198     // VertexListGraph requirements
0199     typedef filter_iterator< VertexPredicate, typename Traits::vertex_iterator >
0200         vertex_iterator;
0201     typedef typename Traits::vertices_size_type vertices_size_type;
0202
0203     // EdgeListGraph requirements
0204     typedef filter_iterator< EdgePred, typename Traits::edge_iterator >
0205         edge_iterator;
0206     typedef typename Traits::edges_size_type edges_size_type;
0207
0208     typedef filtered_graph_tag graph_tag;
0209
0210     // Bundled properties support
0211     template < typename Descriptor >
0212     typename graph::detail::bundled_result< Graph, Descriptor >::type&
0213     operator[](Descriptor x)
0214     {
0215         return const_cast< Graph& >(this->m_g)[x];
0216     }
0217
0218     template < typename Descriptor >
0219     typename graph::detail::bundled_result< Graph, Descriptor >::type const&
0220     operator[](Descriptor x) const
0221     {
0222         return this->m_g[x];
0223     }
0224
0225     static vertex_descriptor null_vertex() { return Traits::null_vertex(); }
0226
0227     // private:
0228     EdgePredicate m_edge_pred;
0229     VertexPredicate m_vertex_pred;
0230 };
0231
0232 // Do not instantiate these unless needed
0233 template < typename Graph, typename EdgePredicate, typename VertexPredicate >
0234 struct vertex_property_type<
0235     filtered_graph< Graph, EdgePredicate, VertexPredicate > >
0236 : vertex_property_type< Graph >
0237 {
0238 };
0239
0240 template < typename Graph, typename EdgePredicate, typename VertexPredicate >
0241 struct edge_property_type<
0242     filtered_graph< Graph, EdgePredicate, VertexPredicate > >
0243 : edge_property_type< Graph >
0244 {
0245 };
0246
0247 template < typename Graph, typename EdgePredicate, typename VertexPredicate >
0248 struct graph_property_type<
0249     filtered_graph< Graph, EdgePredicate, VertexPredicate > >
0250 : graph_property_type< Graph >
0251 {
0252 };
0253
0254 template < typename Graph, typename EdgePredicate, typename VertexPredicate >
0255 struct vertex_bundle_type<
0256     filtered_graph< Graph, EdgePredicate, VertexPredicate > >
0257 : vertex_bundle_type< Graph >
0258 {
0259 };
0260
0261 template < typename Graph, typename EdgePredicate, typename VertexPredicate >
0262 struct edge_bundle_type<
0263     filtered_graph< Graph, EdgePredicate, VertexPredicate > >
0264 : edge_bundle_type< Graph >
0265 {
0266 };
0267
0268 template < typename Graph, typename EdgePredicate, typename VertexPredicate >
0269 struct graph_bundle_type<
0270     filtered_graph< Graph, EdgePredicate, VertexPredicate > >
0271 : graph_bundle_type< Graph >
0272 {
0273 };
0274
0275 //===========================================================================
0276 // Non-member functions for the Filtered Edge Graph
0277
0278 // Helper functions
0279 template < typename Graph, typename EdgePredicate >
0280 inline filtered_graph< Graph, EdgePredicate > make_filtered_graph(
0281     Graph& g, EdgePredicate ep)
0282 {
0283     return filtered_graph< Graph, EdgePredicate >(g, ep);
0284 }
0285 template < typename Graph, typename EdgePredicate, typename VertexPredicate >
0286 inline filtered_graph< Graph, EdgePredicate, VertexPredicate >
0287 make_filtered_graph(Graph& g, EdgePredicate ep, VertexPredicate vp)
0288 {
0289     return filtered_graph< Graph, EdgePredicate, VertexPredicate >(g, ep, vp);
0290 }
0291
0292 template < typename Graph, typename EdgePredicate >
0293 inline filtered_graph< const Graph, EdgePredicate > make_filtered_graph(
0294     const Graph& g, EdgePredicate ep)
0295 {
0296     return filtered_graph< const Graph, EdgePredicate >(g, ep);
0297 }
0298 template < typename Graph, typename EdgePredicate, typename VertexPredicate >
0299 inline filtered_graph< const Graph, EdgePredicate, VertexPredicate >
0300 make_filtered_graph(const Graph& g, EdgePredicate ep, VertexPredicate vp)
0301 {
0302     return filtered_graph< const Graph, EdgePredicate, VertexPredicate >(
0303         g, ep, vp);
0304 }
0305
0306 template < typename G, typename EP, typename VP >
0307 std::pair< typename filtered_graph< G, EP, VP >::vertex_iterator,
0308     typename filtered_graph< G, EP, VP >::vertex_iterator >
0309 vertices(const filtered_graph< G, EP, VP >& g)
0310 {
0311     typedef filtered_graph< G, EP, VP > Graph;
0312     typename graph_traits< G >::vertex_iterator f, l;
0313     boost::tie(f, l) = vertices(g.m_g);
0314     typedef typename Graph::vertex_iterator iter;
0315     return std::make_pair(
0316         iter(g.m_vertex_pred, f, l), iter(g.m_vertex_pred, l, l));
0317 }
0318
0319 template < typename G, typename EP, typename VP >
0320 std::pair< typename filtered_graph< G, EP, VP >::edge_iterator,
0321     typename filtered_graph< G, EP, VP >::edge_iterator >
0322 edges(const filtered_graph< G, EP, VP >& g)
0323 {
0324     typedef filtered_graph< G, EP, VP > Graph;
0325     typename Graph::EdgePred pred(g.m_edge_pred, g.m_vertex_pred, g);
0326     typename graph_traits< G >::edge_iterator f, l;
0327     boost::tie(f, l) = edges(g.m_g);
0328     typedef typename Graph::edge_iterator iter;
0329     return std::make_pair(iter(pred, f, l), iter(pred, l, l));
0330 }
0331
0332 // An alternative for num_vertices() and num_edges() would be to
0333 // count the number in the filtered graph. This is problematic
0334 // because of the interaction with the vertex indices...  they would
0335 // no longer go from 0 to num_vertices(), which would cause trouble
0336 // for algorithms allocating property storage in an array. We could
0337 // try to create a mapping to new recalibrated indices, but I don't
0338 // see an efficient way to do this.
0339 //
0340 // However, the current solution is still unsatisfactory because
0341 // the following semantic constraints no longer hold:
0342 // boost::tie(vi, viend) = vertices(g);
0343 // assert(std::distance(vi, viend) == num_vertices(g));
0344
0345 template < typename G, typename EP, typename VP >
0346 typename filtered_graph< G, EP, VP >::vertices_size_type num_vertices(
0347     const filtered_graph< G, EP, VP >& g)
0348 {
0349     return num_vertices(g.m_g);
0350 }
0351
0352 template < typename G, typename EP, typename VP >
0353 typename filtered_graph< G, EP, VP >::edges_size_type num_edges(
0354     const filtered_graph< G, EP, VP >& g)
0355 {
0356     return num_edges(g.m_g);
0357 }
0358
0359 template < typename G >
0360 typename filtered_graph_base< G >::vertex_descriptor source(
0361     typename filtered_graph_base< G >::edge_descriptor e,
0362     const filtered_graph_base< G >& g)
0363 {
0364     return source(e, g.m_g);
0365 }
0366
0367 template < typename G >
0368 typename filtered_graph_base< G >::vertex_descriptor target(
0369     typename filtered_graph_base< G >::edge_descriptor e,
0370     const filtered_graph_base< G >& g)
0371 {
0372     return target(e, g.m_g);
0373 }
0374
0375 template < typename G, typename EP, typename VP >
0376 std::pair< typename filtered_graph< G, EP, VP >::out_edge_iterator,
0377     typename filtered_graph< G, EP, VP >::out_edge_iterator >
0378 out_edges(typename filtered_graph< G, EP, VP >::vertex_descriptor u,
0379     const filtered_graph< G, EP, VP >& g)
0380 {
0381     typedef filtered_graph< G, EP, VP > Graph;
0382     typename Graph::OutEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g);
0383     typedef typename Graph::out_edge_iterator iter;
0384     typename graph_traits< G >::out_edge_iterator f, l;
0385     boost::tie(f, l) = out_edges(u, g.m_g);
0386     return std::make_pair(iter(pred, f, l), iter(pred, l, l));
0387 }
0388
0389 template < typename G, typename EP, typename VP >
0390 typename filtered_graph< G, EP, VP >::degree_size_type out_degree(
0391     typename filtered_graph< G, EP, VP >::vertex_descriptor u,
0392     const filtered_graph< G, EP, VP >& g)
0393 {
0394     typename filtered_graph< G, EP, VP >::degree_size_type n = 0;
0395     typename filtered_graph< G, EP, VP >::out_edge_iterator f, l;
0396     for (boost::tie(f, l) = out_edges(u, g); f != l; ++f)
0397         ++n;
0398     return n;
0399 }
0400
0401 template < typename G, typename EP, typename VP >
0402 std::pair< typename filtered_graph< G, EP, VP >::adjacency_iterator,
0403     typename filtered_graph< G, EP, VP >::adjacency_iterator >
0404 adjacent_vertices(typename filtered_graph< G, EP, VP >::vertex_descriptor u,
0405     const filtered_graph< G, EP, VP >& g)
0406 {
0407     typedef filtered_graph< G, EP, VP > Graph;
0408     typedef typename Graph::adjacency_iterator adjacency_iterator;
0409     typename Graph::out_edge_iterator f, l;
0410     boost::tie(f, l) = out_edges(u, g);
0411     return std::make_pair(adjacency_iterator(f, const_cast< Graph* >(&g)),
0412         adjacency_iterator(l, const_cast< Graph* >(&g)));
0413 }
0414
0415 template < typename G, typename EP, typename VP >
0416 std::pair< typename filtered_graph< G, EP, VP >::in_edge_iterator,
0417     typename filtered_graph< G, EP, VP >::in_edge_iterator >
0418 in_edges(typename filtered_graph< G, EP, VP >::vertex_descriptor u,
0419     const filtered_graph< G, EP, VP >& g)
0420 {
0421     typedef filtered_graph< G, EP, VP > Graph;
0422     typename Graph::InEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g);
0423     typedef typename Graph::in_edge_iterator iter;
0424     typename graph_traits< G >::in_edge_iterator f, l;
0425     boost::tie(f, l) = in_edges(u, g.m_g);
0426     return std::make_pair(iter(pred, f, l), iter(pred, l, l));
0427 }
0428
0429 template < typename G, typename EP, typename VP >
0430 typename filtered_graph< G, EP, VP >::degree_size_type in_degree(
0431     typename filtered_graph< G, EP, VP >::vertex_descriptor u,
0432     const filtered_graph< G, EP, VP >& g)
0433 {
0434     typename filtered_graph< G, EP, VP >::degree_size_type n = 0;
0435     typename filtered_graph< G, EP, VP >::in_edge_iterator f, l;
0436     for (boost::tie(f, l) = in_edges(u, g); f != l; ++f)
0437         ++n;
0438     return n;
0439 }
0440
0441 template < typename G, typename EP, typename VP >
0442 typename enable_if< typename is_directed_graph< G >::type,
0443     typename filtered_graph< G, EP, VP >::degree_size_type >::type
0444 degree(typename filtered_graph< G, EP, VP >::vertex_descriptor u,
0445     const filtered_graph< G, EP, VP >& g)
0446 {
0447     return out_degree(u, g) + in_degree(u, g);
0448 }
0449
0450 template < typename G, typename EP, typename VP >
0451 typename disable_if< typename is_directed_graph< G >::type,
0452     typename filtered_graph< G, EP, VP >::degree_size_type >::type
0453 degree(typename filtered_graph< G, EP, VP >::vertex_descriptor u,
0454     const filtered_graph< G, EP, VP >& g)
0455 {
0456     return out_degree(u, g);
0457 }
0458
0459 template < typename G, typename EP, typename VP >
0460 std::pair< typename filtered_graph< G, EP, VP >::edge_descriptor, bool > edge(
0461     typename filtered_graph< G, EP, VP >::vertex_descriptor u,
0462     typename filtered_graph< G, EP, VP >::vertex_descriptor v,
0463     const filtered_graph< G, EP, VP >& g)
0464 {
0465     typename graph_traits< G >::edge_descriptor e;
0466     bool exists;
0467     boost::tie(e, exists) = edge(u, v, g.m_g);
0468     return std::make_pair(e, exists && g.m_edge_pred(e));
0469 }
0470
0471 template < typename G, typename EP, typename VP >
0472 std::pair< typename filtered_graph< G, EP, VP >::out_edge_iterator,
0473     typename filtered_graph< G, EP, VP >::out_edge_iterator >
0474 edge_range(typename filtered_graph< G, EP, VP >::vertex_descriptor u,
0475     typename filtered_graph< G, EP, VP >::vertex_descriptor v,
0476     const filtered_graph< G, EP, VP >& g)
0477 {
0478     typedef filtered_graph< G, EP, VP > Graph;
0479     typename Graph::OutEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g);
0480     typedef typename Graph::out_edge_iterator iter;
0481     typename graph_traits< G >::out_edge_iterator f, l;
0482     boost::tie(f, l) = edge_range(u, v, g.m_g);
0483     return std::make_pair(iter(pred, f, l), iter(pred, l, l));
0484 }
0485
0486 //===========================================================================
0487 // Property map
0488
0489 template < typename G, typename EP, typename VP, typename Property >
0490 struct property_map< filtered_graph< G, EP, VP >, Property >
0491 : property_map< G, Property >
0492 {
0493 };
0494
0495 template < typename G, typename EP, typename VP, typename Property >
0496 typename property_map< G, Property >::type get(
0497     Property p, filtered_graph< G, EP, VP >& g)
0498 {
0499     return get(p, const_cast< G& >(g.m_g));
0500 }
0501
0502 template < typename G, typename EP, typename VP, typename Property >
0503 typename property_map< G, Property >::const_type get(
0504     Property p, const filtered_graph< G, EP, VP >& g)
0505 {
0506     return get(p, (const G&)g.m_g);
0507 }
0508
0509 template < typename G, typename EP, typename VP, typename Property,
0510     typename Key >
0511 typename property_map_value< G, Property >::type get(
0512     Property p, const filtered_graph< G, EP, VP >& g, const Key& k)
0513 {
0514     return get(p, (const G&)g.m_g, k);
0515 }
0516
0517 template < typename G, typename EP, typename VP, typename Property,
0518     typename Key, typename Value >
0519 void put(Property p, const filtered_graph< G, EP, VP >& g, const Key& k,
0520     const Value& val)
0521 {
0522     put(p, const_cast< G& >(g.m_g), k, val);
0523 }
0524
0525 //===========================================================================
0526 // Some filtered subgraph specializations
0527
0528 template < typename Graph, typename Set > struct vertex_subset_filter
0529 {
0530     typedef filtered_graph< Graph, keep_all, is_in_subset< Set > > type;
0531 };
0532 template < typename Graph, typename Set >
0533 inline typename vertex_subset_filter< Graph, Set >::type
0534 make_vertex_subset_filter(Graph& g, const Set& s)
0535 {
0536     typedef typename vertex_subset_filter< Graph, Set >::type Filter;
0537     is_in_subset< Set > p(s);
0538     return Filter(g, keep_all(), p);
0539 }
0540
0541 // This is misspelled, but present for backwards compatibility; new code
0542 // should use the version below that has the correct spelling.
0543 template < typename Graph, typename Set > struct vertex_subset_compliment_filter
0544 {
0545     typedef filtered_graph< Graph, keep_all, is_not_in_subset< Set > > type;
0546 };
0547 template < typename Graph, typename Set >
0548 inline typename vertex_subset_compliment_filter< Graph, Set >::type
0549 make_vertex_subset_compliment_filter(Graph& g, const Set& s)
0550 {
0551     typedef typename vertex_subset_compliment_filter< Graph, Set >::type Filter;
0552     is_not_in_subset< Set > p(s);
0553     return Filter(g, keep_all(), p);
0554 }
0555
0556 template < typename Graph, typename Set > struct vertex_subset_complement_filter
0557 {
0558     typedef filtered_graph< Graph, keep_all, is_not_in_subset< Set > > type;
0559 };
0560 template < typename Graph, typename Set >
0561 inline typename vertex_subset_complement_filter< Graph, Set >::type
0562 make_vertex_subset_complement_filter(Graph& g, const Set& s)
0563 {
0564     typedef typename vertex_subset_complement_filter< Graph, Set >::type Filter;
0565     is_not_in_subset< Set > p(s);
0566     return Filter(g, keep_all(), p);
0567 }
0568
0569 // Filter that uses a property map whose value_type is a boolean
0570 template < typename PropertyMap > struct property_map_filter
0571 {
0572
0573     property_map_filter() {}
0574
0575     property_map_filter(const PropertyMap& property_map)
0576     : m_property_map(property_map)
0577     {
0578     }
0579
0580     template < typename Key > bool operator()(const Key& key) const
0581     {
0582         return (get(m_property_map, key));
0583     }
0584
0585 private:
0586     PropertyMap m_property_map;
0587 };
0588
0589 } // namespace boost
0590
0591 #endif // BOOST_FILTERED_GRAPH_HPP