// 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_VERTEX_LIST_ADAPTOR_HPP
|
#define BOOST_VERTEX_LIST_ADAPTOR_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 <vector>
|
#include <boost/shared_ptr.hpp>
|
#include <boost/property_map/property_map.hpp>
|
#include <boost/graph/parallel/algorithm.hpp>
|
#include <boost/graph/parallel/container_traits.hpp>
|
#include <boost/property_map/vector_property_map.hpp>
|
|
namespace boost { namespace graph {
|
|
// --------------------------------------------------------------------------
|
// Global index map built from a distribution
|
// --------------------------------------------------------------------------
|
template<typename Distribution, typename OwnerPropertyMap,
|
typename LocalPropertyMap>
|
class distribution_global_index_map
|
{
|
public:
|
typedef std::size_t value_type;
|
typedef value_type reference;
|
typedef typename property_traits<OwnerPropertyMap>::key_type key_type;
|
typedef readable_property_map_tag category;
|
|
distribution_global_index_map(const Distribution& distribution,
|
const OwnerPropertyMap& owner,
|
const LocalPropertyMap& local)
|
: distribution_(distribution), owner(owner), local(local) { }
|
|
Distribution distribution_;
|
OwnerPropertyMap owner;
|
LocalPropertyMap local;
|
};
|
|
template<typename Distribution, typename OwnerPropertyMap,
|
typename LocalPropertyMap>
|
inline
|
typename distribution_global_index_map<Distribution, OwnerPropertyMap,
|
LocalPropertyMap>::value_type
|
get(const distribution_global_index_map<Distribution, OwnerPropertyMap,
|
LocalPropertyMap>& p,
|
typename distribution_global_index_map<Distribution, OwnerPropertyMap,
|
LocalPropertyMap>::key_type x)
|
{
|
using boost::get;
|
return p.distribution_.global(get(p.owner, x), get(p.local, x));
|
}
|
|
template<typename Graph, typename Distribution>
|
inline
|
distribution_global_index_map<
|
Distribution,
|
typename property_map<Graph, vertex_owner_t>::const_type,
|
typename property_map<Graph, vertex_local_t>::const_type>
|
make_distribution_global_index_map(const Graph& g, const Distribution& d)
|
{
|
typedef distribution_global_index_map<
|
Distribution,
|
typename property_map<Graph, vertex_owner_t>::const_type,
|
typename property_map<Graph, vertex_local_t>::const_type>
|
result_type;
|
return result_type(d, get(vertex_owner, g), get(vertex_local, g));
|
}
|
|
// --------------------------------------------------------------------------
|
// Global index map built from a distributed index map and list of vertices
|
// --------------------------------------------------------------------------
|
template<typename IndexMap>
|
class stored_global_index_map : public IndexMap
|
{
|
public:
|
typedef readable_property_map_tag category;
|
|
stored_global_index_map(const IndexMap& index_map) : IndexMap(index_map) {
|
// When we have a global index, we need to always have the indices
|
// of every key we've seen
|
this->set_max_ghost_cells(0);
|
}
|
};
|
|
// --------------------------------------------------------------------------
|
// Global index map support code
|
// --------------------------------------------------------------------------
|
namespace detail {
|
template<typename PropertyMap, typename ForwardIterator>
|
inline void
|
initialize_global_index_map(const PropertyMap&,
|
ForwardIterator, ForwardIterator)
|
{ }
|
|
template<typename IndexMap, typename ForwardIterator>
|
void
|
initialize_global_index_map(stored_global_index_map<IndexMap>& p,
|
ForwardIterator first, ForwardIterator last)
|
{
|
using std::distance;
|
|
typedef typename property_traits<IndexMap>::value_type size_t;
|
|
size_t n = distance(first, last);
|
for (size_t i = 0; i < n; ++i, ++first) local_put(p, *first, i);
|
}
|
}
|
|
// --------------------------------------------------------------------------
|
// Adapts a Distributed Vertex List Graph to a Vertex List Graph
|
// --------------------------------------------------------------------------
|
template<typename Graph, typename GlobalIndexMap>
|
class vertex_list_adaptor : public graph_traits<Graph>
|
{
|
typedef graph_traits<Graph> inherited;
|
|
typedef typename inherited::traversal_category base_traversal_category;
|
|
public:
|
typedef typename inherited::vertex_descriptor vertex_descriptor;
|
typedef typename std::vector<vertex_descriptor>::iterator vertex_iterator;
|
typedef typename std::vector<vertex_descriptor>::size_type
|
vertices_size_type;
|
|
struct traversal_category
|
: public virtual base_traversal_category,
|
public virtual vertex_list_graph_tag {};
|
|
vertex_list_adaptor(const Graph& g,
|
const GlobalIndexMap& index_map = GlobalIndexMap())
|
: g(&g), index_map(index_map)
|
{
|
using boost::vertices;
|
|
all_vertices_.reset(new std::vector<vertex_descriptor>());
|
all_gather(process_group(), vertices(g).first, vertices(g).second,
|
*all_vertices_);
|
detail::initialize_global_index_map(this->index_map,
|
all_vertices_->begin(),
|
all_vertices_->end());
|
}
|
|
const Graph& base() const { return *g; }
|
|
// --------------------------------------------------------------------------
|
// Distributed Container
|
// --------------------------------------------------------------------------
|
typedef typename boost::graph::parallel::process_group_type<Graph>::type
|
process_group_type;
|
|
process_group_type process_group() const
|
{
|
using boost::graph::parallel::process_group;
|
return process_group(*g);
|
}
|
|
std::pair<vertex_iterator, vertex_iterator> vertices() const
|
{ return std::make_pair(all_vertices_->begin(), all_vertices_->end()); }
|
|
vertices_size_type num_vertices() const { return all_vertices_->size(); }
|
|
GlobalIndexMap get_index_map() const { return index_map; }
|
|
private:
|
const Graph* g;
|
GlobalIndexMap index_map;
|
shared_ptr<std::vector<vertex_descriptor> > all_vertices_;
|
};
|
|
template<typename Graph, typename GlobalIndexMap>
|
inline vertex_list_adaptor<Graph, GlobalIndexMap>
|
make_vertex_list_adaptor(const Graph& g, const GlobalIndexMap& index_map)
|
{ return vertex_list_adaptor<Graph, GlobalIndexMap>(g, index_map); }
|
|
namespace detail {
|
template<typename Graph>
|
class default_global_index_map
|
{
|
typedef typename graph_traits<Graph>::vertices_size_type value_type;
|
typedef typename property_map<Graph, vertex_index_t>::const_type local_map;
|
|
public:
|
typedef vector_property_map<value_type, local_map> distributed_map;
|
typedef stored_global_index_map<distributed_map> type;
|
};
|
}
|
|
template<typename Graph>
|
inline
|
vertex_list_adaptor<Graph,
|
typename detail::default_global_index_map<Graph>::type>
|
make_vertex_list_adaptor(const Graph& g)
|
{
|
typedef typename detail::default_global_index_map<Graph>::type
|
GlobalIndexMap;
|
typedef typename detail::default_global_index_map<Graph>::distributed_map
|
DistributedMap;
|
typedef vertex_list_adaptor<Graph, GlobalIndexMap> result_type;
|
return result_type(g,
|
GlobalIndexMap(DistributedMap(num_vertices(g),
|
get(vertex_index, g))));
|
}
|
|
// --------------------------------------------------------------------------
|
// Incidence Graph
|
// --------------------------------------------------------------------------
|
template<typename Graph, typename GlobalIndexMap>
|
inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor
|
source(typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor e,
|
const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return source(e, g.base()); }
|
|
template<typename Graph, typename GlobalIndexMap>
|
inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor
|
target(typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor e,
|
const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return target(e, g.base()); }
|
|
template<typename Graph, typename GlobalIndexMap>
|
inline
|
std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::out_edge_iterator,
|
typename vertex_list_adaptor<Graph, GlobalIndexMap>::out_edge_iterator>
|
out_edges(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
|
const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return out_edges(v, g.base()); }
|
|
template<typename Graph, typename GlobalIndexMap>
|
inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
|
out_degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
|
const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return out_degree(v, g.base()); }
|
|
// --------------------------------------------------------------------------
|
// Bidirectional Graph
|
// --------------------------------------------------------------------------
|
template<typename Graph, typename GlobalIndexMap>
|
inline
|
std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::in_edge_iterator,
|
typename vertex_list_adaptor<Graph, GlobalIndexMap>::in_edge_iterator>
|
in_edges(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
|
const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return in_edges(v, g.base()); }
|
|
template<typename Graph, typename GlobalIndexMap>
|
inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
|
in_degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
|
const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return in_degree(v, g.base()); }
|
|
template<typename Graph, typename GlobalIndexMap>
|
inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
|
degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
|
const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return degree(v, g.base()); }
|
|
// --------------------------------------------------------------------------
|
// Adjacency Graph
|
// --------------------------------------------------------------------------
|
template<typename Graph, typename GlobalIndexMap>
|
inline
|
std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::adjacency_iterator,
|
typename vertex_list_adaptor<Graph, GlobalIndexMap>::adjacency_iterator>
|
adjacent_vertices(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
|
const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return adjacent_vertices(v, g.base()); }
|
|
|
// --------------------------------------------------------------------------
|
// Vertex List Graph
|
// --------------------------------------------------------------------------
|
template<typename Graph, typename GlobalIndexMap>
|
inline
|
std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_iterator,
|
typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_iterator>
|
vertices(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return g.vertices(); }
|
|
template<typename Graph, typename GlobalIndexMap>
|
inline
|
typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertices_size_type
|
num_vertices(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return g.num_vertices(); }
|
|
// --------------------------------------------------------------------------
|
// Edge List Graph
|
// --------------------------------------------------------------------------
|
template<typename Graph, typename GlobalIndexMap>
|
inline
|
std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_iterator,
|
typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_iterator>
|
edges(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return edges(g.base()); }
|
|
template<typename Graph, typename GlobalIndexMap>
|
inline
|
typename vertex_list_adaptor<Graph, GlobalIndexMap>::edges_size_type
|
num_edges(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return num_edges(g.base()); }
|
|
// --------------------------------------------------------------------------
|
// Property Graph
|
// --------------------------------------------------------------------------
|
template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
|
inline typename property_map<Graph, PropertyTag>::type
|
get(PropertyTag p, vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return get(p, g.base()); }
|
|
template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
|
inline typename property_map<Graph, PropertyTag>::const_type
|
get(PropertyTag p, const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return get(p, g.base()); }
|
|
template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
|
inline typename property_traits<
|
typename property_map<Graph, PropertyTag>::type
|
>::value_type
|
get(PropertyTag p, const vertex_list_adaptor<Graph, GlobalIndexMap>& g,
|
typename property_traits<
|
typename property_map<Graph, PropertyTag>::type
|
>::key_type const& x)
|
{ return get(p, g.base(), x); }
|
|
template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
|
inline void
|
put(PropertyTag p, vertex_list_adaptor<Graph, GlobalIndexMap>& g,
|
typename property_traits<
|
typename property_map<Graph, PropertyTag>::type
|
>::key_type const& x,
|
typename property_traits<
|
typename property_map<Graph, PropertyTag>::type
|
>::value_type const& v)
|
{ return put(p, g.base(), x, v); }
|
|
// --------------------------------------------------------------------------
|
// Property Graph: vertex_index property
|
// --------------------------------------------------------------------------
|
template<typename Graph, typename GlobalIndexMap>
|
inline GlobalIndexMap
|
get(vertex_index_t, const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return g.get_index_map(); }
|
|
template<typename Graph, typename GlobalIndexMap>
|
inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertices_size_type
|
get(vertex_index_t, const vertex_list_adaptor<Graph, GlobalIndexMap>& g,
|
typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor x)
|
{ return get(g.get_index_map(), x); }
|
|
// --------------------------------------------------------------------------
|
// Adjacency Matrix Graph
|
// --------------------------------------------------------------------------
|
template<typename Graph, typename GlobalIndexMap>
|
std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor,
|
bool>
|
edge(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor u,
|
typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
|
vertex_list_adaptor<Graph, GlobalIndexMap>& g)
|
{ return edge(u, v, g.base()); }
|
|
} } // end namespace boost::graph
|
|
namespace boost {
|
|
// --------------------------------------------------------------------------
|
// Property Graph: vertex_index property
|
// --------------------------------------------------------------------------
|
template<typename Graph, typename GlobalIndexMap>
|
class property_map<vertex_index_t,
|
graph::vertex_list_adaptor<Graph, GlobalIndexMap> >
|
{
|
public:
|
typedef GlobalIndexMap type;
|
typedef type const_type;
|
};
|
|
template<typename Graph, typename GlobalIndexMap>
|
class property_map<vertex_index_t,
|
const graph::vertex_list_adaptor<Graph, GlobalIndexMap> >
|
{
|
public:
|
typedef GlobalIndexMap type;
|
typedef type const_type;
|
};
|
|
using graph::distribution_global_index_map;
|
using graph::make_distribution_global_index_map;
|
using graph::stored_global_index_map;
|
using graph::make_vertex_list_adaptor;
|
using graph::vertex_list_adaptor;
|
|
} // end namespace boost
|
|
#endif // BOOST_VERTEX_LIST_ADAPTOR_HPP
|
