| //======================================================================= | |
| // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
| // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek | |
| // | |
| // Distributed under the Boost Software License, Version 1.0. (See | |
| // accompanying file LICENSE_1_0.txt or copy at | |
| // http://www.boost.org/LICENSE_1_0.txt) | |
| //======================================================================= | |
| #ifndef BOOST_FILTERED_GRAPH_HPP | |
| #define BOOST_FILTERED_GRAPH_HPP | |
| #include <boost/graph/graph_traits.hpp> | |
| #include <boost/graph/properties.hpp> | |
| #include <boost/graph/adjacency_iterator.hpp> | |
| #include <boost/graph/detail/set_adaptor.hpp> | |
| #include <boost/iterator/filter_iterator.hpp> | |
| namespace boost { | |
| //========================================================================= | |
| // Some predicate classes. | |
| struct keep_all { | |
| template <typename T> | |
| bool operator()(const T&) const { return true; } | |
| }; | |
| // Keep residual edges (used in maximum-flow algorithms). | |
| template <typename ResidualCapacityEdgeMap> | |
| struct is_residual_edge { | |
| is_residual_edge() { } | |
| is_residual_edge(ResidualCapacityEdgeMap rcap) : m_rcap(rcap) { } | |
| template <typename Edge> | |
| bool operator()(const Edge& e) const { | |
| return 0 < get(m_rcap, e); | |
| } | |
| ResidualCapacityEdgeMap m_rcap; | |
| }; | |
| template <typename Set> | |
| struct is_in_subset { | |
| is_in_subset() : m_s(0) { } | |
| is_in_subset(const Set& s) : m_s(&s) { } | |
| template <typename Elt> | |
| bool operator()(const Elt& x) const { | |
| return set_contains(*m_s, x); | |
| } | |
| const Set* m_s; | |
| }; | |
| template <typename Set> | |
| struct is_not_in_subset { | |
| is_not_in_subset() : m_s(0) { } | |
| is_not_in_subset(const Set& s) : m_s(&s) { } | |
| template <typename Elt> | |
| bool operator()(const Elt& x) const { | |
| return !set_contains(*m_s, x); | |
| } | |
| const Set* m_s; | |
| }; | |
| namespace detail { | |
| template <typename EdgePredicate, typename VertexPredicate, typename Graph> | |
| struct out_edge_predicate { | |
| out_edge_predicate() { } | |
| out_edge_predicate(EdgePredicate ep, VertexPredicate vp, | |
| const Graph& g) | |
| : m_edge_pred(ep), m_vertex_pred(vp), m_g(&g) { } | |
| template <typename Edge> | |
| bool operator()(const Edge& e) const { | |
| return m_edge_pred(e) && m_vertex_pred(target(e, *m_g)); | |
| } | |
| EdgePredicate m_edge_pred; | |
| VertexPredicate m_vertex_pred; | |
| const Graph* m_g; | |
| }; | |
| template <typename EdgePredicate, typename VertexPredicate, typename Graph> | |
| struct in_edge_predicate { | |
| in_edge_predicate() { } | |
| in_edge_predicate(EdgePredicate ep, VertexPredicate vp, | |
| const Graph& g) | |
| : m_edge_pred(ep), m_vertex_pred(vp), m_g(&g) { } | |
| template <typename Edge> | |
| bool operator()(const Edge& e) const { | |
| return m_edge_pred(e) && m_vertex_pred(source(e, *m_g)); | |
| } | |
| EdgePredicate m_edge_pred; | |
| VertexPredicate m_vertex_pred; | |
| const Graph* m_g; | |
| }; | |
| template <typename EdgePredicate, typename VertexPredicate, typename Graph> | |
| struct edge_predicate { | |
| edge_predicate() { } | |
| edge_predicate(EdgePredicate ep, VertexPredicate vp, | |
| const Graph& g) | |
| : m_edge_pred(ep), m_vertex_pred(vp), m_g(&g) { } | |
| template <typename Edge> | |
| bool operator()(const Edge& e) const { | |
| return m_edge_pred(e) | |
| && m_vertex_pred(source(e, *m_g)) && m_vertex_pred(target(e, *m_g)); | |
| } | |
| EdgePredicate m_edge_pred; | |
| VertexPredicate m_vertex_pred; | |
| const Graph* m_g; | |
| }; | |
| } // namespace detail | |
| //=========================================================================== | |
| // Filtered Graph | |
| struct filtered_graph_tag { }; | |
| // This base class is a stupid hack to change overload resolution | |
| // rules for the source and target functions so that they are a | |
| // worse match than the source and target functions defined for | |
| // pairs in graph_traits.hpp. I feel dirty. -JGS | |
| template <class G> | |
| struct filtered_graph_base { | |
| typedef graph_traits<G> Traits; | |
| typedef typename Traits::vertex_descriptor vertex_descriptor; | |
| typedef typename Traits::edge_descriptor edge_descriptor; | |
| filtered_graph_base(const G& g) : m_g(g) { } | |
| //protected: | |
| const G& m_g; | |
| }; | |
| template <typename Graph, | |
| typename EdgePredicate, | |
| typename VertexPredicate = keep_all> | |
| class filtered_graph : public filtered_graph_base<Graph> { | |
| typedef filtered_graph_base<Graph> Base; | |
| typedef graph_traits<Graph> Traits; | |
| typedef filtered_graph self; | |
| public: | |
| typedef Graph graph_type; | |
| typedef detail::out_edge_predicate<EdgePredicate, | |
| VertexPredicate, self> OutEdgePred; | |
| typedef detail::in_edge_predicate<EdgePredicate, | |
| VertexPredicate, self> InEdgePred; | |
| typedef detail::edge_predicate<EdgePredicate, | |
| VertexPredicate, self> EdgePred; | |
| // Constructors | |
| filtered_graph(const Graph& g, EdgePredicate ep) | |
| : Base(g), m_edge_pred(ep) { } | |
| filtered_graph(const Graph& g, EdgePredicate ep, VertexPredicate vp) | |
| : Base(g), m_edge_pred(ep), m_vertex_pred(vp) { } | |
| // Graph requirements | |
| typedef typename Traits::vertex_descriptor vertex_descriptor; | |
| typedef typename Traits::edge_descriptor edge_descriptor; | |
| typedef typename Traits::directed_category directed_category; | |
| typedef typename Traits::edge_parallel_category edge_parallel_category; | |
| typedef typename Traits::traversal_category traversal_category; | |
| // IncidenceGraph requirements | |
| typedef filter_iterator< | |
| OutEdgePred, typename Traits::out_edge_iterator | |
| > out_edge_iterator; | |
| typedef typename Traits::degree_size_type degree_size_type; | |
| // AdjacencyGraph requirements | |
| typedef typename adjacency_iterator_generator<self, | |
| vertex_descriptor, out_edge_iterator>::type adjacency_iterator; | |
| // BidirectionalGraph requirements | |
| typedef filter_iterator< | |
| InEdgePred, typename Traits::in_edge_iterator | |
| > in_edge_iterator; | |
| // VertexListGraph requirements | |
| typedef filter_iterator< | |
| VertexPredicate, typename Traits::vertex_iterator | |
| > vertex_iterator; | |
| typedef typename Traits::vertices_size_type vertices_size_type; | |
| // EdgeListGraph requirements | |
| typedef filter_iterator< | |
| EdgePred, typename Traits::edge_iterator | |
| > edge_iterator; | |
| typedef typename Traits::edges_size_type edges_size_type; | |
| typedef filtered_graph_tag graph_tag; | |
| #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES | |
| // Bundled properties support | |
| template<typename Descriptor> | |
| typename graph::detail::bundled_result<Graph, Descriptor>::type& | |
| operator[](Descriptor x) | |
| { return const_cast<Graph&>(this->m_g)[x]; } | |
| template<typename Descriptor> | |
| typename graph::detail::bundled_result<Graph, Descriptor>::type const& | |
| operator[](Descriptor x) const | |
| { return this->m_g[x]; } | |
| #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES | |
| static vertex_descriptor null_vertex() | |
| { | |
| return Graph::null_vertex(); | |
| } | |
| //private: | |
| EdgePredicate m_edge_pred; | |
| VertexPredicate m_vertex_pred; | |
| }; | |
| // Do not instantiate these unless needed | |
| template <typename Graph, | |
| typename EdgePredicate, | |
| typename VertexPredicate> | |
| struct vertex_property_type<filtered_graph<Graph, EdgePredicate, VertexPredicate> > { | |
| typedef typename vertex_property_type<Graph>::type type; | |
| }; | |
| template <typename Graph, | |
| typename EdgePredicate, | |
| typename VertexPredicate> | |
| struct edge_property_type<filtered_graph<Graph, EdgePredicate, VertexPredicate> > { | |
| typedef typename edge_property_type<Graph>::type type; | |
| }; | |
| template <typename Graph, | |
| typename EdgePredicate, | |
| typename VertexPredicate> | |
| struct graph_property_type<filtered_graph<Graph, EdgePredicate, VertexPredicate> > { | |
| typedef typename graph_property_type<Graph>::type type; | |
| }; | |
| #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES | |
| template<typename Graph, typename EdgePredicate, typename VertexPredicate> | |
| struct vertex_bundle_type<filtered_graph<Graph, EdgePredicate, | |
| VertexPredicate> > | |
| : vertex_bundle_type<Graph> { }; | |
| template<typename Graph, typename EdgePredicate, typename VertexPredicate> | |
| struct edge_bundle_type<filtered_graph<Graph, EdgePredicate, | |
| VertexPredicate> > | |
| : edge_bundle_type<Graph> { }; | |
| template<typename Graph, typename EdgePredicate, typename VertexPredicate> | |
| struct graph_bundle_type<filtered_graph<Graph, EdgePredicate, | |
| VertexPredicate> > | |
| : graph_bundle_type<Graph> { }; | |
| #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES | |
| //=========================================================================== | |
| // Non-member functions for the Filtered Edge Graph | |
| // Helper functions | |
| template <typename Graph, typename EdgePredicate> | |
| inline filtered_graph<Graph, EdgePredicate> | |
| make_filtered_graph(Graph& g, EdgePredicate ep) { | |
| return filtered_graph<Graph, EdgePredicate>(g, ep); | |
| } | |
| template <typename Graph, typename EdgePredicate, typename VertexPredicate> | |
| inline filtered_graph<Graph, EdgePredicate, VertexPredicate> | |
| make_filtered_graph(Graph& g, EdgePredicate ep, VertexPredicate vp) { | |
| return filtered_graph<Graph, EdgePredicate, VertexPredicate>(g, ep, vp); | |
| } | |
| template <typename Graph, typename EdgePredicate> | |
| inline filtered_graph<const Graph, EdgePredicate> | |
| make_filtered_graph(const Graph& g, EdgePredicate ep) { | |
| return filtered_graph<const Graph, EdgePredicate>(g, ep); | |
| } | |
| template <typename Graph, typename EdgePredicate, typename VertexPredicate> | |
| inline filtered_graph<const Graph, EdgePredicate, VertexPredicate> | |
| make_filtered_graph(const Graph& g, EdgePredicate ep, VertexPredicate vp) { | |
| return filtered_graph<const Graph, EdgePredicate, VertexPredicate>(g, ep, vp); | |
| } | |
| template <typename G, typename EP, typename VP> | |
| std::pair<typename filtered_graph<G, EP, VP>::vertex_iterator, | |
| typename filtered_graph<G, EP, VP>::vertex_iterator> | |
| vertices(const filtered_graph<G, EP, VP>& g) | |
| { | |
| typedef filtered_graph<G, EP, VP> Graph; | |
| typename graph_traits<G>::vertex_iterator f, l; | |
| boost::tie(f, l) = vertices(g.m_g); | |
| typedef typename Graph::vertex_iterator iter; | |
| return std::make_pair(iter(g.m_vertex_pred, f, l), | |
| iter(g.m_vertex_pred, l, l)); | |
| } | |
| template <typename G, typename EP, typename VP> | |
| std::pair<typename filtered_graph<G, EP, VP>::edge_iterator, | |
| typename filtered_graph<G, EP, VP>::edge_iterator> | |
| edges(const filtered_graph<G, EP, VP>& g) | |
| { | |
| typedef filtered_graph<G, EP, VP> Graph; | |
| typename Graph::EdgePred pred(g.m_edge_pred, g.m_vertex_pred, g); | |
| typename graph_traits<G>::edge_iterator f, l; | |
| boost::tie(f, l) = edges(g.m_g); | |
| typedef typename Graph::edge_iterator iter; | |
| return std::make_pair(iter(pred, f, l), iter(pred, l, l)); | |
| } | |
| // An alternative for num_vertices() and num_edges() would be to | |
| // count the number in the filtered graph. This is problematic | |
| // because of the interaction with the vertex indices... they would | |
| // no longer go from 0 to num_vertices(), which would cause trouble | |
| // for algorithms allocating property storage in an array. We could | |
| // try to create a mapping to new recalibrated indices, but I don't | |
| // see an efficient way to do this. | |
| // | |
| // However, the current solution is still unsatisfactory because | |
| // the following semantic constraints no longer hold: | |
| // boost::tie(vi, viend) = vertices(g); | |
| // assert(std::distance(vi, viend) == num_vertices(g)); | |
| template <typename G, typename EP, typename VP> | |
| typename filtered_graph<G, EP, VP>::vertices_size_type | |
| num_vertices(const filtered_graph<G, EP, VP>& g) { | |
| return num_vertices(g.m_g); | |
| } | |
| template <typename G, typename EP, typename VP> | |
| typename filtered_graph<G, EP, VP>::edges_size_type | |
| num_edges(const filtered_graph<G, EP, VP>& g) { | |
| return num_edges(g.m_g); | |
| } | |
| template <typename G> | |
| typename filtered_graph_base<G>::vertex_descriptor | |
| source(typename filtered_graph_base<G>::edge_descriptor e, | |
| const filtered_graph_base<G>& g) | |
| { | |
| return source(e, g.m_g); | |
| } | |
| template <typename G> | |
| typename filtered_graph_base<G>::vertex_descriptor | |
| target(typename filtered_graph_base<G>::edge_descriptor e, | |
| const filtered_graph_base<G>& g) | |
| { | |
| return target(e, g.m_g); | |
| } | |
| template <typename G, typename EP, typename VP> | |
| std::pair<typename filtered_graph<G, EP, VP>::out_edge_iterator, | |
| typename filtered_graph<G, EP, VP>::out_edge_iterator> | |
| out_edges(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
| const filtered_graph<G, EP, VP>& g) | |
| { | |
| typedef filtered_graph<G, EP, VP> Graph; | |
| typename Graph::OutEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g); | |
| typedef typename Graph::out_edge_iterator iter; | |
| typename graph_traits<G>::out_edge_iterator f, l; | |
| boost::tie(f, l) = out_edges(u, g.m_g); | |
| return std::make_pair(iter(pred, f, l), iter(pred, l, l)); | |
| } | |
| template <typename G, typename EP, typename VP> | |
| typename filtered_graph<G, EP, VP>::degree_size_type | |
| out_degree(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
| const filtered_graph<G, EP, VP>& g) | |
| { | |
| typename filtered_graph<G, EP, VP>::degree_size_type n = 0; | |
| typename filtered_graph<G, EP, VP>::out_edge_iterator f, l; | |
| for (boost::tie(f, l) = out_edges(u, g); f != l; ++f) | |
| ++n; | |
| return n; | |
| } | |
| template <typename G, typename EP, typename VP> | |
| std::pair<typename filtered_graph<G, EP, VP>::adjacency_iterator, | |
| typename filtered_graph<G, EP, VP>::adjacency_iterator> | |
| adjacent_vertices(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
| const filtered_graph<G, EP, VP>& g) | |
| { | |
| typedef filtered_graph<G, EP, VP> Graph; | |
| typedef typename Graph::adjacency_iterator adjacency_iterator; | |
| typename Graph::out_edge_iterator f, l; | |
| boost::tie(f, l) = out_edges(u, g); | |
| return std::make_pair(adjacency_iterator(f, const_cast<Graph*>(&g)), | |
| adjacency_iterator(l, const_cast<Graph*>(&g))); | |
| } | |
| template <typename G, typename EP, typename VP> | |
| std::pair<typename filtered_graph<G, EP, VP>::in_edge_iterator, | |
| typename filtered_graph<G, EP, VP>::in_edge_iterator> | |
| in_edges(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
| const filtered_graph<G, EP, VP>& g) | |
| { | |
| typedef filtered_graph<G, EP, VP> Graph; | |
| typename Graph::InEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g); | |
| typedef typename Graph::in_edge_iterator iter; | |
| typename graph_traits<G>::in_edge_iterator f, l; | |
| boost::tie(f, l) = in_edges(u, g.m_g); | |
| return std::make_pair(iter(pred, f, l), iter(pred, l, l)); | |
| } | |
| template <typename G, typename EP, typename VP> | |
| typename filtered_graph<G, EP, VP>::degree_size_type | |
| in_degree(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
| const filtered_graph<G, EP, VP>& g) | |
| { | |
| typename filtered_graph<G, EP, VP>::degree_size_type n = 0; | |
| typename filtered_graph<G, EP, VP>::in_edge_iterator f, l; | |
| for (boost::tie(f, l) = in_edges(u, g); f != l; ++f) | |
| ++n; | |
| return n; | |
| } | |
| template <typename G, typename EP, typename VP> | |
| std::pair<typename filtered_graph<G, EP, VP>::edge_descriptor, bool> | |
| edge(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
| typename filtered_graph<G, EP, VP>::vertex_descriptor v, | |
| const filtered_graph<G, EP, VP>& g) | |
| { | |
| typename graph_traits<G>::edge_descriptor e; | |
| bool exists; | |
| boost::tie(e, exists) = edge(u, v, g.m_g); | |
| return std::make_pair(e, exists && g.m_edge_pred(e)); | |
| } | |
| template <typename G, typename EP, typename VP> | |
| std::pair<typename filtered_graph<G, EP, VP>::out_edge_iterator, | |
| typename filtered_graph<G, EP, VP>::out_edge_iterator> | |
| edge_range(typename filtered_graph<G, EP, VP>::vertex_descriptor u, | |
| typename filtered_graph<G, EP, VP>::vertex_descriptor v, | |
| const filtered_graph<G, EP, VP>& g) | |
| { | |
| typedef filtered_graph<G, EP, VP> Graph; | |
| typename Graph::OutEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g); | |
| typedef typename Graph::out_edge_iterator iter; | |
| typename graph_traits<G>::out_edge_iterator f, l; | |
| boost::tie(f, l) = edge_range(u, v, g.m_g); | |
| return std::make_pair(iter(pred, f, l), iter(pred, l, l)); | |
| } | |
| //=========================================================================== | |
| // Property map | |
| template <typename G, typename EP, typename VP, typename Property> | |
| struct property_map<filtered_graph<G, EP, VP>, Property> | |
| : property_map<G, Property> {}; | |
| template <typename G, typename EP, typename VP, typename Property> | |
| typename property_map<G, Property>::type | |
| get(Property p, filtered_graph<G, EP, VP>& g) | |
| { | |
| return get(p, const_cast<G&>(g.m_g)); | |
| } | |
| template <typename G, typename EP, typename VP,typename Property> | |
| typename property_map<G, Property>::const_type | |
| get(Property p, const filtered_graph<G, EP, VP>& g) | |
| { | |
| return get(p, (const G&)g.m_g); | |
| } | |
| template <typename G, typename EP, typename VP, typename Property, | |
| typename Key> | |
| typename property_map_value<G, Property>::type | |
| get(Property p, const filtered_graph<G, EP, VP>& g, const Key& k) | |
| { | |
| return get(p, (const G&)g.m_g, k); | |
| } | |
| template <typename G, typename EP, typename VP, typename Property, | |
| typename Key, typename Value> | |
| void | |
| put(Property p, const filtered_graph<G, EP, VP>& g, const Key& k, | |
| const Value& val) | |
| { | |
| put(p, const_cast<G&>(g.m_g), k, val); | |
| } | |
| //=========================================================================== | |
| // Some filtered subgraph specializations | |
| template <typename Graph, typename Set> | |
| struct vertex_subset_filter { | |
| typedef filtered_graph<Graph, keep_all, is_in_subset<Set> > type; | |
| }; | |
| template <typename Graph, typename Set> | |
| inline typename vertex_subset_filter<Graph, Set>::type | |
| make_vertex_subset_filter(Graph& g, const Set& s) { | |
| typedef typename vertex_subset_filter<Graph, Set>::type Filter; | |
| is_in_subset<Set> p(s); | |
| return Filter(g, keep_all(), p); | |
| } | |
| // This is misspelled, but present for backwards compatibility; new code | |
| // should use the version below that has the correct spelling. | |
| template <typename Graph, typename Set> | |
| struct vertex_subset_compliment_filter { | |
| typedef filtered_graph<Graph, keep_all, is_not_in_subset<Set> > type; | |
| }; | |
| template <typename Graph, typename Set> | |
| inline typename vertex_subset_compliment_filter<Graph, Set>::type | |
| make_vertex_subset_compliment_filter(Graph& g, const Set& s) { | |
| typedef typename vertex_subset_compliment_filter<Graph, Set>::type Filter; | |
| is_not_in_subset<Set> p(s); | |
| return Filter(g, keep_all(), p); | |
| } | |
| template <typename Graph, typename Set> | |
| struct vertex_subset_complement_filter { | |
| typedef filtered_graph<Graph, keep_all, is_not_in_subset<Set> > type; | |
| }; | |
| template <typename Graph, typename Set> | |
| inline typename vertex_subset_complement_filter<Graph, Set>::type | |
| make_vertex_subset_complement_filter(Graph& g, const Set& s) { | |
| typedef typename vertex_subset_complement_filter<Graph, Set>::type Filter; | |
| is_not_in_subset<Set> p(s); | |
| return Filter(g, keep_all(), p); | |
| } | |
| // Filter that uses a property map whose value_type is a boolean | |
| template <typename PropertyMap> | |
| struct property_map_filter { | |
| property_map_filter() { } | |
| property_map_filter(const PropertyMap& property_map) : | |
| m_property_map(property_map) { } | |
| template <typename Key> | |
| bool operator()(const Key& key) const { | |
| return (get(m_property_map, key)); | |
| } | |
| private : | |
| PropertyMap m_property_map; | |
| }; | |
| } // namespace boost | |
| #endif // BOOST_FILTERED_GRAPH_HPP |