// Copyright (C) 2004-2006 The Trustees of Indiana University. | |
// Use, modification and distribution is subject to 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) | |
// Authors: Douglas Gregor | |
// Andrew Lumsdaine | |
#ifndef BOOST_GRAPH_LOCAL_SUBGRAPH_HPP | |
#define BOOST_GRAPH_LOCAL_SUBGRAPH_HPP | |
#ifndef BOOST_GRAPH_USE_MPI | |
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" | |
#endif | |
#include <boost/graph/graph_traits.hpp> | |
#include <boost/graph/filtered_graph.hpp> | |
#include <boost/type_traits/is_same.hpp> | |
#include <boost/type_traits/is_base_and_derived.hpp> | |
#include <boost/graph/parallel/container_traits.hpp> | |
namespace boost { | |
namespace graph { namespace detail { | |
// Optionally, virtually derive from a base class | |
template<bool Derive, typename Base> struct derive_from_if; | |
template<typename Base> struct derive_from_if<true, Base> : virtual Base {}; | |
template<typename Base> struct derive_from_if<false, Base> {}; | |
template<typename NewBase, typename Tag, typename OldBase = NewBase> | |
struct derive_from_if_tag_is : | |
derive_from_if<(is_base_and_derived<OldBase, Tag>::value | |
|| is_same<OldBase, Tag>::value), | |
NewBase> | |
{ | |
}; | |
} } // end namespace graph::detail | |
template<typename DistributedGraph> | |
class is_local_edge | |
{ | |
public: | |
typedef bool result_type; | |
typedef typename graph_traits<DistributedGraph>::edge_descriptor | |
argument_type; | |
is_local_edge() : g(0) {} | |
is_local_edge(DistributedGraph& g) : g(&g), owner(get(vertex_owner, g)) {} | |
// Since either the source or target vertex must be local, the | |
// equivalence of their owners indicates a local edge. | |
result_type operator()(const argument_type& e) const | |
{ return get(owner, source(e, *g)) == get(owner, target(e, *g)); } | |
private: | |
DistributedGraph* g; | |
typename property_map<DistributedGraph, vertex_owner_t>::const_type owner; | |
}; | |
template<typename DistributedGraph> | |
class is_local_vertex | |
{ | |
public: | |
typedef bool result_type; | |
typedef typename graph_traits<DistributedGraph>::vertex_descriptor | |
argument_type; | |
is_local_vertex() : g(0) {} | |
is_local_vertex(DistributedGraph& g) : g(&g), owner(get(vertex_owner, g)) { } | |
// Since either the source or target vertex must be local, the | |
// equivalence of their owners indicates a local edge. | |
result_type operator()(const argument_type& v) const | |
{ | |
return get(owner, v) == process_id(process_group(*g)); | |
} | |
private: | |
DistributedGraph* g; | |
typename property_map<DistributedGraph, vertex_owner_t>::const_type owner; | |
}; | |
template<typename DistributedGraph> | |
class local_subgraph | |
: public filtered_graph<DistributedGraph, | |
is_local_edge<DistributedGraph>, | |
is_local_vertex<DistributedGraph> > | |
{ | |
typedef filtered_graph<DistributedGraph, | |
is_local_edge<DistributedGraph>, | |
is_local_vertex<DistributedGraph> > | |
inherited; | |
typedef typename graph_traits<DistributedGraph>::traversal_category | |
inherited_category; | |
public: | |
struct traversal_category : | |
graph::detail::derive_from_if_tag_is<incidence_graph_tag, | |
inherited_category>, | |
graph::detail::derive_from_if_tag_is<adjacency_graph_tag, | |
inherited_category>, | |
graph::detail::derive_from_if_tag_is<vertex_list_graph_tag, | |
inherited_category>, | |
graph::detail::derive_from_if_tag_is<edge_list_graph_tag, | |
inherited_category>, | |
graph::detail::derive_from_if_tag_is<vertex_list_graph_tag, | |
inherited_category, | |
distributed_vertex_list_graph_tag>, | |
graph::detail::derive_from_if_tag_is<edge_list_graph_tag, | |
inherited_category, | |
distributed_edge_list_graph_tag> | |
{ }; | |
local_subgraph(DistributedGraph& g) | |
: inherited(g, | |
is_local_edge<DistributedGraph>(g), | |
is_local_vertex<DistributedGraph>(g)), | |
g(g) | |
{ | |
} | |
// Distributed Container | |
typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type | |
process_group_type; | |
process_group_type& process_group() | |
{ | |
using boost::graph::parallel::process_group; | |
return process_group(g); | |
} | |
const process_group_type& process_group() const | |
{ | |
using boost::graph::parallel::process_group; | |
return boost::graph::parallel::process_group(g); | |
} | |
DistributedGraph& base() { return g; } | |
const DistributedGraph& base() const { return g; } | |
private: | |
DistributedGraph& g; | |
}; | |
template<typename DistributedGraph, typename PropertyTag> | |
class property_map<local_subgraph<DistributedGraph>, PropertyTag> | |
: public property_map<DistributedGraph, PropertyTag> { }; | |
template<typename DistributedGraph, typename PropertyTag> | |
class property_map<local_subgraph<const DistributedGraph>, PropertyTag> | |
{ | |
public: | |
typedef typename property_map<DistributedGraph, PropertyTag>::const_type | |
type; | |
typedef type const_type; | |
}; | |
template<typename PropertyTag, typename DistributedGraph> | |
inline typename property_map<local_subgraph<DistributedGraph>, PropertyTag>::type | |
get(PropertyTag p, local_subgraph<DistributedGraph>& g) | |
{ return get(p, g.base()); } | |
template<typename PropertyTag, typename DistributedGraph> | |
inline typename property_map<local_subgraph<DistributedGraph>, PropertyTag> | |
::const_type | |
get(PropertyTag p, const local_subgraph<DistributedGraph>& g) | |
{ return get(p, g.base()); } | |
template<typename DistributedGraph> | |
inline local_subgraph<DistributedGraph> | |
make_local_subgraph(DistributedGraph& g) | |
{ return local_subgraph<DistributedGraph>(g); } | |
} // end namespace boost | |
#endif // BOOST_GRAPH_LOCAL_SUBGRAPH_HPP |