// 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 |