123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560 |
- //=======================================================================
- // 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;
- // 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]; }
- static vertex_descriptor null_vertex()
- {
- return Traits::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> >:
- vertex_property_type<Graph> {};
- template <typename Graph,
- typename EdgePredicate,
- typename VertexPredicate>
- struct edge_property_type<filtered_graph<Graph, EdgePredicate, VertexPredicate> >:
- edge_property_type<Graph> {};
- template <typename Graph,
- typename EdgePredicate,
- typename VertexPredicate>
- struct graph_property_type<filtered_graph<Graph, EdgePredicate, VertexPredicate> >:
- graph_property_type<Graph> {};
- 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> { };
- //===========================================================================
- // 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>
- typename enable_if<typename is_directed_graph<G>::type,
- typename filtered_graph<G, EP, VP>::degree_size_type
- >::type
- degree(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
- const filtered_graph<G, EP, VP>& g)
- {
- return out_degree(u, g) + in_degree(u, g);
- }
- template <typename G, typename EP, typename VP>
- typename disable_if<typename is_directed_graph<G>::type,
- typename filtered_graph<G, EP, VP>::degree_size_type
- >::type
- degree(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
- const filtered_graph<G, EP, VP>& g)
- {
- return out_degree(u, g);
- }
- 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
|