Subject: [Boost-commit] svn:boost r54751 - in branches/release: boost/graph/distributed libs/graph_parallel/test
From: jewillco_at_[hidden]
Date: 2009-07-06 22:52:16
Author: jewillco
Date: 2009-07-06 22:52:15 EDT (Mon, 06 Jul 2009)
New Revision: 54751
URL: http://svn.boost.org/trac/boost/changeset/54751
Log:
Merged in comments 59-61 from #3134, plus other changes; all merges for 1.40 should be done now; closes #3134
Added:
branches/release/libs/graph_parallel/test/distributed_st_connected_test.cpp
- copied unchanged from r54750, /trunk/libs/graph_parallel/test/distributed_st_connected_test.cpp
Text files modified:
branches/release/boost/graph/distributed/betweenness_centrality.hpp | 24 -
branches/release/boost/graph/distributed/compressed_sparse_row_graph.hpp | 835 +++++++++++++++++++++++++++++++++++++++
branches/release/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp | 12
branches/release/boost/graph/distributed/st_connected.hpp | 6
branches/release/libs/graph_parallel/test/CMakeLists.txt | 1
branches/release/libs/graph_parallel/test/Jamfile.v2 | 1
branches/release/libs/graph_parallel/test/algorithm_performance.cpp | 12
branches/release/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp | 11
branches/release/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp | 4
branches/release/libs/graph_parallel/test/distributed_dimacs_reader.cpp | 1
branches/release/libs/graph_parallel/test/ssca.cpp | 3
11 files changed, 871 insertions(+), 39 deletions(-)
Modified: branches/release/boost/graph/distributed/betweenness_centrality.hpp
==============================================================================
--- branches/release/boost/graph/distributed/betweenness_centrality.hpp (original)
+++ branches/release/boost/graph/distributed/betweenness_centrality.hpp 2009-07-06 22:52:15 EDT (Mon, 06 Jul 2009)
@@ -79,30 +79,6 @@
} // serialization
- namespace graph { namespace distributed {
-
- // HACKY: Overload get on a tuple to return the value at the key indicated
- // by the first element of the tuple so that we can use tuples in a distributed queue
- template<typename PropertyMap, typename Vertex, typename X, typename Y, typename Z>
- inline
- typename PropertyMap::value_type
- get(PropertyMap& pm, boost::tuple<Vertex, X, Y, Z> const& t)
- {
- return get(pm, boost::tuples::get<0>(t));
- }
-
- // HACKY: Same as above for std::pair
- template<typename PropertyMap, typename Vertex, typename X>
- inline
- typename PropertyMap::value_type
- get(PropertyMap& pm, std::pair<Vertex, X> const& t)
- {
- return get(pm, t.first);
- }
-
- } } // graph::distributed
-
-
template <typename OwnerMap, typename Tuple>
class get_owner_of_first_tuple_element {
Modified: branches/release/boost/graph/distributed/compressed_sparse_row_graph.hpp
==============================================================================
--- branches/release/boost/graph/distributed/compressed_sparse_row_graph.hpp (original)
+++ branches/release/boost/graph/distributed/compressed_sparse_row_graph.hpp 2009-07-06 22:52:15 EDT (Mon, 06 Jul 2009)
@@ -17,6 +17,8 @@
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
#endif
+#define BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
#include <boost/graph/compressed_sparse_row_graph.hpp>
#include <boost/graph/distributed/selector.hpp>
#include <boost/mpl/if.hpp>
@@ -29,6 +31,11 @@
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;
@@ -142,6 +149,181 @@
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 <typename Distribution>
+ 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 <typename Distribution>
+ 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) {}
+
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
+ template <typename InputIterator>
+ 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 <typename InputIterator, typename Distribution>
+ 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 <typename InputIterator, typename EdgePropertyIterator>
+ 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 <typename InputIterator, typename EdgePropertyIterator,
+ typename Distribution>
+ 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 <typename InputIterator>
+ 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 <typename InputIterator, typename Distribution>
+ 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 <typename InputIterator, typename EdgePropertyIterator>
+ 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 <typename InputIterator, typename EdgePropertyIterator,
+ typename Distribution>
+ 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 <typename MultiPassInputIterator>
+ 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 <typename MultiPassInputIterator, typename Distribution>
+ 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 <typename MultiPassInputIterator, typename EdgePropertyIterator>
+ 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 <typename MultiPassInputIterator, typename EdgePropertyIterator,
+ typename Distribution>
+ 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 <typename Source>
+ compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
+ std::vector<Source>& sources,
+ std::vector<vertex_descriptor>& targets,
+ vertices_size_type numverts,
+ const ProcessGroup& pg = ProcessGroup(),
+ const GraphProperty& prop = GraphProperty());
+
+ template <typename Distribution, typename Source>
+ compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
+ std::vector<Source>& sources,
+ std::vector<vertex_descriptor>& targets,
+ vertices_size_type numverts,
+ const ProcessGroup& pg,
+ const Distribution& dist,
+ const GraphProperty& prop = GraphProperty());
+
+ template <typename Source>
+ compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
+ std::vector<Source>& sources,
+ std::vector<vertex_descriptor>& targets,
+ std::vector<edge_bundled>& edge_props,
+ vertices_size_type numverts,
+ const ProcessGroup& pg = ProcessGroup(),
+ const GraphProperty& prop = GraphProperty());
+
+ template <typename Distribution, typename Source>
+ compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
+ std::vector<Source>& sources,
+ std::vector<vertex_descriptor>& targets,
+ std::vector<edge_bundled>& edge_props,
+ vertices_size_type numverts,
+ const ProcessGroup& pg,
+ const Distribution& dist,
+ const GraphProperty& prop = GraphProperty());
+
+#endif
+
template<typename InputIterator>
compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
@@ -223,6 +405,57 @@
return make_vertex_descriptor(process_id(m_process_group), v);
}
+ // Structural modification
+ vertex_descriptor add_vertex()
+ {
+ typename graph_traits<base_type>::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<base_type>::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<base_type>::vertex_descriptor v
+ = boost::add_vertices(count, m_base);
+
+ return make_vertex_descriptor(process_id(m_process_group), v);
+ }
+
+ template <typename InputIterator>
+ void
+ add_edges(InputIterator first, InputIterator last)
+ { boost::add_edges_global(first, last, get(vertex_local, *this), m_base); }
+
+ template <typename InputIterator, typename EdgePropertyIterator>
+ 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 <typename InputIterator>
+ void
+ add_edges_sorted(InputIterator first, InputIterator last)
+ { boost::add_edges_sorted_global(first, last,
+ get(vertex_local, *this), m_base); }
+
+ template <typename InputIterator, typename EdgePropertyIterator>
+ 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;
@@ -471,6 +704,501 @@
// -----------------------------------------------------------------
// Graph constructors
+
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+// Returns true if a vertex belongs to a process according to a distribution
+template <typename OwnerMap, typename ProcessId>
+struct local_edge {
+
+ local_edge(OwnerMap owner, ProcessId id)
+ : owner(owner), id(id) {}
+
+ template <typename Vertex>
+ bool operator()(std::pair<Vertex, Vertex>& x)
+ { return get(owner, x.first) == id; }
+
+ template <typename Vertex>
+ bool operator()(const std::pair<Vertex, Vertex>& x) const
+ { return get(owner, x.first) == id; }
+
+private:
+ OwnerMap owner;
+ ProcessId id;
+};
+
+// Turns an index iterator into a vertex iterator
+template<typename IndexIterator, typename Graph>
+class index_to_vertex_iterator {
+
+public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef std::pair<Vertex, Vertex> 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<IndexIterator>::value_type& x)
+ { return std::make_pair(vertex(x.first, g), vertex(x.second, g)); }
+
+ IndexIterator index;
+ const Graph& g;
+ value_type current;
+};
+
+template <typename Distribution, typename Graph>
+struct index_to_vertex_func {
+
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+ typedef typename boost::graph_traits<Graph>::vertices_size_type vertices_size_type;
+ typedef std::pair<vertex_descriptor, vertex_descriptor> result_type;
+ typedef std::pair<vertices_size_type, vertices_size_type> 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 <typename IndexIterator, typename Distribution, typename Graph>
+boost::transform_iterator<index_to_vertex_func<Distribution, Graph>, IndexIterator>
+make_index_to_vertex_iterator(IndexIterator it, const Distribution& dist,
+ const Graph& g) {
+ return boost::make_transform_iterator(
+ it, index_to_vertex_func<Distribution, Graph>(dist, g));
+}
+#endif
+
+// Forward declaration of csr_vertex_owner_map
+template<typename ProcessID, typename Key> class csr_vertex_owner_map;
+
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template<typename InputIterator>
+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<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
+ m_distribution.block_size(process_id(m_process_group), numverts),
+ get(vertex_local, *this),
+ local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ prop)
+{ }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template <typename InputIterator, typename Distribution>
+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<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
+ m_distribution.block_size(process_id(m_process_group), numverts),
+ get(vertex_local, *this),
+ local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ prop)
+{ }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template<typename InputIterator, typename EdgePropertyIterator>
+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<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
+ ep_iter,
+ m_distribution.block_size(process_id(m_process_group), numverts),
+ get(vertex_local, *this),
+ local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ prop)
+{ }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template <typename InputIterator, typename EdgePropertyIterator,
+ typename Distribution>
+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<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
+ ep_iter,
+ m_distribution.block_size(process_id(m_process_group), numverts),
+ get(vertex_local, *this),
+ local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ prop)
+{ }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template<typename InputIterator>
+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<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
+ get(vertex_local, *this),
+ local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ m_distribution.block_size(process_id(m_process_group), numverts),
+ prop)
+{ }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template <typename InputIterator, typename Distribution>
+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<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
+ get(vertex_local, *this),
+ local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ m_distribution.block_size(process_id(m_process_group), numverts),
+ prop)
+{ }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template<typename InputIterator, typename EdgePropertyIterator>
+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<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
+ ep_iter,
+ get(vertex_local, *this),
+ local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ m_distribution.block_size(process_id(m_process_group), numverts),
+ prop)
+{ }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template<typename InputIterator, typename EdgePropertyIterator,
+ typename Distribution>
+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<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
+ ep_iter,
+ get(vertex_local, *this),
+ local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ m_distribution.block_size(process_id(m_process_group), numverts),
+ prop)
+{ }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template<typename MultiPassInputIterator>
+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_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ prop)
+{ }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template <typename MultiPassInputIterator, typename Distribution>
+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_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ prop)
+{ }
+
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template<typename MultiPassInputIterator, typename EdgePropertyIterator>
+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_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ prop)
+{ }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template <typename MultiPassInputIterator, typename EdgePropertyIterator,
+ typename Distribution>
+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_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ prop)
+{ }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template<typename Source>
+BOOST_DISTRIB_CSR_GRAPH_TYPE::
+compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
+ std::vector<Source>& sources,
+ std::vector<vertex_descriptor>& 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<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template <typename Distribution, typename Source>
+BOOST_DISTRIB_CSR_GRAPH_TYPE::
+compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
+ std::vector<Source>& sources,
+ std::vector<vertex_descriptor>& 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<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template<typename Source>
+BOOST_DISTRIB_CSR_GRAPH_TYPE::
+compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
+ std::vector<Source>& sources,
+ std::vector<vertex_descriptor>& targets,
+ std::vector<edge_bundled>& 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<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+template <typename Distribution, typename Source>
+BOOST_DISTRIB_CSR_GRAPH_TYPE::
+compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
+ std::vector<Source>& sources,
+ std::vector<vertex_descriptor>& targets,
+ std::vector<edge_bundled>& 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?
+}
+
+#endif
+
+//
+// Old (untagged) ctors, these default to the unsorted sequential ctors
+//
template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
template<typename InputIterator>
BOOST_DISTRIB_CSR_GRAPH_TYPE::
@@ -480,8 +1208,21 @@
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(parallel::block(m_process_group, numverts)),
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
m_base(m_distribution.block_size(process_id(m_process_group), numverts))
+#else
+ m_base(edges_are_unsorted_global,
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
+ m_distribution.block_size(process_id(m_process_group), numverts),
+ get(vertex_local, *this),
+ local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ prop)
+#endif
+
{
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
parallel::block dist(m_process_group, numverts);
// Allows us to add edges
@@ -499,6 +1240,7 @@
}
++edge_begin;
}
+#endif
}
template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
@@ -510,9 +1252,23 @@
const ProcessGroup& pg,
const GraphProperty& prop)
: m_process_group(pg),
+
m_distribution(parallel::block(m_process_group, numverts)),
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
m_base(m_distribution.block_size(process_id(m_process_group), numverts))
+#else
+ m_base(edges_are_unsorted_global,
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
+ ep_iter,
+ m_distribution.block_size(process_id(m_process_group), numverts),
+ get(vertex_local, *this),
+ local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ prop)
+#endif
{
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
parallel::block dist(m_process_group, numverts);
// Allows us to add edges
@@ -526,12 +1282,12 @@
EdgeIndex tgt =
make_vertex_descriptor(dist(edge_begin->second),
dist.local(edge_begin->second));
-
add_edge(dist.local(src), tgt, *ep_iter, m_base);
}
++edge_begin;
++ep_iter;
}
+#endif
}
template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
@@ -544,8 +1300,20 @@
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(dist),
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
m_base(dist.block_size(process_id(m_process_group), numverts))
+#else
+ m_base(edges_are_unsorted_global,
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
+ m_distribution.block_size(process_id(m_process_group), numverts),
+ get(vertex_local, *this),
+ local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ prop)
+#endif
{
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Allows us to add edges
m_base.m_last_source = 0;
@@ -563,6 +1331,7 @@
}
++edge_begin;
}
+#endif
}
template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
@@ -577,8 +1346,20 @@
const GraphProperty& prop)
: m_process_group(pg),
m_distribution(dist),
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
m_base(dist.block_size(process_id(m_process_group), numverts))
+#else
+ m_base(edges_are_unsorted_global,
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
+ index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
+ m_distribution.block_size(process_id(m_process_group), numverts),
+ get(vertex_local, *this),
+ local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ prop)
+#endif
{
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Allows us to add edges
m_base.m_last_source = 0;
@@ -595,6 +1376,7 @@
++edge_begin;
++ep_iter;
}
+#endif
}
// -----------------------------------------------------------------
@@ -745,6 +1527,57 @@
};
// -----------------------------------------------------------------
+// Structural modifiers
+
+#if 0
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
+add_vertex(BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
+{ return g.add_vertex(); }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+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<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
+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<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
+void
+add_edges(InputIterator first, InputIterator last,
+ BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
+{ g.add_edges(first, last); }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
+ typename EdgePropertyIterator>
+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<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
+void
+add_edges_sorted(InputIterator first, InputIterator last,
+ BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
+{ return g.add_edges_sorted(first, last); }
+
+template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
+ typename EdgePropertyIterator>
+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<typename ProcessID, typename Key>
class csr_vertex_owner_map
Modified: branches/release/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp
==============================================================================
--- branches/release/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp (original)
+++ branches/release/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp 2009-07-06 22:52:15 EDT (Mon, 06 Jul 2009)
@@ -113,10 +113,20 @@
boost::parallel::caching_property_map<PredecessorMap> c_pred(m_predecessor);
boost::parallel::caching_property_map<DistanceMap> c_dist(m_distance);
+ distance_type old_distance = get(c_dist, target(e, g));
+
bool m_decreased = relax(e, g, m_weight, c_pred, c_dist,
m_combine, m_compare);
- if (m_decreased) {
+ /* On x86 Linux with optimization, we sometimes get into a
+ horrible case where m_decreased is true but the distance hasn't
+ actually changed. This occurs when the comparison inside
+ relax() occurs with the 80-bit precision of the x87 floating
+ point unit, but the difference is lost when the resulting
+ values are written back to lower-precision memory (e.g., a
+ double). With the eager Dijkstra's implementation, this results
+ in looping. */
+ if (m_decreased && old_distance != get(c_dist, target(e, g))) {
m_Q.update(target(e, g));
m_vis.edge_relaxed(e, g);
} else
Modified: branches/release/boost/graph/distributed/st_connected.hpp
==============================================================================
--- branches/release/boost/graph/distributed/st_connected.hpp (original)
+++ branches/release/boost/graph/distributed/st_connected.hpp 2009-07-06 22:52:15 EDT (Mon, 06 Jul 2009)
@@ -15,7 +15,7 @@
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/two_bit_color_map.hpp>
-#include <boost/graph/parallel/distributed_queue.hpp>
+#include <boost/graph/distributed/queue.hpp>
#include <boost/pending/queue.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/parallel/container_traits.hpp>
@@ -46,8 +46,8 @@
typename graph_traits<DistributedGraph>::vertex_descriptor t,
ColorMap color, OwnerMap owner)
{
- using boost::parallel::process_group;
- using boost::parallel::process_group_type;
+ using boost::graph::parallel::process_group;
+ using boost::graph::parallel::process_group_type;
using boost::parallel::all_reduce;
typedef typename property_traits<ColorMap>::value_type Color;
Modified: branches/release/libs/graph_parallel/test/CMakeLists.txt
==============================================================================
--- branches/release/libs/graph_parallel/test/CMakeLists.txt (original)
+++ branches/release/libs/graph_parallel/test/CMakeLists.txt 2009-07-06 22:52:15 EDT (Mon, 06 Jul 2009)
@@ -87,6 +87,7 @@
boost_graph_parallel_test(distributed_rmat_cc_ps)
boost_graph_parallel_test(distributed_rmat_cc)
boost_graph_parallel_test(distributed_rmat_pagerank)
+ boost_graph_parallel_test(distributed_st_connected_test)
boost_add_executable(ssca
ssca.cpp
Modified: branches/release/libs/graph_parallel/test/Jamfile.v2
==============================================================================
--- branches/release/libs/graph_parallel/test/Jamfile.v2 (original)
+++ branches/release/libs/graph_parallel/test/Jamfile.v2 2009-07-06 22:52:15 EDT (Mon, 06 Jul 2009)
@@ -41,6 +41,7 @@
[ mpi-test distributed_rmat_cc_ps : : : 2 ]
[ mpi-test distributed_rmat_cc : : : 2 ]
[ mpi-test distributed_rmat_pagerank : : : 2 ]
+ [ mpi-test distributed_st_connected_test : : : 2 ]
;
}
Modified: branches/release/libs/graph_parallel/test/algorithm_performance.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/algorithm_performance.cpp (original)
+++ branches/release/libs/graph_parallel/test/algorithm_performance.cpp 2009-07-06 22:52:15 EDT (Mon, 06 Jul 2009)
@@ -359,7 +359,8 @@
typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
seqGraph;
- seqGraph sg(sorted_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
+ seqGraph sg(edges_are_sorted,
+ sorted_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
sorted_rmat_iterator<RandomGenerator, seqGraph>(),
make_generator_iterator(gen, uniform_int<int>(1, C)),
N);
@@ -394,7 +395,8 @@
typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
seqGraph;
- seqGraph sg(sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
+ seqGraph sg(edges_are_sorted,
+ sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(),
make_generator_iterator(gen, uniform_int<int>(1, C)),
N);
@@ -428,7 +430,8 @@
typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
seqGraph;
- seqGraph sg(sorted_erdos_renyi_iterator<RandomGenerator, seqGraph>(gen, N, _p/2),
+ seqGraph sg(edges_are_sorted,
+ sorted_erdos_renyi_iterator<RandomGenerator, seqGraph>(gen, N, _p/2),
sorted_erdos_renyi_iterator<RandomGenerator, seqGraph>(),
make_generator_iterator(gen, uniform_int<int>(1, C)),
N);
@@ -463,7 +466,8 @@
typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
seqGraph;
- seqGraph sg(small_world_iterator<RandomGenerator, seqGraph>(gen, N, k, p),
+ seqGraph sg(edges_are_sorted,
+ small_world_iterator<RandomGenerator, seqGraph>(gen, N, k, p),
small_world_iterator<RandomGenerator, seqGraph>(),
make_generator_iterator(gen, uniform_int<int>(1, C)),
N);
Modified: branches/release/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp (original)
+++ branches/release/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp 2009-07-06 22:52:15 EDT (Mon, 06 Jul 2009)
@@ -96,9 +96,7 @@
typedef int weight_type;
struct WeightedEdge {
- WeightedEdge(weight_type weight = 1) : weight(weight) { }
-
- void operator=(weight_type x) { weight = x; }
+ WeightedEdge(weight_type weight = 0) : weight(weight) { }
weight_type weight;
@@ -130,6 +128,7 @@
property<edge_weight_t, int> > seqGraph;
#endif
+
typedef sorted_erdos_renyi_iterator<minstd_rand, Graph> ERIter;
typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
@@ -152,7 +151,11 @@
gen.seed(1); // Re-seed PRNG so we get the same graph
- seqGraph sg(edges_are_sorted, ERIter(gen, n, prob), ERIter(),
+ seqGraph sg(
+#ifdef CSR
+ edges_are_sorted,
+#endif
+ ERIter(gen, n, prob), ERIter(),
make_generator_iterator(gen, uniform_int<int>(1, C)),
n);
Modified: branches/release/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp (original)
+++ branches/release/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp 2009-07-06 22:52:15 EDT (Mon, 06 Jul 2009)
@@ -29,6 +29,7 @@
#include <boost/graph/strong_components.hpp>
#include <boost/graph/distributed/betweenness_centrality.hpp>
#include <boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp>
+#include <boost/graph/distributed/st_connected.hpp>
#if 0 // Contains internal AdjList types not present in CSR graph
# include <boost/graph/distributed/connected_components_parallel_search.hpp>
@@ -299,6 +300,9 @@
get(vertex_index, g));
#endif
+ // Test S-T Connected
+ st_connected(g, vertex(0, g), vertex(1, g), color, get(vertex_owner, g));
+
// Test Connected Components
//
// CC requires an undirected graph, currently CSR graphs must be directed
Modified: branches/release/libs/graph_parallel/test/distributed_dimacs_reader.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_dimacs_reader.cpp (original)
+++ branches/release/libs/graph_parallel/test/distributed_dimacs_reader.cpp 2009-07-06 22:52:15 EDT (Mon, 06 Jul 2009)
@@ -54,7 +54,6 @@
test_dimacs_reader(const char *filename)
{
mpi_process_group pg;
- mpi_process_group::process_id_type id = process_id(pg);
typedef adjacency_list<vecS,
distributedS<mpi_process_group, vecS>,
Modified: branches/release/libs/graph_parallel/test/ssca.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/ssca.cpp (original)
+++ branches/release/libs/graph_parallel/test/ssca.cpp 2009-07-06 22:52:15 EDT (Mon, 06 Jul 2009)
@@ -616,7 +616,8 @@
time_type start = get_time();
#ifdef CSR
- seqGraph sg(sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, n, m, a, b, c, d),
+ seqGraph sg(edges_are_sorted,
+ sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, n, m, a, b, c, d),
sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(),
make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)),
n);