/usr/include/boost/graph/distributed
Edit: /usr/include/boost/graph/distributed/compressed_sparse_row_graph.hpp (81805B)
// Copyright (C) 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
// Jeremiah Willcock
// Andrew Lumsdaine
// Distributed compressed sparse row graph type
#ifndef BOOST_GRAPH_DISTRIBUTED_CSR_HPP
#define BOOST_GRAPH_DISTRIBUTED_CSR_HPP
#ifndef BOOST_GRAPH_USE_MPI
#error "Parallel BGL files should not be included unless
has been included"
#endif
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
namespace boost {
// Distributed and sequential inplace ctors have the same signature so
// we need a separate tag for distributed inplace ctors
enum distributed_construct_inplace_from_sources_and_targets_t
{distributed_construct_inplace_from_sources_and_targets};
// The number of bits we reserve for the processor ID.
// DPG TBD: This is a hack. It will eventually be a run-time quantity.
static const int processor_bits = 8;
// Tag class for a distributed CSR graph
struct distributed_csr_tag
: public virtual distributed_graph_tag,
public virtual distributed_vertex_list_graph_tag,
public virtual distributed_edge_list_graph_tag,
public virtual incidence_graph_tag,
public virtual adjacency_graph_tag {};
template
class compressed_sparse_row_graph<
directedS, VertexProperty, EdgeProperty, GraphProperty,
distributedS,
InEdgeIndex>
{
typedef compressed_sparse_row_graph self_type;
private:
/**
* Determine the type used to represent vertices in the graph. If
* the user has overridden the default, use the user's
* parameter. Otherwise, fall back to std::size_t.
*/
typedef typename mpl::if_,
std::size_t,
InVertex>::type Vertex;
/**
* Determine the type used to represent edges in the graph. If
* the user has overridden the default (which is to be the same as
* the distributed vertex selector type), use the user's
* parameter. Otherwise, fall back to the value of @c Vertex.
*/
typedef typename mpl::if_ >,
Vertex,
InEdgeIndex>::type EdgeIndex;
public:
/**
* The type of the CSR graph that will be stored locally.
*/
typedef compressed_sparse_row_graph
base_type;
// -----------------------------------------------------------------
// Graph concept requirements
typedef Vertex vertex_descriptor;
typedef typename graph_traits::edge_descriptor edge_descriptor;
typedef directed_tag directed_category;
typedef allow_parallel_edge_tag edge_parallel_category;
typedef distributed_csr_tag traversal_category;
static vertex_descriptor null_vertex();
// -----------------------------------------------------------------
// Distributed Vertex List Graph concept requirements
typedef Vertex vertices_size_type;
class vertex_iterator;
// -----------------------------------------------------------------
// Distributed Edge List Graph concept requirements
typedef EdgeIndex edges_size_type;
class edge_iterator;
// -----------------------------------------------------------------
// Incidence Graph concept requirements
typedef typename graph_traits::out_edge_iterator
out_edge_iterator;
typedef typename graph_traits::degree_size_type
degree_size_type;
// -----------------------------------------------------------------
// Adjacency Graph concept requirements
typedef typename graph_traits::adjacency_iterator
adjacency_iterator;
// Note: This graph type does not model Bidirectional Graph.
// However, this typedef is required to satisfy graph_traits.
typedef void in_edge_iterator;
// -----------------------------------------------------------------
// Distributed Container concept requirements
typedef ProcessGroup process_group_type;
typedef boost::parallel::variant_distribution
distribution_type;
// -----------------------------------------------------------------
// Workarounds
// NOTE: This graph type does not have old-style graph properties. It only
// accepts bundles.
typedef no_property vertex_property_type;
typedef no_property edge_property_type;
typedef no_property graph_property_type;
typedef typename mpl::if_,
void****,
VertexProperty>::type vertex_bundled;
typedef typename mpl::if_,
void****,
EdgeProperty>::type edge_bundled;
typedef typename mpl::if_,
void****,
GraphProperty>::type graph_bundled;
// -----------------------------------------------------------------
// Useful types
typedef typename ProcessGroup::process_id_type process_id_type;
// -----------------------------------------------------------------
// Graph constructors
compressed_sparse_row_graph(const ProcessGroup& pg = ProcessGroup())
: m_process_group(pg), m_distribution(parallel::block(pg, 0)) {}
compressed_sparse_row_graph(const GraphProperty& prop,
const ProcessGroup& pg = ProcessGroup())
: m_process_group(pg), m_distribution(parallel::block(pg, 0)) {}
compressed_sparse_row_graph(vertices_size_type numverts,
const ProcessGroup& pg = ProcessGroup())
: m_process_group(pg), m_distribution(parallel::block(pg, 0)),
m_base(numverts)
{}
compressed_sparse_row_graph(vertices_size_type numverts,
const GraphProperty& prop,
const ProcessGroup& pg = ProcessGroup())
: m_process_group(pg), m_distribution(parallel::block(pg, 0)),
m_base(numverts)
{}
template
compressed_sparse_row_graph(vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist)
: m_process_group(pg), m_distribution(dist), m_base(numverts) {}
template
compressed_sparse_row_graph(vertices_size_type numverts,
const GraphProperty& prop,
const ProcessGroup& pg,
const Distribution& dist)
: m_process_group(pg), m_distribution(dist), m_base(numverts) {}
template
compressed_sparse_row_graph(edges_are_unsorted_t,
InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg = ProcessGroup(),
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(edges_are_unsorted_t,
InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(edges_are_unsorted_t,
InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg = ProcessGroup(),
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(edges_are_unsorted_t,
InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(edges_are_sorted_t,
InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
edges_size_type numedges = 0,
const ProcessGroup& pg = ProcessGroup(),
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(edges_are_sorted_t,
InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(edges_are_sorted_t,
InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
edges_size_type numedges = 0,
const ProcessGroup& pg = ProcessGroup(),
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(edges_are_sorted_t,
InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg = ProcessGroup(),
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg = ProcessGroup(),
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
std::vector& sources,
std::vector& targets,
vertices_size_type numverts,
const ProcessGroup& pg = ProcessGroup(),
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
std::vector& sources,
std::vector& targets,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
std::vector& sources,
std::vector& targets,
std::vector& edge_props,
vertices_size_type numverts,
const ProcessGroup& pg = ProcessGroup(),
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
std::vector& sources,
std::vector& targets,
std::vector& edge_props,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg = ProcessGroup(),
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg = ProcessGroup(),
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop = GraphProperty());
template
compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop = GraphProperty());
base_type& base() { return m_base; }
const base_type& base() const { return m_base; }
process_group_type process_group() const { return m_process_group.base(); }
distribution_type& distribution() { return m_distribution; }
const distribution_type& distribution() const { return m_distribution; }
// Directly access a vertex or edge bundle
vertex_bundled& operator[](vertex_descriptor v)
{
return get(vertex_bundle, *this, v);
}
const vertex_bundled& operator[](vertex_descriptor v) const
{
return get(vertex_bundle, *this, v);
}
edge_bundled& operator[](edge_descriptor e)
{
return get(edge_bundle, *this, e);
}
const edge_bundled& operator[](edge_descriptor e) const
{
return get(edge_bundle, *this, e);
}
// Create a vertex descriptor from a process ID and a local index.
vertex_descriptor
make_vertex_descriptor(process_id_type p, vertex_descriptor v) const
{
vertex_descriptor vertex_local_index_bits =
sizeof(vertex_descriptor) * CHAR_BIT - processor_bits;
return v | ((vertex_descriptor)p << vertex_local_index_bits);
}
// Convert a local vertex descriptor into a global vertex descriptor
vertex_descriptor local_to_global_vertex(vertex_descriptor v) const
{
return make_vertex_descriptor(process_id(m_process_group), v);
}
// Structural modification
vertex_descriptor add_vertex()
{
typename graph_traits::vertex_descriptor v
= boost::add_vertex(m_base);
return make_vertex_descriptor(process_id(m_process_group), v);
}
vertex_descriptor add_vertex(const vertex_bundled& p)
{
typename graph_traits::vertex_descriptor v
= boost::add_vertex(m_base, p);
return make_vertex_descriptor(process_id(m_process_group), v);
}
vertex_descriptor add_vertices(vertices_size_type count)
{
typename graph_traits::vertex_descriptor v
= boost::add_vertices(count, m_base);
return make_vertex_descriptor(process_id(m_process_group), v);
}
template
void
add_edges(InputIterator first, InputIterator last)
{ boost::add_edges_global(first, last, get(vertex_local, *this), m_base); }
template
void
add_edges(InputIterator first, InputIterator last,
EdgePropertyIterator ep_iter,
EdgePropertyIterator ep_iter_end)
{ boost::add_edges_global(first, last, ep_iter, ep_iter_end,
get(vertex_local, *this), m_base); }
template
void
add_edges_sorted(InputIterator first, InputIterator last)
{ boost::add_edges_sorted_global(first, last,
get(vertex_local, *this), m_base); }
template
void
add_edges_sorted(InputIterator first_sorted, InputIterator last_sorted,
EdgePropertyIterator ep_iter_sorted)
{ boost::add_edges_sorted_global(first_sorted, last_sorted, ep_iter_sorted,
get(vertex_local, *this), m_base); }
protected:
ProcessGroup m_process_group;
distribution_type m_distribution;
base_type m_base;
};
/** @brief Helper macro containing the template parameters for the
* distributed CSR graph.
*
* This macro contains all of the template parameters needed for the
* distributed compressed_sparse_row graph type. It is used to reduce
* the amount of typing required to declare free functions for this
* graph type.
*/
#define BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS \
typename VertexProperty, typename EdgeProperty, \
typename GraphProperty, typename ProcessGroup, typename InVertex, \
typename InDistribution, typename InEdgeIndex
/** @brief Helper macro containing the typical instantiation of the
* distributed CSR graph.
*
* This macro contains an instantiation of the distributed CSR graph
* type using the typical template parameters names (e.g., those
* provided by the macro @c
* BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS). It is used to reduce
* the amount of typing required to declare free functions for this
* graph type.
*/
#define BOOST_DISTRIB_CSR_GRAPH_TYPE \
compressed_sparse_row_graph< \
directedS, VertexProperty, EdgeProperty, GraphProperty, \
distributedS, \
InEdgeIndex>
// -----------------------------------------------------------------
// Graph concept operations
template
inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
BOOST_DISTRIB_CSR_GRAPH_TYPE::null_vertex()
{
return graph_traits::null_vertex();
}
// -----------------------------------------------------------------
// Incidence Graph concept operations
template
inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
source(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor e,
const BOOST_DISTRIB_CSR_GRAPH_TYPE&)
{ return e.src; }
template
inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
target(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor e,
const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{ return target(e, g.base()); }
template
inline std::pair
out_edges(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u,
const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
edges_size_type;
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor ed;
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator it;
edges_size_type u_local = get(vertex_local, g, u);
edges_size_type u_row_start = g.base().m_forward.m_rowstart[u_local];
edges_size_type next_row_start = g.base().m_forward.m_rowstart[u_local + 1];
return std::make_pair(it(ed(u, u_row_start)),
it(ed(u, (std::max)(u_row_start, next_row_start))));
}
template
inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::degree_size_type
out_degree(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u,
const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
return out_degree(get(vertex_local, g, u), g.base());
}
// -----------------------------------------------------------------
// DistributedGraph concept requirements
template
void synchronize(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
synchronize(g.process_group());
}
template
ProcessGroup
process_group(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{ return g.process_group(); }
// -----------------------------------------------------------------
// Adjacency Graph concept requirements
template
inline std::pair
adjacent_vertices(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u,
const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
return adjacent_vertices(get(vertex_local, g, u), g.base());
}
// -----------------------------------------------------------------
// Distributed Vertex List Graph concept operations
template
class BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator
: public iterator_adaptor,
Vertex,
random_access_traversal_tag,
Vertex>
{
typedef iterator_adaptor,
Vertex,
random_access_traversal_tag,
Vertex> inherited;
public:
vertex_iterator() {}
explicit vertex_iterator(Vertex v, const self_type* graph)
: inherited(counting_iterator(v)), graph(graph) { }
Vertex dereference() const
{
return graph->local_to_global_vertex(*(this->base_reference()));
}
friend class iterator_core_access;
private:
const self_type* graph;
};
template
inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::degree_size_type
num_vertices(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
return num_vertices(g.base());
}
template
inline std::pair
vertices(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator
vertex_iterator;
return std::make_pair(vertex_iterator(0, &g),
vertex_iterator(num_vertices(g), &g));
}
// -----------------------------------------------------------------
// Distributed Edge List Graph concept operations
template
class BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator
{
public:
typedef std::forward_iterator_tag iterator_category;
typedef edge_descriptor value_type;
typedef const edge_descriptor* pointer;
typedef edge_descriptor reference;
typedef typename int_t::fast difference_type;
edge_iterator() : graph(0), current_edge(), end_of_this_vertex(0) {}
edge_iterator(const compressed_sparse_row_graph& graph,
edge_descriptor current_edge,
EdgeIndex end_of_this_vertex)
: graph(&graph), local_src(current_edge.src), current_edge(current_edge),
end_of_this_vertex(end_of_this_vertex)
{
// The edge that comes in has a local source vertex. Make it global.
current_edge.src = graph.local_to_global_vertex(current_edge.src);
}
// From InputIterator
reference operator*() const { return current_edge; }
pointer operator->() const { return ¤t_edge; }
bool operator==(const edge_iterator& o) const {
return current_edge == o.current_edge;
}
bool operator!=(const edge_iterator& o) const {
return current_edge != o.current_edge;
}
edge_iterator& operator++()
{
++current_edge.idx;
while (current_edge.idx == end_of_this_vertex && local_src < num_vertices(*graph)-1) {
++local_src;
current_edge.src = graph->local_to_global_vertex(local_src);
end_of_this_vertex = graph->base().m_forward.m_rowstart[local_src + 1];
}
return *this;
}
edge_iterator operator++(int) {
edge_iterator temp = *this;
++*this;
return temp;
}
private:
const compressed_sparse_row_graph* graph;
EdgeIndex local_src;
edge_descriptor current_edge;
EdgeIndex end_of_this_vertex;
};
template
inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
num_edges(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
return g.base().m_forward.m_column.size();
}
template
std::pair
edges(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor Vertex;
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator ei;
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
if (g.base().m_forward.m_rowstart.size() == 1 ||
g.base().m_forward.m_column.empty()) {
return std::make_pair(ei(), ei());
} else {
// Find the first vertex that has outgoing edges
Vertex src = 0;
while (g.base().m_forward.m_rowstart[src + 1] == 0) ++src;
return std::make_pair(ei(g, edgedesc(src, 0), g.base().m_forward.m_rowstart[src + 1]),
ei(g, edgedesc(num_vertices(g), g.base().m_forward.m_column.size()), 0));
}
}
// -----------------------------------------------------------------
// Graph constructors
// Returns true if a vertex belongs to a process according to a distribution
template
struct local_vertex {
local_vertex(OwnerMap owner, ProcessId id)
: owner(owner), id(id) {}
template
bool operator()(Vertex x)
{ return get(owner, x) == id; }
template
bool operator()(Vertex x) const
{ return get(owner, x) == id; }
private:
OwnerMap owner;
ProcessId id;
};
// Returns true if a vertex belongs to a process according to a distribution
template
struct local_edge {
local_edge(OwnerMap owner, ProcessId id)
: owner(owner), id(id) {}
template
bool operator()(std::pair& x)
{ return get(owner, x.first) == id; }
template
bool operator()(const std::pair& x) const
{ return get(owner, x.first) == id; }
private:
OwnerMap owner;
ProcessId id;
};
// Turns an index iterator into a vertex iterator
template
class index_to_vertex_iterator {
public:
typedef std::input_iterator_tag iterator_category;
typedef typename graph_traits::vertex_descriptor Vertex;
typedef std::pair value_type;
typedef const value_type& reference;
typedef const value_type* pointer;
typedef void difference_type;
index_to_vertex_iterator(IndexIterator index,
const Graph& g)
: index(index), g(g), current(to_edge(*index)) {}
reference operator*() { current = to_edge(*index); return current; }
pointer operator->() { current = to_edge(*index); return ¤t; }
index_to_vertex_iterator& operator++()
{
++index;
return *this;
}
index_to_vertex_iterator operator++(int)
{
index_to_vertex_iterator temp(*this);
++(*this);
return temp;
}
bool operator==(const index_to_vertex_iterator& other) const
{ return index == other.index; }
bool operator!=(const index_to_vertex_iterator& other) const
{ return !(*this == other); }
private:
value_type to_edge(const typename std::iterator_traits::value_type& x)
{ return std::make_pair(vertex(x.first, g), vertex(x.second, g)); }
IndexIterator index;
const Graph& g;
value_type current;
};
template
struct index_to_vertex_func {
typedef typename boost::graph_traits::vertex_descriptor vertex_descriptor;
typedef typename boost::graph_traits::vertices_size_type vertices_size_type;
typedef std::pair result_type;
typedef std::pair base_iterator_type;
index_to_vertex_func(const Distribution& dist, const Graph& g)
: dist(dist), g(g) {}
result_type operator()(const base_iterator_type& p) const
{
return std::make_pair(vertex(p.first, g), vertex(p.second, g));
}
private:
const Distribution& dist;
const Graph& g;
};
// NGE: This method only works with iterators that have a difference_type,
// the index_to_vertex_iterator class above is retained for compatibility
// with BGL generators which have no difference_type
template
boost::transform_iterator, IndexIterator>
make_index_to_vertex_iterator(IndexIterator it, const Distribution& dist,
const Graph& g) {
return boost::make_transform_iterator(
it, index_to_vertex_func(dist, g));
}
// Forward declaration of csr_vertex_owner_map
template class csr_vertex_owner_map;
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(edges_are_unsorted_t,
InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(parallel::block(m_process_group, numverts)),
m_base(edges_are_unsorted_global,
index_to_vertex_iterator(edge_begin, *this),
index_to_vertex_iterator(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(edges_are_unsorted_t,
InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(dist),
m_base(edges_are_unsorted_global,
index_to_vertex_iterator(edge_begin, *this),
index_to_vertex_iterator(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(edges_are_unsorted_t,
InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(parallel::block(m_process_group, numverts)),
m_base(edges_are_unsorted_global,
index_to_vertex_iterator(edge_begin, *this),
index_to_vertex_iterator(edge_end, *this),
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(edges_are_unsorted_t,
InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(dist),
m_base(edges_are_unsorted_global,
index_to_vertex_iterator(edge_begin, *this),
index_to_vertex_iterator(edge_end, *this),
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(edges_are_sorted_t,
InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
edges_size_type numedges, // This is not used as there is no appropriate BGL ctor
const ProcessGroup& pg,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(parallel::block(m_process_group, numverts)),
m_base(edges_are_sorted_global,
index_to_vertex_iterator(edge_begin, *this),
index_to_vertex_iterator(edge_end, *this),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
m_distribution.block_size(process_id(m_process_group), numverts),
prop)
{ }
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(edges_are_sorted_t,
InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(dist),
m_base(edges_are_sorted_global,
index_to_vertex_iterator(edge_begin, *this),
index_to_vertex_iterator(edge_end, *this),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
m_distribution.block_size(process_id(m_process_group), numverts),
prop)
{ }
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(edges_are_sorted_t,
InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
edges_size_type numedges, // This is not used as there is no appropriate BGL ctor
const ProcessGroup& pg,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(parallel::block(m_process_group, numverts)),
m_base(edges_are_sorted_global,
index_to_vertex_iterator(edge_begin, *this),
index_to_vertex_iterator(edge_end, *this),
ep_iter,
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
m_distribution.block_size(process_id(m_process_group), numverts),
prop)
{ }
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(edges_are_sorted_t,
InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(dist),
m_base(edges_are_sorted_global,
index_to_vertex_iterator(edge_begin, *this),
index_to_vertex_iterator(edge_end, *this),
ep_iter,
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
m_distribution.block_size(process_id(m_process_group), numverts),
prop)
{ }
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(parallel::block(m_process_group, numverts)),
m_base(edges_are_unsorted_multi_pass_global,
make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this),
make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(dist),
m_base(edges_are_unsorted_multi_pass_global,
make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this),
make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(parallel::block(m_process_group, numverts)),
m_base(edges_are_unsorted_multi_pass_global,
make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this),
make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(dist),
m_base(edges_are_unsorted_multi_pass_global,
make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this),
make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
std::vector& sources,
std::vector& targets,
vertices_size_type numverts,
const ProcessGroup& pg,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(parallel::block(m_process_group, numverts)),
m_base(m_distribution.block_size(process_id(m_process_group), numverts))
{
// Convert linear indices to global indices
for (edges_size_type i = 0; i < sources.size(); ++i) {
sources[i] = m_distribution.local(sources[i]);
targets[i] = make_vertex_descriptor(m_distribution(targets[i]),
m_distribution.local(targets[i]));
}
m_base.assign_sources_and_targets_global(
sources, targets, m_distribution.block_size(process_id(m_process_group), numverts),
identity_property_map());
// TODO: set property on m_base?
}
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
std::vector& sources,
std::vector& targets,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(dist),
m_base(m_distribution.block_size(process_id(m_process_group), numverts))
{
// Convert linear indices to global indices
for (edges_size_type i = 0; i < sources.size(); ++i) {
sources[i] = m_distribution.local(sources[i]);
targets[i] = make_vertex_descriptor(m_distribution(targets[i]),
m_distribution.local(targets[i]));
}
m_base.assign_sources_and_targets_global(
sources, targets, m_distribution.block_size(process_id(m_process_group), numverts),
identity_property_map());
// TODO: set property on m_base?
}
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
std::vector& sources,
std::vector& targets,
std::vector& edge_props,
vertices_size_type numverts,
const ProcessGroup& pg,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(parallel::block(m_process_group, numverts)),
m_base(m_distribution.block_size(process_id(m_process_group), numverts))
{
// Convert linear indices to global indices
for (edges_size_type i = 0; i < sources.size(); ++i) {
sources[i] = m_distribution.local(sources[i]);
targets[i] = make_vertex_descriptor(m_distribution(targets[i]),
m_distribution.local(targets[i]));
}
m_base.assign_sources_and_targets_global(
sources, targets, edge_props,
m_distribution.block_size(process_id(m_process_group), numverts),
identity_property_map());
// TODO: set property on m_base?
}
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
std::vector& sources,
std::vector& targets,
std::vector& edge_props,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(dist),
m_base(m_distribution.block_size(process_id(m_process_group), numverts))
{
// Convert linear indices to global indices
for (edges_size_type i = 0; i < sources.size(); ++i) {
sources[i] = m_distribution.local(sources[i]);
targets[i] = make_vertex_descriptor(m_distribution(targets[i]),
m_distribution.local(targets[i]));
}
m_base.assign_sources_and_targets_global(
sources, targets, edge_props,
m_distribution.block_size(process_id(m_process_group), numverts),
identity_property_map());
// TODO: set property on m_base?
}
//
// Old (untagged) ctors, these default to the unsorted sequential ctors
//
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(parallel::block(m_process_group, numverts)),
m_base(edges_are_unsorted_global,
index_to_vertex_iterator(edge_begin, *this),
index_to_vertex_iterator(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{
}
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(parallel::block(m_process_group, numverts)),
m_base(edges_are_unsorted_global,
index_to_vertex_iterator(edge_begin, *this),
index_to_vertex_iterator(edge_end, *this),
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{
}
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(dist),
m_base(edges_are_unsorted_global,
index_to_vertex_iterator(edge_begin, *this),
index_to_vertex_iterator(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{
}
template
template
BOOST_DISTRIB_CSR_GRAPH_TYPE::
compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const ProcessGroup& pg,
const Distribution& dist,
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(dist),
m_base(edges_are_unsorted_global,
index_to_vertex_iterator(edge_begin, *this),
index_to_vertex_iterator(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
local_vertex,
process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{
}
// -----------------------------------------------------------------
// Vertex Global Property Map
template
class csr_vertex_global_map
{
public:
// -----------------------------------------------------------------
// Readable Property Map concept requirements
typedef std::pair value_type;
typedef value_type reference;
typedef Key key_type;
typedef readable_property_map_tag category;
};
template
inline std::pair
get(csr_vertex_global_map,
typename csr_vertex_global_map::key_type k)
{
const int local_index_bits = sizeof(Key) * CHAR_BIT - processor_bits;
const Key local_index_mask = Key(-1) >> processor_bits;
return std::pair(k >> local_index_bits,
k & local_index_mask);
}
template
class property_map
{
public:
typedef csr_vertex_global_map<
typename ProcessGroup::process_id_type,
typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor> type;
typedef type const_type;
};
template
inline
typename property_map::type
get(vertex_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
typedef typename property_map
::type result_type;
return result_type();
}
template
inline
std::pair
get(vertex_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
{
return get(vertex_global,
const_cast(g),
k);
}
template
inline
typename property_map::const_type
get(vertex_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
typedef typename property_map
::const_type result_type;
return result_type();
}
template
inline
std::pair
get(vertex_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
{
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
vertex_descriptor;
typedef std::pair
result_type;
const int local_index_bits =
sizeof(vertex_descriptor) * CHAR_BIT - processor_bits;
const vertex_descriptor local_index_mask =
vertex_descriptor(-1) >> processor_bits;
return result_type(k >> local_index_bits, k & local_index_mask);
}
// -----------------------------------------------------------------
// Extra, common functions
template
inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
vertex(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type i,
const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
return g.make_vertex_descriptor(g.distribution()(i),
g.distribution().local(i));
}
// Unlike for an adjacency_matrix, edge_range and edge take lg(out_degree(i))
// time
template
inline std::pair
edge_range(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor i,
typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor j,
const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor Vertex;
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type EdgeIndex;
typedef typename std::vector::const_iterator adj_iter;
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor edge_desc;
std::pair raw_adjacencies = adjacent_vertices(i, g);
std::pair adjacencies =
std::equal_range(raw_adjacencies.first, raw_adjacencies.second, j);
EdgeIndex idx_begin = adjacencies.first - g.base().m_forward.m_column.begin();
EdgeIndex idx_end = adjacencies.second - g.base().m_forward.m_column.begin();
return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)),
out_edge_iter(edge_desc(i, idx_end)));
}
template
inline std::pair
edge(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor i,
typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor j,
const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
std::pair range = edge_range(i, j, g);
if (range.first == range.second)
return std::make_pair(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor(),
false);
else
return std::make_pair(*range.first, true);
}
// A helper that turns requests for property maps for const graphs
// into property maps for non-const graphs.
template
class property_map
{
public:
typedef typename property_map
::const_type type;
typedef type const_type;
};
// -----------------------------------------------------------------
// Structural modifiers
#if 0
template
typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
add_vertex(BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{ return g.add_vertex(); }
template
typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
add_vertex(const typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_bundled& p,
BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{ return g.add_vertex(p); }
template
typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
add_vertices(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type count,
BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{ return g.add_vertices(count); }
template
void
add_edges(InputIterator first, InputIterator last,
BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{ g.add_edges(first, last); }
template
void
add_edges(InputIterator first, InputIterator last,
EdgePropertyIterator ep_iter,
EdgePropertyIterator ep_iter_end,
BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{ return g.add_edges(first, last, ep_iter, ep_iter_end); }
template
void
add_edges_sorted(InputIterator first, InputIterator last,
BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{ return g.add_edges_sorted(first, last); }
template
void
add_edges_sorted(InputIterator first_sorted, InputIterator last_sorted,
EdgePropertyIterator ep_iter_sorted,
BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{ g.add_edges_sorted(first_sorted, last_sorted, ep_iter_sorted); }
#endif
// -----------------------------------------------------------------
// Vertex Owner Property Map
template
class csr_vertex_owner_map
{
public:
// -----------------------------------------------------------------
// Readable Property Map concept requirements
typedef ProcessID value_type;
typedef value_type reference;
typedef Key key_type;
typedef readable_property_map_tag category;
};
template
inline ProcessID
get(csr_vertex_owner_map pm,
typename csr_vertex_owner_map::key_type k)
{
const int local_index_bits = sizeof(Key) * CHAR_BIT - processor_bits;
return k >> local_index_bits;
}
template
class property_map
{
public:
typedef csr_vertex_owner_map<
typename ProcessGroup::process_id_type,
typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor> type;
typedef type const_type;
};
template
inline
typename property_map::type
get(vertex_owner_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
typedef typename property_map
::type result_type;
return result_type();
}
template
inline typename ProcessGroup::process_id_type
get(vertex_owner_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
{
return get(vertex_owner,
const_cast(g),
k);
}
template
inline
typename property_map::const_type
get(vertex_owner_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
typedef typename property_map
::const_type result_type;
return result_type();
}
template