summaryrefslogtreecommitdiffstats
path: root/src/boost/libs/graph_parallel
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-27 18:24:20 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-27 18:24:20 +0000
commit483eb2f56657e8e7f419ab1a4fab8dce9ade8609 (patch)
treee5d88d25d870d5dedacb6bbdbe2a966086a0a5cf /src/boost/libs/graph_parallel
parentInitial commit. (diff)
downloadceph-483eb2f56657e8e7f419ab1a4fab8dce9ade8609.tar.xz
ceph-483eb2f56657e8e7f419ab1a4fab8dce9ade8609.zip
Adding upstream version 14.2.21.upstream/14.2.21upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/boost/libs/graph_parallel')
-rw-r--r--src/boost/libs/graph_parallel/build/Jamfile.v243
-rw-r--r--src/boost/libs/graph_parallel/example/Jamfile.v214
-rw-r--r--src/boost/libs/graph_parallel/example/breadth_first_search.cpp111
-rw-r--r--src/boost/libs/graph_parallel/example/dijkstra_shortest_paths.cpp98
-rw-r--r--src/boost/libs/graph_parallel/index.html20
-rw-r--r--src/boost/libs/graph_parallel/meta/libraries.json16
-rw-r--r--src/boost/libs/graph_parallel/src/mpi_process_group.cpp1113
-rw-r--r--src/boost/libs/graph_parallel/src/tag_allocator.cpp45
-rw-r--r--src/boost/libs/graph_parallel/test/Jamfile.v247
-rw-r--r--src/boost/libs/graph_parallel/test/adjlist_build_test.cpp245
-rw-r--r--src/boost/libs/graph_parallel/test/adjlist_redist_test.cpp216
-rw-r--r--src/boost/libs/graph_parallel/test/adjlist_remove_test.cpp146
-rw-r--r--src/boost/libs/graph_parallel/test/algorithm_performance.cpp887
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_adjacency_list_test.cpp284
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp295
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_connected_components_test.cpp204
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp369
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_csr_test.cpp103
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_dfs_test.cpp167
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_dimacs_reader.cpp85
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_graph_coloring_test.cpp101
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_mst_test.cpp151
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_page_rank_test.cpp110
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_property_map_test.cpp356
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_queue_test.cpp116
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_rmat_cc.cpp118
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_rmat_cc_ps.cpp117
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_rmat_pagerank.cpp113
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_shortest_paths_test.cpp214
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_st_connected_test.cpp85
-rw-r--r--src/boost/libs/graph_parallel/test/distributed_strong_components_test.cpp175
-rw-r--r--src/boost/libs/graph_parallel/test/hohberg_biconnected_components_test.cpp175
-rw-r--r--src/boost/libs/graph_parallel/test/mesh_generator_test.cpp133
-rw-r--r--src/boost/libs/graph_parallel/test/named_vertices_hash_test.cpp158
-rw-r--r--src/boost/libs/graph_parallel/test/named_vertices_seq.cpp91
-rw-r--r--src/boost/libs/graph_parallel/test/named_vertices_test.cpp121
-rw-r--r--src/boost/libs/graph_parallel/test/process_group_serialization.cpp58
-rw-r--r--src/boost/libs/graph_parallel/test/ssca.cpp1263
38 files changed, 8163 insertions, 0 deletions
diff --git a/src/boost/libs/graph_parallel/build/Jamfile.v2 b/src/boost/libs/graph_parallel/build/Jamfile.v2
new file mode 100644
index 00000000..5256fa78
--- /dev/null
+++ b/src/boost/libs/graph_parallel/build/Jamfile.v2
@@ -0,0 +1,43 @@
+# Copyright (c) 2002 Trustees of Indiana University
+#
+# Distributed under 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)
+
+import mpi ;
+
+project boost/graph_parallel
+ : requirements <include>../src
+ : source-location ../src
+ ;
+
+local optional_sources ;
+local optional_reqs ;
+
+if [ mpi.configured ]
+{
+ lib boost_graph_parallel
+ : mpi_process_group.cpp tag_allocator.cpp
+ : <library>../../mpi/build//boost_mpi
+ <library>/mpi//mpi [ mpi.extra-requirements ]
+ <define>BOOST_GRAPH_NO_LIB=1
+ <link>shared:<define>BOOST_GRAPH_DYN_LINK=1
+ # # Intel compiler ICEs if we turn optimization on
+ <toolset>intel-vc71-win-9.1:<optimization>off
+ # Without these flags, MSVC 7.1 crash
+ # User reports that VC++ 8 no longer has this problem
+ <toolset>msvc-7.1:<cxxflags>-GR-
+ <local-visibility>global
+ ;
+
+}
+else
+{
+ message boost_graph_parallel
+ : "warning: Graph library does not contain MPI-based parallel components."
+ : "note: to enable them, add \"using mpi ;\" to your user-config.jam."
+ : "note: to suppress this message, pass \"--without-graph_parallel\" to bjam."
+ ;
+}
+
+boost-install boost_graph_parallel ;
diff --git a/src/boost/libs/graph_parallel/example/Jamfile.v2 b/src/boost/libs/graph_parallel/example/Jamfile.v2
new file mode 100644
index 00000000..e8877757
--- /dev/null
+++ b/src/boost/libs/graph_parallel/example/Jamfile.v2
@@ -0,0 +1,14 @@
+# Copyright 2009 Vladimir Prus.
+#
+# Distributed under 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)
+
+
+project : requirements <library>../build//boost_graph_parallel
+ <library>../../system/build//boost_system
+ <library>../../mpi/build//boost_mpi
+ ;
+
+exe breadth_first_search : breadth_first_search.cpp ;
+exe dijkstra_shortest_paths : dijkstra_shortest_paths.cpp ;
diff --git a/src/boost/libs/graph_parallel/example/breadth_first_search.cpp b/src/boost/libs/graph_parallel/example/breadth_first_search.cpp
new file mode 100644
index 00000000..e1dbc985
--- /dev/null
+++ b/src/boost/libs/graph_parallel/example/breadth_first_search.cpp
@@ -0,0 +1,111 @@
+// Copyright (C) 2004-2008 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
+
+// Example usage of breadth_first_search algorithm
+
+// Enable PBGL interfaces to BGL algorithms
+#include <boost/graph/use_mpi.hpp>
+
+// Communicate via MPI
+#include <boost/graph/distributed/mpi_process_group.hpp>
+
+// Breadth-first search algorithm
+#include <boost/graph/breadth_first_search.hpp>
+
+// Distributed adjacency list
+#include <boost/graph/distributed/adjacency_list.hpp>
+
+// METIS Input
+#include <boost/graph/metis.hpp>
+
+// Graphviz Output
+#include <boost/graph/distributed/graphviz.hpp>
+
+// For choose_min_reducer
+#include <boost/graph/distributed/distributed_graph_utility.hpp>
+
+// Standard Library includes
+#include <fstream>
+#include <string>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+/* An undirected graph with distance values stored on the vertices. */
+typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, undirectedS,
+ /*Vertex properties=*/property<vertex_distance_t, std::size_t> >
+ Graph;
+
+int main(int argc, char* argv[])
+{
+ boost::mpi::environment env(argc,argv);
+
+ // Parse command-line options
+ const char* filename = "weighted_graph.gr";
+ if (argc > 1) filename = argv[1];
+
+ // Open the METIS input file
+ std::ifstream in(filename);
+ graph::metis_reader reader(in);
+
+ // Load the graph using the default distribution
+ Graph g(reader.begin(), reader.end(),
+ reader.num_vertices());
+
+ // Get vertex 0 in the graph
+ graph_traits<Graph>::vertex_descriptor start = vertex(0, g);
+
+ // Compute BFS levels from vertex 0
+ property_map<Graph, vertex_distance_t>::type distance =
+ get(vertex_distance, g);
+
+ // Initialize distances to infinity and set reduction operation to 'min'
+ BGL_FORALL_VERTICES(v, g, Graph) {
+ put(distance, v, (std::numeric_limits<std::size_t>::max)());
+ }
+ distance.set_reduce(boost::graph::distributed::choose_min_reducer<std::size_t>());
+
+ put(distance, start, 0);
+ breadth_first_search
+ (g, start,
+ visitor(make_bfs_visitor(record_distances(distance, on_tree_edge()))));
+
+ // Output a Graphviz DOT file
+ std::string outfile;
+
+ if (argc > 2)
+ outfile = argv[2];
+ else {
+ outfile = filename;
+ size_t i = outfile.rfind('.');
+ if (i != std::string::npos)
+ outfile.erase(outfile.begin() + i, outfile.end());
+ outfile += "-bfs.dot";
+ }
+
+ if (process_id(process_group(g)) == 0) {
+ std::cout << "Writing GraphViz output to " << outfile << "... ";
+ std::cout.flush();
+ }
+ write_graphviz(outfile, g,
+ make_label_writer(distance));
+ if (process_id(process_group(g)) == 0)
+ std::cout << "Done." << std::endl;
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/example/dijkstra_shortest_paths.cpp b/src/boost/libs/graph_parallel/example/dijkstra_shortest_paths.cpp
new file mode 100644
index 00000000..161271a4
--- /dev/null
+++ b/src/boost/libs/graph_parallel/example/dijkstra_shortest_paths.cpp
@@ -0,0 +1,98 @@
+// 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
+
+// Example usage of dijkstra_shortest_paths algorithm
+
+// Enable PBGL interfaces to BGL algorithms
+#include <boost/graph/use_mpi.hpp>
+
+// Communication via MPI
+#include <boost/graph/distributed/mpi_process_group.hpp>
+
+// Dijkstra's single-source shortest paths algorithm
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+
+// Distributed adjacency list
+#include <boost/graph/distributed/adjacency_list.hpp>
+
+// METIS Input
+#include <boost/graph/metis.hpp>
+
+// Graphviz Output
+#include <boost/graph/distributed/graphviz.hpp>
+
+// Standard Library includes
+#include <fstream>
+#include <string>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+/* An undirected, weighted graph with distance values stored on the
+ vertices. */
+typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, undirectedS,
+ /*Vertex properties=*/property<vertex_distance_t, float>,
+ /*Edge properties=*/property<edge_weight_t, float> >
+ Graph;
+
+int main(int argc, char* argv[])
+{
+ boost::mpi::environment env(argc,argv);
+
+ // Parse command-line options
+ const char* filename = "weighted_graph.gr";
+ if (argc > 1) filename = argv[1];
+
+ // Open the METIS input file
+ std::ifstream in(filename);
+ graph::metis_reader reader(in);
+
+ // Load the graph using the default distribution
+ Graph g(reader.begin(), reader.end(), reader.weight_begin(),
+ reader.num_vertices());
+
+ // Get vertex 0 in the graph
+ graph_traits<Graph>::vertex_descriptor start = vertex(0, g);
+
+ // Compute shortest paths from vertex 0
+ dijkstra_shortest_paths(g, start,
+ distance_map(get(vertex_distance, g)));
+
+ // Output a Graphviz DOT file
+ std::string outfile = filename;
+ if (argc > 2)
+ outfile = argv[2];
+ else {
+ size_t i = outfile.rfind('.');
+ if (i != std::string::npos)
+ outfile.erase(outfile.begin() + i, outfile.end());
+ outfile += "-dijkstra.dot";
+ }
+
+ if (process_id(process_group(g)) == 0) {
+ std::cout << "Writing GraphViz output to " << outfile << "... ";
+ std::cout.flush();
+ }
+ write_graphviz(outfile, g,
+ make_label_writer(get(vertex_distance, g)),
+ make_label_writer(get(edge_weight, g)));
+ if (process_id(process_group(g)) == 0)
+ std::cout << "Done." << std::endl;
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/index.html b/src/boost/libs/graph_parallel/index.html
new file mode 100644
index 00000000..611797da
--- /dev/null
+++ b/src/boost/libs/graph_parallel/index.html
@@ -0,0 +1,20 @@
+<html>
+<!--
+ Copyright (c) 2004-2009 Trustees of Indiana University
+
+ Distributed under 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)
+ -->
+<head>
+<meta http-equiv="refresh" content="0; URL=doc/html/index.html">
+</head>
+<body>
+Automatic redirection failed, please go to
+<a href="doc/html/index.html">doc/html/index.html</a>.
+<hr>
+<p>Distributed under the Boost Software License, Version 1.0. (See accompanying
+file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or copy
+at <a href="http://www.boost.org/LICENSE_1_0.txt">www.boost.org/LICENSE_1_0.txt</a>)</p>
+</body>
+</html>
diff --git a/src/boost/libs/graph_parallel/meta/libraries.json b/src/boost/libs/graph_parallel/meta/libraries.json
new file mode 100644
index 00000000..1cfb99a4
--- /dev/null
+++ b/src/boost/libs/graph_parallel/meta/libraries.json
@@ -0,0 +1,16 @@
+{
+ "key": "graph_parallel",
+ "name": "GraphParallel",
+ "authors": [
+ "Jeremy Siek, Doug Gregor, and a University of Notre Dame team."
+ ],
+ "description": "The PBGL graph interface and graph components are generic, in the same sense as the the Standard Template Library (STL).",
+ "category": [
+ "Algorithms",
+ "Containers",
+ "Iterators"
+ ],
+ "maintainers": [
+ "K. Noel Belcourt <kbelco -at- sandia.gov>"
+ ]
+}
diff --git a/src/boost/libs/graph_parallel/src/mpi_process_group.cpp b/src/boost/libs/graph_parallel/src/mpi_process_group.cpp
new file mode 100644
index 00000000..050b0f29
--- /dev/null
+++ b/src/boost/libs/graph_parallel/src/mpi_process_group.cpp
@@ -0,0 +1,1113 @@
+// Copyright (C) 2004-2006 The Trustees of Indiana University.
+// Copyright (C) 2007 Douglas Gregor <doug.gregor@gmail.com>
+// Copyright (C) 2007 Matthias Troyer <troyer@boost-consulting.com>
+
+// 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
+// Matthias Troyer
+#include <boost/assert.hpp>
+#include <boost/graph/use_mpi.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/serialization/vector.hpp>
+#include <boost/mpi/environment.hpp>
+#include <boost/lexical_cast.hpp>
+#include <memory>
+#include <algorithm>
+
+//#define DEBUG 1
+
+
+//#define MAX_BATCHES 1500
+#define PREALLOCATE_BATCHES 250
+// 500 is a better setting for PREALLOCATE_BATCHES if you're not using process
+// subgroups and are building 64-bit binaries. 250 allows all the CTest
+// tests to pass in both 32 and 64-bit modes. If you create multiple process
+// groups with PREALLOCATE_BATCHES at a reasonable level in 32-bit mode you
+// _will_ run out of memory and get "malloc failed" errors
+
+//#define NO_ISEND_BATCHES
+//#define NO_IMMEDIATE_PROCESSING
+//#define NO_SPLIT_BATCHES
+#define IRECV_BATCH
+
+// we cannot keep track of how many we received if we do not process them
+#ifdef NO_IMMEDIATE_PROCESSING
+#undef IRECV_BATCH
+#endif
+
+#ifdef DEBUG
+# include <iostream>
+#endif // DEBUG
+
+namespace boost { namespace graph { namespace distributed {
+
+struct mpi_process_group::deallocate_block
+{
+ explicit deallocate_block(blocks_type* blocks) : blocks(blocks) { }
+
+ void operator()(int* block_num)
+ {
+ block_type* block = (*blocks)[*block_num];
+
+ // Mark this block as inactive
+ (*blocks)[*block_num] = 0;
+
+#ifdef DEBUG
+ fprintf(stderr, "Processor %i deallocated block #%i\n",
+ boost::mpi::communicator().rank(), *block_num);
+#endif
+
+ // Delete the block and its block number
+ delete block_num;
+ delete block;
+ }
+
+private:
+ blocks_type* blocks;
+};
+
+mpi_process_group::impl::incoming_messages::incoming_messages()
+{
+ next_header.push_back(headers.begin());
+}
+
+mpi_process_group::impl::impl(std::size_t num_headers, std::size_t buffer_sz,
+ communicator_type parent_comm)
+ : comm(parent_comm, boost::mpi::comm_duplicate),
+ oob_reply_comm(parent_comm, boost::mpi::comm_duplicate),
+ allocated_tags(boost::mpi::environment::max_tag())
+{
+ max_sent=0;
+ max_received=0;
+ int n = comm.size();
+ outgoing.resize(n);
+ incoming.resize(n);
+
+ // no synchronization stage means -1
+ // to keep the convention
+ synchronizing_stage.resize(n,-1);
+ number_sent_batches.resize(n);
+ number_received_batches.resize(n);
+ trigger_context = trc_none;
+ processing_batches = 0;
+
+ // Allocator a placeholder block "0"
+ blocks.push_back(new block_type);
+
+ synchronizing = false;
+
+ set_batch_size(num_headers,buffer_sz);
+
+ for (int i = 0; i < n; ++i) {
+ incoming[i].next_header.front() = incoming[i].headers.end();
+ outgoing[i].buffer.reserve(batch_message_size);
+ }
+
+#ifdef PREALLOCATE_BATCHES
+ batch_pool.resize(PREALLOCATE_BATCHES);
+ for (std::size_t i = 0 ; i < batch_pool.size(); ++i) {
+ batch_pool[i].buffer.reserve(batch_message_size);
+ batch_pool[i].request=MPI_REQUEST_NULL;
+ free_batches.push(i);
+ }
+#endif
+}
+
+void mpi_process_group::impl::set_batch_size(std::size_t header_num, std::size_t buffer_sz)
+{
+ batch_header_number = header_num;
+ batch_buffer_size = buffer_sz;
+
+ // determine batch message size by serializing the largest possible batch
+ outgoing_messages msg;
+ msg.headers.resize(batch_header_number);
+ msg.buffer.resize(batch_buffer_size);
+ boost::mpi::packed_oarchive oa(comm);
+ oa << const_cast<const outgoing_messages&>(msg);
+ batch_message_size = oa.size();
+}
+
+
+mpi_process_group::impl::~impl()
+{
+ // Delete the placeholder "0" block
+ delete blocks.front();
+ if (!boost::mpi::environment::finalized())
+ for (std::vector<MPI_Request>::iterator it=requests.begin();
+ it != requests.end();++it)
+ MPI_Cancel(&(*it));
+}
+
+namespace detail {
+// global batch handlers
+void handle_batch (mpi_process_group const& self, int source, int,
+ mpi_process_group::outgoing_messages& batch,bool out_of_band)
+{
+#ifdef DEBUG
+ std::cerr << "Processing batch trigger\n";
+ std::cerr << "BATCH: " << process_id(self) << " <- " << source << " ("
+ << batch.headers.size() << " headers, "
+ << batch.buffer.size() << " bytes)"
+ << std::endl;
+#endif
+ // If we are not synchronizing, then this must be an early receive
+ trigger_receive_context old_context = self.impl_->trigger_context;
+ if (self.impl_->trigger_context != trc_in_synchronization)
+ self.impl_->trigger_context = trc_early_receive;
+
+ // Receive the batched messages
+ self.receive_batch(source,batch);
+
+ // Restore the previous context
+ self.impl_->trigger_context = old_context;
+}
+
+// synchronization handler
+void handle_sync (mpi_process_group const& self, int source, int tag, int val,
+ bool)
+{
+ // increment the stage for the source
+ std::size_t stage = static_cast<std::size_t>(
+ ++self.impl_->synchronizing_stage[source]);
+
+ BOOST_ASSERT(source != process_id(self));
+
+#ifdef DEBUG
+ std::ostringstream out;
+ out << process_id(self) << ": handle_sync from " << source
+ << " (stage = " << self.impl_->synchronizing_stage[source] << ")\n";
+ std::cerr << out.str();
+#endif
+
+ // record how many still have messages to be sent
+ if (self.impl_->synchronizing_unfinished.size()<=stage) {
+ BOOST_ASSERT(self.impl_->synchronizing_unfinished.size() == stage);
+ self.impl_->synchronizing_unfinished.push_back(val >= 0 ? 1 : 0);
+ }
+ else
+ self.impl_->synchronizing_unfinished[stage]+=(val >= 0 ? 1 : 0);
+
+ // record how many are in that stage
+ if (self.impl_->processors_synchronizing_stage.size()<=stage) {
+ BOOST_ASSERT(self.impl_->processors_synchronizing_stage.size() == stage);
+ self.impl_->processors_synchronizing_stage.push_back(1);
+ }
+ else
+ ++self.impl_->processors_synchronizing_stage[stage];
+
+ // subtract how many batches we were supposed to receive
+ if (val>0)
+ self.impl_->number_received_batches[source] -= val;
+}
+
+
+}
+
+mpi_process_group::mpi_process_group(communicator_type parent_comm)
+{
+ // 64K messages and 1MB buffer turned out to be a reasonable choice
+ impl_.reset(new impl(64*1024,1024*1024,parent_comm));
+#ifndef IRECV_BATCH
+ global_trigger<outgoing_messages>(msg_batch,&detail::handle_batch);
+#else // use irecv version by providing a maximum buffer size
+ global_trigger<outgoing_messages>(msg_batch,&detail::handle_batch,
+ impl_->batch_message_size);
+#endif
+ global_trigger<outgoing_messages>(msg_large_batch,&detail::handle_batch);
+ global_trigger<int>(msg_synchronizing,&detail::handle_sync);
+ rank = impl_->comm.rank();
+ size = impl_->comm.size();
+
+#ifdef SEND_OOB_BSEND
+ // let us try with a default bufferr size of 16 MB
+ if (!message_buffer_size())
+ set_message_buffer_size(16*1024*1024);
+#endif
+}
+
+mpi_process_group::mpi_process_group(std::size_t h, std::size_t sz,
+ communicator_type parent_comm)
+{
+ impl_.reset(new impl(h,sz,parent_comm));
+#ifndef IRECV_BATCH
+ global_trigger<outgoing_messages>(msg_batch,&detail::handle_batch);
+#else // use irecv version by providing a maximum buffer size
+ global_trigger<outgoing_messages>(msg_batch,&detail::handle_batch,
+ impl_->batch_message_size);
+#endif
+ global_trigger<outgoing_messages>(msg_large_batch,&detail::handle_batch);
+ global_trigger<int>(msg_synchronizing,&detail::handle_sync);
+ rank = impl_->comm.rank();
+ size = impl_->comm.size();
+#ifdef SEND_OOB_BSEND
+ // let us try with a default bufferr size of 16 MB
+ if (!message_buffer_size())
+ set_message_buffer_size(16*1024*1024);
+#endif
+}
+
+mpi_process_group::mpi_process_group(const mpi_process_group& other,
+ const receiver_type& handler, bool)
+ : impl_(other.impl_)
+{
+ rank = impl_->comm.rank();
+ size = impl_->comm.size();
+ replace_handler(handler);
+}
+
+mpi_process_group::mpi_process_group(const mpi_process_group& other,
+ attach_distributed_object, bool)
+ : impl_(other.impl_)
+{
+ rank = impl_->comm.rank();
+ size = impl_->comm.size();
+ allocate_block();
+
+ for (std::size_t i = 0; i < impl_->incoming.size(); ++i) {
+ if (my_block_number() >= (int)impl_->incoming[i].next_header.size()) {
+ impl_->incoming[i].next_header
+ .push_back(impl_->incoming[i].headers.begin());
+ } else {
+ impl_->incoming[i].next_header[my_block_number()] =
+ impl_->incoming[i].headers.begin();
+ }
+
+#ifdef DEBUG
+ if (process_id(*this) == 0) {
+ std::cerr << "Allocated tag block " << my_block_number() << std::endl;
+ }
+#endif
+ }
+}
+
+mpi_process_group::~mpi_process_group() {
+ /*
+ std::string msg = boost::lexical_cast<std::string>(process_id(*this)) + " " +
+ boost::lexical_cast<std::string>(impl_->max_received) + " " +
+ boost::lexical_cast<std::string>(impl_->max_sent) + "\n";
+ std::cerr << msg << "\n";
+ */
+}
+
+
+mpi_process_group::communicator_type communicator(const mpi_process_group& pg)
+{ return pg.impl_->comm; }
+
+void
+mpi_process_group::replace_handler(const receiver_type& handler,
+ bool out_of_band_receive)
+{
+ make_distributed_object();
+
+ // Attach the receive handler
+ impl_->blocks[my_block_number()]->on_receive = handler;
+}
+
+void
+mpi_process_group::make_distributed_object()
+{
+ if (my_block_number() == 0) {
+ allocate_block();
+
+ for (std::size_t i = 0; i < impl_->incoming.size(); ++i) {
+ if (my_block_number() >= (int)impl_->incoming[i].next_header.size()) {
+ impl_->incoming[i].next_header
+ .push_back(impl_->incoming[i].headers.begin());
+ } else {
+ impl_->incoming[i].next_header[my_block_number()] =
+ impl_->incoming[i].headers.begin();
+ }
+
+#ifdef DEBUG
+ if (process_id(*this) == 0) {
+ std::cerr << "Allocated tag block " << my_block_number() << std::endl;
+ }
+#endif
+ }
+ } else {
+ // Clear out the existing triggers
+ std::vector<shared_ptr<trigger_base> >()
+ .swap(impl_->blocks[my_block_number()]->triggers);
+ }
+
+ // Clear out the receive handler
+ impl_->blocks[my_block_number()]->on_receive = 0;
+}
+
+void
+mpi_process_group::
+replace_on_synchronize_handler(const on_synchronize_event_type& handler)
+{
+ if (my_block_number() > 0)
+ impl_->blocks[my_block_number()]->on_synchronize = handler;
+}
+
+int mpi_process_group::allocate_block(bool out_of_band_receive)
+{
+ BOOST_ASSERT(!block_num);
+ block_iterator i = impl_->blocks.begin();
+ while (i != impl_->blocks.end() && *i) ++i;
+
+ if (i == impl_->blocks.end()) {
+ impl_->blocks.push_back(new block_type());
+ i = impl_->blocks.end() - 1;
+ } else {
+ *i = new block_type();
+ }
+
+ block_num.reset(new int(i - impl_->blocks.begin()),
+ deallocate_block(&impl_->blocks));
+
+#ifdef DEBUG
+ fprintf(stderr,
+ "Processor %i allocated block #%i\n", process_id(*this), *block_num);
+#endif
+
+ return *block_num;
+}
+
+bool mpi_process_group::maybe_emit_receive(int process, int encoded_tag) const
+{
+ std::pair<int, int> decoded = decode_tag(encoded_tag);
+
+ BOOST_ASSERT (decoded.first < static_cast<int>(impl_->blocks.size()));
+
+ block_type* block = impl_->blocks[decoded.first];
+ if (!block) {
+ std::cerr << "Received message from process " << process << " with tag "
+ << decoded.second << " for non-active block "
+ << decoded.first << std::endl;
+ std::cerr << "Active blocks are: ";
+ for (std::size_t i = 0; i < impl_->blocks.size(); ++i)
+ if (impl_->blocks[i])
+ std::cerr << i << ' ';
+ std::cerr << std::endl;
+ BOOST_ASSERT(block);
+ }
+
+ if (decoded.second < static_cast<int>(block->triggers.size())
+ && block->triggers[decoded.second]) {
+ // We have a trigger for this message; use it
+ trigger_receive_context old_context = impl_->trigger_context;
+ impl_->trigger_context = trc_out_of_band;
+ block->triggers[decoded.second]->receive(*this, process, decoded.second,
+ impl_->trigger_context,
+ decoded.first);
+ impl_->trigger_context = old_context;
+ }
+ else
+ return false;
+ // We receives the message above
+ return true;
+}
+
+bool mpi_process_group::emit_receive(int process, int encoded_tag) const
+{
+ std::pair<int, int> decoded = decode_tag(encoded_tag);
+
+ if (decoded.first >= static_cast<int>(impl_->blocks.size()))
+ // This must be an out-of-band message destined for
+ // send_oob_with_reply; ignore it.
+ return false;
+
+ // Find the block that will receive this message
+ block_type* block = impl_->blocks[decoded.first];
+ BOOST_ASSERT(block);
+ if (decoded.second < static_cast<int>(block->triggers.size())
+ && block->triggers[decoded.second])
+ // We have a trigger for this message; use it
+ block->triggers[decoded.second]->receive(*this,process, decoded.second,
+ impl_->trigger_context);
+ else if (block->on_receive)
+ // Fall back to the normal message handler
+ block->on_receive(process, decoded.second);
+ else
+ // There was no handler for this message
+ return false;
+
+ // The message was handled above
+ return true;
+}
+
+void mpi_process_group::emit_on_synchronize() const
+{
+ for (block_iterator i = impl_->blocks.begin(); i != impl_->blocks.end(); ++i)
+ if (*i && (*i)->on_synchronize) (*i)->on_synchronize();
+}
+
+
+optional<std::pair<mpi_process_group::process_id_type, int> >
+mpi_process_group::probe() const
+{
+#ifdef DEBUG
+ std::cerr << "PROBE: " << process_id(*this) << ", tag block = "
+ << my_block_number() << std::endl;
+#endif
+
+ typedef std::pair<process_id_type, int> result_type;
+
+ int tag_block = my_block_number();
+
+ for (std::size_t source = 0; source < impl_->incoming.size(); ++source) {
+ impl::incoming_messages& incoming = impl_->incoming[source];
+ std::vector<impl::message_header>::iterator& i =
+ incoming.next_header[tag_block];
+ std::vector<impl::message_header>::iterator end = incoming.headers.end();
+
+ while (i != end) {
+ if (i->tag != -1 && decode_tag(i->tag).first == my_block_number()) {
+#ifdef DEBUG
+ std::cerr << "PROBE: " << process_id(*this) << " <- " << source
+ << ", block = " << my_block_number() << ", tag = "
+ << decode_tag(i->tag).second << ", bytes = " << i->bytes
+ << std::endl;
+#endif
+ return result_type(source, decode_tag(i->tag).second);
+ }
+ ++i;
+ }
+ }
+ return optional<result_type>();
+}
+
+void
+mpi_process_group::maybe_send_batch(process_id_type dest) const
+{
+#ifndef NO_SPLIT_BATCHES
+ impl::outgoing_messages& outgoing = impl_->outgoing[dest];
+ if (outgoing.buffer.size() >= impl_->batch_buffer_size ||
+ outgoing.headers.size() >= impl_->batch_header_number) {
+ // we are full and need to send
+ outgoing_messages batch;
+ batch.buffer.reserve(impl_->batch_buffer_size);
+ batch.swap(outgoing);
+ if (batch.buffer.size() >= impl_->batch_buffer_size
+ && batch.headers.size()>1 ) {
+ // we are too large, keep the last message in the outgoing buffer
+ std::copy(batch.buffer.begin()+batch.headers.back().offset,
+ batch.buffer.end(),std::back_inserter(outgoing.buffer));
+ batch.buffer.resize(batch.headers.back().offset);
+ outgoing.headers.push_back(batch.headers.back());
+ batch.headers.pop_back();
+ outgoing.headers.front().offset=0;
+ }
+ send_batch(dest,batch);
+ }
+#endif
+}
+
+void
+mpi_process_group::send_batch(process_id_type dest) const
+{
+ impl::outgoing_messages& outgoing = impl_->outgoing[dest];
+ if (outgoing.headers.size()) {
+ // need to copy to avoid race conditions
+ outgoing_messages batch;
+ batch.buffer.reserve(impl_->batch_buffer_size);
+ batch.swap(outgoing);
+ send_batch(dest,batch);
+ }
+}
+
+
+void
+mpi_process_group::send_batch(process_id_type dest,
+ outgoing_messages& outgoing) const
+{
+ impl_->free_sent_batches();
+ process_id_type id = process_id(*this);
+
+ // clear the batch
+#ifdef DEBUG
+ std::cerr << "Sending batch: " << id << " -> " << dest << std::endl;
+#endif
+ // we increment the number of batches sent
+ ++impl_->number_sent_batches[dest];
+ // and send the batch
+ BOOST_ASSERT(outgoing.headers.size() <= impl_->batch_header_number);
+ if (id != dest) {
+#ifdef NO_ISEND_BATCHES
+ impl::batch_request req;
+#else
+#ifdef PREALLOCATE_BATCHES
+ while (impl_->free_batches.empty()) {
+ impl_->free_sent_batches();
+ poll();
+ }
+ impl::batch_request& req = impl_->batch_pool[impl_->free_batches.top()];
+ impl_->free_batches.pop();
+#else
+ impl_->sent_batches.push_back(impl::batch_request());
+ impl::batch_request& req = impl_->sent_batches.back();
+#endif
+#endif
+ boost::mpi::packed_oarchive oa(impl_->comm,req.buffer);
+ oa << outgoing;
+
+ int tag = msg_batch;
+
+#ifdef IRECV_BATCH
+ if (oa.size() > impl_->batch_message_size)
+ tag = msg_large_batch;
+#endif
+
+#ifndef NDEBUG // Prevent uninitialized variable warning with NDEBUG is on
+ int result =
+#endif // !NDEBUG
+ MPI_Isend(const_cast<void*>(oa.address()), oa.size(),
+ MPI_PACKED, dest, tag, impl_->comm,
+ &req.request);
+ BOOST_ASSERT(result == MPI_SUCCESS);
+ impl_->max_sent = (std::max)(impl_->max_sent,impl_->sent_batches.size());
+#ifdef NO_ISEND_BATCHES
+ int done=0;
+ do {
+ poll();
+ MPI_Test(&req.request,&done,MPI_STATUS_IGNORE);
+ } while (!done);
+#else
+#ifdef MAX_BATCHES
+ while (impl_->sent_batches.size() >= MAX_BATCHES-1) {
+ impl_->free_sent_batches();
+ poll();
+ }
+#endif
+#endif
+ }
+ else
+ receive_batch(id,outgoing);
+}
+
+void mpi_process_group::process_batch(int source) const
+{
+ bool processing_from_queue = !impl_->new_batches.empty();
+ impl_->processing_batches++;
+ typedef std::vector<impl::message_header>::iterator iterator;
+
+ impl::incoming_messages& incoming = impl_->incoming[source];
+
+ // Set up the iterators pointing to the next header in each block
+ for (std::size_t i = 0; i < incoming.next_header.size(); ++i)
+ incoming.next_header[i] = incoming.headers.begin();
+
+ buffer_type remaining_buffer;
+ std::vector<impl::message_header> remaining_headers;
+
+ iterator end = incoming.headers.end();
+
+ for (iterator i = incoming.headers.begin(); i != end; ++i) {
+ // This this message has already been received, skip it
+ if (i->tag == -1)
+ continue;
+
+#ifdef BATCH_DEBUG
+ std::cerr << process_id(*this) << ": emit_receive(" << source << ", "
+ << decode_tag(i->tag).first << ":" << decode_tag(i->tag).second
+ << ")\n";
+#endif
+
+ if (!emit_receive(source, i->tag)) {
+#ifdef BATCH_DEBUG
+ std::cerr << process_id(*this) << ": keeping message # "
+ << remaining_headers.size() << " from " << source << " ("
+ << decode_tag(i->tag).first << ":"
+ << decode_tag(i->tag).second << ", "
+ << i->bytes << " bytes)\n";
+#endif
+ // Hold on to this message until the next stage
+ remaining_headers.push_back(*i);
+ remaining_headers.back().offset = remaining_buffer.size();
+ remaining_buffer.insert(remaining_buffer.end(),
+ &incoming.buffer[i->offset],
+ &incoming.buffer[i->offset] + i->bytes);
+ }
+ }
+
+ // Swap the remaining messages into the "incoming" set.
+ incoming.headers.swap(remaining_headers);
+ incoming.buffer.swap(remaining_buffer);
+
+ // Set up the iterators pointing to the next header in each block
+ for (std::size_t i = 0; i < incoming.next_header.size(); ++i)
+ incoming.next_header[i] = incoming.headers.begin();
+ impl_->processing_batches--;
+
+ if (!processing_from_queue)
+ while (!impl_->new_batches.empty()) {
+ receive_batch(impl_->new_batches.front().first,
+ impl_->new_batches.front().second);
+ impl_->new_batches.pop();
+ }
+}
+
+
+void mpi_process_group::receive_batch(process_id_type source,
+ outgoing_messages& new_messages) const
+{
+ impl_->free_sent_batches();
+ if(!impl_->processing_batches) {
+ // increase the number of received batches
+ ++impl_->number_received_batches[source];
+ // and receive the batch
+ impl::incoming_messages& incoming = impl_->incoming[source];
+ typedef std::vector<impl::message_header>::iterator iterator;
+ iterator end = new_messages.headers.end();
+ for (iterator i = new_messages.headers.begin(); i != end; ++i) {
+ incoming.headers.push_back(*i);
+ incoming.headers.back().offset = incoming.buffer.size();
+ incoming.buffer.insert(incoming.buffer.end(),
+ &new_messages.buffer[i->offset],
+ &new_messages.buffer[i->offset] + i->bytes);
+ }
+ // Set up the iterators pointing to the next header in each block
+ for (std::size_t i = 0; i < incoming.next_header.size(); ++i)
+ incoming.next_header[i] = incoming.headers.begin();
+#ifndef NO_IMMEDIATE_PROCESSING
+ process_batch(source);
+#endif
+ }
+ else {
+ #ifdef DEBUG
+ std::cerr << "Pushing incoming message batch onto queue since we are already processing a batch.\n";
+ #endif
+ // use swap to avoid copying
+ impl_->new_batches.push(std::make_pair(int(source),outgoing_messages()));
+ impl_->new_batches.back().second.swap(new_messages);
+ impl_->max_received = (std::max)(impl_->max_received,impl_->new_batches.size());
+ }
+}
+
+
+void mpi_process_group::pack_headers() const
+{
+ for (process_id_type other = 0; other < num_processes(*this); ++other) {
+ typedef std::vector<impl::message_header>::iterator iterator;
+
+ impl::incoming_messages& incoming = impl_->incoming[other];
+
+ buffer_type remaining_buffer;
+ std::vector<impl::message_header> remaining_headers;
+
+ iterator end = incoming.headers.end();
+ for (iterator i = incoming.headers.begin(); i != end; ++i) {
+ if (i->tag == -1)
+ continue;
+
+ // Hold on to this message until the next stage
+ remaining_headers.push_back(*i);
+ remaining_headers.back().offset = remaining_buffer.size();
+ remaining_buffer.insert(remaining_buffer.end(),
+ &incoming.buffer[i->offset],
+ &incoming.buffer[i->offset] + i->bytes);
+ }
+
+ // Swap the remaining messages into the "incoming" set.
+ incoming.headers.swap(remaining_headers);
+ incoming.buffer.swap(remaining_buffer);
+
+ // Set up the iterators pointing to the next header in each block
+ for (std::size_t i = 0; i < incoming.next_header.size(); ++i)
+ incoming.next_header[i] = incoming.headers.begin();
+ }
+}
+
+void mpi_process_group::receive_batch(boost::mpi::status& status) const
+{
+ //std::cerr << "Handling batch\n";
+ outgoing_messages batch;
+ //impl_->comm.recv(status.source(),status.tag(),batch);
+
+ //receive_oob(*this,status.source(),msg_batch,batch);
+
+ // Determine how big the receive buffer should be
+#if BOOST_VERSION >= 103600
+ int size = status.count<boost::mpi::packed>().get();
+#else
+ int size;
+ MPI_Status mpi_status(status);
+ MPI_Get_count(&mpi_status, MPI_PACKED, &size);
+#endif
+
+ // Allocate the receive buffer
+ boost::mpi::packed_iarchive in(impl_->comm,size);
+
+ // Receive the message data
+ MPI_Recv(in.address(), size, MPI_PACKED,
+ status.source(), status.tag(),
+ impl_->comm, MPI_STATUS_IGNORE);
+
+ // Unpack the message data
+ in >> batch;
+ receive_batch(status.source(),batch);
+}
+
+std::pair<boost::mpi::communicator, int>
+mpi_process_group::actual_communicator_and_tag(int tag, int block) const
+{
+ if (tag >= max_tags * static_cast<int>(impl_->blocks.size()))
+ // Use the out-of-band reply communicator
+ return std::make_pair(impl_->oob_reply_comm, tag);
+ else
+ // Use the normal communicator and translate the tag
+ return std::make_pair(impl_->comm,
+ encode_tag(block == -1? my_block_number() : block,
+ tag));
+}
+
+
+void mpi_process_group::synchronize() const
+{
+ // Don't synchronize if we've already finished
+ if (boost::mpi::environment::finalized())
+ return;
+
+#ifdef DEBUG
+ std::cerr << "SYNC: " << process_id(*this) << std::endl;
+#endif
+
+ emit_on_synchronize();
+
+ process_id_type id = process_id(*this); // Our rank
+ process_size_type p = num_processes(*this); // The number of processes
+
+ // Pack the remaining incoming messages into the beginning of the
+ // buffers, so that we can receive new messages in this
+ // synchronization step without losing those messages that have not
+ // yet been received.
+ pack_headers();
+
+ impl_->synchronizing_stage[id] = -1;
+ int stage=-1;
+ bool no_new_messages = false;
+ while (true) {
+ ++stage;
+#ifdef DEBUG
+ std::cerr << "SYNC: " << id << " starting stage " << (stage+1) << ".\n";
+#endif
+
+ // Tell everyone that we are synchronizing. Note: we use MPI_Isend since
+ // we absolutely cannot have any of these operations blocking.
+
+ // increment the stage for the source
+ ++impl_->synchronizing_stage[id];
+ if (impl_->synchronizing_stage[id] != stage)
+ std::cerr << "Expected stage " << stage << ", got " << impl_->synchronizing_stage[id] << std::endl;
+ BOOST_ASSERT(impl_->synchronizing_stage[id]==stage);
+ // record how many still have messages to be sent
+ if (static_cast<int>(impl_->synchronizing_unfinished.size())<=stage) {
+ BOOST_ASSERT(static_cast<int>(impl_->synchronizing_unfinished.size()) == stage);
+ impl_->synchronizing_unfinished.push_back(no_new_messages ? 0 : 1);
+ }
+ else
+ impl_->synchronizing_unfinished[stage]+=(no_new_messages ? 0 : 1);
+
+ // record how many are in that stage
+ if (static_cast<int>(impl_->processors_synchronizing_stage.size())<=stage) {
+ BOOST_ASSERT(static_cast<int>(impl_->processors_synchronizing_stage.size()) == stage);
+ impl_->processors_synchronizing_stage.push_back(1);
+ }
+ else
+ ++impl_->processors_synchronizing_stage[stage];
+
+ impl_->synchronizing = true;
+
+ for (int dest = 0; dest < p; ++dest) {
+ int sync_message = no_new_messages ? -1 : impl_->number_sent_batches[dest];
+ if (dest != id) {
+ impl_->number_sent_batches[dest]=0;
+ MPI_Request request;
+ MPI_Isend(&sync_message, 1, MPI_INT, dest, msg_synchronizing, impl_->comm,&request);
+ int done=0;
+ do {
+ poll();
+ MPI_Test(&request,&done,MPI_STATUS_IGNORE);
+ } while (!done);
+ }
+ else { // need to subtract how many messages I should have received
+ impl_->number_received_batches[id] -=impl_->number_sent_batches[id];
+ impl_->number_sent_batches[id]=0;
+ }
+ }
+
+ // Keep handling out-of-band messages until everyone has gotten
+ // to this point.
+ while (impl_->processors_synchronizing_stage[stage] <p) {
+ // with the trigger based solution we cannot easily pass true here
+ poll(/*wait=*/false, -1, true);
+
+ }
+
+ // check that everyone is at least here
+ for (int source=0; source<p ; ++source)
+ BOOST_ASSERT(impl_->synchronizing_stage[source] >= stage);
+
+ // receive any batches sent in the meantime
+ // all have to be available already
+ while (true) {
+ bool done=true;
+ for (int source=0; source<p ; ++source)
+ if(impl_->number_received_batches[source] < 0)
+ done = false;
+ if (done)
+ break;
+ poll(false,-1,true);
+ }
+
+#ifndef NO_IMMEDIATE_PROCESSING
+ for (int source=0; source<p ; ++source)
+ BOOST_ASSERT(impl_->number_received_batches[source] >= 0);
+#endif
+
+ impl_->synchronizing = false;
+
+ // Flush out remaining messages
+ if (impl_->synchronizing_unfinished[stage]==0)
+ break;
+#ifdef NO_IMMEDIATE_PROCESSING
+ for (process_id_type dest = 0; dest < p; ++dest)
+ process_batch(dest);
+#endif
+
+ no_new_messages = true;
+ for (process_id_type dest = 0; dest < p; ++dest) {
+ if (impl_->outgoing[dest].headers.size() ||
+ impl_->number_sent_batches[dest]>0)
+ no_new_messages = false;
+ send_batch(dest);
+ }
+ }
+
+ impl_->comm.barrier/*nomacro*/();
+#if 0
+ // set up for next synchronize call
+ for (int source=0; source<p; ++source) {
+ if (impl_->synchronizing_stage[source] != stage) {
+ std::cerr << id << ": expecting stage " << stage << " from source "
+ << source << ", got " << impl_->synchronizing_stage[source]
+ << std::endl;
+ }
+ BOOST_ASSERT(impl_->synchronizing_stage[source]==stage);
+ }
+#endif
+ std::fill(impl_->synchronizing_stage.begin(),
+ impl_->synchronizing_stage.end(), -1);
+
+ // get rid of the information regarding recorded numbers of processors
+ // for the stages we just finished
+ impl_->processors_synchronizing_stage.clear();
+ impl_->synchronizing_unfinished.clear();
+
+ for (process_id_type dest = 0; dest < p; ++dest)
+ BOOST_ASSERT (impl_->outgoing[dest].headers.empty());
+#ifndef NO_IMMEDIATE_PROCESSING
+ for (int source=0; source<p ; ++source)
+ BOOST_ASSERT (impl_->number_received_batches[source] == 0);
+#endif
+
+ impl_->free_sent_batches();
+#ifdef DEBUG
+ std::cerr << "SYNC: " << process_id(*this) << " completed." << std::endl;
+#endif
+}
+
+optional<std::pair<mpi_process_group::process_id_type, int> >
+probe(const mpi_process_group& pg)
+{ return pg.probe(); }
+
+void mpi_process_group::poll_requests(int block) const
+{
+ int size = impl_->requests.size();
+ if (size==0)
+ return;
+ std::vector<MPI_Status> statuses(size);
+ std::vector<int> indices(size);
+
+ while (true) {
+ MPI_Testsome(impl_->requests.size(),&impl_->requests[0],
+ &size,&indices[0],&statuses[0]);
+ if (size==0)
+ return; // no message waiting
+
+ // remove handled requests before we get the chance to be recursively called
+ if (size) {
+ std::vector<MPI_Request> active_requests;
+ std::size_t i=0;
+ int j=0;
+ for (;i< impl_->requests.size() && j< size; ++i) {
+ if (int(i)==indices[j])
+ // release the dealt-with request
+ ++j;
+ else // copy and keep the request
+ active_requests.push_back(impl_->requests[i]);
+ }
+ while (i < impl_->requests.size())
+ active_requests.push_back(impl_->requests[i++]);
+ impl_->requests.swap(active_requests);
+ }
+
+ optional<std::pair<int, int> > result;
+ for (int i=0;i < size; ++i) {
+ std::pair<int, int> decoded = decode_tag(statuses[i].MPI_TAG);
+ block_type* block = impl_->blocks[decoded.first];
+
+ BOOST_ASSERT (decoded.second < static_cast<int>(block->triggers.size()) && block->triggers[decoded.second]);
+ // We have a trigger for this message; use it
+ trigger_receive_context old_context = impl_->trigger_context;
+ impl_->trigger_context = trc_irecv_out_of_band;
+ block->triggers[decoded.second]->receive(*this, statuses[i].MPI_SOURCE,
+ decoded.second, impl_->trigger_context, decoded.first);
+ impl_->trigger_context = old_context;
+ }
+ }
+}
+
+
+optional<std::pair<int, int> >
+mpi_process_group::
+poll(bool wait, int block, bool synchronizing) const
+{
+ // Set the new trigger context for these receive operations
+ trigger_receive_context old_context = impl_->trigger_context;
+ if (synchronizing)
+ impl_->trigger_context = trc_in_synchronization;
+ else
+ impl_->trigger_context = trc_out_of_band;
+
+ //wait = false;
+ optional<boost::mpi::status> status;
+ bool finished=false;
+ optional<std::pair<int, int> > result;
+ do {
+ poll_requests(block);
+ // Check for any messages not yet received.
+#ifdef PBGL_PROCESS_GROUP_NO_IRECV
+ if (wait)
+ status = impl_->comm.probe();
+ else
+#endif
+ status = impl_->comm.iprobe();
+
+ if (status) { // we have a message
+ // Decode the message
+ std::pair<int, int> decoded = decode_tag(status.get().tag());
+ if (maybe_emit_receive(status.get().source(), status.get().tag()))
+ // We received the message out-of-band; poll again
+ finished = false;
+ else if (decoded.first == (block == -1 ? my_block_number() : block)) {
+ // This message is for us, but not through a trigger. Return
+ // the decoded message.
+ result = std::make_pair(status.get().source(), decoded.second);
+ // otherwise we didn't match any message we know how to deal with, so
+ // pretend no message exists.
+ finished = true;
+ }
+ }
+ else
+ // We don't have a message to process; we're done.
+ finished=!wait;
+ } while (!finished);
+
+ // Restore the prior trigger context
+ impl_->trigger_context = old_context;
+ poll_requests(block);
+ return result;
+}
+
+void synchronize(const mpi_process_group& pg) { pg.synchronize(); }
+
+mpi_process_group mpi_process_group::base() const
+{
+ mpi_process_group copy(*this);
+ copy.block_num.reset();
+ return copy;
+}
+
+
+void mpi_process_group::impl::free_sent_batches()
+{
+ typedef std::list<batch_request>::iterator iterator;
+ iterator it = sent_batches.begin();
+ int flag;
+ int result;
+ while(it != sent_batches.end()) {
+ result = MPI_Test(&it->request,&flag,MPI_STATUS_IGNORE);
+ BOOST_ASSERT(result == MPI_SUCCESS);
+ iterator next=it;
+ ++next;
+ if (flag)
+ sent_batches.erase(it);
+ it=next;
+ }
+#ifdef PREALLOCATE_BATCHES
+ for (std::size_t i=0; i< batch_pool.size();++i) {
+ if(batch_pool[i].request != MPI_REQUEST_NULL) {
+ result = MPI_Test(&batch_pool[i].request,&flag,MPI_STATUS_IGNORE);
+ BOOST_ASSERT(result == MPI_SUCCESS);
+ if (flag) {
+ free_batches.push(i);
+ batch_pool[i].request = MPI_REQUEST_NULL;
+ batch_pool[i].buffer.resize(0);
+ }
+ }
+ }
+#endif
+}
+
+void
+mpi_process_group::install_trigger(int tag, int block,
+ shared_ptr<trigger_base> const& launcher)
+{
+ block_type* my_block = impl_->blocks[block];
+ BOOST_ASSERT(my_block);
+
+ // Make sure we have enough space in the structure for this trigger.
+ if (launcher->tag() >= static_cast<int>(my_block->triggers.size()))
+ my_block->triggers.resize(launcher->tag() + 1);
+
+ // If someone already put a trigger in this spot, we have a big
+ // problem.
+ if (my_block->triggers[launcher->tag()]) {
+ std::cerr << "Block " << my_block_number()
+ << " already has a trigger for tag " << launcher->tag()
+ << std::endl;
+ }
+ BOOST_ASSERT(!my_block->triggers[launcher->tag()]);
+
+ // Attach a new trigger launcher
+ my_block->triggers[launcher->tag()] = launcher;
+}
+
+std::size_t mpi_process_group::message_buffer_size()
+{
+ return message_buffer.size();
+}
+
+
+void mpi_process_group::set_message_buffer_size(std::size_t s)
+{
+ int sz;
+ void* ptr;
+ if (!message_buffer.empty()) {
+ MPI_Buffer_detach(&ptr,&sz);
+ BOOST_ASSERT(ptr == &message_buffer.front());
+ BOOST_ASSERT(static_cast<std::size_t>(sz) == message_buffer.size());
+ }
+ else if (old_buffer != 0)
+ MPI_Buffer_detach(&old_buffer,&old_buffer_size);
+ message_buffer.resize(s);
+ if (s)
+ MPI_Buffer_attach(&message_buffer.front(), message_buffer.size());
+ else if (old_buffer_size)
+ MPI_Buffer_attach(old_buffer, old_buffer_size);
+}
+
+
+std::vector<char> mpi_process_group::message_buffer;
+int mpi_process_group::old_buffer_size=0;
+void* mpi_process_group::old_buffer=0;
+
+} } } // end namespace boost::graph::distributed
diff --git a/src/boost/libs/graph_parallel/src/tag_allocator.cpp b/src/boost/libs/graph_parallel/src/tag_allocator.cpp
new file mode 100644
index 00000000..a89a2a2d
--- /dev/null
+++ b/src/boost/libs/graph_parallel/src/tag_allocator.cpp
@@ -0,0 +1,45 @@
+// Copyright (C) 2007 Douglas Gregor <doug.gregor@gmail.com>
+
+// 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)
+#include <boost/graph/use_mpi.hpp>
+#include <boost/graph/distributed/detail/tag_allocator.hpp>
+
+namespace boost { namespace graph { namespace distributed { namespace detail {
+
+tag_allocator::token tag_allocator::get_tag()
+{
+ int tag;
+
+ if (!freed.empty()) {
+ // Grab the tag at the top of the stack.
+ tag = freed.back();
+ freed.pop_back();
+ } else
+ // Grab the bottom tag and move the bottom down
+ tag = bottom--;
+
+ return token(this, tag);
+}
+
+tag_allocator::token::token(const token& other)
+ : allocator(other.allocator), tag_(other.tag_)
+{
+ // other no longer owns this tag
+ other.tag_ = -1;
+}
+
+tag_allocator::token::~token()
+{
+ if (tag_ != -1) {
+ if (tag_ == allocator->bottom + 1)
+ // This is the bottommost tag: just bump up the bottom
+ ++allocator->bottom;
+ else
+ // This tag isn't the bottom, so push it only the freed stack
+ allocator->freed.push_back(tag_);
+ }
+}
+
+} } } } // end namespace boost::graph::distributed::detail
diff --git a/src/boost/libs/graph_parallel/test/Jamfile.v2 b/src/boost/libs/graph_parallel/test/Jamfile.v2
new file mode 100644
index 00000000..61bf1618
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/Jamfile.v2
@@ -0,0 +1,47 @@
+#
+# (C) Copyright 2005, 2006 Trustees of Indiana University
+# (C) Copyright 2005 Douglas Gregor
+#
+# Distributed under 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.)
+
+
+# use-project /boost/mpi : ../build ;
+
+project /boost/graph_parallel/test
+ : requirements <library>../build//boost_graph_parallel <library>../../system/build//boost_system ;
+
+import mpi : mpi-test ;
+
+if [ mpi.configured ]
+{
+test-suite graph_parallel
+ :
+ [ mpi-test distributed_property_map_test : : : 2 ]
+ [ mpi-test distributed_queue_test : : : 2 ]
+ [ mpi-test process_group_serialization : : : 2 ]
+ [ mpi-test adjlist_build_test : : : 2 ]
+ [ mpi-test adjlist_redist_test : : : 2 ]
+ [ mpi-test adjlist_remove_test : : : 2 ]
+ [ mpi-test distributed_adjacency_list_test : : : 2 ]
+ [ mpi-test distributed_connected_components_test : : : 2 ]
+ [ mpi-test distributed_page_rank_test : : : 2 ]
+ [ mpi-test distributed_csr_test : : : 2 ]
+ [ mpi-test distributed_dfs_test : : : 2 ]
+ [ mpi-test distributed_graph_coloring_test : : : 2 ]
+ [ mpi-test distributed_mst_test : : : 2 ]
+ [ mpi-test distributed_strong_components_test : : : 2 ]
+ [ mpi-test hohberg_biconnected_components_test : : : 2 ]
+ [ mpi-test mesh_generator_test : : <testing.arg>"1000 1000 1 0" : 2 ]
+ [ mpi-test named_vertices_seq : : : 1 ]
+ [ mpi-test distributed_shortest_paths_test : : : 2 ]
+ [ mpi-test distributed_csr_algorithm_test : : : 1 ]
+ [ mpi-test distributed_betweenness_centrality_test : : : 2 ]
+ [ mpi-test distributed_dimacs_reader : : : 2 ]
+ [ 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 ]
+ ;
+}
+
diff --git a/src/boost/libs/graph_parallel/test/adjlist_build_test.cpp b/src/boost/libs/graph_parallel/test/adjlist_build_test.cpp
new file mode 100644
index 00000000..87335a50
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/adjlist_build_test.cpp
@@ -0,0 +1,245 @@
+// Copyright (C) 2007 Douglas Gregor
+
+// 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)
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/test/minimal.hpp>
+#include <boost/random/linear_congruential.hpp>
+#include <boost/graph/erdos_renyi_generator.hpp>
+#include <boost/lexical_cast.hpp>
+#include <ctime>
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+
+int test_main(int argc, char** argv)
+{
+ boost::mpi::environment env(argc, argv);
+
+ int n = 10000;
+ double p = 3e-3;
+ int seed = std::time(0);
+ int immediate_response_percent = 10;
+
+ if (argc > 1) n = lexical_cast<int>(argv[1]);
+ if (argc > 2) p = lexical_cast<double>(argv[2]);
+ if (argc > 3) seed = lexical_cast<int>(argv[3]);
+
+ typedef adjacency_list<listS,
+ distributedS<mpi_process_group, vecS>,
+ bidirectionalS> Graph;
+
+ mpi_process_group pg;
+ int rank = process_id(pg);
+ int numprocs = num_processes(pg);
+ bool i_am_root = rank == 0;
+
+ // broadcast the seed
+ broadcast(pg, seed, 0);
+
+ // Random number generator
+ minstd_rand gen;
+ minstd_rand require_response_gen;
+
+ if (i_am_root) {
+ std::cout << "n = " << n << ", p = " << p << ", seed = " << seed
+ << "\nBuilding graph with the iterator constructor... ";
+ std::cout.flush();
+ }
+
+ // Build a graph using the iterator constructor, where each of the
+ // processors has exactly the same information.
+ gen.seed(seed);
+ Graph g1(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, p),
+ erdos_renyi_iterator<minstd_rand, Graph>(),
+ n, pg, Graph::graph_property_type());
+ // NGE: Grrr, the default graph property is needed to resolve an
+ // ambiguous overload in the adjaceny list constructor
+
+ // Build another, identical graph using add_edge
+ if (i_am_root) {
+ std::cout << "done.\nBuilding graph with add_edge from the root...";
+ std::cout.flush();
+ }
+
+ gen.seed(seed);
+ require_response_gen.seed(1);
+ Graph g2(n, pg);
+ if (i_am_root) {
+ // The root will add all of the edges, some percentage of which
+ // will require an immediate response from the owner of the edge.
+ for (erdos_renyi_iterator<minstd_rand, Graph> first(gen, n, p), last;
+ first != last; ++first) {
+ Graph::lazy_add_edge lazy
+ = add_edge(vertex(first->first, g2), vertex(first->second, g2), g2);
+
+ if ((int)require_response_gen() % 100 < immediate_response_percent) {
+ // Send out-of-band to require a response
+ std::pair<graph_traits<Graph>::edge_descriptor, bool> result(lazy);
+ BOOST_CHECK(source(result.first, g2) == vertex(first->first, g2));
+ BOOST_CHECK(target(result.first, g2) == vertex(first->second, g2));
+ }
+ }
+ }
+
+ if (i_am_root) {
+ std::cout << "synchronizing...";
+ std::cout.flush();
+ }
+
+ synchronize(g2);
+
+ // Verify that the two graphs are indeed identical.
+ if (i_am_root) {
+ std::cout << "done.\nVerifying graphs...";
+ std::cout.flush();
+ }
+
+ // Check the number of vertices
+ if (num_vertices(g1) != num_vertices(g2)) {
+ std::cerr << g1.processor() << ": g1 has " << num_vertices(g1)
+ << " vertices, g2 has " << num_vertices(g2) << " vertices.\n";
+ communicator(pg).abort(-1);
+ }
+
+ // Check the number of edges
+ if (num_edges(g1) != num_edges(g2)) {
+ std::cerr << g1.processor() << ": g1 has " << num_edges(g1)
+ << " edges, g2 has " << num_edges(g2) << " edges.\n";
+ communicator(pg).abort(-1);
+ }
+
+ // Check the in-degree and out-degree of each vertex
+ graph_traits<Graph>::vertex_iterator vfirst1, vlast1, vfirst2, vlast2;
+ boost::tie(vfirst1, vlast1) = vertices(g1);
+ boost::tie(vfirst2, vlast2) = vertices(g2);
+ for(; vfirst1 != vlast1 && vfirst2 != vlast2; ++vfirst1, ++vfirst2) {
+ if (out_degree(*vfirst1, g1) != out_degree(*vfirst2, g2)) {
+ std::cerr << g1.processor() << ": out-degree mismatch ("
+ << out_degree(*vfirst1, g1) << " vs. "
+ << out_degree(*vfirst2, g2) << ").\n";
+ communicator(pg).abort(-1);
+ }
+
+ if (in_degree(*vfirst1, g1) != in_degree(*vfirst2, g2)) {
+ std::cerr << g1.processor() << ": in-degree mismatch ("
+ << in_degree(*vfirst1, g1) << " vs. "
+ << in_degree(*vfirst2, g2) << ").\n";
+ communicator(pg).abort(-1);
+ }
+ }
+
+ // TODO: Check the actual edge targets
+
+ // Build another, identical graph using add_edge
+ if (i_am_root) {
+ std::cout << "done.\nBuilding graph with add_edge from everywhere...";
+ std::cout.flush();
+ }
+
+ gen.seed(seed);
+ require_response_gen.seed(1);
+ Graph g3(n, pg);
+
+ {
+ // Each processor will take a chunk of incoming edges and add
+ // them. Some percentage of the edge additions will require an
+ // immediate response from the owner of the edge. This should
+ // create a lot of traffic when building the graph, but should
+ // produce a graph identical to the other graphs.
+ typedef graph_traits<Graph>::edges_size_type edges_size_type;
+
+ erdos_renyi_iterator<minstd_rand, Graph> first(gen, n, p);
+ edges_size_type chunk_size = edges_size_type(p*n*n)/numprocs;
+ edges_size_type start = chunk_size * rank;
+ edges_size_type remaining_edges =
+ (rank < numprocs - 1? chunk_size
+ : edges_size_type(p*n*n) - start);
+
+ // Spin the generator to the first edge we're responsible for
+ for (; start; ++first, --start) ;
+
+ for (; remaining_edges; --remaining_edges, ++first) {
+ Graph::lazy_add_edge lazy
+ = add_edge(vertex(first->first, g3), vertex(first->second, g3), g3);
+
+ if ((int)require_response_gen() % 100 < immediate_response_percent) {
+ // Send out-of-band to require a response
+ std::pair<graph_traits<Graph>::edge_descriptor, bool> result(lazy);
+ BOOST_CHECK(source(result.first, g3) == vertex(first->first, g3));
+ BOOST_CHECK(target(result.first, g3) == vertex(first->second, g3));
+ }
+ }
+ }
+
+ if (i_am_root) {
+ std::cout << "synchronizing...";
+ std::cout.flush();
+ }
+
+ synchronize(g3);
+
+ // Verify that the two graphs are indeed identical.
+ if (i_am_root) {
+ std::cout << "done.\nVerifying graphs...";
+ std::cout.flush();
+ }
+
+ // Check the number of vertices
+ if (num_vertices(g1) != num_vertices(g3)) {
+ std::cerr << g1.processor() << ": g1 has " << num_vertices(g1)
+ << " vertices, g3 has " << num_vertices(g3) << " vertices.\n";
+ communicator(pg).abort(-1);
+ }
+
+ // Check the number of edges
+ if (num_edges(g1) != num_edges(g3)) {
+ std::cerr << g1.processor() << ": g1 has " << num_edges(g1)
+ << " edges, g3 has " << num_edges(g3) << " edges.\n";
+ communicator(pg).abort(-1);
+ }
+
+ // Check the in-degree and out-degree of each vertex
+ boost::tie(vfirst1, vlast1) = vertices(g1);
+ boost::tie(vfirst2, vlast2) = vertices(g3);
+ for(; vfirst1 != vlast1 && vfirst2 != vlast2; ++vfirst1, ++vfirst2) {
+ if (out_degree(*vfirst1, g1) != out_degree(*vfirst2, g3)) {
+ std::cerr << g1.processor() << ": out-degree mismatch ("
+ << out_degree(*vfirst1, g1) << " vs. "
+ << out_degree(*vfirst2, g3) << ").\n";
+ communicator(pg).abort(-1);
+ }
+
+ if (in_degree(*vfirst1, g1) != in_degree(*vfirst2, g3)) {
+ std::cerr << g1.processor() << ": in-degree mismatch ("
+ << in_degree(*vfirst1, g1) << " vs. "
+ << in_degree(*vfirst2, g3) << ").\n";
+ communicator(pg).abort(-1);
+ }
+ }
+
+ // TODO: Check the actual edge targets
+
+ if (i_am_root) {
+ std::cout << "done.\n";
+ std::cout.flush();
+ }
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/adjlist_redist_test.cpp b/src/boost/libs/graph_parallel/test/adjlist_redist_test.cpp
new file mode 100644
index 00000000..96a659ae
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/adjlist_redist_test.cpp
@@ -0,0 +1,216 @@
+// Copyright (C) 2005, 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
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/serialization/vector.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/random/linear_congruential.hpp>
+#include <iostream>
+#include <boost/property_map/property_map_iterator.hpp>
+#include <boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp>
+#include <boost/graph/distributed/vertex_list_adaptor.hpp>
+#include <boost/graph/erdos_renyi_generator.hpp>
+#include <boost/graph/distributed/graphviz.hpp>
+#include <sstream>
+#include <string>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/test/minimal.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+/****************************************************************************
+ * Edge weight generator iterator *
+ ****************************************************************************/
+template<typename F>
+class generator_iterator
+{
+public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef typename F::result_type value_type;
+ typedef const value_type& reference;
+ typedef const value_type* pointer;
+ typedef void difference_type;
+
+ explicit generator_iterator(const F& f = F()) : f(f) { value = this->f(); }
+
+ reference operator*() const { return value; }
+ pointer operator->() const { return &value; }
+
+ generator_iterator& operator++()
+ {
+ value = f();
+ return *this;
+ }
+
+ generator_iterator operator++(int)
+ {
+ generator_iterator temp(*this);
+ ++(*this);
+ return temp;
+ }
+
+ bool operator==(const generator_iterator& other) const
+ { return f == other.f; }
+
+ bool operator!=(const generator_iterator& other) const
+ { return !(*this == other); }
+
+private:
+ F f;
+ value_type value;
+};
+
+template<typename F>
+inline generator_iterator<F> make_generator_iterator(const F& f)
+{ return generator_iterator<F>(f); }
+
+typedef minstd_rand RandomGenerator;
+
+template<typename Graph>
+double get_mst_weight (const Graph& g)
+{
+ typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
+ typename property_map<Graph, edge_weight_t>::const_type weight
+ = get(edge_weight, g);
+
+ // Boruvka then merge test
+ std::vector<edge_descriptor> results;
+ graph::boruvka_then_merge(make_vertex_list_adaptor(g), weight,
+ std::back_inserter(results));
+ if (process_id(g.process_group()) == 0)
+ return accumulate(make_property_map_iterator(weight, results.begin()),
+ make_property_map_iterator(weight, results.end()),
+ 0.0);
+ else
+ return 0.0;
+}
+
+template<typename Graph>
+void test_redistribution(int n, double p, int iterations, bool debug_output)
+{
+ RandomGenerator gen;
+ Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, n, p),
+ erdos_renyi_iterator<RandomGenerator, Graph>(),
+ make_generator_iterator(uniform_01<RandomGenerator>(gen)),
+ n);
+
+ int iter = 0;
+ mpi_process_group pg = g.process_group();
+
+ // Set the names of the vertices to be the global index in the
+ // initial distribution. Then when we are debugging we'll be able to
+ // see how vertices have moved.
+ {
+ typedef typename property_map<Graph, vertex_index_t>::type VertexIndexMap;
+ typedef typename property_map<Graph, vertex_global_t>::type VertexGlobalMap;
+ typename property_map<Graph, vertex_name_t>::type name_map
+ = get(vertex_name, g);
+
+ parallel::global_index_map<VertexIndexMap, VertexGlobalMap>
+ global_index(g.process_group(), num_vertices(g),
+ get(vertex_index, g), get(vertex_global, g));
+ BGL_FORALL_VERTICES_T(v, g, Graph)
+ put(name_map, v, get(global_index, v));
+ }
+
+ if (debug_output)
+ write_graphviz("redist-0.dot", g,
+ make_label_writer(get(vertex_name, g)),
+ make_label_writer(get(edge_weight, g)));
+
+ double mst_weight = get_mst_weight(g);
+ if (process_id(pg) == 0)
+ std::cout << "MST weight = " << mst_weight << std::endl;
+
+ RandomGenerator nonsync_gen(process_id(pg) + gen());
+ while (++iter <= iterations) {
+ typename property_map<Graph, vertex_rank_t>::type to_processor_map =
+ get(vertex_rank, g);
+
+ // Randomly assign a new distribution
+ typename graph_traits<Graph>::vertex_iterator vi, vi_end;
+ for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
+ put(to_processor_map, *vi, gen() % num_processes(pg));
+
+ if (process_id(pg) == 0)
+ std::cout << "Redistributing...";
+ // Perform the actual redistribution
+ g.redistribute(to_processor_map);
+
+ if (process_id(pg) == 0)
+ std::cout << " done." << std::endl;
+
+ if (debug_output) {
+ std::ostringstream out;
+ out << "redist-" << iter << ".dot";
+ write_graphviz(out.str().c_str(), g,
+ make_label_writer(get(vertex_name, g)),
+ make_label_writer(get(edge_weight, g)));
+ }
+
+ // Check that the MST weight is unchanged
+ double new_mst_weight = get_mst_weight(g);
+ if (process_id(pg) == 0) {
+ std::cout << "MST weight = " << new_mst_weight << std::endl;
+ if (std::fabs(new_mst_weight - mst_weight) > 0.0001)
+ communicator(pg).abort(-1); }
+ }
+}
+
+int test_main(int argc, char** argv)
+{
+ int n = 1000;
+ double p = 3e-3;
+ int iterations = 5;
+ bool debug_output = false;
+
+ boost::mpi::environment env(argc, argv);
+
+ if (argc > 1) n = lexical_cast<int>(argv[1]);
+ if (argc > 2) p = lexical_cast<double>(argv[2]);
+ if (argc > 3) iterations = lexical_cast<int>(argv[3]);
+ if (argc > 4) debug_output = true;
+
+ typedef adjacency_list<listS,
+ distributedS<mpi_process_group, vecS>,
+ undirectedS,
+ // Vertex properties
+ property<vertex_name_t, std::size_t,
+ property<vertex_rank_t, int> >,
+ // Edge properties
+ property<edge_weight_t, double> > UnstableUDGraph;
+ typedef adjacency_list<listS,
+ distributedS<mpi_process_group, listS>,
+ undirectedS,
+ // Vertex properties
+ property<vertex_name_t, std::size_t,
+ property<vertex_rank_t, int,
+ property<vertex_index_t, std::size_t> > >,
+ // Edge properties
+ property<edge_weight_t, double> > StableUDGraph;
+
+ test_redistribution<UnstableUDGraph>(n, p, iterations, debug_output);
+ test_redistribution<StableUDGraph>(n, p, iterations, debug_output);
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/adjlist_remove_test.cpp b/src/boost/libs/graph_parallel/test/adjlist_remove_test.cpp
new file mode 100644
index 00000000..549c5195
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/adjlist_remove_test.cpp
@@ -0,0 +1,146 @@
+// Copyright 2004 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
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/parallel/distribution.hpp>
+#include <iostream>
+#include <cassert>
+#include <boost/test/minimal.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+void test_bidirectional_graph()
+{
+ typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>,
+ bidirectionalS> Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+
+ typedef std::pair<std::size_t, std::size_t> E;
+ E edges[3] = { E(0,3), E(1,4), E(2,5) };
+
+ Graph g(&edges[0], &edges[0] + 3, 6);
+ assert(num_processes(g.process_group()) == 2);
+
+ if (process_id(g.process_group()) == 0)
+ std::cerr << "Testing bidirectional graph edge removal...";
+ synchronize(g.process_group());
+
+ graph_traits<Graph>::vertex_iterator vi = vertices(g).first;
+ Vertex u = *vi++;
+ Vertex v = *vi++;
+ Vertex w = *vi++;
+ BOOST_CHECK(vi == vertices(g).second);
+
+ BOOST_CHECK((process_id(g.process_group()) == 0 && out_degree(u, g) == 1)
+ || (process_id(g.process_group()) == 1 && in_degree(u, g) == 1));
+
+ BOOST_CHECK((process_id(g.process_group()) == 0 && out_degree(v, g) == 1)
+ || (process_id(g.process_group()) == 1 && in_degree(v, g) == 1));
+
+ BOOST_CHECK((process_id(g.process_group()) == 0 && out_degree(w, g) == 1)
+ || (process_id(g.process_group()) == 1 && in_degree(w, g) == 1));
+
+ // Remove edges
+ if (process_id(g.process_group()) == 0) {
+ remove_edge(*out_edges(u, g).first, g);
+ remove_edge(*out_edges(w, g).first, g);
+ } else {
+ remove_edge(*in_edges(v, g).first, g);
+ remove_edge(*in_edges(w, g).first, g);
+ }
+
+ synchronize(g);
+
+ BOOST_CHECK(num_edges(g) == 0);
+ BOOST_CHECK(out_degree(u, g) == 0);
+ BOOST_CHECK(out_degree(v, g) == 0);
+ BOOST_CHECK(out_degree(w, g) == 0);
+ BOOST_CHECK(in_degree(u, g) == 0);
+ BOOST_CHECK(in_degree(v, g) == 0);
+ BOOST_CHECK(in_degree(w, g) == 0);
+
+ if (process_id(g.process_group()) == 0) std::cerr << "OK.\n";
+}
+
+void test_undirected_graph()
+{
+ typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>,
+ undirectedS> Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef graph_traits<Graph>::edge_descriptor Edge;
+
+ typedef std::pair<std::size_t, std::size_t> E;
+ E the_edges[3] = { E(0,3), E(1,4), E(2,5) };
+
+ Graph g(&the_edges[0], &the_edges[0] + 3, 6);
+ assert(num_processes(g.process_group()) == 2);
+
+ if (process_id(g.process_group()) == 0)
+ std::cerr << "Testing undirected graph edge removal...";
+ synchronize(g.process_group());
+
+ graph_traits<Graph>::vertex_iterator vi = vertices(g).first;
+ Vertex u = *vi++;
+ Vertex v = *vi++;
+ Vertex w = *vi++;
+ BOOST_CHECK(vi == vertices(g).second);
+ BOOST_CHECK(degree(u, g) == 1);
+ BOOST_CHECK(degree(v, g) == 1);
+ BOOST_CHECK(degree(w, g) == 1);
+
+ // Remove edges
+ if (process_id(g.process_group()) == 0) {
+ BOOST_CHECK(num_edges(g) == 3);
+ remove_edge(*out_edges(u, g).first, g);
+ remove_edge(*out_edges(w, g).first, g);
+ } else {
+ BOOST_CHECK(num_edges(g) == 0);
+ remove_edge(*in_edges(v, g).first, g);
+ remove_edge(*in_edges(w, g).first, g);
+ }
+
+ synchronize(g);
+
+ if (num_edges(g) > 0) {
+ Edge e = *edges(g).first;
+ std::cerr << "#" << process_id(g.process_group()) << ": extra edge! ("
+ << local(source(e, g)) << "@" << owner(source(e, g))
+ << ", "
+ << local(target(e, g)) << "@" << owner(target(e, g))
+ << ")\n";
+ }
+
+ BOOST_CHECK(num_edges(g) == 0);
+ BOOST_CHECK(degree(u, g) == 0);
+ BOOST_CHECK(degree(v, g) == 0);
+ BOOST_CHECK(degree(w, g) == 0);
+ if (process_id(g.process_group()) == 0) std::cerr << "OK.\n";
+}
+
+int test_main(int argc, char** argv)
+{
+ boost::mpi::environment env(argc, argv);
+ test_bidirectional_graph();
+ test_undirected_graph();
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/algorithm_performance.cpp b/src/boost/libs/graph_parallel/test/algorithm_performance.cpp
new file mode 100644
index 00000000..c4973b41
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/algorithm_performance.cpp
@@ -0,0 +1,887 @@
+// Copyright 2004 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: Nick Edmonds
+// Andrew Lumsdaine
+
+// #define PBGL_ACCOUNTING
+
+#include <boost/graph/use_mpi.hpp>
+
+#include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+
+#include <boost/graph/distributed/mpi_process_group.hpp>
+
+#include <boost/test/minimal.hpp>
+#include <boost/random.hpp>
+#include <boost/property_map/parallel/distributed_property_map.hpp>
+#include <boost/graph/distributed/graphviz.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/properties.hpp>
+
+#include <boost/graph/rmat_graph_generator.hpp>
+#include <boost/graph/small_world_generator.hpp>
+#include <boost/graph/erdos_renyi_generator.hpp>
+
+#include <boost/graph/distributed/connected_components.hpp>
+#include <boost/graph/distributed/connected_components_parallel_search.hpp>
+#include <boost/graph/distributed/betweenness_centrality.hpp>
+#include <boost/graph/distributed/delta_stepping_shortest_paths.hpp>
+
+#include <time.h>
+#include <sys/time.h>
+
+#include <iostream>
+#include <iomanip>
+#include <vector>
+#include <stdint.h>
+
+// Edge distribution tags select a generator
+struct rmat_edge_distribution_tag { };
+struct rmat_unique_edge_distribution_tag { };
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+/****************************************************************************
+ * Timing
+ ****************************************************************************/
+#ifndef PBGL_ACCOUNTING
+
+typedef double time_type;
+
+inline time_type get_time()
+{
+ timeval tp;
+ gettimeofday(&tp, 0);
+ return tp.tv_sec + tp.tv_usec / 1000000.0;
+}
+
+std::string print_time(time_type t)
+{
+ std::ostringstream out;
+ out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
+ return out.str();
+}
+
+#endif // PBGL_ACCOUNTING
+
+/****************************************************************************
+ * Edge weight generator iterator *
+ ****************************************************************************/
+template<typename F, typename RandomGenerator>
+class generator_iterator
+{
+public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef typename F::result_type value_type;
+ typedef const value_type& reference;
+ typedef const value_type* pointer;
+ typedef void difference_type;
+
+ explicit
+ generator_iterator(RandomGenerator& gen, const F& f = F())
+ : f(f), gen(&gen)
+ {
+ value = this->f(gen);
+ }
+
+ reference operator*() const { return value; }
+ pointer operator->() const { return &value; }
+
+ generator_iterator& operator++()
+ {
+ value = f(*gen);
+ return *this;
+ }
+
+ generator_iterator operator++(int)
+ {
+ generator_iterator temp(*this);
+ ++(*this);
+ return temp;
+ }
+
+ bool operator==(const generator_iterator& other) const
+ { return f == other.f; }
+
+ bool operator!=(const generator_iterator& other) const
+ { return !(*this == other); }
+
+private:
+ F f;
+ RandomGenerator* gen;
+ value_type value;
+};
+
+template<typename F, typename RandomGenerator>
+inline generator_iterator<F, RandomGenerator>
+make_generator_iterator( RandomGenerator& gen, const F& f)
+{ return generator_iterator<F, RandomGenerator>(gen, f); }
+
+/****************************************************************************
+ * Edge Property *
+ ****************************************************************************/
+typedef int weight_type;
+
+struct WeightedEdge {
+ WeightedEdge(weight_type weight = 0) : weight(weight) { }
+
+ weight_type weight;
+
+ template<typename Archiver>
+ void serialize(Archiver& ar, const unsigned int /*version*/)
+ {
+ ar & weight;
+ }
+};
+
+/****************************************************************************
+ * Algorithm Tests *
+ ****************************************************************************/
+template <typename Graph>
+void test_directed_sequential_algorithms(const Graph& g)
+{ }
+
+template <typename Graph>
+void test_undirected_sequential_algorithms(const Graph& g)
+{
+ std::vector<unsigned int> componentS(num_vertices(g));
+ typedef iterator_property_map<
+ std::vector<unsigned int>::iterator,
+ typename property_map<Graph, vertex_index_t>::type>
+ ComponentMap;
+ ComponentMap component(componentS.begin(), get(vertex_index, g));
+
+ time_type start = get_time();
+ unsigned int num_components = connected_components(g, component);
+ time_type end = get_time();
+
+ std::cerr << " Sequential connected Components time = "
+ << print_time(end - start) << " seconds.\n"
+ << " " << num_components << " components identified\n";
+}
+
+template <typename Graph, typename EdgeWeightMap>
+void test_directed_csr_only_algorithms(const Graph& g, EdgeWeightMap weight,
+ typename graph_traits<Graph>::vertices_size_type num_sources,
+ typename property_traits<EdgeWeightMap>::value_type C)
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+ typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
+ typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
+ typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
+
+ typedef typename boost::graph::parallel::process_group_type<Graph>::type
+ process_group_type;
+
+ process_group_type pg = process_group(g);
+ typename process_group_type::process_id_type id = process_id(pg);
+ typename process_group_type::process_size_type p = num_processes(pg);
+
+ vertices_size_type n = num_vertices(g);
+ n = boost::parallel::all_reduce(pg, n, std::plus<vertices_size_type>());
+
+ edges_size_type m = num_edges(g);
+ m = boost::parallel::all_reduce(pg, m, std::plus<edges_size_type>());
+
+ //
+ // Betweenness Centrality (Approximate)
+ //
+ queue<vertex_descriptor> delta_stepping_vertices;
+
+ {
+ // Distributed Centrality Map
+ typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
+ typedef iterator_property_map<std::vector<int>::iterator, IndexMap> CentralityMap;
+
+ std::vector<int> centralityS(num_vertices(g), 0);
+ CentralityMap centrality(centralityS.begin(), get(vertex_index, g));
+
+ // Calculate number of vertices of degree 0
+ vertices_size_type n0 = 0;
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ if (out_degree(v, g) == 0) n0++;
+ }
+ n0 = boost::parallel::all_reduce(pg, n0, std::plus<vertices_size_type>());
+
+ queue<vertex_descriptor> sources;
+
+ {
+ assert(num_sources >= p); // Don't feel like adding a special case for num_sources < p
+
+ minstd_rand gen;
+ uniform_int<vertices_size_type> rand_vertex(0, num_vertices(g) - 1);
+ std::vector<vertex_descriptor> all_sources, local_sources;
+ vertices_size_type local_vertices = vertices_size_type(floor((double)num_sources / p));
+ local_vertices += (id < (num_sources - (p * local_vertices)) ? 1 : 0);
+
+ while (local_vertices > 0) {
+ vertex_iterator iter = vertices(g).first;
+ std::advance(iter, rand_vertex(gen));
+
+ if (out_degree(*iter, g) != 0
+ && std::find(local_sources.begin(), local_sources.end(), *iter) == local_sources.end()) {
+ local_sources.push_back(*iter);
+ --local_vertices;
+ }
+ }
+ all_gather(pg, local_sources.begin(), local_sources.end(), all_sources);
+ std::sort(all_sources.begin(), all_sources.end());
+ for (typename std::vector<vertex_descriptor>::iterator iter = all_sources.begin();
+ iter != all_sources.end(); ++iter) {
+ sources.push(*iter);
+ delta_stepping_vertices.push(*iter);
+ }
+ }
+
+ // NOTE: The delta below assumes uniform edge weight distribution
+ time_type start = get_time();
+ brandes_betweenness_centrality(g, buffer(sources).weight_map(weight).
+ centrality_map(centrality).lookahead((m / n) * (C / 2)));
+ time_type end = get_time();
+
+ edges_size_type exactTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start)));
+
+ if (id == 0)
+ std::cerr << " Betweenness Centrality Approximate (" << num_sources << " sources) = "
+ << print_time(end - start) << " (" << exactTEPs << " TEPs)\n";
+ }
+
+ //
+ // Delta stepping performance (to compare to SSSP inside BC
+ //
+ if (false) {
+ typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
+ typedef iterator_property_map<std::vector<int>::iterator, IndexMap> DistanceMap;
+
+ std::vector<int> distanceS(num_vertices(g), 0);
+ DistanceMap distance(distanceS.begin(), get(vertex_index, g));
+
+ while(!delta_stepping_vertices.empty()) {
+
+ time_type start = get_time();
+ delta_stepping_shortest_paths(g, delta_stepping_vertices.top(), dummy_property_map(),
+ distance, weight);
+ time_type end = get_time();
+
+ delta_stepping_vertices.pop();
+ distance.reset();
+
+ if (id == 0)
+ std::cerr << " Delta-stepping shortest paths = " << print_time(end - start)
+ << std::endl;
+ }
+ }
+
+}
+
+template <typename Graph>
+void test_directed_algorithms(const Graph& g)
+{
+}
+
+template <typename Graph>
+void test_undirected_algorithms(const Graph& g)
+{
+ typedef typename boost::graph::parallel::process_group_type<Graph>::type
+ process_group_type;
+
+ process_group_type pg = process_group(g);
+ typename process_group_type::process_id_type id = process_id(pg);
+ typename process_group_type::process_size_type p = num_processes(pg);
+
+
+ // Connected Components
+ std::vector<unsigned int> local_components_vec(num_vertices(g));
+ typedef iterator_property_map<
+ std::vector<unsigned int>::iterator,
+ typename property_map<Graph, vertex_index_t>::type>
+ ComponentMap;
+ ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
+
+ int num_components;
+
+ time_type start = get_time();
+ num_components = connected_components(g, component);
+ time_type end = get_time();
+ if (id == 0)
+ std::cerr << " Connected Components time = " << print_time(end - start)
+ << " seconds.\n"
+ << " " << num_components << " components identified\n";
+
+ start = get_time();
+ num_components = boost::graph::distributed::connected_components_ps(g, component);
+ end = get_time();
+ if (id == 0)
+ std::cerr << " Connected Components (parallel search) time = "
+ << print_time(end - start) << " seconds.\n"
+ << " " << num_components << " components identified\n";
+}
+
+/****************************************************************************
+ * Graph Type Tests *
+ ****************************************************************************/
+
+// TODO: Re-seed PRNG before sequential tests to get the same graph as the
+// distributed case?
+
+//
+// Compressed Sparse Row
+//
+
+// R-MAT
+template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
+void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
+ bool sequential_tests, size_t N, size_t M, size_t C,
+ double a, double b, double c, double d, size_t num_sources,
+ rmat_edge_distribution_tag)
+{
+ if (process_id(pg) == 0)
+ std::cerr << " R-MAT\n";
+
+ typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property,
+ distributedS<mpi_process_group> > Graph;
+
+ Graph g(sorted_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
+ sorted_rmat_iterator<RandomGenerator, Graph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N, pg, distrib);
+
+ test_directed_algorithms(g);
+ test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C);
+
+ if (sequential_tests && process_id(pg) == 0) {
+ typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
+ seqGraph;
+
+ 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);
+
+ test_directed_sequential_algorithms(sg);
+ }
+}
+
+// R-MAT with unique edges
+template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
+void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
+ bool sequential_tests, size_t N, size_t M, size_t C,
+ double a, double b, double c, double d, size_t num_sources,
+ rmat_unique_edge_distribution_tag)
+{
+ if (process_id(pg) == 0)
+ std::cerr << " R-MAT - unique\n";
+
+ typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property,
+ distributedS<mpi_process_group> > Graph;
+
+ // Last boolean parameter makes R-MAT bidirectional
+ Graph g(sorted_unique_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
+ sorted_unique_rmat_iterator<RandomGenerator, Graph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N, pg, distrib);
+
+ test_directed_algorithms(g);
+ test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C);
+
+ if (sequential_tests && process_id(pg) == 0) {
+ typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
+ seqGraph;
+
+ 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);
+
+ test_directed_sequential_algorithms(sg);
+ }
+}
+
+// Erdos-Renyi
+template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
+void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
+ bool sequential_tests, size_t N, size_t M, size_t C, size_t num_sources)
+{
+ if (process_id(pg) == 0)
+ std::cerr << " Erdos-Renyi\n";
+
+ double _p = static_cast<double>(M) / (N*N);
+
+ typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property,
+ distributedS<mpi_process_group> > Graph;
+
+ Graph g(sorted_erdos_renyi_iterator<RandomGenerator, Graph>(gen, N, _p/2),
+ sorted_erdos_renyi_iterator<RandomGenerator, Graph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N, pg, distrib);
+
+ test_directed_algorithms(g);
+ test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C);
+
+ if (sequential_tests && process_id(pg) == 0) {
+ typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
+ seqGraph;
+
+ 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);
+
+ test_directed_sequential_algorithms(sg);
+ }
+}
+
+// Small World
+template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
+void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
+ bool sequential_tests, size_t N, size_t M, size_t C, double p,
+ size_t num_sources)
+{
+ if (process_id(pg) == 0)
+ std::cerr << " Small-World\n";
+
+ int k = M / N;
+
+ typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property,
+ distributedS<mpi_process_group> > Graph;
+
+ Graph g(small_world_iterator<RandomGenerator, Graph>(gen, N, k, p),
+ small_world_iterator<RandomGenerator, Graph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N, pg, distrib);
+
+ test_directed_algorithms(g);
+ test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C);
+
+ if (sequential_tests && process_id(pg) == 0) {
+ typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
+ seqGraph;
+
+ 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);
+
+ test_directed_sequential_algorithms(sg);
+ }
+}
+
+//
+// Adjacency List
+//
+
+// R-MAT
+template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
+void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
+ bool sequential_tests, size_t N, size_t M, size_t C,
+ double a, double b, double c, double d,
+ rmat_edge_distribution_tag)
+{
+ if (process_id(pg) == 0)
+ std::cerr << "R-MAT\n";
+
+ {
+ typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
+ directedS, no_property, WeightedEdge> Graph;
+
+ Graph g(rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
+ rmat_iterator<RandomGenerator, Graph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N, pg, distrib);
+
+ test_directed_algorithms(g);
+ }
+
+ {
+ typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
+ undirectedS, no_property, WeightedEdge> Graph;
+
+ Graph g(rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
+ rmat_iterator<RandomGenerator, Graph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N, pg, distrib);
+
+ test_undirected_algorithms(g);
+ }
+
+ if (sequential_tests && process_id(pg) == 0) {
+ {
+ typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> >
+ seqGraph;
+
+ seqGraph sg(rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
+ rmat_iterator<RandomGenerator, seqGraph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N);
+
+ test_directed_sequential_algorithms(sg);
+ }
+
+ {
+ typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> >
+ seqGraph;
+
+ seqGraph sg(rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
+ rmat_iterator<RandomGenerator, seqGraph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N);
+
+ test_undirected_sequential_algorithms(sg);
+ }
+ }
+}
+
+// R-MAT with unique edges
+template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
+void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
+ bool sequential_tests, size_t N, size_t M, size_t C,
+ double a, double b, double c, double d,
+ rmat_unique_edge_distribution_tag)
+{
+ if (process_id(pg) == 0)
+ std::cerr << " R-MAT - unique\n";
+
+ {
+ typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
+ directedS, no_property, WeightedEdge> Graph;
+
+ Graph g(sorted_unique_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
+ sorted_unique_rmat_iterator<RandomGenerator, Graph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N, pg, distrib);
+
+ test_directed_algorithms(g);
+ }
+
+ {
+ typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
+ undirectedS, no_property, WeightedEdge> Graph;
+
+ Graph g(sorted_unique_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
+ sorted_unique_rmat_iterator<RandomGenerator, Graph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N, pg, distrib);
+
+ test_undirected_algorithms(g);
+ }
+
+ if (sequential_tests && process_id(pg) == 0) {
+ {
+ typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> >
+ seqGraph;
+
+ seqGraph sg(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);
+
+ test_directed_sequential_algorithms(sg);
+ }
+
+ {
+ typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> >
+ seqGraph;
+
+ seqGraph sg(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);
+
+ test_undirected_sequential_algorithms(sg);
+ }
+ }
+}
+
+// Erdos-Renyi
+template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
+void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
+ bool sequential_tests, size_t N, size_t M, size_t C)
+{
+ if (process_id(pg) == 0)
+ std::cerr << " Erdos-Renyi\n";
+
+ double _p = static_cast<double>(M) / N*N;
+
+ {
+ typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
+ directedS, no_property, WeightedEdge> Graph;
+
+ Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, N, _p/2),
+ erdos_renyi_iterator<RandomGenerator, Graph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N, pg, distrib);
+
+ test_directed_algorithms(g);
+ }
+
+ {
+ typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
+ undirectedS, no_property, WeightedEdge> Graph;
+
+ Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, N, _p/2),
+ erdos_renyi_iterator<RandomGenerator, Graph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N, pg, distrib);
+
+ test_undirected_algorithms(g);
+ }
+
+ if (sequential_tests && process_id(pg) == 0) {
+ {
+ typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> >
+ seqGraph;
+
+ seqGraph sg(erdos_renyi_iterator<RandomGenerator, seqGraph>(gen, N, _p/2),
+ erdos_renyi_iterator<RandomGenerator, seqGraph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N);
+
+ test_directed_sequential_algorithms(sg);
+ }
+
+ {
+ typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> >
+ seqGraph;
+
+ seqGraph sg(erdos_renyi_iterator<RandomGenerator, seqGraph>(gen, N, _p/2),
+ erdos_renyi_iterator<RandomGenerator, seqGraph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N);
+
+ test_undirected_sequential_algorithms(sg);
+ }
+ }
+}
+
+// Small World
+template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
+void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
+ bool sequential_tests, size_t N, size_t M, size_t C, double p)
+{
+ if (process_id(pg) == 0)
+ std::cerr << " Small-World\n";
+
+ int k = M / N;
+
+ {
+ typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
+ directedS, no_property, WeightedEdge> Graph;
+
+ Graph g(small_world_iterator<RandomGenerator, Graph>(gen, N, k, p),
+ small_world_iterator<RandomGenerator, Graph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N, pg, distrib);
+
+ test_directed_algorithms(g);
+ }
+
+ {
+ typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
+ undirectedS, no_property, WeightedEdge> Graph;
+
+ Graph g(small_world_iterator<RandomGenerator, Graph>(gen, N, k, p),
+ small_world_iterator<RandomGenerator, Graph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N, pg, distrib);
+
+ test_undirected_algorithms(g);
+ }
+
+ if (sequential_tests && process_id(pg) == 0) {
+ {
+ typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> >
+ seqGraph;
+
+ seqGraph sg(small_world_iterator<RandomGenerator, seqGraph>(gen, N, k, p),
+ small_world_iterator<RandomGenerator, seqGraph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N);
+
+ test_directed_sequential_algorithms(sg);
+ }
+
+ {
+ typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> >
+ seqGraph;
+
+ seqGraph sg(small_world_iterator<RandomGenerator, seqGraph>(gen, N, k, p),
+ small_world_iterator<RandomGenerator, seqGraph>(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ N);
+
+ test_undirected_sequential_algorithms(sg);
+ }
+ }
+}
+
+void usage()
+{
+ std::cerr << "Algorithm Performance Test\n"
+ << "Usage : algorithm_performance [options]\n\n"
+ << "Options are:\n"
+ << "\t--vertices v\t\t\tNumber of vertices in the graph\n"
+ << "\t--edges v\t\t\tNumber of edges in the graph\n"
+ << "\t--seed s\t\t\tSeed for synchronized random number generator\n"
+ << "\t--max-weight miw\t\tMaximum integer edge weight\n"
+ << "\t--rewire-probability\t\tRewire-probabitility (p) for small-world graphs\n"
+ << "\t--dot\t\t\t\tEmit a dot file containing the graph\n"
+ << "\t--verify\t\t\tVerify result\n"
+ << "\t--degree-dist\t\t\tOutput degree distribution of graph\n"
+ << "\t--sequential-graph\t\tRun sequential graph tests\n"
+ << "\t--erdos-renyi\t\t\tRun tests on Erdos-Renyi graphs\n"
+ << "\t--small-world\t\t\tRun tests on Small World graphs\n"
+ << "\t--rmat\t\t\t\tRun tests on R-MAT graphs\n"
+ << "\t--rmat-unique\t\t\tRun tests on R-MAT graphs with no duplicate edges\n"
+ << "\t--csr <bool>\t\t\tRun tests using CSR graphs\n"
+ << "\t--adjacency-list <bool>\t\tRun tests using Adjacency List graphs\n";
+}
+
+
+int test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ rand48 gen;
+
+ // Default args
+ size_t n = 100,
+ m = 8*n,
+ c = 100,
+ num_sources = 32,
+ num_headers = 16 * 1024,
+ batch_buffer_size = 1024 * 1024;
+ uint64_t seed = 1;
+ bool emit_dot_file = false,
+ verify = false,
+ sequential_graph = false,
+ show_degree_dist = false,
+ erdos_renyi = false,
+ small_world = false,
+ rmat = false,
+ rmat_unique = false,
+ csr = false,
+ adj_list = false;
+ double p = 0.1,
+ rmat_a = 0.5,
+ rmat_b = 0.25,
+ rmat_c = 0.1,
+ rmat_d = 0.15;
+
+ // Parse args
+ for (int i = 1; i < argc; ++i) {
+ std::string arg = argv[i];
+
+ if (arg == "--vertices")
+ n = boost::lexical_cast<size_t>( argv[i+1] );
+
+ if (arg == "--seed")
+ seed = boost::lexical_cast<uint64_t>( argv[i+1] );
+
+ if (arg == "--edges")
+ m = boost::lexical_cast<size_t>( argv[i+1] );
+
+ if (arg == "--max-weight")
+ c = boost::lexical_cast<int>( argv[i+1] );
+
+ if (arg == "--batch-buffer-size") {
+ batch_buffer_size = boost::lexical_cast<size_t>( argv[i+1] );
+ num_headers = batch_buffer_size / 16;
+ num_headers = num_headers > 0 ? num_headers : 1;
+ }
+
+ if (arg == "--rewire-probability")
+ p = boost::lexical_cast<double>( argv[i+1] );
+
+ if (arg == "--num-sources")
+ num_sources = boost::lexical_cast<size_t>( argv[i + 1] );
+
+ if (arg == "--erdos-renyi")
+ erdos_renyi = true;
+
+ if (arg == "--small-world")
+ small_world = true;
+
+ if (arg == "--rmat")
+ rmat = true;
+
+ if (arg == "--rmat-unique")
+ rmat_unique = true;
+
+ if (arg == "--dot")
+ emit_dot_file = true;
+
+ if (arg == "--verify")
+ verify = true;
+
+ if (arg == "--degree-dist")
+ show_degree_dist = true;
+
+ if (arg == "--sequential-graph")
+ sequential_graph = true;
+
+ if (arg == "--csr")
+ csr = std::string(argv[i+1]) == "true";
+
+ if (arg == "--adjacency-list")
+ adj_list = std::string(argv[i+1]) == "true";
+ }
+
+ mpi_process_group pg(num_headers, batch_buffer_size);
+
+ if (argc == 1) {
+ if (process_id(pg) == 0)
+ usage();
+ exit(-1);
+ }
+
+ gen.seed(seed);
+
+ parallel::variant_distribution<mpi_process_group> distrib
+ = parallel::block(pg, n);
+
+ if (csr) {
+ if (process_id(pg) == 0)
+ std::cerr << "CSR Graph Tests\n";
+
+ if (erdos_renyi)
+ test_csr(pg, gen, distrib, sequential_graph, n, m, c, num_sources);
+ if (small_world)
+ test_csr(pg, gen, distrib, sequential_graph, n, m, c, p, num_sources);
+ if (rmat)
+ test_csr(pg, gen, distrib, sequential_graph, n, m, c,
+ rmat_a, rmat_b, rmat_c, rmat_d, num_sources, rmat_edge_distribution_tag());
+ if (rmat_unique)
+ test_csr(pg, gen, distrib, sequential_graph, n, m, c,
+ rmat_a, rmat_b, rmat_c, rmat_d, num_sources, rmat_unique_edge_distribution_tag());
+ }
+
+ gen.seed(seed); // DEBUG
+
+ if (adj_list) {
+ if (process_id(pg) == 0)
+ std::cerr << "Adjacency List Graph Tests\n";
+
+ if (erdos_renyi)
+ test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c);
+ if (small_world)
+ test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c, p);
+ if (rmat)
+ test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c,
+ rmat_a, rmat_b, rmat_c, rmat_d, rmat_edge_distribution_tag());
+ if (rmat_unique)
+ test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c,
+ rmat_a, rmat_b, rmat_c, rmat_d, rmat_unique_edge_distribution_tag());
+ }
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_adjacency_list_test.cpp b/src/boost/libs/graph_parallel/test/distributed_adjacency_list_test.cpp
new file mode 100644
index 00000000..cc7ce8cf
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_adjacency_list_test.cpp
@@ -0,0 +1,284 @@
+// Copyright (C) 2004-2008 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
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/distributed/local_subgraph.hpp>
+#include <boost/graph/parallel/distribution.hpp>
+#include <iostream>
+#include <cassert>
+#include <boost/test/minimal.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+template<typename Graph>
+struct never
+{
+ typedef typename graph_traits<Graph>::edge_descriptor argument_type;
+ typedef bool result_type;
+
+ result_type operator()(argument_type) { return false; }
+};
+
+int test_main(int argc, char** argv)
+{
+ boost::mpi::environment env(argc, argv);
+
+ mpi_process_group pg;
+ parallel::block dist(pg, 20);
+
+ typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>,
+ bidirectionalS> Graph1;
+ typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>,
+ directedS> Graph2;
+ typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>,
+ undirectedS> Graph3;
+
+ if (num_processes(pg) > 20) return -1;
+
+ if (process_id(pg) == 0) std::cout << "Graph 1------------------\n";
+
+ std::cout << "Processor #" << process_id(pg) << ": "
+ << dist.block_size(20) << " vertices." << std::endl;
+ {
+ Graph1 g1(20);
+
+ // if (process_id(pg) == num_processes(pg)() - 1)
+ // add_vertex(g1);
+
+ graph_traits<Graph1>::vertex_iterator v, v_end;
+ int counter = 0;
+ for (boost::tie(v, v_end) = vertices(g1); v != v_end; ++v) {
+ std::cout << "Processor #" << process_id(pg) << ": vertex " << ++counter
+ << std::endl;
+
+ out_edges(*v, g1);
+ out_degree(*v, g1);
+ in_edges(*v, g1);
+ in_degree(*v, g1);
+
+ graph_traits<Graph1>::vertex_descriptor other = *v;
+ other.owner = (other.owner + 1) % num_processes(pg);
+ other.local = 0;
+ add_edge(*v, other, g1);
+
+ std::cout << "Adding edge from processor " << process_id(pg)
+ << " to processor " << other.owner << std::endl;
+ }
+
+ synchronize(g1);
+ assert((std::size_t)std::distance(edges(g1).first, edges(g1).second) == num_vertices(g1));
+
+ if (num_vertices(g1) >= 2) {
+ graph_traits<Graph1>::vertex_iterator vi = vertices(g1).first;
+ graph_traits<Graph1>::vertex_descriptor u = *vi++;
+ graph_traits<Graph1>::vertex_descriptor v = *vi++;
+ add_edge(u, v, g1);
+ assert(out_degree(u, g1) == 2);
+ assert(in_degree(v, g1) == 1);
+ }
+
+ int prior_processor = (process_id(pg) + num_processes(pg) - 1)
+ % num_processes(pg);
+ const int n = 20;
+ std::size_t vertices_in_prior = (n / num_processes(pg))
+ + (n % num_processes(pg) > prior_processor? 1 : 0);
+
+ graph_traits<Graph1>::vertex_descriptor u = *vertices(g1).first;
+ if (in_degree(u, g1) != vertices_in_prior) {
+ std::cout << "Processor #" << process_id(pg) << ": " << in_degree(u, g1)
+ << " vs. " << vertices_in_prior << std::endl;
+ }
+ assert(in_degree(u, g1) == vertices_in_prior);
+ std::cout << "Processor #" << process_id(pg) << ": " << num_edges(g1)
+ << " edges.\n";
+
+ local_subgraph<Graph1> local_g1(g1);
+ edges(local_g1);
+ vertices(local_g1);
+ if (num_vertices(local_g1) > 0) {
+ out_edges(*vertices(local_g1).first, local_g1);
+ in_edges(*vertices(local_g1).first, local_g1);
+ adjacent_vertices(*vertices(local_g1).first, local_g1);
+ if (false) {
+ remove_out_edge_if(*vertices(g1).first, never<Graph1>(), g1);
+ remove_in_edge_if(*vertices(g1).first, never<Graph1>(), g1);
+ clear_out_edges(*vertices(g1).first, g1);
+ clear_in_edges(*vertices(g1).first, g1);
+ clear_vertex(*vertices(g1).first, g1);
+ remove_vertex(*vertices(g1).first, g1);
+ }
+ }
+ remove_edge_if(never<Graph1>(), g1);
+ }
+
+
+ if (process_id(pg) == 0) std::cout << "Graph 2------------------\n";
+
+ {
+ Graph2 g2(20);
+
+ if (process_id(pg) == num_processes(pg) - 1)
+ add_vertex(g2);
+
+ graph_traits<Graph2>::vertex_iterator v, v_end;
+ int counter = 0;
+ for (boost::tie(v, v_end) = vertices(g2); v != v_end; ++v) {
+ std::cout << "Processor #" << process_id(pg) << ": vertex " << ++counter
+ << std::endl;
+
+ out_edges(*v, g2);
+ }
+
+ synchronize(g2);
+
+ if (num_vertices(g2) >= 2) {
+ graph_traits<Graph2>::vertex_iterator vi = vertices(g2).first;
+ graph_traits<Graph2>::vertex_descriptor u = *vi++;
+ graph_traits<Graph2>::vertex_descriptor v = *vi++;
+ add_edge(u, v, g2);
+ assert(out_degree(u, g2) == 1);
+ assert(*adjacent_vertices(u, g2).first == v);
+ std::cout << "Processor #" << process_id(pg) << ": " << num_edges(g2)
+ << " edges.\n";
+ assert(std::distance(edges(g2).first, edges(g2).second) == 1);
+
+ }
+ synchronize(g2);
+
+ local_subgraph<Graph2> local_g2(g2);
+ edges(local_g2);
+ vertices(local_g2);
+ if (num_vertices(local_g2) > 0) {
+ out_edges(*vertices(local_g2).first, local_g2);
+ adjacent_vertices(*vertices(local_g2).first, local_g2);
+ remove_out_edge_if(*vertices(g2).first, never<Graph2>(), g2);
+ clear_out_edges(*vertices(g2).first, g2);
+ remove_vertex(*vertices(g2).first, g2);
+ }
+ remove_edge_if(never<Graph2>(), g2);
+ }
+
+ if (process_id(pg) == 0) std::cout << "Graph 3------------------\n";
+
+ {
+ Graph3 g3(20);
+
+ // if (process_id(pg) == num_processes(pg) - 1)
+ // add_vertex(g3);
+
+ graph_traits<Graph3>::vertex_iterator v, v_end;
+ int counter = 0;
+ for (boost::tie(v, v_end) = vertices(g3); v != v_end; ++v) {
+ std::cout << "Processor #" << process_id(pg) << ": vertex " << ++counter
+ << std::endl;
+
+ out_edges(*v, g3);
+ out_degree(*v, g3);
+ in_edges(*v, g3);
+ in_degree(*v, g3);
+ }
+
+ graph_traits<Graph3>::vertices_size_type added_edges = 0;
+ if (num_vertices(g3) >= 2) {
+ graph_traits<Graph3>::vertex_iterator vi = vertices(g3).first;
+ graph_traits<Graph3>::vertex_descriptor u = *vi++;
+ graph_traits<Graph3>::vertex_descriptor v = *vi++;
+ add_edge(u, v, g3); ++added_edges;
+ assert(out_degree(u, g3) == 1);
+ assert(in_degree(u, g3) == 1);
+ graph_traits<Graph3>::edge_descriptor e = *out_edges(u, g3).first;
+ assert(source(e, g3) == u);
+ assert(target(e, g3) == v);
+ e = *in_edges(u, g3).first;
+ assert(source(e, g3) == v);
+ assert(target(e, g3) == u);
+ assert(out_degree(v, g3) == 1);
+ assert(in_degree(v, g3) == 1);
+ e = *out_edges(v, g3).first;
+ assert(source(e, g3) == v);
+ assert(target(e, g3) == u);
+ e = *in_edges(v, g3).first;
+ assert(source(e, g3) == u);
+ assert(target(e, g3) == v);
+
+ assert(*adjacent_vertices(u, g3).first == v);
+ assert(*adjacent_vertices(v, g3).first == u);
+ std::cout << "Processor #" << process_id(pg) << ": " << num_edges(g3)
+ << " edges.\n";
+ }
+
+ // Add some remote edges
+ for (boost::tie(v, v_end) = vertices(g3); v != v_end; ++v) {
+ graph_traits<Graph1>::vertex_descriptor other = *v;
+ other.owner = (other.owner + 1) % num_processes(pg);
+ other.local = 0;
+ add_edge(*v, other, g3); ++added_edges;
+
+ std::cout << "Adding edge from processor " << process_id(pg)
+ << " to processor " << other.owner << std::endl;
+ }
+
+ synchronize(g3);
+ assert(std::distance(edges(g3).first, edges(g3).second) == (ptrdiff_t)added_edges);
+ assert(num_edges(g3) == added_edges);
+
+ // Verify the remote edges
+ if (num_vertices(g3) >= 2) {
+ graph_traits<Graph3>::vertex_iterator vi = vertices(g3).first;
+ graph_traits<Graph3>::vertex_descriptor u = *vi++;
+
+ int prior_processor = (process_id(pg) + num_processes(pg) - 1)
+ % num_processes(pg);
+ const int n = 20;
+ graph_traits<Graph3>::vertices_size_type vertices_in_prior = (n / num_processes(pg))
+ + (n % num_processes(pg) > prior_processor? 1 : 0);
+ if (in_degree(u, g3) != vertices_in_prior + 2) {
+ std::cerr << "#" << process_id(pg) << ": " << in_degree(u, g3)
+ << " != " << vertices_in_prior + 2 << std::endl;
+ }
+
+ assert(in_degree(u, g3) == vertices_in_prior + 2);
+ assert(out_degree(u, g3) == vertices_in_prior + 2);
+ }
+
+ local_subgraph<Graph3> local_g3(g3);
+ edges(local_g3);
+ vertices(local_g3);
+ if (num_vertices(local_g3) > 0) {
+ out_edges(*vertices(local_g3).first, local_g3);
+ in_edges(*vertices(local_g3).first, local_g3);
+ adjacent_vertices(*vertices(local_g3).first, local_g3);
+ remove_out_edge_if(*vertices(g3).first, never<Graph3>(), g3);
+ remove_in_edge_if(*vertices(g3).first, never<Graph3>(), g3);
+ if (false) {
+ // Removing an edge from two processes concurrently is not yet
+ // supported.
+ clear_vertex(*vertices(g3).first, g3);
+ remove_vertex(*vertices(g3).first, g3);
+ }
+ }
+ remove_edge_if(never<Graph3>(), g3);
+ }
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp b/src/boost/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp
new file mode 100644
index 00000000..90c93143
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp
@@ -0,0 +1,295 @@
+// 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: Nick Edmonds
+// Andrew Lumsdaine
+
+#include <boost/graph/use_mpi.hpp>
+
+#define CSR
+
+#ifdef CSR
+# include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
+#else
+# include <boost/graph/distributed/adjacency_list.hpp>
+#endif
+
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/distributed/concepts.hpp>
+#include <boost/graph/erdos_renyi_generator.hpp>
+#include <boost/graph/distributed/betweenness_centrality.hpp>
+#include <boost/random/linear_congruential.hpp>
+#include <boost/graph/graphviz.hpp>
+#include <boost/property_map/vector_property_map.hpp>
+#include <boost/test/minimal.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+/****************************************************************************
+ * Edge weight generator iterator *
+ ****************************************************************************/
+template<typename F, typename RandomGenerator>
+class generator_iterator
+{
+public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef typename F::result_type value_type;
+ typedef const value_type& reference;
+ typedef const value_type* pointer;
+ typedef void difference_type;
+
+ explicit
+ generator_iterator(RandomGenerator& gen, const F& f = F())
+ : f(f), gen(&gen)
+ {
+ value = this->f(gen);
+ }
+
+ reference operator*() const { return value; }
+ pointer operator->() const { return &value; }
+
+ generator_iterator& operator++()
+ {
+ value = f(*gen);
+ return *this;
+ }
+
+ generator_iterator operator++(int)
+ {
+ generator_iterator temp(*this);
+ ++(*this);
+ return temp;
+ }
+
+ bool operator==(const generator_iterator& other) const
+ { return f == other.f; }
+
+ bool operator!=(const generator_iterator& other) const
+ { return !(*this == other); }
+
+private:
+ F f;
+ RandomGenerator* gen;
+ value_type value;
+};
+
+template<typename F, typename RandomGenerator>
+inline generator_iterator<F, RandomGenerator>
+make_generator_iterator( RandomGenerator& gen, const F& f)
+{ return generator_iterator<F, RandomGenerator>(gen, f); }
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+typedef int weight_type;
+
+struct WeightedEdge {
+ WeightedEdge(weight_type weight = 0) : weight(weight) { }
+
+ weight_type weight;
+
+ template<typename Archiver>
+ void serialize(Archiver& ar, const unsigned int /*version*/)
+ {
+ ar & weight;
+ }
+};
+
+int test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+#ifdef CSR
+ typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge,
+ no_property, distributedS<mpi_process_group> >
+ Graph;
+ typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
+ seqGraph;
+#else
+ typedef adjacency_list<vecS,
+ distributedS<mpi_process_group, vecS>,
+ directedS,
+ no_property,
+ property<edge_weight_t, int> > Graph;
+
+ typedef adjacency_list<vecS, vecS, directedS, no_property,
+ property<edge_weight_t, int> > seqGraph;
+#endif
+
+
+ typedef sorted_erdos_renyi_iterator<minstd_rand, Graph> ERIter;
+
+ int n = 100;
+ double prob = 0.1;
+ int C = 3;
+
+ minstd_rand gen;
+
+ gen.seed(1);
+
+ // NOTE: Weighted betweenness centrality only works with non-zero edge weights
+
+ // Build graphs
+ Graph g(edges_are_sorted, ERIter(gen, n, prob), ERIter(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ n);
+
+ gen.seed(1); // Re-seed PRNG so we get the same graph
+
+ seqGraph sg(
+#ifdef CSR
+ edges_are_sorted,
+#endif
+ ERIter(gen, n, prob), ERIter(),
+ make_generator_iterator(gen, uniform_int<int>(1, C)),
+ n);
+
+ // Test Betweenness Centrality
+ typedef property_map<Graph, vertex_index_t>::const_type IndexMap;
+ typedef iterator_property_map<std::vector<int>::iterator, IndexMap>
+ CentralityMap;
+
+ std::vector<int> centralityS(num_vertices(g), 0);
+ CentralityMap centrality(centralityS.begin(), get(vertex_index, g));
+
+ brandes_betweenness_centrality(g, centrality);
+
+ std::vector<int> weightedCentralityS(num_vertices(g), 0);
+ CentralityMap weightedCentrality(weightedCentralityS.begin(), get(vertex_index, g));
+
+ brandes_betweenness_centrality(g, centrality_map(weightedCentrality).
+#ifdef CSR
+ weight_map(get(&WeightedEdge::weight, g)));
+#else
+ weight_map(get(edge_weight, g)));
+#endif
+
+ int g_cpd = central_point_dominance(g, centrality);
+
+ //
+ // Non-distributed (embarassingly parallel) Betweenness Centrality
+ //
+ typedef boost::graph::parallel::process_group_type<Graph>::type
+ process_group_type;
+
+ process_group_type pg = process_group(g);
+
+ process_group_type::process_id_type id = process_id(pg);
+ process_group_type::process_size_type p = num_processes(pg);
+
+ typedef property_map<seqGraph, vertex_index_t>::const_type seqIndexMap;
+ typedef iterator_property_map<std::vector<int>::iterator, seqIndexMap> seqCentralityMap;
+
+ std::vector<int> nonDistributedCentralityS(num_vertices(sg), 0);
+ seqCentralityMap nonDistributedCentrality(nonDistributedCentralityS.begin(), get(vertex_index, sg));
+
+ std::vector<int> nonDistributedWeightedCentralityS(num_vertices(sg), 0);
+ seqCentralityMap nonDistributedWeightedCentrality(nonDistributedWeightedCentralityS.begin(),
+ get(vertex_index, sg));
+
+ non_distributed_brandes_betweenness_centrality(pg, sg, nonDistributedCentrality);
+
+ non_distributed_brandes_betweenness_centrality(pg, sg,
+ centrality_map(nonDistributedWeightedCentrality).
+#ifdef CSR
+ weight_map(get(&WeightedEdge::weight, sg)));
+#else
+ weight_map(get(edge_weight, sg)));
+#endif
+
+ //
+ // Verify
+ //
+ std::vector<int> seqCentralityS(num_vertices(sg), 0);
+ seqCentralityMap seqCentrality(seqCentralityS.begin(), get(vertex_index, sg));
+
+ std::vector<int> seqWeightedCentralityS(num_vertices(sg), 0);
+ seqCentralityMap seqWeightedCentrality(seqWeightedCentralityS.begin(), get(vertex_index, sg));
+
+ brandes_betweenness_centrality(sg, seqCentrality);
+
+ brandes_betweenness_centrality(sg, centrality_map(seqWeightedCentrality).
+#ifdef CSR
+ weight_map(get(&WeightedEdge::weight, sg)));
+#else
+ weight_map(get(edge_weight, sg)));
+#endif
+
+ int sg_cpd = central_point_dominance(sg, seqCentrality);
+
+ // Verify exact betweenness centrality
+ //
+ // We're cheating when we map vertices in g to vertices in sg
+ // since we know that g is using the block distribution here
+ typedef property_map<Graph, vertex_owner_t>::const_type OwnerMap;
+ typedef property_map<Graph, vertex_local_t>::const_type LocalMap;
+
+ OwnerMap owner = get(vertex_owner, g);
+ LocalMap local = get(vertex_local, g);
+
+ bool passed = true;
+
+ {
+ typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
+ vertex_iterator v, v_end;
+
+ for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v) {
+ if (get(centrality, *v) != seqCentralityS[(n/p) * get(owner, *v) + get(local, *v)]) {
+ std::cerr << " " << id << ": Error - centrality of " << get(local, *v) << "@" << get(owner, *v)
+ << " does not match the sequential result (" << get(centrality, *v) << " vs. "
+ << seqCentralityS[(n/p) * get(owner, *v) + get(local, *v)] << ")\n";
+ passed = false;
+ }
+
+ if (get(weightedCentrality, *v) != seqWeightedCentralityS[(n/p) * get(owner, *v) + get(local, *v)]) {
+ std::cerr << " " << id << ": Error - weighted centrality of " << get(local, *v) << "@" << get(owner, *v)
+ << " does not match the sequential result (" << get(weightedCentrality, *v) << " vs. "
+ << seqWeightedCentralityS[(n/p) * get(owner, *v) + get(local, *v)] << ")\n";
+ passed = false;
+ }
+ }
+ }
+
+ if (id == 0) {
+ typedef graph_traits<seqGraph>::vertex_iterator vertex_iterator;
+ vertex_iterator v, v_end;
+
+ for (boost::tie(v, v_end) = vertices(sg); v != v_end; ++v) {
+ if (get(seqCentrality, *v) != get(nonDistributedCentrality, *v)) {
+ std::cerr << " " << id << ": Error - non-distributed centrality of " << *v
+ << " does not match the sequential result (" << get(nonDistributedCentrality, *v)
+ << " vs. " << get(seqCentrality, *v) << ")\n";
+ passed = false;
+ }
+
+ if (get(seqWeightedCentrality, *v) != get(nonDistributedWeightedCentrality, *v)) {
+ std::cerr << " " << id << ": Error - non-distributed weighted centrality of " << *v
+ << " does not match the sequential result (" << get(nonDistributedWeightedCentrality, *v)
+ << " vs. " << get(seqCentrality, *v) << ")\n";
+ passed = false;
+ }
+ }
+ }
+
+ if (g_cpd != sg_cpd) {
+ passed = false;
+ std::cerr << "Central point dominance did not match the sequential result\n";
+ }
+
+ if (!passed)
+ MPI_Abort(MPI_COMM_WORLD, -1);
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_connected_components_test.cpp b/src/boost/libs/graph_parallel/test/distributed_connected_components_test.cpp
new file mode 100644
index 00000000..e630bbb0
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_connected_components_test.cpp
@@ -0,0 +1,204 @@
+// 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
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/serialization/vector.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/graph/connected_components.hpp>
+#include <boost/graph/distributed/connected_components_parallel_search.hpp>
+#include <boost/graph/random.hpp>
+#include <boost/property_map/parallel/distributed_property_map.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/parallel/distribution.hpp>
+#include <boost/graph/erdos_renyi_generator.hpp>
+#include <boost/graph/distributed/graphviz.hpp>
+#include <iostream>
+#include <cstdlib>
+#include <iomanip>
+#include <boost/random.hpp>
+#include <boost/test/minimal.hpp>
+
+#include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
+#include <boost/graph/rmat_graph_generator.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+typedef double time_type;
+
+inline time_type get_time()
+{
+ return MPI_Wtime();
+}
+
+std::string print_time(time_type t)
+{
+ std::ostringstream out;
+ out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
+ return out.str();
+}
+
+template<typename T>
+class map_lt
+{
+public:
+ bool operator()() const { return false; }
+ bool operator()(T x, T y) const { return (owner(x) < owner(y) || (owner(x) == owner(y) && local(x) < local(y))); }
+};
+
+void
+test_distributed_connected_components(int n, double _p, bool verify, bool emit_dot_file, int seed, bool parallel_search)
+{
+// typedef adjacency_list<listS,
+// distributedS<mpi_process_group, vecS>,
+// undirectedS> Graph;
+
+ typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
+ distributedS<mpi_process_group> > Graph;
+
+ minstd_rand gen;
+
+ gen.seed(seed);
+
+ mpi_process_group pg;
+ parallel::variant_distribution<mpi_process_group> distrib
+ = parallel::block(pg, n);
+
+ minstd_rand dist_gen;
+#if 0
+ if (false) {
+ distrib = parallel::random_distribution(pg, dist_gen, n);
+ } else if (true) {
+ distrib = parallel::oned_block_cyclic(pg, 13);
+ }
+#endif
+
+// Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
+// erdos_renyi_iterator<minstd_rand, Graph>(),
+// n, pg, distrib);
+
+ int m = int(n * n * _p/2);
+ double a = 0.57, b = 0.19, c = 0.19, d = 0.05;
+
+ // Last boolean parameter makes R-MAT bidirectional
+ Graph g(sorted_unique_rmat_iterator<minstd_rand, Graph>(gen, n, m, a, b, c, d, true),
+ sorted_unique_rmat_iterator<minstd_rand, Graph>(),
+ n, pg, distrib);
+
+ synchronize(g);
+
+ std::vector<int> local_components_vec(num_vertices(g));
+ typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> ComponentMap;
+ ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
+
+ int num_components = 0;
+
+ time_type start = get_time();
+ if (parallel_search) {
+ num_components = connected_components_ps(g, component);
+ } else {
+ num_components = connected_components(g, component);
+ }
+ time_type end = get_time();
+ if (process_id(g.process_group()) == 0)
+ std::cerr << "Connected Components time = " << print_time(end - start) << " seconds.\n"
+ << num_components << " components identified\n";
+
+ if ( verify )
+ {
+ if ( process_id(g.process_group()) == 0 )
+ {
+ component.set_max_ghost_cells(0);
+ for (int i = 0; i < n; ++i)
+ get(component, vertex(i, g));
+ synchronize(component);
+
+ // Check against the sequential version
+ typedef adjacency_list<listS,
+ vecS,
+ undirectedS,
+ // Vertex properties
+ no_property,
+ // Edge properties
+ no_property > Graph2;
+
+ gen.seed(seed);
+
+// Graph2 g2(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
+// erdos_renyi_iterator<minstd_rand, Graph>(),
+// n);
+
+ Graph2 g2( sorted_unique_rmat_iterator<minstd_rand, Graph>(gen, n, m, a, b, c, d, true),
+ sorted_unique_rmat_iterator<minstd_rand, Graph>(),
+ n);
+
+ std::vector<int> component2 (n);
+ int tmp;
+ tmp = connected_components(g2, make_iterator_property_map(component2.begin(), get(vertex_index, g2)));
+ std::cerr << "Verifier found " << tmp << " components" << std::endl;
+
+ // Make sure components and component2 match
+ std::map<int, int> c2c;
+ int i;
+ // This fails if there are more components in 'component' than
+ // 'component2' because multiple components in 'component' may
+ // legitimately map to the same component number in 'component2'.
+ // We can either test the mapping in the opposite direction or
+ // just assert that the numbers of components found by both
+ // algorithms is the same
+ for ( i = 0; i < n; i++ )
+ if ( c2c.find( get(component, vertex(i, g)) ) == c2c.end() )
+ c2c[get(component, vertex(i, g))] = component2[i];
+ else
+ if ( c2c[get(component, vertex(i, g))] != component2[i] )
+ break;
+
+ if ( i < n || num_components != tmp) {
+ printf("Unable to verify CC result...\n");
+ } else
+ printf("Passed verification... %i connected components\n",
+ (int)c2c.size());
+ }
+ else
+ {
+ synchronize(component);
+ }
+ if ( emit_dot_file )
+ write_graphviz("cc.dot", g, paint_by_number(component));
+ }
+}
+
+int test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ if ( argc < 6 ) {
+ test_distributed_connected_components(10000, 0.001, true, false, 1, false);
+ test_distributed_connected_components(10000, 0.001, true, false, 1, true);
+ }
+ else
+ test_distributed_connected_components
+ (atoi(argv[1]), atof(argv[2]),
+ argv[3]==std::string("true"), argv[4]==std::string("true"),
+ argc == 6? 1 : atoi(argv[6]),
+ argv[5]==std::string("true"));
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp b/src/boost/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp
new file mode 100644
index 00000000..0653cc91
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp
@@ -0,0 +1,369 @@
+// 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: Nick Edmonds
+// Andrew Lumsdaine
+
+// A test of the distributed compressed sparse row graph type
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/distributed/concepts.hpp>
+
+#include <boost/graph/erdos_renyi_generator.hpp>
+#include <boost/graph/small_world_generator.hpp>
+#include <boost/graph/rmat_graph_generator.hpp>
+
+#include <boost/graph/breadth_first_search.hpp>
+#include <boost/graph/depth_first_search.hpp>
+#include <boost/graph/distributed/delta_stepping_shortest_paths.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/graph/distributed/page_rank.hpp>
+#include <boost/graph/distributed/boman_et_al_graph_coloring.hpp>
+#include <boost/graph/connected_components.hpp>
+#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>
+#endif
+
+#include <boost/graph/distributed/vertex_list_adaptor.hpp> // Needed for MST
+
+#include <boost/random/linear_congruential.hpp>
+#include <boost/graph/graphviz.hpp>
+#include <boost/property_map/vector_property_map.hpp>
+#include <boost/test/minimal.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+
+/****************************************************************************
+ * Edge weight generator iterator *
+ ****************************************************************************/
+template<typename F, typename RandomGenerator>
+class generator_iterator
+{
+public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef typename F::result_type value_type;
+ typedef const value_type& reference;
+ typedef const value_type* pointer;
+ typedef void difference_type;
+
+ explicit
+ generator_iterator(RandomGenerator& gen, const F& f = F())
+ : f(f), gen(&gen)
+ {
+ value = this->f(gen);
+ }
+
+ reference operator*() const { return value; }
+ pointer operator->() const { return &value; }
+
+ generator_iterator& operator++()
+ {
+ value = f(*gen);
+ return *this;
+ }
+
+ generator_iterator operator++(int)
+ {
+ generator_iterator temp(*this);
+ ++(*this);
+ return temp;
+ }
+
+ bool operator==(const generator_iterator& other) const
+ { return f == other.f; }
+
+ bool operator!=(const generator_iterator& other) const
+ { return !(*this == other); }
+
+private:
+ F f;
+ RandomGenerator* gen;
+ value_type value;
+};
+
+template<typename F, typename RandomGenerator>
+inline generator_iterator<F, RandomGenerator>
+make_generator_iterator( RandomGenerator& gen, const F& f)
+{ return generator_iterator<F, RandomGenerator>(gen, f); }
+
+
+/****************************************************************************
+ * Printing DFS Visitor *
+ ****************************************************************************/
+
+struct printing_dfs_visitor
+{
+ template<typename Vertex, typename Graph>
+ void initialize_vertex(Vertex v, const Graph& g)
+ {
+ vertex_event("initialize_vertex", v, g);
+ }
+
+ template<typename Vertex, typename Graph>
+ void start_vertex(Vertex v, const Graph& g)
+ {
+ vertex_event("start_vertex", v, g);
+ }
+
+ template<typename Vertex, typename Graph>
+ void discover_vertex(Vertex v, const Graph& g)
+ {
+ vertex_event("discover_vertex", v, g);
+ }
+
+ template<typename Edge, typename Graph>
+ void examine_edge(Edge e, const Graph& g)
+ {
+ edge_event("examine_edge", e, g);
+ }
+
+ template<typename Edge, typename Graph>
+ void tree_edge(Edge e, const Graph& g)
+ {
+ edge_event("tree_edge", e, g);
+ }
+
+ template<typename Edge, typename Graph>
+ void back_edge(Edge e, const Graph& g)
+ {
+ edge_event("back_edge", e, g);
+ }
+
+ template<typename Edge, typename Graph>
+ void forward_or_cross_edge(Edge e, const Graph& g)
+ {
+ edge_event("forward_or_cross_edge", e, g);
+ }
+
+ template<typename Vertex, typename Graph>
+ void finish_vertex(Vertex v, const Graph& g)
+ {
+ vertex_event("finish_vertex", v, g);
+ }
+
+private:
+ template<typename Vertex, typename Graph>
+ void vertex_event(const char* name, Vertex v, const Graph& g)
+ {
+ std::cerr << "#" << process_id(g.process_group()) << ": " << name << "("
+ << get_vertex_name(v, g) << ": " << local(v) << "@" << owner(v)
+ << ")\n";
+ }
+
+ template<typename Edge, typename Graph>
+ void edge_event(const char* name, Edge e, const Graph& g)
+ {
+ std::cerr << "#" << process_id(g.process_group()) << ": " << name << "("
+ << get_vertex_name(source(e, g), g) << ": "
+ << local(source(e, g)) << "@" << owner(source(e, g)) << ", "
+ << get_vertex_name(target(e, g), g) << ": "
+ << local(target(e, g)) << "@" << owner(target(e, g)) << ")\n";
+ }
+
+};
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+typedef int weight_type;
+
+struct WeightedEdge {
+ WeightedEdge(weight_type weight = 0) : weight(weight) { }
+
+ weight_type weight;
+
+ template<typename Archiver>
+ void serialize(Archiver& ar, const unsigned int /*version*/)
+ {
+ ar & weight;
+ }
+};
+
+struct VertexProperties {
+ VertexProperties(int d = 0)
+ : distance(d) { }
+
+ int distance;
+
+ template<typename Archiver>
+ void serialize(Archiver& ar, const unsigned int /*version*/)
+ {
+ ar & distance;
+ }
+};
+
+int test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ typedef compressed_sparse_row_graph<directedS, VertexProperties, WeightedEdge,
+ no_property, distributedS<mpi_process_group> >
+ Digraph;
+
+ // Make sure we can build graphs using common graph generators
+ typedef sorted_erdos_renyi_iterator<minstd_rand, Digraph> ERIter;
+ typedef small_world_iterator<minstd_rand, Digraph> SWIter;
+ typedef sorted_rmat_iterator<minstd_rand, Digraph> RMATIter;
+
+ typedef graph_traits<Digraph>::edge_descriptor edge_descriptor;
+
+ int n = 40;
+ int k = 3;
+ double prob = 0.1;
+ int C = 10;
+ double a = 0.5, b = 0.1, c = 0.25, d = 0.15;
+ int iterations = 50;
+ int num_colors = n / 10;
+ int lookahead = C / 10;
+
+ minstd_rand gen;
+
+ // Directed Graphs
+ Digraph g(ERIter(gen, n, prob), ERIter(),
+ make_generator_iterator(gen, uniform_int<int>(0, C)),
+ n);
+ Digraph g2(SWIter(gen, n, k, prob), SWIter(), n);
+ Digraph g3(RMATIter(gen, n, size_t(n*n*prob), a, b, c, d), RMATIter(), n);
+
+ // Test BFS
+ breadth_first_search(g, vertex(0, g), visitor(bfs_visitor<>()));
+
+ // Test SSSP Algorithms
+ graph::distributed::delta_stepping_shortest_paths(g,
+ vertex(0, g),
+ dummy_property_map(),
+ get(&VertexProperties::distance, g),
+ get(&WeightedEdge::weight, g));
+
+ dijkstra_shortest_paths(g, vertex(0, g),
+ distance_map(get(&VertexProperties::distance, g)).
+ weight_map(get(&WeightedEdge::weight, g)));
+
+ dijkstra_shortest_paths(g, vertex(0, g),
+ distance_map(get(&VertexProperties::distance, g)).
+ weight_map(get(&WeightedEdge::weight, g)).
+ lookahead(lookahead));
+
+ // Test PageRank
+ using boost::graph::n_iterations;
+
+ std::vector<double> ranks(num_vertices(g));
+
+ page_rank(g,
+ make_iterator_property_map(ranks.begin(),
+ get(boost::vertex_index, g)),
+ n_iterations(iterations), 0.85, vertex(0, g));
+
+ // Test Graph Coloring
+ typedef property_map<Digraph, vertex_index_t>::type vertex_index_map;
+
+ std::vector<int> colors_vec(num_vertices(g));
+ iterator_property_map<int*, vertex_index_map> color(&colors_vec[0],
+ get(vertex_index, g));
+
+ graph::boman_et_al_graph_coloring(g, color, num_colors);
+
+ // Test DFS
+ //
+ // DFS requires an undirected graph, currently CSR graphs must be directed
+#if 0
+ std::vector<vertex_descriptor> parent(num_vertices(g));
+ std::vector<vertex_descriptor> explore(num_vertices(g));
+
+ boost::graph::tsin_depth_first_visit
+ (g,
+ vertex(0, g),
+ printing_dfs_visitor(),
+ color,
+ make_iterator_property_map(parent.begin(), get(vertex_index, g)),
+ make_iterator_property_map(explore.begin(), get(vertex_index, g)),
+ 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
+#if 0
+ std::vector<int> local_components_vec(num_vertices(g));
+ typedef iterator_property_map<std::vector<int>::iterator,
+ vertex_index_map> ComponentMap;
+ ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
+
+ assert(connected_components(g, component) ==
+ connected_components_ps(g, component));
+#endif
+
+ // Test Betweenness Centrality
+ //
+ // Betweenness Centrality is broken at the moment
+ typedef iterator_property_map<std::vector<int>::iterator, vertex_index_map>
+ CentralityMap;
+
+ std::vector<int> centralityS(num_vertices(g), 0);
+ CentralityMap centrality(centralityS.begin(), get(vertex_index, g));
+
+ brandes_betweenness_centrality(g, centrality);
+
+ //
+ // Test MST
+ //
+ std::vector<edge_descriptor> mst_edges;
+
+ dense_boruvka_minimum_spanning_tree(make_vertex_list_adaptor(g),
+ get(&WeightedEdge::weight, g),
+ std::back_inserter(mst_edges));
+
+ mst_edges.clear();
+ merge_local_minimum_spanning_trees(make_vertex_list_adaptor(g),
+ get(&WeightedEdge::weight, g),
+ std::back_inserter(mst_edges));
+
+ mst_edges.clear();
+ boruvka_then_merge(make_vertex_list_adaptor(g),
+ get(&WeightedEdge::weight, g),
+ std::back_inserter(mst_edges));
+
+ mst_edges.clear();
+ boruvka_mixed_merge(make_vertex_list_adaptor(g),
+ get(&WeightedEdge::weight, g),
+ std::back_inserter(mst_edges));
+
+ // Test Strong Components
+ //
+ // Can't build reverse graph of a CSR graph
+#if 0
+ std::vector<int> local_components_vec(num_vertices(g));
+ typedef iterator_property_map<std::vector<int>::iterator,
+ vertex_index_map> ComponentMap;
+ ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
+
+ int num_components = strong_components(g, component);
+#endif
+
+ std::ofstream out("dcsr.dot");
+ write_graphviz(out, g);
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_csr_test.cpp b/src/boost/libs/graph_parallel/test/distributed_csr_test.cpp
new file mode 100644
index 00000000..a6833ecb
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_csr_test.cpp
@@ -0,0 +1,103 @@
+// 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
+// Andrew Lumsdaine
+
+// A test of the distributed compressed sparse row graph type
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/serialization/vector.hpp>
+#include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/distributed/concepts.hpp>
+#include <boost/graph/erdos_renyi_generator.hpp>
+#include <boost/random/linear_congruential.hpp>
+#include <boost/graph/breadth_first_search.hpp>
+#include <boost/graph/graphviz.hpp>
+#include <boost/property_map/vector_property_map.hpp>
+#include <boost/test/minimal.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+void concept_checks()
+{
+ typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
+ distributedS<mpi_process_group> >
+ Digraph;
+ typedef graph_traits<Digraph>::vertex_descriptor vertex_descriptor;
+ typedef graph_traits<Digraph>::edge_descriptor edge_descriptor;
+
+ function_requires< GraphConcept<Digraph> >();
+ function_requires< IncidenceGraphConcept<Digraph> >();
+ function_requires< AdjacencyGraphConcept<Digraph> >();
+
+ function_requires< DistributedVertexListGraphConcept<Digraph> >();
+ function_requires< DistributedEdgeListGraphConcept<Digraph> >();
+
+ function_requires<
+ ReadablePropertyGraphConcept<Digraph, vertex_descriptor, vertex_global_t>
+ >();
+ function_requires<
+ ReadablePropertyGraphConcept<Digraph, vertex_descriptor, vertex_owner_t>
+ >();
+ function_requires<
+ ReadablePropertyGraphConcept<Digraph, vertex_descriptor, vertex_local_t>
+ >();
+ function_requires<
+ ReadablePropertyGraphConcept<Digraph, vertex_descriptor, vertex_index_t>
+ >();
+
+ function_requires<
+ ReadablePropertyGraphConcept<Digraph, edge_descriptor, edge_global_t>
+ >();
+
+ // DPG TBD: edge_owner, edge_local property maps
+
+ function_requires<
+ ReadablePropertyGraphConcept<Digraph, edge_descriptor, edge_index_t>
+ >();
+
+ // Check default construction
+ Digraph g;
+}
+
+int test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ concept_checks();
+
+ typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
+ distributedS<mpi_process_group> >
+ Digraph;
+
+ // Build an Erdos-Renyi graph to test with
+ typedef sorted_erdos_renyi_iterator<minstd_rand, Digraph> ERIter;
+
+ int n = 40;
+ double prob = 0.1;
+
+ minstd_rand gen;
+ Digraph g(ERIter(gen, n, prob), ERIter(), n);
+
+ breadth_first_search(g, vertex(0, g), visitor(bfs_visitor<>()));
+
+ std::ofstream out("dcsr.dot");
+ write_graphviz(out, g);
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_dfs_test.cpp b/src/boost/libs/graph_parallel/test/distributed_dfs_test.cpp
new file mode 100644
index 00000000..d21491b3
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_dfs_test.cpp
@@ -0,0 +1,167 @@
+//=======================================================================
+// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
+// Copyright 2004 Douglas Gregor
+// Copyright (C) 2006-2008
+
+// Distributed under 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)
+//=======================================================================
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/serialization/vector.hpp>
+#include <boost/graph/depth_first_search.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/test/minimal.hpp>
+#include <iostream>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+// Set up the vertex names
+enum vertex_id_t { u, v, w, x, y, z, N };
+char vertex_names[] = { 'u', 'v', 'w', 'x', 'y', 'z' };
+
+template<typename Vertex, typename Graph>
+char get_vertex_name(Vertex v, const Graph& g)
+{
+ return vertex_names[g.distribution().global(owner(v), local(v))];
+}
+
+struct printing_dfs_visitor
+{
+ template<typename Vertex, typename Graph>
+ void initialize_vertex(Vertex v, const Graph& g)
+ {
+ vertex_event("initialize_vertex", v, g);
+ }
+
+ template<typename Vertex, typename Graph>
+ void start_vertex(Vertex v, const Graph& g)
+ {
+ vertex_event("start_vertex", v, g);
+ }
+
+ template<typename Vertex, typename Graph>
+ void discover_vertex(Vertex v, const Graph& g)
+ {
+ vertex_event("discover_vertex", v, g);
+ }
+
+ template<typename Edge, typename Graph>
+ void examine_edge(Edge e, const Graph& g)
+ {
+ edge_event("examine_edge", e, g);
+ }
+
+ template<typename Edge, typename Graph>
+ void tree_edge(Edge e, const Graph& g)
+ {
+ edge_event("tree_edge", e, g);
+ }
+
+ template<typename Edge, typename Graph>
+ void back_edge(Edge e, const Graph& g)
+ {
+ edge_event("back_edge", e, g);
+ }
+
+ template<typename Edge, typename Graph>
+ void forward_or_cross_edge(Edge e, const Graph& g)
+ {
+ edge_event("forward_or_cross_edge", e, g);
+ }
+
+ template<typename Vertex, typename Graph>
+ void finish_vertex(Vertex v, const Graph& g)
+ {
+ vertex_event("finish_vertex", v, g);
+ }
+
+private:
+ template<typename Vertex, typename Graph>
+ void vertex_event(const char* name, Vertex v, const Graph& g)
+ {
+ std::cerr << "#" << process_id(g.process_group()) << ": " << name << "("
+ << get_vertex_name(v, g) << ": " << local(v) << "@" << owner(v)
+ << ")\n";
+ }
+
+ template<typename Edge, typename Graph>
+ void edge_event(const char* name, Edge e, const Graph& g)
+ {
+ std::cerr << "#" << process_id(g.process_group()) << ": " << name << "("
+ << get_vertex_name(source(e, g), g) << ": "
+ << local(source(e, g)) << "@" << owner(source(e, g)) << ", "
+ << get_vertex_name(target(e, g), g) << ": "
+ << local(target(e, g)) << "@" << owner(target(e, g)) << ")\n";
+ }
+
+};
+
+void
+test_distributed_dfs()
+{
+ typedef adjacency_list<listS,
+ distributedS<mpi_process_group, vecS>,
+ undirectedS,
+ // Vertex properties
+ property<vertex_color_t, default_color_type> >
+ Graph;
+ typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+
+ // Specify the edges in the graph
+ typedef std::pair<int, int> E;
+ E edge_array[] = { E(u, v), E(u, w), E(u, x), E(x, v), E(y, x),
+ E(v, y), E(w, y), E(w, z), E(z, z) };
+ Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(E), N);
+
+ std::vector<vertex_descriptor> parent(num_vertices(g));
+ std::vector<vertex_descriptor> explore(num_vertices(g));
+
+ boost::graph::tsin_depth_first_visit
+ (g,
+ vertex(u, g),
+ printing_dfs_visitor(),
+ get(vertex_color, g),
+ make_iterator_property_map(parent.begin(), get(vertex_index, g)),
+ make_iterator_property_map(explore.begin(), get(vertex_index, g)),
+ get(vertex_index, g));
+
+#if 0
+ std::size_t correct_parents1[N] = {u, u, y, y, v, w};
+ std::size_t correct_parents2[N] = {u, u, y, v, x, w};
+#endif
+
+ for (std::size_t i = 0; i < N; ++i) {
+ vertex_descriptor v = vertex(i, g);
+ if (owner(v) == process_id(g.process_group())) {
+ std::cout << "parent(" << get_vertex_name(v, g) << ") = "
+ << get_vertex_name(parent[v.local], g) << std::endl;
+
+ }
+ }
+
+ if (false) {
+ depth_first_visit(g, vertex(u, g), printing_dfs_visitor());
+ }
+}
+
+int
+test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+ test_distributed_dfs();
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_dimacs_reader.cpp b/src/boost/libs/graph_parallel/test/distributed_dimacs_reader.cpp
new file mode 100644
index 00000000..a2e3cb7b
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_dimacs_reader.cpp
@@ -0,0 +1,85 @@
+// 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: Brian Barrett
+// Nick Edmonds
+// Andrew Lumsdaine
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/property_map/parallel/distributed_property_map.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/dimacs.hpp>
+#include <boost/graph/graphviz.hpp>
+#include <boost/test/minimal.hpp>
+
+#include <iostream>
+#include <cstdlib>
+#include <iomanip>
+#include <fstream>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using namespace boost::graph;
+using boost::graph::distributed::mpi_process_group;
+
+typedef double time_type;
+
+inline time_type get_time()
+{
+ return MPI_Wtime();
+}
+
+std::string print_time(time_type t)
+{
+ std::ostringstream out;
+ out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
+ return out.str();
+}
+
+void
+test_dimacs_reader(const char *filename)
+{
+ mpi_process_group pg;
+
+ typedef adjacency_list<vecS,
+ distributedS<mpi_process_group, vecS>,
+ undirectedS> Graph;
+
+ std::ifstream file(filename);
+ dimacs_basic_reader reader = dimacs_basic_reader(file, false);
+ dimacs_basic_reader end;
+ boost::parallel::variant_distribution<mpi_process_group> distrib =
+ boost::parallel::block(pg, reader.n_vertices());
+
+ Graph g(dimacs_edge_iterator<dimacs_basic_reader>(reader),
+ dimacs_edge_iterator<dimacs_basic_reader>(end),
+ reader.n_vertices(), pg, distrib);;
+
+ // write_graphviz("reader.dot", g);
+}
+
+int
+test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ if (argc == 2) {
+ test_dimacs_reader(argv[1]);
+ }
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_graph_coloring_test.cpp b/src/boost/libs/graph_parallel/test/distributed_graph_coloring_test.cpp
new file mode 100644
index 00000000..2b219c0a
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_graph_coloring_test.cpp
@@ -0,0 +1,101 @@
+// Copyright (C) 2005, 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
+#define PBGL_ACCOUNTING
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/serialization/vector.hpp>
+#include <boost/graph/distributed/boman_et_al_graph_coloring.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/graph/parallel/distribution.hpp>
+#include <boost/graph/erdos_renyi_generator.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/graph/graphviz.hpp>
+#include <iostream>
+#include <boost/random.hpp>
+#include <boost/test/minimal.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+void
+test_distributed_graph_coloring(int n, double p, int s,
+ int seed, bool emit_dot_file)
+{
+ typedef adjacency_list<listS,
+ distributedS<mpi_process_group, vecS>,
+ undirectedS> Graph;
+
+ typedef property_map<Graph, vertex_index_t>::type vertex_index_map;
+
+ // Build a random number generator
+ minstd_rand gen;
+ gen.seed(seed);
+
+ // Build a random graph
+ Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, p),
+ erdos_renyi_iterator<minstd_rand, Graph>(),
+ n);
+
+ // Set up color map
+ std::vector<int> colors_vec(num_vertices(g));
+ iterator_property_map<int*, vertex_index_map> color(&colors_vec[0],
+ get(vertex_index, g));
+
+ // Run the graph coloring algorithm
+ graph::boman_et_al_graph_coloring(g, color, s);
+
+ if (process_id(g.process_group()) == 0) {
+ graph::distributed::boman_et_al_graph_coloring_stats.print(std::cout);
+ }
+
+ if ( emit_dot_file ) {
+ if ( process_id(g.process_group()) == 0 ) {
+ for (int i = 0; i < n; ++i)
+ get(color, vertex(i, g));
+ synchronize(color);
+ } else {
+ synchronize(color);
+ }
+
+ write_graphviz("coloring.dot", g, paint_by_number(color));
+ }
+}
+
+int test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ int n = 1000;
+ double p = 0.01;
+ int s = 100;
+ int seed = 1;
+ bool emit_dot_file = false;
+
+ if (argc > 1) n = lexical_cast<int>(argv[1]);
+ if (argc > 2) p = lexical_cast<double>(argv[2]);
+ if (argc > 3) s = lexical_cast<int>(argv[3]);
+ if (argc > 4) seed = lexical_cast<int>(argv[4]);
+ if (argc > 5) emit_dot_file = lexical_cast<bool>(argv[5]);
+
+ test_distributed_graph_coloring(n, p, s, seed, emit_dot_file);
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_mst_test.cpp b/src/boost/libs/graph_parallel/test/distributed_mst_test.cpp
new file mode 100644
index 00000000..614116f6
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_mst_test.cpp
@@ -0,0 +1,151 @@
+// Copyright 2004 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
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/serialization/vector.hpp>
+#include <boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/distributed/vertex_list_adaptor.hpp>
+#include <boost/graph/parallel/distribution.hpp>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <iostream>
+#include <cstdlib>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+template<typename Graph, typename WeightMap, typename InputIterator>
+int
+total_weight(const Graph& g, WeightMap weight_map,
+ InputIterator first, InputIterator last)
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+
+ int total_weight = 0;
+ while (first != last) {
+ total_weight += get(weight_map, *first);
+ if (process_id(g.process_group()) == 0) {
+ vertex_descriptor u = source(*first, g);
+ vertex_descriptor v = target(*first, g);
+ std::cout << "(" << g.distribution().global(owner(u), local(u))
+ << ", " << g.distribution().global(owner(v), local(v))
+ << ")\n";
+ }
+ ++first;
+ }
+
+ return total_weight;
+}
+
+void
+test_distributed_dense_boruvka()
+{
+ typedef adjacency_list<listS,
+ distributedS<mpi_process_group, vecS>,
+ undirectedS,
+ // Vertex properties
+ no_property,
+ // Edge properties
+ property<edge_weight_t, int> > Graph;
+
+ typedef graph_traits<Graph>::edge_descriptor edge_descriptor;
+
+ typedef std::pair<int, int> E;
+
+ const int num_nodes = 5;
+ E edge_array[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3),
+ E(3, 4), E(4, 0), E(4, 1)
+ };
+ int weights[] = { 1, 1, 2, 7, 3, 1, 1, 1 };
+ std::size_t num_edges = sizeof(edge_array) / sizeof(E);
+
+ Graph g(edge_array, edge_array + num_edges, weights, num_nodes);
+
+ {
+ if (process_id(g.process_group()) == 0)
+ std::cerr << "--Dense Boruvka--\n";
+ typedef property_map<Graph, edge_weight_t>::type WeightMap;
+ WeightMap weight_map = get(edge_weight, g);
+
+ std::vector<edge_descriptor> mst_edges;
+ dense_boruvka_minimum_spanning_tree(make_vertex_list_adaptor(g),
+ weight_map,
+ std::back_inserter(mst_edges));
+ int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
+ BOOST_CHECK(w == 4);
+ BOOST_CHECK(mst_edges.size() == 4);
+ }
+
+ {
+ if (process_id(g.process_group()) == 0)
+ std::cerr << "--Merge local MSTs--\n";
+ typedef property_map<Graph, edge_weight_t>::type WeightMap;
+ WeightMap weight_map = get(edge_weight, g);
+
+ std::vector<edge_descriptor> mst_edges;
+ merge_local_minimum_spanning_trees(make_vertex_list_adaptor(g), weight_map,
+ std::back_inserter(mst_edges));
+ if (process_id(g.process_group()) == 0) {
+ int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
+ BOOST_CHECK(w == 4);
+ BOOST_CHECK(mst_edges.size() == 4);
+ }
+ }
+
+ {
+ if (process_id(g.process_group()) == 0)
+ std::cerr << "--Boruvka then Merge--\n";
+ typedef property_map<Graph, edge_weight_t>::type WeightMap;
+ WeightMap weight_map = get(edge_weight, g);
+
+ std::vector<edge_descriptor> mst_edges;
+ boruvka_then_merge(make_vertex_list_adaptor(g), weight_map,
+ std::back_inserter(mst_edges));
+ if (process_id(g.process_group()) == 0) {
+ int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
+ BOOST_CHECK(w == 4);
+ BOOST_CHECK(mst_edges.size() == 4);
+ }
+ }
+
+ {
+ if (process_id(g.process_group()) == 0)
+ std::cerr << "--Boruvka mixed Merge--\n";
+ typedef property_map<Graph, edge_weight_t>::type WeightMap;
+ WeightMap weight_map = get(edge_weight, g);
+
+ std::vector<edge_descriptor> mst_edges;
+ boruvka_mixed_merge(make_vertex_list_adaptor(g), weight_map,
+ std::back_inserter(mst_edges));
+ if (process_id(g.process_group()) == 0) {
+ int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
+ BOOST_CHECK(w == 4);
+ BOOST_CHECK(mst_edges.size() == 4);
+ }
+ }
+}
+
+int test_main(int argc, char** argv)
+{
+ boost::mpi::environment env(argc, argv);
+ test_distributed_dense_boruvka();
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_page_rank_test.cpp b/src/boost/libs/graph_parallel/test/distributed_page_rank_test.cpp
new file mode 100644
index 00000000..d7b29457
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_page_rank_test.cpp
@@ -0,0 +1,110 @@
+// Copyright 2004 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
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/serialization/vector.hpp>
+#include <boost/graph/distributed/page_rank.hpp>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/test/minimal.hpp>
+#include <vector>
+#include <iostream>
+#include <stdlib.h>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+bool close_to(double x, double y)
+{
+ double diff = x - y;
+ if (diff < 0) diff = -diff;
+ double base = (y == 0? x : y);
+ if (base != 0) return diff / base < 0.01;
+ else return true;
+}
+
+// Make convenient labels for the vertices
+enum vertex_id_t { A, B, C, D, N };
+
+void test_distributed_page_rank(int iterations)
+{
+ using namespace boost::graph;
+
+ // create a typedef for the Graph type
+ typedef adjacency_list<vecS,
+ distributedS<mpi_process_group, vecS>,
+ bidirectionalS
+ > Graph;
+ typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+
+ // writing out the edges in the graph
+ typedef std::pair<int, int> Edge;
+ Edge edge_array[] =
+ { Edge(A,B), Edge(A,C), Edge(B,C), Edge(C,A), Edge(D,C) };
+ const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
+
+ // declare a graph object
+ Graph g(edge_array, edge_array + num_edges, N);
+
+ std::vector<double> ranks(num_vertices(g));
+
+ page_rank(g,
+ make_iterator_property_map(ranks.begin(),
+ get(boost::vertex_index, g)),
+ n_iterations(iterations), 0.85, N);
+
+ double local_sum = 0.0;
+ for(unsigned int i = 0; i < num_vertices(g); ++i) {
+ std::cout << (char)('A' + g.distribution().global(i)) << " = "
+ << ranks[i] << std::endl;
+ local_sum += ranks[i];
+ }
+ double sum=0.;
+ boost::mpi::reduce(communicator(g.process_group()),
+ local_sum, sum, std::plus<double>(), 0);
+ if (process_id(g.process_group()) == 0) {
+ std::cout << "Sum = " << sum << "\n\n";
+ BOOST_CHECK(close_to(sum, 4)); // 1 when alpha=0
+ }
+
+ // double expected_ranks0[N] = {0.400009, 0.199993, 0.399998, 0.0};
+ double expected_ranks[N] = {1.49011, 0.783296, 1.5766, 0.15};
+ for (int i = 0; i < N; ++i) {
+ vertex_descriptor v = vertex(i, g);
+ if (v != Graph::null_vertex()
+ && owner(v) == process_id(g.process_group())) {
+ BOOST_CHECK(close_to(ranks[local(v)], expected_ranks[i]));
+ }
+ }
+}
+
+int test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ int iterations = 50;
+ if (argc > 1) {
+ iterations = atoi(argv[1]);
+ }
+
+ test_distributed_page_rank(iterations);
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_property_map_test.cpp b/src/boost/libs/graph_parallel/test/distributed_property_map_test.cpp
new file mode 100644
index 00000000..6304fffa
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_property_map_test.cpp
@@ -0,0 +1,356 @@
+// Copyright (C) 2004-2008 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
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <boost/test/minimal.hpp>
+#include <vector>
+#include <string>
+#include <boost/serialization/vector.hpp>
+#include <boost/serialization/string.hpp>
+#include <boost/serialization/utility.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/graph/parallel/basic_reduce.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+enum color_t { red, blue };
+
+struct remote_key
+{
+ remote_key(int p = -1, std::size_t l = 0) : processor(p), local_key(l) {}
+
+ int processor;
+ std::size_t local_key;
+
+ template<typename Archiver>
+ void serialize(Archiver& ar, const unsigned int /*version*/)
+ {
+ ar & processor & local_key;
+ }
+};
+
+namespace boost { namespace mpi {
+ template<> struct is_mpi_datatype<remote_key> : mpl::true_ { };
+} }
+BOOST_IS_BITWISE_SERIALIZABLE(remote_key)
+BOOST_CLASS_IMPLEMENTATION(remote_key,object_serializable)
+BOOST_CLASS_TRACKING(remote_key,track_never)
+
+namespace boost {
+
+template<>
+struct hash<remote_key>
+{
+ std::size_t operator()(const remote_key& key) const
+ {
+ std::size_t hash = hash_value(key.processor);
+ hash_combine(hash, key.local_key);
+ return hash;
+ }
+};
+}
+
+inline bool operator==(const remote_key& x, const remote_key& y)
+{ return x.processor == y.processor && x.local_key == y.local_key; }
+
+struct remote_key_to_global
+{
+ typedef readable_property_map_tag category;
+ typedef remote_key key_type;
+ typedef std::pair<int, std::size_t> value_type;
+ typedef value_type reference;
+};
+
+inline std::pair<int, std::size_t>
+get(remote_key_to_global, const remote_key& key)
+{
+ return std::make_pair(key.processor, key.local_key);
+}
+
+template<typename T>
+struct my_reduce : boost::parallel::basic_reduce<T> {
+ BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
+};
+
+void colored_test()
+{
+ mpi_process_group pg;
+ const int n = 500;
+
+ color_t my_start_color = process_id(pg) % 2 == 0? ::red : ::blue;
+ int next_processor = (process_id(pg) + 1) % num_processes(pg);
+ color_t next_start_color = next_processor % 2 == 0? ::red : ::blue;
+
+ // Initial color map: even-numbered processes are all red,
+ // odd-numbered processes are all blue.
+ std::vector<color_t> color_vec(n, my_start_color);
+
+ typedef iterator_property_map<std::vector<color_t>::iterator,
+ identity_property_map> LocalPropertyMap;
+ LocalPropertyMap local_colors(color_vec.begin(), identity_property_map());
+
+ synchronize(pg);
+
+ // Create the distributed property map
+ typedef boost::parallel::distributed_property_map<mpi_process_group,
+ remote_key_to_global,
+ LocalPropertyMap> ColorMap;
+ ColorMap colors(pg, remote_key_to_global(), local_colors);
+ colors.set_reduce(my_reduce<color_t>());
+
+ if (process_id(pg) == 0) std::cerr << "Checking local colors...";
+ // check local processor colors
+ for (int i = 0; i < n; ++i) {
+ remote_key k(process_id(pg), i);
+ BOOST_CHECK(get(colors, k) == my_start_color);
+ }
+
+ colors.set_consistency_model(boost::parallel::cm_bidirectional);
+ if (process_id(pg) == 0) std::cerr << "OK.\nChecking next processor's default colors...";
+ // check next processor's colors
+ for (int i = 0; i < n; ++i) {
+ remote_key k(next_processor, i);
+ BOOST_CHECK(get(colors, k) == color_t());
+ }
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing...";
+ synchronize(pg);
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nChecking next processor's colors...";
+ // check next processor's colors
+ for (int i = 0; i < n; ++i) {
+ remote_key k(next_processor, i);
+ BOOST_CHECK(get(colors, k) == next_start_color);
+ }
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing...";
+ synchronize(pg);
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nChanging next processor's colors...";
+ // change the next processor's colors
+ color_t next_finish_color = next_processor % 2 == 0? ::blue : ::red;
+ for (int i = 0; i < n; ++i) {
+ remote_key k(next_processor, i);
+ put(colors, k, next_finish_color);
+ }
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing...";
+ synchronize(pg);
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nChecking changed colors...";
+ // check our own colors
+ color_t my_finish_color = process_id(pg) % 2 == 0? ::blue : ::red;
+ for (int i = 0; i < n; ++i) {
+ remote_key k(process_id(pg), i);
+ BOOST_CHECK(get(colors, k) == my_finish_color);
+ }
+
+ // check our neighbor's colors
+ if (process_id(pg) == 0) std::cerr << "OK.\nChecking changed colors on neighbor...";
+ for (int i = 0; i < n; ++i) {
+ remote_key k(next_processor, i);
+ BOOST_CHECK(get(colors, k) == next_finish_color);
+ }
+
+ synchronize(pg);
+
+ if (process_id(pg) == 0) std::cerr << "OK.\n";
+}
+
+void bool_test()
+{
+ mpi_process_group pg;
+ const int n = 500;
+
+ bool my_start_value = process_id(pg) % 2;
+ int next_processor = (process_id(pg) + 1) % num_processes(pg);
+ bool next_start_value = ((process_id(pg) + 1) % num_processes(pg)) % 2;
+
+ // Initial color map: even-numbered processes are false,
+ // odd-numbered processes are true
+ std::vector<bool> bool_vec(n, my_start_value);
+
+ typedef iterator_property_map<std::vector<bool>::iterator,
+ identity_property_map> LocalPropertyMap;
+ LocalPropertyMap local_values(bool_vec.begin(), identity_property_map());
+
+ synchronize(pg);
+
+ // Create the distributed property map
+ typedef boost::parallel::distributed_property_map<mpi_process_group,
+ remote_key_to_global,
+ LocalPropertyMap> ValueMap;
+ ValueMap values(pg, remote_key_to_global(), local_values);
+ values.set_reduce(my_reduce<bool>());
+
+ if (process_id(pg) == 0) std::cerr << "Checking local values...";
+ // check local processor values
+ for (int i = 0; i < n; ++i) {
+ remote_key k(process_id(pg), i);
+ BOOST_CHECK(get(values, k) == my_start_value);
+ }
+
+ values.set_consistency_model(boost::parallel::cm_bidirectional);
+ if (process_id(pg) == 0) std::cerr << "OK.\nChecking next processor's default values...";
+ // check next processor's values
+ for (int i = 0; i < n; ++i) {
+ remote_key k(next_processor, i);
+ BOOST_CHECK(get(values, k) == false);
+ }
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing...";
+ synchronize(pg);
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nChecking next processor's values...";
+ // check next processor's values
+ for (int i = 0; i < n; ++i) {
+ remote_key k(next_processor, i);
+ BOOST_CHECK(get(values, k) == next_start_value);
+ }
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing...";
+ synchronize(pg);
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nChanging next processor's values...";
+ // change the next processor's values
+ bool next_finish_value = next_processor % 2 == 0;
+ for (int i = 0; i < n; ++i) {
+ remote_key k(next_processor, i);
+ put(values, k, next_finish_value);
+ }
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing...";
+ synchronize(pg);
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nChecking changed values...";
+ // check our own values
+ bool my_finish_value = process_id(pg) % 2 == 0;
+ for (int i = 0; i < n; ++i) {
+ remote_key k(process_id(pg), i);
+ BOOST_CHECK(get(values, k) == my_finish_value);
+ }
+
+ // check our neighbor's values
+ if (process_id(pg) == 0) std::cerr << "OK.\nChecking changed values on neighbor...";
+ for (int i = 0; i < n; ++i) {
+ remote_key k(next_processor, i);
+ BOOST_CHECK(get(values, k) == next_finish_value);
+ }
+
+ synchronize(pg);
+
+ if (process_id(pg) == 0) std::cerr << "OK.\n";
+}
+
+void string_test()
+{
+ mpi_process_group pg;
+ const int n = 500;
+
+ std::string my_start_string = lexical_cast<std::string>(process_id(pg));
+ int next_processor = (process_id(pg) + 1) % num_processes(pg);
+ std::string next_start_string = lexical_cast<std::string>(next_processor);
+
+ // Initial color map: even-numbered processes are false,
+ // odd-numbered processes are true
+ std::vector<std::string> string_vec(n, my_start_string);
+
+ typedef iterator_property_map<std::vector<std::string>::iterator,
+ identity_property_map> LocalPropertyMap;
+ LocalPropertyMap local_strings(string_vec.begin(), identity_property_map());
+
+ synchronize(pg);
+
+ // Create the distributed property map
+ typedef boost::parallel::distributed_property_map<mpi_process_group,
+ remote_key_to_global,
+ LocalPropertyMap> StringMap;
+ StringMap strings(pg, remote_key_to_global(), local_strings);
+ strings.set_reduce(my_reduce<std::string>());
+
+ if (process_id(pg) == 0) std::cerr << "Checking local strings...";
+ // check local processor strings
+ for (int i = 0; i < n; ++i) {
+ remote_key k(process_id(pg), i);
+ BOOST_CHECK(get(strings, k) == my_start_string);
+ }
+
+ strings.set_consistency_model(boost::parallel::cm_bidirectional);
+ if (process_id(pg) == 0) std::cerr << "OK.\nChecking next processor's default strings...";
+ // check next processor's strings
+ for (int i = 0; i < n; ++i) {
+ remote_key k(next_processor, i);
+ BOOST_CHECK(get(strings, k) == (num_processes(pg) == 1 ? my_start_string : std::string()));
+ }
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing...";
+ synchronize(pg);
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nChecking next processor's strings...";
+ // check next processor's strings
+ for (int i = 0; i < n; ++i) {
+ remote_key k(next_processor, i);
+ BOOST_CHECK(get(strings, k) == next_start_string);
+ }
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing...";
+ synchronize(pg);
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nChanging next processor's strings...";
+ // change the next processor's strings
+ std::string next_finish_string = next_start_string + next_start_string;
+ for (int i = 0; i < n; ++i) {
+ remote_key k(next_processor, i);
+ put(strings, k, next_finish_string);
+ }
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing...";
+ synchronize(pg);
+
+ if (process_id(pg) == 0) std::cerr << "OK.\nChecking changed strings...";
+ // check our own strings
+ std::string my_finish_string = my_start_string + my_start_string;
+ for (int i = 0; i < n; ++i) {
+ remote_key k(process_id(pg), i);
+ BOOST_CHECK(get(strings, k) == my_finish_string);
+ }
+
+ // check our neighbor's strings
+ if (process_id(pg) == 0) std::cerr << "OK.\nChecking changed strings on neighbor...";
+ for (int i = 0; i < n; ++i) {
+ remote_key k(next_processor, i);
+ BOOST_CHECK(get(strings, k) == next_finish_string);
+ }
+
+ synchronize(pg);
+
+ if (process_id(pg) == 0) std::cerr << "OK.\n";
+}
+
+int test_main(int argc, char** argv)
+{
+ boost::mpi::environment env(argc, argv);
+ colored_test();
+ bool_test();
+ string_test();
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_queue_test.cpp b/src/boost/libs/graph_parallel/test/distributed_queue_test.cpp
new file mode 100644
index 00000000..5a363038
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_queue_test.cpp
@@ -0,0 +1,116 @@
+// 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
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/serialization/vector.hpp>
+#include <boost/graph/distributed/queue.hpp>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/pending/queue.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <utility>
+#include <iostream>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using boost::graph::distributed::mpi_process_group;
+
+struct global_value
+{
+ global_value(int p = -1, std::size_t l = 0) : processor(p), value(l) {}
+
+ int processor;
+ std::size_t value;
+
+ template<typename Archiver>
+ void serialize(Archiver& ar, const unsigned int /*version*/)
+ {
+ ar & processor & value;
+ }
+};
+
+namespace boost { namespace mpi {
+ template<> struct is_mpi_datatype<global_value> : mpl::true_ { };
+} } // end namespace boost::mpi
+
+BOOST_IS_BITWISE_SERIALIZABLE(global_value)
+BOOST_CLASS_IMPLEMENTATION(global_value,object_serializable)
+BOOST_CLASS_TRACKING(global_value,track_never)
+
+inline bool operator==(const global_value& x, const global_value& y)
+{ return x.processor == y.processor && x.value == y.value; }
+
+struct global_value_owner_map
+{
+ typedef int value_type;
+ typedef value_type reference;
+ typedef global_value key_type;
+ typedef boost::readable_property_map_tag category;
+};
+
+int get(global_value_owner_map, global_value k)
+{
+ return k.processor;
+}
+
+void test_distributed_queue()
+{
+ mpi_process_group process_group;
+
+ typedef boost::queue<global_value> local_queue_type;
+
+ typedef boost::graph::distributed::distributed_queue<mpi_process_group,
+ global_value_owner_map,
+ local_queue_type> dist_queue_type;
+
+ dist_queue_type Q(process_group, global_value_owner_map());
+
+ mpi_process_group::process_id_type id = process_id(process_group),
+ n = num_processes(process_group);
+ global_value v(0, 0);
+
+ if (id == 0) {
+ std::cerr << "Should print level of each processor in a binary tree:\n";
+ }
+ synchronize(process_group);
+
+ if (id == n-1) Q.push(v);
+ while (!Q.empty()) {
+ v = Q.top(); Q.pop();
+
+ std::cerr << "#" << id << ": level = " << v.value << std::endl;
+
+ int level_begin = 1;
+ for (std::size_t i = 0; i < v.value; ++i) level_begin *= 2;
+ int level_end = level_begin * 2;
+ BOOST_CHECK(level_begin <= (id + 1));
+ BOOST_CHECK((id + 1) <= level_end);
+
+ ++v.value;
+ v.processor = v.processor * 2 + 1;
+ if (v.processor < n) Q.push(v);
+ ++v.processor;
+ if (v.processor < n) Q.push(v);
+ }
+}
+
+int test_main(int argc, char** argv)
+{
+ boost::mpi::environment env(argc, argv);
+ test_distributed_queue();
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_rmat_cc.cpp b/src/boost/libs/graph_parallel/test/distributed_rmat_cc.cpp
new file mode 100644
index 00000000..60638175
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_rmat_cc.cpp
@@ -0,0 +1,118 @@
+// 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: Brian Barrett
+// Nick Edmonds
+// Andrew Lumsdaine
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/property_map/parallel/distributed_property_map.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/distributed/concepts.hpp>
+#include <boost/graph/distributed/connected_components_parallel_search.hpp>
+#include <boost/graph/distributed/connected_components.hpp>
+#include <boost/graph/rmat_graph_generator.hpp>
+#include <boost/random/linear_congruential.hpp>
+#include <boost/graph/graphviz.hpp>
+#include <boost/property_map/vector_property_map.hpp>
+
+#include <iostream>
+#include <cstdlib>
+#include <iomanip>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+typedef double time_type;
+
+inline time_type get_time()
+{
+ return MPI_Wtime();
+}
+
+std::string print_time(time_type t)
+{
+ std::ostringstream out;
+ out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
+ return out.str();
+}
+
+void
+test_filtered_rmat_cc(int n, int m, double a, double b, double c, double d)
+{
+ mpi_process_group pg;
+ mpi_process_group::process_id_type id = process_id(pg);
+
+ if (id == 0) printf("INFO: Params: n=%d, m=%d, a=%f, b=%f, c=%f, d=%f.\n",
+ n, m, a, b, c, d);
+
+ parallel::variant_distribution<mpi_process_group> distrib
+ = parallel::block(pg, n);
+
+ typedef adjacency_list<vecS,
+ distributedS<mpi_process_group, vecS>,
+ undirectedS> Graph;
+
+ typedef keep_local_edges<parallel::variant_distribution<mpi_process_group>,
+ mpi_process_group::process_id_type>
+ EdgeFilter;
+
+ typedef unique_rmat_iterator<rand48, Graph, EdgeFilter>
+ RMATIter;
+
+ if (id == 0) printf("INFO: Generating graph.\n");
+
+ rand48 gen;
+ Graph g(RMATIter(gen, n, m, a, b, c, d, true, EdgeFilter(distrib, id)),
+ RMATIter(), n, pg, distrib);
+
+ synchronize(g);
+
+ if (id == 0) printf("INFO: Starting connected components.\n");
+
+ std::vector<int> local_components_vec(num_vertices(g));
+ typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> ComponentMap;
+ ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
+
+ time_type start = get_time();
+ int num_components = connected_components(g, component);
+ time_type end = get_time();
+
+ if (process_id(g.process_group()) == 0) {
+ std::cout << "INFO: Test Complete. components found = " << num_components
+ << ", time = " << print_time(end - start) << "s." << std::endl;
+ printf("RESULT: %d %d %d %f %f %f %f %f\n",
+ num_processes(pg), n, m, a, b, c, d, end - start);
+ }
+
+}
+
+int
+main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ if (argc < 7)
+ test_filtered_rmat_cc(40, 200, 0.58, 0.19, 0.19, 0.04);
+ else
+ test_filtered_rmat_cc(atoi(argv[1]), atoi(argv[2]),
+ atof(argv[3]), atof(argv[4]),
+ atof(argv[5]), atof(argv[6]));
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_rmat_cc_ps.cpp b/src/boost/libs/graph_parallel/test/distributed_rmat_cc_ps.cpp
new file mode 100644
index 00000000..020465c5
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_rmat_cc_ps.cpp
@@ -0,0 +1,117 @@
+// 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: Brian Barrett
+// Nick Edmonds
+// Andrew Lumsdaine
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/property_map/parallel/distributed_property_map.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/distributed/concepts.hpp>
+#include <boost/graph/distributed/connected_components_parallel_search.hpp>
+#include <boost/graph/distributed/connected_components.hpp>
+#include <boost/graph/rmat_graph_generator.hpp>
+#include <boost/random/linear_congruential.hpp>
+#include <boost/graph/graphviz.hpp>
+#include <boost/property_map/vector_property_map.hpp>
+
+#include <iostream>
+#include <cstdlib>
+#include <iomanip>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+typedef double time_type;
+
+inline time_type get_time()
+{
+ return MPI_Wtime();
+}
+
+std::string print_time(time_type t)
+{
+ std::ostringstream out;
+ out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
+ return out.str();
+}
+
+void
+test_filtered_rmat_cc(int n, int m, double a, double b, double c, double d)
+{
+ mpi_process_group pg;
+ std::size_t id = process_id(pg);
+
+ if (id == 0) printf("INFO: Params: n=%d, m=%d, a=%f, b=%f, c=%f, d=%f.\n",
+ n, m, a, b, c, d);
+
+ typedef parallel::variant_distribution<mpi_process_group> Distribution;
+ Distribution distrib = parallel::block(pg, n);
+
+ typedef adjacency_list<vecS,
+ distributedS<mpi_process_group, vecS>,
+ undirectedS> Graph;
+
+ typedef scalable_rmat_iterator<mpi_process_group, Distribution, rand48, Graph>
+ RMATIter;
+
+ if (id == 0) printf("INFO: Generating graph.\n");
+
+ rand48 gen;
+ time_type gen_start = get_time();
+ Graph g(RMATIter(pg, distrib, gen, n, m, a, b, c, d, true),
+ RMATIter(), n, pg, distrib);
+ time_type gen_end = get_time();
+ std::cout << "INFO: Graph Gen time: " << print_time(gen_end - gen_start) << std::endl;
+
+ synchronize(g);
+
+ if (id == 0) printf("INFO: Starting connected components.\n");
+
+ std::vector<int> local_components_vec(num_vertices(g));
+ typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> ComponentMap;
+ ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
+
+ time_type start = get_time();
+ int num_components = connected_components_ps(g, component);
+ time_type end = get_time();
+
+ if (process_id(g.process_group()) == 0) {
+ std::cout << "INFO: Test Complete. components found = " << num_components
+ << ", time = " << print_time(end - start) << "s." << std::endl;
+ printf("RESULT: %d %d %d %f %f %f %f %f\n",
+ num_processes(pg), n, m, a, b, c, d, end - start);
+ }
+
+}
+
+int
+main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ if (argc < 7)
+ test_filtered_rmat_cc(40, 200, 0.58, 0.19, 0.19, 0.04);
+ else
+ test_filtered_rmat_cc(atoi(argv[1]), atoi(argv[2]),
+ atof(argv[3]), atof(argv[4]),
+ atof(argv[5]), atof(argv[6]));
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_rmat_pagerank.cpp b/src/boost/libs/graph_parallel/test/distributed_rmat_pagerank.cpp
new file mode 100644
index 00000000..8700249e
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_rmat_pagerank.cpp
@@ -0,0 +1,113 @@
+// 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: Brian Barrett
+// Nick Edmonds
+// Andrew Lumsdaine
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
+#include <boost/property_map/parallel/distributed_property_map.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/distributed/concepts.hpp>
+#include <boost/graph/distributed/page_rank.hpp>
+#include <boost/graph/rmat_graph_generator.hpp>
+#include <boost/random/linear_congruential.hpp>
+#include <boost/graph/graphviz.hpp>
+#include <boost/property_map/vector_property_map.hpp>
+
+#include <iostream>
+#include <cstdlib>
+#include <iomanip>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+typedef double time_type;
+
+inline time_type get_time()
+{
+ return MPI_Wtime();
+}
+
+std::string print_time(time_type t)
+{
+ std::ostringstream out;
+ out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
+ return out.str();
+}
+
+void
+test_filtered_rmat_pagerank(int n, int m, double a, double b, double c, double d, int iters)
+{
+ mpi_process_group pg;
+ std::size_t id = process_id(pg);
+
+ if (id == 0) printf("INFO: Params: n=%d, m=%d, a=%f, b=%f, c=%f, d=%f, iters=%d.\n",
+ n, m, a, b, c, d, iters);
+
+ typedef parallel::variant_distribution<mpi_process_group> Distribution;
+ Distribution distrib = parallel::block(pg, n);
+
+ typedef adjacency_list<vecS,
+ distributedS<mpi_process_group, vecS>,
+ bidirectionalS> Graph;
+
+ typedef scalable_rmat_iterator<mpi_process_group, Distribution, rand48, Graph>
+ RMATIter;
+
+ if (id == 0) printf("INFO: Generating graph.\n");
+
+ rand48 gen;
+ Graph g(RMATIter(pg, distrib, gen, n, m, a, b, c, d, true),
+ RMATIter(), n, pg, distrib);
+
+ synchronize(g);
+
+ if (id == 0) printf("INFO: Starting PageRank.\n");
+
+ std::vector<double> ranks(num_vertices(g));
+
+ time_type start = get_time();
+ page_rank(g, make_iterator_property_map(ranks.begin(), get(boost::vertex_index, g)),
+ graph::n_iterations(iters), 0.85, n);
+ time_type end = get_time();
+
+ if (process_id(g.process_group()) == 0) {
+ std::cout << "INFO: Test Complete. time = " <<
+ print_time(end - start) << "s." << std::endl;
+ printf("RESULT: %d %d %d %f %f %f %f %f\n",
+ num_processes(pg), n, m, a, b, c, d, end - start);
+ }
+
+}
+
+int
+main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ if (argc < 8)
+ test_filtered_rmat_pagerank(40, 200, 0.58, 0.19, 0.19, 0.04, 10);
+ else
+ test_filtered_rmat_pagerank(atoi(argv[1]), atoi(argv[2]), atof(argv[3]),
+ atof(argv[4]), atof(argv[5]), atof(argv[6]),
+ atoi(argv[7]));
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_shortest_paths_test.cpp b/src/boost/libs/graph_parallel/test/distributed_shortest_paths_test.cpp
new file mode 100644
index 00000000..fce4c255
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_shortest_paths_test.cpp
@@ -0,0 +1,214 @@
+// Copyright (C) 2005, 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
+#define PBGL_ACCOUNTING
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/delta_stepping_shortest_paths.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/graph/parallel/distribution.hpp>
+#include <boost/graph/erdos_renyi_generator.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/graph/graphviz.hpp>
+#include <boost/random.hpp>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/iteration_macros.hpp>
+
+#include <iostream>
+#include <iomanip>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+/****************************************************************************
+ * Timing *
+ ****************************************************************************/
+typedef double time_type;
+
+inline time_type get_time()
+{
+ return MPI_Wtime();
+}
+
+std::string print_time(time_type t)
+{
+ std::ostringstream out;
+ out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
+ return out.str();
+}
+
+/****************************************************************************
+ * Edge weight generator iterator *
+ ****************************************************************************/
+template<typename F, typename RandomGenerator>
+class generator_iterator
+{
+public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef typename F::result_type value_type;
+ typedef const value_type& reference;
+ typedef const value_type* pointer;
+ typedef void difference_type;
+
+ explicit
+ generator_iterator(RandomGenerator& gen, const F& f = F())
+ : f(f), gen(&gen)
+ {
+ value = this->f(gen);
+ }
+
+ reference operator*() const { return value; }
+ pointer operator->() const { return &value; }
+
+ generator_iterator& operator++()
+ {
+ value = f(*gen);
+ return *this;
+ }
+
+ generator_iterator operator++(int)
+ {
+ generator_iterator temp(*this);
+ ++(*this);
+ return temp;
+ }
+
+ bool operator==(const generator_iterator& other) const
+ { return f == other.f; }
+
+ bool operator!=(const generator_iterator& other) const
+ { return !(*this == other); }
+
+private:
+ F f;
+ RandomGenerator* gen;
+ value_type value;
+};
+
+template<typename F, typename RandomGenerator>
+inline generator_iterator<F, RandomGenerator>
+make_generator_iterator( RandomGenerator& gen, const F& f)
+{ return generator_iterator<F, RandomGenerator>(gen, f); }
+
+/****************************************************************************
+ * Verification *
+ ****************************************************************************/
+template <typename Graph, typename DistanceMap, typename WeightMap>
+void
+verify_shortest_paths(const Graph& g, DistanceMap distance,
+ const WeightMap& weight) {
+
+ distance.set_max_ghost_cells(0);
+
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ BGL_FORALL_OUTEDGES_T(v, e, g, Graph) {
+ get(distance, target(e, g));
+ }
+ }
+
+ synchronize(process_group(g));
+
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ BGL_FORALL_OUTEDGES_T(v, e, g, Graph) {
+ assert(get(distance, target(e, g)) <=
+ get(distance, source(e, g)) + get(weight, e));
+ }
+ }
+}
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+typedef int weight_type;
+
+struct WeightedEdge {
+ WeightedEdge(weight_type weight = 0) : weight(weight) { }
+
+ weight_type weight;
+
+ template<typename Archiver>
+ void serialize(Archiver& ar, const unsigned int /*version*/)
+ {
+ ar & weight;
+ }
+};
+
+struct VertexProperties {
+ VertexProperties(int d = 0)
+ : distance(d) { }
+
+ int distance;
+
+ template<typename Archiver>
+ void serialize(Archiver& ar, const unsigned int /*version*/)
+ {
+ ar & distance;
+ }
+};
+
+void
+test_distributed_shortest_paths(int n, double p, int c, int seed)
+{
+ typedef adjacency_list<listS,
+ distributedS<mpi_process_group, vecS>,
+ undirectedS,
+ VertexProperties,
+ WeightedEdge> Graph;
+
+ typedef graph_traits<Graph>::vertices_size_type vertices_size_type;
+
+ // Build a random number generator
+ minstd_rand gen;
+ gen.seed(seed);
+
+ // Build a random graph
+ Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, p),
+ erdos_renyi_iterator<minstd_rand, Graph>(),
+ make_generator_iterator(gen, uniform_int<int>(0, c)),
+ n);
+
+ uniform_int<vertices_size_type> rand_vertex(0, n);
+
+ graph::distributed::delta_stepping_shortest_paths(g,
+ vertex(rand_vertex(gen), g),
+ dummy_property_map(),
+ get(&VertexProperties::distance, g),
+ get(&WeightedEdge::weight, g));
+
+ verify_shortest_paths(g,
+ get(&VertexProperties::distance, g),
+ get(&WeightedEdge::weight, g));
+}
+
+int test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ int n = 1000;
+ double p = 0.01;
+ int c = 100;
+ int seed = 1;
+
+ if (argc > 1) n = lexical_cast<int>(argv[1]);
+ if (argc > 2) p = lexical_cast<double>(argv[2]);
+ if (argc > 3) c = lexical_cast<int>(argv[3]);
+ if (argc > 4) seed = lexical_cast<int>(argv[4]);
+
+ test_distributed_shortest_paths(n, p, c, seed);
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_st_connected_test.cpp b/src/boost/libs/graph_parallel/test/distributed_st_connected_test.cpp
new file mode 100644
index 00000000..a65f404f
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_st_connected_test.cpp
@@ -0,0 +1,85 @@
+// 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: Nick Edmonds
+// Andrew Lumsdaine
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/graph/random.hpp>
+#include <boost/property_map/parallel/distributed_property_map.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/distributed/st_connected.hpp>
+#include <boost/graph/parallel/distribution.hpp>
+#include <boost/graph/small_world_generator.hpp>
+#include <iostream>
+#include <cstdlib>
+#include <iomanip>
+#include <boost/random.hpp>
+#include <boost/test/minimal.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+// Set up the vertex names
+enum vertex_id_t { u, v, w, x, y, z, N };
+char vertex_names[] = { 'u', 'v', 'w', 'x', 'y', 'z' };
+
+void
+test_distributed_st_connected() {
+
+ typedef adjacency_list<listS,
+ distributedS<mpi_process_group, vecS>,
+ undirectedS,
+ // Vertex properties
+ property<vertex_color_t, default_color_type> >
+ Graph;
+
+ // Specify the edges in the graph
+ {
+ typedef std::pair<int, int> E;
+ E edge_array[] = { E(u, u), E(u, v), E(u, w), E(v, w), E(x, y),
+ E(x, z), E(z, y), E(z, z) };
+ Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(E), N);
+
+ bool connected = st_connected(g, vertex(u, g), vertex(z, g),
+ get(vertex_color, g), get(vertex_owner, g));
+
+ assert(!connected);
+ }
+
+ {
+ typedef std::pair<int, int> E;
+ E edge_array[] = { E(u, v), E(u, w), E(u, x), E(x, v), E(y, x),
+ E(v, y), E(w, y), E(w, z), E(z, z) };
+ Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(E), N);
+
+ bool connected = st_connected(g, vertex(u, g), vertex(z, g),
+ get(vertex_color, g), get(vertex_owner, g));
+
+ assert(connected);
+ }
+
+
+}
+
+int test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+ test_distributed_st_connected();
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/distributed_strong_components_test.cpp b/src/boost/libs/graph_parallel/test/distributed_strong_components_test.cpp
new file mode 100644
index 00000000..cbbd41b5
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/distributed_strong_components_test.cpp
@@ -0,0 +1,175 @@
+// Copyright (C) 2004-2008 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: Nick Edmonds
+// Douglas Gregor
+// Andrew Lumsdaine
+
+// SCC won't work with CSR currently due to the way the reverse graph
+// is constructed in the SCC algorithm
+
+#include <boost/graph/use_mpi.hpp>
+
+// #define CSR
+
+#ifdef CSR
+# include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
+#else
+# include <boost/graph/distributed/adjacency_list.hpp>
+#endif
+
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/strong_components.hpp>
+#include <boost/graph/random.hpp>
+#include <boost/property_map/parallel/distributed_property_map.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/parallel/distribution.hpp>
+#include <boost/graph/erdos_renyi_generator.hpp>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/distributed/graphviz.hpp>
+#include <iostream>
+#include <cstdlib>
+#include <iomanip>
+#include <boost/random.hpp>
+#include <boost/test/minimal.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+typedef double time_type;
+
+inline time_type get_time()
+{
+ return MPI_Wtime();
+}
+
+std::string print_time(time_type t)
+{
+ std::ostringstream out;
+ out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
+ return out.str();
+}
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+void
+test_distributed_strong_components(int n, double _p, bool verify, bool emit_dot_file, int seed)
+{
+#ifdef CSR
+ typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
+ distributedS<mpi_process_group> > Graph;
+#else
+ typedef adjacency_list<listS,
+ distributedS<mpi_process_group, vecS>,
+ bidirectionalS > Graph;
+#endif
+
+ minstd_rand gen;
+
+ gen.seed(seed);
+
+ mpi_process_group pg;
+ parallel::variant_distribution<mpi_process_group> distrib
+ = parallel::block(pg, n);
+
+#ifdef CSR
+ Graph g(sorted_erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
+ sorted_erdos_renyi_iterator<minstd_rand, Graph>(),
+ n, pg, distrib);
+#else
+ Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
+ erdos_renyi_iterator<minstd_rand, Graph>(),
+ n, pg, distrib);
+#endif
+
+ synchronize(g);
+
+ std::vector<int> local_components_vec(num_vertices(g));
+ typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> ComponentMap;
+ ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
+
+ int num_components = 0;
+
+ time_type start = get_time();
+ num_components = strong_components(g, component);
+ time_type end = get_time();
+ if (process_id(g.process_group()) == 0)
+ std::cerr << "Erdos-Reyni graph:\n" << n << " Vertices " << _p << " Edge probability "
+ << num_processes(pg) << " Processors\n"
+ << "Strong Components time = " << print_time(end - start) << " seconds.\n"
+ << num_components << " components identified\n";
+
+
+ if ( verify )
+ {
+ if ( process_id(g.process_group()) == 0 )
+ {
+ for (int i = 0; i < n; ++i)
+ get(component, vertex(i, g));
+ synchronize(component);
+
+ // Check against the sequential version
+ typedef adjacency_list<listS, vecS, directedS> Graph2;
+
+ gen.seed(seed);
+
+ Graph2 g2(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
+ erdos_renyi_iterator<minstd_rand, Graph>(),
+ n);
+
+ std::vector<int> component2(n);
+ int seq_num_components = strong_components(g2, make_iterator_property_map(component2.begin(), get(vertex_index, g2)));
+
+ assert(num_components == seq_num_components);
+
+ // Make sure components and component2 match
+ std::map<int, int> c2c;
+ int i;
+ for ( i = 0; i < n; i++ )
+ if ( c2c.find( get(component, vertex(i, g)) ) == c2c.end() )
+ c2c[get(component, vertex(i, g))] = component2[i];
+ else
+ if ( c2c[get(component, vertex(i, g))] != component2[i] )
+ break;
+
+ if ( i < n )
+ std::cerr << "Unable to verify SCC result...\n";
+ else
+ std::cerr << "Passed verification... " << seq_num_components << " strong components\n";
+ }
+ else
+ {
+ synchronize(component);
+ }
+ if ( emit_dot_file )
+ write_graphviz("scc.dot", g, paint_by_number(component));
+ }
+}
+
+int test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ if (argc == 1)
+ test_distributed_strong_components(10000, 0.0005, true, false, 1);
+ else if ( argc < 5 )
+ std::cerr << "usage: test_distributed_strong_components <int num_vertices> <double p> <bool verify?> <bool emit_dotfile?> [seed]\n";
+ else
+ test_distributed_strong_components
+ (atoi(argv[1]), atof(argv[2]),
+ argv[3]==std::string("true"), argv[4]==std::string("true"),
+ argc == 5? 1 : atoi(argv[5]));
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/hohberg_biconnected_components_test.cpp b/src/boost/libs/graph_parallel/test/hohberg_biconnected_components_test.cpp
new file mode 100644
index 00000000..f0133300
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/hohberg_biconnected_components_test.cpp
@@ -0,0 +1,175 @@
+// Copyright (C) 2005-2008 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
+//
+// Test of Hohberg's distributed biconnected components algorithm.
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/hohberg_biconnected_components.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/test/minimal.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using boost::graph::distributed::mpi_process_group;
+
+using namespace boost;
+
+template<typename Graph>
+void check_components(const Graph& g, std::size_t num_comps)
+{
+ std::size_t not_mapped = (std::numeric_limits<std::size_t>::max)();
+ std::vector<std::size_t> color_to_name(num_comps, not_mapped);
+ BGL_FORALL_EDGES_T(e, g, Graph) {
+ BOOST_CHECK(get(edge_color, g, e) < num_comps);
+ if (color_to_name[get(edge_color, g, e)] == not_mapped)
+ color_to_name[get(edge_color, g, e)] = get(edge_name, g, e);
+ BOOST_CHECK(color_to_name[get(edge_color,g,e)] == get(edge_name,g,e));
+
+ if (color_to_name[get(edge_color,g,e)] != get(edge_name,g,e)) {
+ for (std::size_t i = 0; i < color_to_name.size(); ++i)
+ std::cerr << color_to_name[i] << ' ';
+
+ std::cerr << std::endl;
+
+ std::cerr << color_to_name[get(edge_color,g,e)] << " != "
+ << get(edge_name,g,e) << " on edge "
+ << local(source(e, g)) << " -> " << local(target(e, g))
+ << std::endl;
+ }
+ }
+}
+
+template<typename Graph>
+void
+test_small_hohberg_biconnected_components(Graph& g, int n, int comps_expected,
+ bool single_component = true)
+{
+ using boost::graph::distributed::hohberg_biconnected_components;
+
+ bool is_root = (process_id(process_group(g)) == 0);
+
+ if (single_component) {
+ for (int i = 0; i < n; ++i) {
+ if (is_root) std::cerr << "Testing with leader = " << i << std::endl;
+
+ // Scramble edge_color_map
+ BGL_FORALL_EDGES_T(e, g, Graph)
+ put(edge_color, g, e, 17);
+
+ typename graph_traits<Graph>::vertex_descriptor leader = vertex(i, g);
+ int num_comps =
+ hohberg_biconnected_components(g, get(edge_color, g), &leader,
+ &leader + 1);
+
+ BOOST_CHECK(num_comps == comps_expected);
+ check_components(g, num_comps);
+ }
+ }
+
+ if (is_root) std::cerr << "Testing simple interface." << std::endl;
+ synchronize(g);
+
+ // Scramble edge_color_map
+ int i = 0;
+ BGL_FORALL_EDGES_T(e, g, Graph) {
+ ++i;
+ put(edge_color, g, e, 17);
+ }
+ std::cerr << process_id(process_group(g)) << " has "
+ << i << " edges.\n";
+
+ int num_comps = hohberg_biconnected_components(g, get(edge_color, g));
+
+ BOOST_CHECK(num_comps == comps_expected);
+ check_components(g, num_comps);
+}
+
+int test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ typedef adjacency_list<listS,
+ distributedS<mpi_process_group, vecS>,
+ undirectedS,
+ // Vertex properties
+ no_property,
+ // Edge properties
+ property<edge_name_t, std::size_t,
+ property<edge_color_t, std::size_t> > > Graph;
+
+ typedef std::pair<int, int> E;
+
+ {
+ // Example 1: A single component with 2 bicomponents
+ E edges_init[] = { E(0, 1), E(0, 2), E(1, 3), E(2, 4), E(3, 4), E(4, 5),
+ E(4, 6), E(5, 6) };
+ const int m = sizeof(edges_init) / sizeof(E);
+ std::size_t expected_components[m] = { 0, 0, 0, 0, 0, 1, 1, 1 };
+ const int n = 7;
+ Graph g(&edges_init[0], &edges_init[0] + m, &expected_components[0], n);
+
+ int num_comps_expected =
+ *std::max_element(&expected_components[0], &expected_components[0] + m)
+ + 1;
+
+ test_small_hohberg_biconnected_components(g, n, num_comps_expected);
+ }
+
+ {
+ // Example 2: A single component with 4 bicomponents
+ E edges_init[] = { E(0, 1), E(1, 2), E(2, 0), E(2, 3), E(3, 4), E(4, 5),
+ E(5, 2), E(3, 6), E(6, 7), E(7, 8), E(8, 6) };
+ const int m = sizeof(edges_init) / sizeof(E);
+ std::size_t expected_components[m] = { 0, 0, 0, 1, 1, 1, 1, 2, 3, 3, 3 };
+ const int n = 9;
+ Graph g(&edges_init[0], &edges_init[0] + m, &expected_components[0], n);
+
+ int num_comps_expected =
+ *std::max_element(&expected_components[0], &expected_components[0] + m)
+ + 1;
+
+ test_small_hohberg_biconnected_components(g, n, num_comps_expected);
+ }
+
+ {
+ // Example 3: Two components, 6 bicomponents
+ // This is just the concatenation of the two previous graphs.
+ E edges_init[] = { /* Example 1 graph */
+ E(0, 1), E(0, 2), E(1, 3), E(2, 4), E(3, 4), E(4, 5),
+ E(4, 6), E(5, 6),
+ /* Example 2 graph */
+ E(7, 8), E(8, 9), E(9, 7), E(9, 10), E(10, 11),
+ E(11, 12), E(12, 9), E(10, 13), E(13, 14), E(14, 15),
+ E(15, 13) };
+ const int m = sizeof(edges_init) / sizeof(E);
+ std::size_t expected_components[m] =
+ { /* Example 1 */0, 0, 0, 0, 0, 1, 1, 1,
+ /* Example 2 */2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5 };
+ const int n = 16;
+ Graph g(&edges_init[0], &edges_init[0] + m, &expected_components[0], n);
+
+ int num_comps_expected =
+ *std::max_element(&expected_components[0], &expected_components[0] + m)
+ + 1;
+
+ test_small_hohberg_biconnected_components(g, n, num_comps_expected,
+ false);
+ }
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/mesh_generator_test.cpp b/src/boost/libs/graph_parallel/test/mesh_generator_test.cpp
new file mode 100644
index 00000000..160d1b50
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/mesh_generator_test.cpp
@@ -0,0 +1,133 @@
+// Copyright (C) 2004-2008 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
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/mesh_graph_generator.hpp>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/distributed/graphviz.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <string>
+#include <boost/test/minimal.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+/****************************************************************************
+ * Timing
+ ****************************************************************************/
+typedef double time_type;
+
+inline time_type get_time()
+{
+ return MPI_Wtime();
+}
+
+std::string print_time(time_type t)
+{
+ std::ostringstream out;
+ out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
+ return out.str();
+}
+
+/****************************************************************************
+ * Edge weight generator iterator *
+ ****************************************************************************/
+template<typename F>
+class generator_iterator
+{
+public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef typename F::result_type value_type;
+ typedef const value_type& reference;
+ typedef const value_type* pointer;
+ typedef void difference_type;
+
+ explicit generator_iterator(const F& f = F()) : f(f) { value = this->f(); }
+
+ reference operator*() const { return value; }
+ pointer operator->() const { return &value; }
+
+ generator_iterator& operator++()
+ {
+ value = f();
+ return *this;
+ }
+
+ generator_iterator operator++(int)
+ {
+ generator_iterator temp(*this);
+ ++(*this);
+ return temp;
+ }
+
+ bool operator==(const generator_iterator& other) const
+ { return f == other.f; }
+
+ bool operator!=(const generator_iterator& other) const
+ { return !(*this == other); }
+
+private:
+ F f;
+ value_type value;
+};
+
+template<typename F>
+inline generator_iterator<F> make_generator_iterator(const F& f)
+{ return generator_iterator<F>(f); }
+
+int test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ if (argc < 5) {
+ std::cerr << "Usage: mesh_generator_test <x> <y> <toroidal> <emit dot file>\n";
+ exit(-1);
+ }
+
+ int x(atoi(argv[1])), y(atoi(argv[2]));
+ bool toroidal(argv[3] == std::string("true"));
+ bool emit_dot_file(argv[4] == std::string("true"));
+
+ typedef adjacency_list<listS,
+ distributedS<mpi_process_group, vecS>,
+ undirectedS> Graph;
+
+ Graph g(mesh_iterator<Graph>(x, y, toroidal),
+ mesh_iterator<Graph>(),
+ x*y);
+
+ synchronize(g);
+
+ BGL_FORALL_VERTICES(v, g, Graph)
+ if (toroidal)
+ assert(out_degree(v, g) == 4);
+ else
+ assert(out_degree(v, g) >= 2 && out_degree(v, g) <= 4);
+
+ if ( emit_dot_file )
+ write_graphviz("mesh.dot", g);
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/named_vertices_hash_test.cpp b/src/boost/libs/graph_parallel/test/named_vertices_hash_test.cpp
new file mode 100644
index 00000000..c859a9a6
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/named_vertices_hash_test.cpp
@@ -0,0 +1,158 @@
+// Copyright (C) 2007-2008 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)
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/mpl/print.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/test/minimal.hpp>
+#include <string>
+#include <iostream>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+/// City structure to be attached to each vertex
+struct City {
+ City() {}
+
+ City(const std::string& name, int population = -1)
+ : name(name), population(population) { }
+
+ template<typename Archiver>
+ void serialize(Archiver& ar, const unsigned int /*version*/)
+ {
+ ar & name & population;
+ }
+
+ std::string name;
+ int population;
+};
+
+/// Our distribution function
+template<typename T>
+struct named_vertices_hashed_distribution
+{
+ template<typename ProcessGroup>
+ named_vertices_hashed_distribution(const ProcessGroup& pg,
+ std::size_t /*num_vertices*/ = 0)
+ : n(num_processes(pg)) { }
+
+ int operator()(const T& value) const
+ {
+ return hasher(value) % n;
+ }
+
+ std::size_t n;
+ boost::hash<T> hasher;
+};
+
+typedef named_vertices_hashed_distribution<std::string> hasher_type;
+
+namespace boost { namespace graph {
+
+/// Use the City name as a key for indexing cities in a graph
+template<>
+struct internal_vertex_name<City>
+{
+ typedef multi_index::member<City, std::string, &City::name> type;
+};
+
+/// Allow the graph to build cities given only their names (filling in
+/// the defaults for fields).
+template<>
+struct internal_vertex_constructor<City>
+{
+ typedef vertex_from_name<City> type;
+};
+
+// namespace distributed
+// {
+// /// Use the City name as the source for the distribution hasher
+// ///
+// /// This is currently needed in addition to the specification of this
+// /// hasher functor as the 3rd template parameter to the distributedS
+// /// template.
+// template<>
+// struct internal_vertex_name_distribution<City>
+// {
+// typedef named_vertices_hashed_distribution<std::string> type;
+// };
+// }
+
+} } // end namespace boost::graph
+
+/// Our road map, where each of the vertices are cities
+typedef boost::adjacency_list<vecS,
+ distributedS<mpi_process_group, vecS, hasher_type>,
+ bidirectionalS, City> RoadMap;
+typedef graph_traits<RoadMap>::vertex_descriptor Vertex;
+
+int test_main(int argc, char** argv)
+{
+ boost::mpi::environment env(argc, argv);
+
+ mpi_process_group pg;
+ RoadMap map; // (pg, hasher_type(pg));
+
+ int rank = process_id(pg);
+ bool i_am_root = rank == 0;
+
+ /// Create vertices for Bloomington, Indianapolis, Chicago. Everyone will
+ /// try to do this, but only one of each vertex will be added.
+ Vertex bloomington = add_vertex(City("Bloomington", 69291), map);
+ Vertex chicago = add_vertex(City("Chicago", 9500000), map);
+ Vertex indianapolis = add_vertex(City("Indianapolis", 791926), map);
+
+ BGL_FORALL_VERTICES(city, map, RoadMap)
+ std::cout << rank << ": " << map[city].name << ", population "
+ << map[city].population << std::endl;
+
+ BOOST_CHECK(*find_vertex("Bloomington", map) == bloomington);
+ BOOST_CHECK(*find_vertex("Indianapolis", map) == indianapolis);
+ BOOST_CHECK(*find_vertex("Chicago", map) == chicago);
+
+ if (i_am_root) {
+ add_edge(bloomington, "Indianapolis", map);
+ add_edge("Indianapolis", chicago, map);
+ add_edge("Indianapolis", "Cincinnati", map);
+ }
+
+ synchronize(map);
+
+ {
+ property_map<RoadMap, std::string City::*>::type
+ city_name = get(&City::name, map);
+
+ BGL_FORALL_EDGES(road, map, RoadMap)
+ std::cout << rank << ": " << get(city_name, source(road, map)) << " -> "
+ << get(city_name, target(road, map)) << std::endl;
+
+ synchronize(map);
+ }
+
+ // Make sure the vertex for "Cincinnati" was created implicitly
+ Vertex cincinnati = *find_vertex("Cincinnati", map);
+ if (get(get(vertex_owner, map), cincinnati)
+ == process_id(map.process_group()))
+ BOOST_CHECK(map[cincinnati].population == -1);
+
+ synchronize(map);
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/named_vertices_seq.cpp b/src/boost/libs/graph_parallel/test/named_vertices_seq.cpp
new file mode 100644
index 00000000..219214c0
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/named_vertices_seq.cpp
@@ -0,0 +1,91 @@
+// Copyright (C) 2007-2008 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)
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <string>
+#include <iostream>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+
+/// City structure to be attached to each vertex
+struct City {
+ City() {}
+
+ City(const std::string& name, int population = -1)
+ : name(name), population(population) { }
+
+ std::string name;
+ int population;
+};
+
+namespace boost { namespace graph {
+
+/// Use the City name as a key for indexing cities in a graph
+template<>
+struct internal_vertex_name<City>
+{
+ typedef multi_index::member<City, std::string, &City::name> type;
+};
+
+/// Allow the graph to build cities given only their names (filling in
+/// the defaults for fields).
+template<>
+struct internal_vertex_constructor<City>
+{
+ typedef vertex_from_name<City> type;
+};
+
+} } // end namespace boost::graph
+
+/// Our road map, where each of the vertices are cities
+typedef adjacency_list<vecS, vecS, directedS, City> RoadMap;
+typedef graph_traits<RoadMap>::vertex_descriptor Vertex;
+
+int test_main(int argc, char* argv[])
+{
+ RoadMap map;
+
+ /// Create vertices for Bloomington, Indianapolis, Chicago
+ Vertex bloomington = add_vertex(City("Bloomington", 69291), map);
+ Vertex indianapolis = add_vertex(City("Indianapolis", 791926), map);
+ Vertex chicago = add_vertex(City("Chicago", 9500000), map);
+
+ BOOST_CHECK(add_vertex(City("Bloomington", 69291), map) == bloomington);
+
+ BGL_FORALL_VERTICES(city, map, RoadMap)
+ std::cout << map[city].name << ", population " << map[city].population
+ << std::endl;
+
+ BOOST_CHECK(*find_vertex("Bloomington", map) == bloomington);
+ BOOST_CHECK(*find_vertex("Indianapolis", map) == indianapolis);
+ BOOST_CHECK(*find_vertex("Chicago", map) == chicago);
+
+ add_edge(bloomington, "Indianapolis", map);
+ add_edge("Indianapolis", chicago, map);
+ add_edge("Indianapolis", "Cincinnati", map);
+
+ BGL_FORALL_EDGES(road, map, RoadMap)
+ std::cout << map[source(road, map)].name << " -> "
+ << map[target(road, map)].name << std::endl;
+
+ BOOST_CHECK(map[*find_vertex("Cincinnati", map)].population == -1);
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/named_vertices_test.cpp b/src/boost/libs/graph_parallel/test/named_vertices_test.cpp
new file mode 100644
index 00000000..a5d7b273
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/named_vertices_test.cpp
@@ -0,0 +1,121 @@
+// Copyright (C) 2007 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)
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/graph/distributed/adjacency_list.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/test/minimal.hpp>
+#include <string>
+#include <iostream>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+using boost::graph::distributed::mpi_process_group;
+
+/// City structure to be attached to each vertex
+struct City {
+ City() {}
+
+ City(const std::string& name, int population = -1)
+ : name(name), population(population) { }
+
+ template<typename Archiver>
+ void serialize(Archiver& ar, const unsigned int /*version*/)
+ {
+ ar & name & population;
+ }
+
+ std::string name;
+ int population;
+};
+
+namespace boost { namespace graph {
+
+/// Use the City name as a key for indexing cities in a graph
+template<>
+struct internal_vertex_name<City>
+{
+ typedef multi_index::member<City, std::string, &City::name> type;
+};
+
+/// Allow the graph to build cities given only their names (filling in
+/// the defaults for fields).
+template<>
+struct internal_vertex_constructor<City>
+{
+ typedef vertex_from_name<City> type;
+};
+
+} } // end namespace boost::graph
+
+/// Our road map, where each of the vertices are cities
+typedef boost::adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
+ bidirectionalS, City> RoadMap;
+typedef graph_traits<RoadMap>::vertex_descriptor Vertex;
+
+int test_main(int argc, char** argv)
+{
+ boost::mpi::environment env(argc, argv);
+
+ RoadMap map;
+
+ int rank = process_id(mpi_process_group());
+ bool i_am_root = rank == 0;
+
+ /// Create vertices for Bloomington, Indianapolis, Chicago. Everyone will
+ /// try to do this, but only one of each vertex will be added.
+ Vertex bloomington = add_vertex(City("Bloomington", 69291), map);
+ Vertex chicago = add_vertex(City("Chicago", 9500000), map);
+ Vertex indianapolis = add_vertex(City("Indianapolis", 791926), map);
+
+ BGL_FORALL_VERTICES(city, map, RoadMap)
+ std::cout << rank << ": " << map[city].name << ", population "
+ << map[city].population << std::endl;
+
+ BOOST_CHECK(*find_vertex("Bloomington", map) == bloomington);
+ BOOST_CHECK(*find_vertex("Indianapolis", map) == indianapolis);
+ BOOST_CHECK(*find_vertex("Chicago", map) == chicago);
+
+ if (i_am_root) {
+ add_edge(bloomington, "Indianapolis", map);
+ add_edge("Indianapolis", chicago, map);
+ add_edge("Indianapolis", "Cincinnati", map);
+ }
+
+ synchronize(map);
+
+ {
+ property_map<RoadMap, std::string City::*>::type
+ city_name = get(&City::name, map);
+
+ BGL_FORALL_EDGES(road, map, RoadMap)
+ std::cout << rank << ": " << get(city_name, source(road, map)) << " -> "
+ << get(city_name, target(road, map)) << std::endl;
+
+ synchronize(map);
+ }
+
+ // Make sure the vertex for "Cincinnati" was created implicitly
+ Vertex cincinnati = *find_vertex("Cincinnati", map);
+ if (get(vertex_owner, map, cincinnati)
+ == process_id(map.process_group()))
+ BOOST_CHECK(map[cincinnati].population == -1);
+
+ synchronize(map);
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/process_group_serialization.cpp b/src/boost/libs/graph_parallel/test/process_group_serialization.cpp
new file mode 100644
index 00000000..80700751
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/process_group_serialization.cpp
@@ -0,0 +1,58 @@
+// 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
+// Andrew Lumsdaine
+
+// FIXME: Including because of a missing header in the serialization library.
+// Patch sent to list...
+#include <cassert>
+
+#include <boost/graph/use_mpi.hpp>
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/serialization/list.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/test/minimal.hpp>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using boost::graph::distributed::mpi_process_group;
+
+int test_main(int argc, char** argv)
+{
+ boost::mpi::environment env(argc, argv);
+
+ mpi_process_group pg;
+
+ int seventeen = 17;
+ std::list<int> seventeens(17, 17);
+
+ if (process_id(pg) == 0) {
+ send(pg, 1, 0, seventeen);
+ send(pg, 1, 1, seventeens);
+ }
+ synchronize(pg);
+
+ if (process_id(pg) == 1) {
+ int value;
+ receive(pg, 0, 0, value);
+ BOOST_CHECK(seventeen == value);
+
+ std::list<int> values;
+ receive(pg, 0, 1, values);
+ BOOST_CHECK(seventeens == values);
+ }
+
+ return 0;
+}
diff --git a/src/boost/libs/graph_parallel/test/ssca.cpp b/src/boost/libs/graph_parallel/test/ssca.cpp
new file mode 100644
index 00000000..0930e4d0
--- /dev/null
+++ b/src/boost/libs/graph_parallel/test/ssca.cpp
@@ -0,0 +1,1263 @@
+// Copyright 2004 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: Nick Edmonds
+// Andrew Lumsdaine
+
+#include <boost/graph/use_mpi.hpp>
+
+#define CSR
+
+#ifdef CSR
+# include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
+#else
+# include <boost/graph/distributed/adjacency_list.hpp>
+#endif
+
+#include <boost/test/minimal.hpp>
+#include <boost/graph/distributed/mpi_process_group.hpp>
+#include <boost/graph/distributed/queue.hpp>
+
+#include <boost/graph/parallel/distribution.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/bind.hpp>
+#include <sys/time.h>
+#include <time.h>
+
+#include <boost/random.hpp>
+#include <boost/property_map/parallel/distributed_property_map.hpp>
+
+#include <boost/random/linear_congruential.hpp>
+
+#include <boost/graph/distributed/graphviz.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/iteration_macros.hpp>
+
+#include <boost/graph/parallel/algorithm.hpp>
+#include <boost/graph/breadth_first_search.hpp>
+#include <boost/pending/queue.hpp>
+
+#include <boost/graph/rmat_graph_generator.hpp>
+#include <boost/graph/distributed/betweenness_centrality.hpp>
+#include <boost/graph/distributed/filtered_graph.hpp>
+#include <boost/graph/parallel/container_traits.hpp>
+
+#include <boost/graph/properties.hpp>
+
+#include <algorithm>
+#include <vector>
+#include <string>
+#include <iostream>
+#include <iomanip>
+#include <fstream>
+#include <string>
+#include <sstream>
+#include <stdint.h>
+
+using namespace boost;
+
+// #define DEBUG
+
+typedef rand48 RandomGenerator;
+
+/****************************************************************************
+ * Timing
+ ****************************************************************************/
+#ifndef PBGL_ACCOUNTING
+
+typedef double time_type;
+
+inline time_type get_time()
+{
+ timeval tp;
+ gettimeofday(&tp, 0);
+ return tp.tv_sec + tp.tv_usec / 1000000.0;
+}
+
+std::string print_time(time_type t)
+{
+ std::ostringstream out;
+ out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
+ return out.str();
+}
+
+#endif // PBGL_ACCOUNTING
+
+/****************************************************************************
+ * Edge weight generator iterator *
+ ****************************************************************************/
+template<typename F, typename RandomGenerator>
+class generator_iterator
+{
+public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef typename F::result_type value_type;
+ typedef const value_type& reference;
+ typedef const value_type* pointer;
+ typedef void difference_type;
+
+ explicit
+ generator_iterator(RandomGenerator& gen, const F& f = F())
+ : f(f), gen(&gen)
+ {
+ value = this->f(gen);
+ }
+
+ reference operator*() const { return value; }
+ pointer operator->() const { return &value; }
+
+ generator_iterator& operator++()
+ {
+ value = f(*gen);
+ return *this;
+ }
+
+ generator_iterator operator++(int)
+ {
+ generator_iterator temp(*this);
+ ++(*this);
+ return temp;
+ }
+
+ bool operator==(const generator_iterator& other) const
+ { return f == other.f; }
+
+ bool operator!=(const generator_iterator& other) const
+ { return !(*this == other); }
+
+private:
+ F f;
+ RandomGenerator* gen;
+ value_type value;
+};
+
+template<typename F, typename RandomGenerator>
+inline generator_iterator<F, RandomGenerator>
+make_generator_iterator( RandomGenerator& gen, const F& f)
+{ return generator_iterator<F, RandomGenerator>(gen, f); }
+
+template<typename Graph, typename DistanceMap, typename WeightMap, typename ColorMap>
+struct ssca_visitor : bfs_visitor<>
+{
+ typedef typename property_traits<WeightMap>::value_type Weight;
+ typedef typename property_traits<ColorMap>::value_type ColorValue;
+ typedef color_traits<ColorValue> Color;
+
+ ssca_visitor(DistanceMap& distance, const WeightMap& weight, ColorMap& color,
+ Weight max_)
+ : distance(distance), weight(weight), color(color), max_(max_) {}
+
+ template<typename Edge>
+ void tree_edge(Edge e, const Graph& g)
+ {
+ int new_distance = get(weight, e) == (std::numeric_limits<Weight>::max)() ?
+ (std::numeric_limits<Weight>::max)() : get(distance, source(e, g)) + get(weight, e);
+
+ put(distance, target(e, g), new_distance);
+ if (new_distance > max_)
+ put(color, target(e, g), Color::black());
+ }
+
+ private:
+ DistanceMap& distance;
+ const WeightMap& weight;
+ ColorMap& color;
+ Weight max_;
+};
+
+// Generate source vertices for approximate BC
+template <typename Graph, typename Buffer>
+void
+generate_sources(const Graph& g, Buffer sources,
+ typename graph_traits<Graph>::vertices_size_type num_sources)
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+ typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
+ typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
+
+ typedef typename boost::graph::parallel::process_group_type<Graph>::type
+ process_group_type;
+ process_group_type pg = g.process_group();
+
+ typename process_group_type::process_id_type id = process_id(pg);
+ typename process_group_type::process_size_type p = num_processes(pg);
+
+ // Don't feel like adding a special case for num_sources < p
+ assert(num_sources >= p);
+
+ minstd_rand gen;
+ uniform_int<vertices_size_type> rand_vertex(0, num_vertices(g) - 1);
+ std::vector<vertex_descriptor> all_sources, local_sources;
+ vertices_size_type local_vertices = vertices_size_type(floor((double)num_sources / p));
+ local_vertices += (id < (num_sources - (p * local_vertices)) ? 1 : 0);
+
+ while (local_vertices > 0) {
+ vertex_iterator iter = vertices(g).first;
+ std::advance(iter, rand_vertex(gen));
+
+ if (out_degree(*iter, g) != 0
+ && std::find(local_sources.begin(), local_sources.end(), *iter) == local_sources.end()) {
+ local_sources.push_back(*iter);
+ --local_vertices;
+ }
+ }
+ all_gather(pg, local_sources.begin(), local_sources.end(), all_sources);
+ std::sort(all_sources.begin(), all_sources.end());
+ for (typename std::vector<vertex_descriptor>::iterator iter = all_sources.begin();
+ iter != all_sources.end(); ++iter)
+ sources.push(*iter);
+}
+
+// Kernel 2 - Classify large sets
+template <typename Graph, typename WeightMap>
+void classify_sets(const Graph& g, const WeightMap& weight_map,
+ std::vector<std::pair<typename graph_traits<Graph>::vertex_descriptor,
+ typename graph_traits<Graph>::vertex_descriptor> > & global_S)
+{
+ typedef typename boost::graph::parallel::process_group_type<Graph>::type
+ process_group_type;
+ process_group_type pg = g.process_group();
+
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+ std::vector<std::pair<vertex_descriptor, vertex_descriptor> > S;
+
+ time_type start = get_time();
+
+#ifdef CSR
+ typedef typename property_map<Graph, vertex_owner_t>::const_type OwnerMap;
+ typedef typename property_map<Graph, vertex_local_t>::const_type LocalMap;
+ OwnerMap owner = get(vertex_owner, g);
+ LocalMap local = get(vertex_local, g);
+#endif
+
+ int max_ = 0;
+ BGL_FORALL_EDGES_T(e, g, Graph) {
+#ifdef CSR
+ if (get(owner, source(e, g)) == process_id(pg)) {
+#endif
+ int w = get(weight_map, e);
+ if (w > max_) {
+ max_ = w;
+ S.clear();
+ }
+
+ if (w >= max_)
+ S.push_back(std::make_pair(source(e, g), target(e, g)));
+#ifdef CSR
+ }
+#endif
+ }
+
+ int global_max = all_reduce(pg, max_, boost::parallel::maximum<int>());
+ if (max_ < global_max)
+ S.clear();
+
+ global_S.clear();
+
+ all_gather(pg, S.begin(), S.end(), global_S);
+
+ // This is probably unnecessary as long as the sets of edges owned by procs is disjoint
+ std::sort(global_S.begin(), global_S.end());
+ std::unique(global_S.begin(), global_S.end());
+
+ synchronize(pg);
+
+ time_type end = get_time();
+
+ if (process_id(pg) == 0) {
+ std::cerr << " Distributed Graph: " << print_time(end - start) << std::endl
+ << " Max int weight = " << global_max << std::endl;
+ }
+}
+
+template <typename ProcessGroup, typename Graph, typename WeightMap,
+ typename EdgeVector>
+void seq_classify_sets(const ProcessGroup& pg, const Graph& g,
+ const WeightMap& weight_map, EdgeVector& S)
+{
+ typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
+ typedef typename property_traits<WeightMap>::value_type edge_weight_type;
+
+ time_type start = get_time();
+
+ edge_weight_type max_ = 0;
+ BGL_FORALL_EDGES_T(e, g, Graph) {
+ edge_weight_type w = get(weight_map, e);
+ if (w > max_) {
+ max_ = w;
+ S.clear();
+ }
+
+ if (w >= max_)
+ S.push_back(e);
+ }
+
+ synchronize(pg);
+
+ time_type end = get_time();
+
+ if (process_id(pg) == 0)
+ std::cerr << " Non-Distributed Graph: " << print_time(end - start) << std::endl
+ << " Max int weight = " << max_ << std::endl;
+}
+
+// Kernel 3 - Graph Extraction
+template <typename Graph, typename OwnerMap, typename LocalMap,
+ typename WeightMap, typename DistanceMap, typename ColorMap,
+ typename EdgeVector>
+void subgraph_extraction(Graph& g, const OwnerMap& owner, const LocalMap& local,
+ const WeightMap& weight_map, DistanceMap distances,
+ ColorMap color_map, const EdgeVector& S,
+ int subGraphEdgeLength)
+{
+ // Nick: I think turning the vertex black when the maximum distance is
+ // exceeded will prevent BFS from exploring beyond the subgraph.
+ // Unfortunately we can't run subgraph extraction in parallel
+ // because the subgraphs may overlap
+
+ typedef typename property_traits<ColorMap>::value_type ColorValue;
+ typedef color_traits<ColorValue> Color;
+
+ typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+
+ typedef typename boost::graph::parallel::process_group_type<Graph>::type
+ process_group_type;
+
+ typedef boost::graph::distributed::distributed_queue<process_group_type,
+ OwnerMap, queue<vertex_descriptor> > queue_t;
+
+ process_group_type pg = g.process_group();
+ typename process_group_type::process_id_type id = process_id(pg);
+
+ queue_t Q(pg, owner);
+
+ EdgeVector sources(S.begin(), S.end());
+
+#ifdef DEBUG
+ std::vector<std::vector<vertex_descriptor> > subgraphs;
+#endif
+
+ synchronize(pg);
+
+ typedef typename std::vector<std::pair<vertex_descriptor, vertex_descriptor> >::iterator
+ source_iterator;
+
+ time_type start = get_time();
+ for (source_iterator iter = sources.begin(); iter != sources.end(); ++iter) {
+ // Reinitialize distance and color maps every BFS
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ if (get(owner, v) == id) {
+ local_put(color_map, v, Color::white());
+ local_put(distances, v, (std::numeric_limits<int>::max)());
+ }
+ }
+
+ vertex_descriptor u = iter->first, v = iter->second;
+
+ local_put(distances, u, 0);
+ local_put(distances, v, 0);
+
+ while (!Q.empty()) Q.pop();
+ if (get(owner, u) == id)
+ Q.push(u);
+
+ local_put(color_map, u, Color::gray());
+
+ breadth_first_search(g, v, Q,
+ ssca_visitor<Graph, DistanceMap, WeightMap, ColorMap>
+ (distances, weight_map, color_map, subGraphEdgeLength),
+ color_map);
+
+ // At this point all vertices with distance > 0 in addition to the
+ // starting vertices compose the subgraph.
+#ifdef DEBUG
+ subgraphs.push_back(std::vector<vertex_descriptor>());
+ std::vector<vertex_descriptor>& subgraph = subgraphs.back();
+
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ if (get(distances, v) < (std::numeric_limits<int>::max)())
+ subgraph.push_back(v);
+ }
+#endif
+ }
+
+ synchronize(pg);
+
+ time_type end = get_time();
+
+#ifdef DEBUG
+ for (unsigned int i = 0; i < subgraphs.size(); i++) {
+ all_gather(pg, subgraphs[i].begin(), subgraphs[i].end(), subgraphs[i]);
+ std::sort(subgraphs[i].begin(), subgraphs[i].end());
+ subgraphs[i].erase(std::unique(subgraphs[i].begin(), subgraphs[i].end()),
+ subgraphs[i].end());
+ }
+
+ if (process_id(pg) == 0)
+ for (int i = 0; abs(i) < subgraphs.size(); i++) {
+ std::cerr << "Subgraph " << i << " :\n";
+ for (int j = 0; abs(j) < subgraphs[i].size(); j++)
+ std::cerr << " " << get(local, subgraphs[i][j]) << "@"
+ << get(owner, subgraphs[i][j]) << std::endl;
+ }
+#endif
+
+ if (process_id(pg) == 0)
+ std::cerr << " Distributed Graph: " << print_time(end - start) << std::endl;
+}
+
+template <typename ProcessGroup, typename Graph, typename WeightMap,
+ typename DistanceMap, typename ColorMap, typename EdgeVector>
+void seq_subgraph_extraction(const ProcessGroup& pg, const Graph& g,
+ const WeightMap& weight_map, DistanceMap distances,
+ ColorMap color_map, const EdgeVector& S,
+ int subGraphEdgeLength)
+{
+ // Nick: I think turning the vertex black when the maximum distance is
+ // exceeded will prevent BFS from exploring beyond the subgraph.
+
+ using boost::graph::distributed::mpi_process_group;
+
+ typedef typename property_traits<ColorMap>::value_type ColorValue;
+ typedef color_traits<ColorValue> Color;
+
+ typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+
+ boost::queue<vertex_descriptor> Q;
+
+ std::vector<edge_descriptor> sources(S.begin(), S.end());
+
+#ifdef DEBUG
+ std::vector<std::vector<vertex_descriptor> > subgraphs;
+#endif
+
+ synchronize(pg);
+
+ typedef ProcessGroup process_group_type;
+
+ typename process_group_type::process_id_type id = process_id(pg);
+ typename process_group_type::process_size_type p = num_processes(pg);
+
+ time_type start = get_time();
+
+ for (int i = id; i < sources.size(); i += p) {
+
+ // Reinitialize distance and color maps every BFS
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ put(color_map, v, Color::white());
+ put(distances, v, (std::numeric_limits<int>::max)());
+ }
+
+ vertex_descriptor u = source(sources[i], g),
+ v = target(sources[i], g);
+
+ put(distances, u, 0);
+ put(distances, v, 0);
+
+ while (!Q.empty()) Q.pop();
+ Q.push(u);
+
+ put(color_map, u, Color::gray());
+
+ breadth_first_search(g, v, Q,
+ ssca_visitor<Graph, DistanceMap, WeightMap, ColorMap>
+ (distances, weight_map, color_map, subGraphEdgeLength),
+ color_map);
+
+#ifdef DEBUG
+ subgraphs.push_back(std::vector<vertex_descriptor>());
+ std::vector<vertex_descriptor>& subgraph = subgraphs.back();
+
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ if (get(distances, v) < (std::numeric_limits<int>::max)())
+ subgraph.push_back(v);
+ }
+#endif
+ }
+
+ synchronize(pg);
+
+ time_type end = get_time();
+
+#ifdef DEBUG
+ std::vector<vertex_descriptor> ser_subgraphs;
+
+ for (int i = 0; i < subgraphs.size(); ++i) {
+ for (int j = 0; j < subgraphs[i].size(); ++j)
+ ser_subgraphs.push_back(subgraphs[i][j]);
+ ser_subgraphs.push_back(graph_traits<Graph>::null_vertex());
+ }
+
+ all_gather(pg, ser_subgraphs.begin(), ser_subgraphs.end(), ser_subgraphs);
+
+ int i = 0;
+ typename std::vector<vertex_descriptor>::iterator iter(ser_subgraphs.begin());
+
+ while (iter != ser_subgraphs.end()) {
+ std::cerr << "Subgraph " << i << " :\n";
+ while (*iter != graph_traits<Graph>::null_vertex()) {
+ std::cerr << " " << *iter << std::endl;
+ ++iter;
+ }
+ ++i;
+ ++iter;
+ }
+#endif
+
+ if (process_id(pg) == 0)
+ std::cerr << " Non-Distributed Graph: " << print_time(end - start) << std::endl;
+}
+
+template <typename ProcessGroup, typename Graph, typename CentralityMap>
+void
+extract_max_bc_vertices(const ProcessGroup& pg, const Graph& g, const CentralityMap& centrality,
+ std::vector<typename graph_traits<Graph>::vertex_descriptor>& max_bc_vec)
+{
+ using boost::graph::parallel::process_group;
+ using boost::parallel::all_gather;
+ using boost::parallel::all_reduce;
+
+ // Find set of vertices with highest BC score
+ typedef typename property_traits<CentralityMap>::value_type centrality_type;
+ std::vector<centrality_type> max_bc_vertices;
+ centrality_type max_ = 0;
+
+ max_bc_vec.clear();
+
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ if (get(centrality, v) == max_)
+ max_bc_vec.push_back(v);
+ else if (get(centrality, v) > max_) {
+ max_ = get(centrality, v);
+ max_bc_vec.clear();
+ max_bc_vec.push_back(v);
+ }
+ }
+
+ centrality_type global_max = all_reduce(pg, max_, boost::parallel::minimum<int>());
+
+ if (global_max > max_)
+ max_bc_vec.clear();
+
+ all_gather(pg, max_bc_vec.begin(), max_bc_vec.end(), max_bc_vec);
+}
+
+
+// Function object to filter edges divisible by 8
+// EdgeWeightMap::value_type must be integral!
+template <typename EdgeWeightMap>
+struct edge_weight_not_divisible_by_eight {
+ typedef typename property_traits<EdgeWeightMap>::value_type weight_type;
+
+ edge_weight_not_divisible_by_eight() { }
+ edge_weight_not_divisible_by_eight(EdgeWeightMap weight) : m_weight(weight) { }
+ template <typename Edge>
+ bool operator()(const Edge& e) const {
+ return (get(m_weight, e) & ((std::numeric_limits<weight_type>::max)() - 7)) != get(m_weight, e);
+ }
+
+ EdgeWeightMap m_weight;
+};
+
+//
+// Vertex and Edge properties
+//
+#ifdef CSR
+typedef int weight_type;
+
+struct WeightedEdge {
+ WeightedEdge(weight_type weight = 0) : weight(weight) { }
+
+ weight_type weight;
+};
+
+struct VertexProperties {
+ VertexProperties(int distance = 0, default_color_type color = white_color)
+ : distance(distance), color(color) { }
+
+ int distance;
+ default_color_type color;
+};
+#endif
+
+template <typename RandomGenerator, typename ProcessGroup, typename vertices_size_type,
+ typename edges_size_type>
+void
+run_non_distributed_graph_tests(RandomGenerator& gen, const ProcessGroup& pg,
+ vertices_size_type n, edges_size_type m,
+ std::size_t maxEdgeWeight, uint64_t seed,
+ int K4Alpha, double a, double b, double c, double d,
+ int subGraphEdgeLength, bool show_degree_dist,
+ bool full_bc, bool verify)
+{
+#ifdef CSR
+ typedef compressed_sparse_row_graph<directedS, VertexProperties, WeightedEdge>
+ seqGraph;
+#else
+ typedef adjacency_list<vecS, vecS, directedS,
+ // Vertex properties
+ property<vertex_distance_t, int,
+ property<vertex_color_t, default_color_type> >,
+ // Edge properties
+ property<edge_weight_t, int> > seqGraph;
+#endif
+
+ // Generate sequential graph for non_distributed betweenness centrality
+ // Reseed the PRNG to get the same graph
+ gen.seed(seed);
+
+ synchronize(pg);
+
+ time_type start = get_time();
+
+#ifdef CSR
+ 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);
+#else
+ seqGraph sg(unique_rmat_iterator<RandomGenerator, seqGraph>(gen, n, m, a, b, c, d),
+ unique_rmat_iterator<RandomGenerator, seqGraph>(),
+ make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)),
+ n);
+#endif
+
+ // Not strictly necessary to synchronize here, but it make sure that the
+ // time we measure is the time needed for all copies of the graph to be
+ // constructed
+ synchronize(pg);
+
+ time_type end = get_time();
+
+ if (process_id(pg) == 0)
+ std::cerr<< "Kernel 1:\n"
+ << " Non-Distributed Graph: " << print_time(end - start) << std::endl;
+
+ std::map<int, int> degree_dist;
+ if ( show_degree_dist ) {
+ BGL_FORALL_VERTICES_T(v, sg, seqGraph) {
+ degree_dist[out_degree(v, sg)]++;
+ }
+
+ std::cerr << "Degree - Fraction of vertices of that degree\n";
+ for (std::map<int, int>::iterator iter = degree_dist.begin();
+ iter != degree_dist.end(); ++iter)
+ std::cerr << " " << iter->first << " - " << double(iter->second) / num_vertices(sg) << std::endl << std::endl;
+ }
+
+ //
+ // Kernel 2 - Classify large sets
+ //
+ std::vector<graph_traits<seqGraph>::edge_descriptor> seqS;
+
+ if (process_id(pg) == 0)
+ std::cerr << "Kernel 2:\n";
+
+ seq_classify_sets(pg, sg,
+#ifdef CSR
+ get(&WeightedEdge::weight, sg),
+#else
+ get(edge_weight, sg),
+#endif
+ seqS);
+
+ //
+ // Kernel 3 - Graph Extraction
+ //
+#ifdef CSR
+ typedef weight_type weight_t;
+ weight_t unit_weight(1);
+#else
+ int unit_weight(1);;
+#endif
+
+ if (process_id(pg) == 0)
+ std::cerr << "Kernel 3:\n";
+
+ seq_subgraph_extraction(pg, sg,
+#ifdef CSR
+// get(&WeightedEdge::weight, sg),
+ ref_property_map<graph_traits<seqGraph>::edge_descriptor, weight_t>(unit_weight),
+ get(&VertexProperties::distance, sg),
+ get(&VertexProperties::color, sg),
+#else
+// get(edge_weight, sg),
+ ref_property_map<graph_traits<seqGraph>::edge_descriptor, int>(unit_weight),
+ get(vertex_distance, sg),
+ get(vertex_color, sg),
+#endif
+ seqS, subGraphEdgeLength);
+
+#ifdef CSR
+ typedef property_map<seqGraph, weight_type WeightedEdge::*>::type seqEdgeWeightMap;
+ edge_weight_not_divisible_by_eight<seqEdgeWeightMap> sg_filter(get(&WeightedEdge::weight, sg));
+#else
+ typedef property_map<seqGraph, edge_weight_t>::type seqEdgeWeightMap;
+ edge_weight_not_divisible_by_eight<seqEdgeWeightMap> sg_filter(get(edge_weight, sg));
+#endif
+
+ typedef filtered_graph<const seqGraph, edge_weight_not_divisible_by_eight<seqEdgeWeightMap> >
+ filteredSeqGraph;
+
+ filteredSeqGraph fsg(sg, sg_filter);
+
+ std::vector<graph_traits<seqGraph>::vertex_descriptor> max_seq_bc_vec;
+
+ // Non-Distributed Centrality Map
+ typedef property_map<seqGraph, vertex_index_t>::const_type seqIndexMap;
+ typedef iterator_property_map<std::vector<int>::iterator, seqIndexMap> seqCentralityMap;
+
+ std::vector<int> non_distributed_centralityS(num_vertices(sg), 0);
+ seqCentralityMap non_distributed_centrality(non_distributed_centralityS.begin(),
+ get(vertex_index, sg));
+
+ vertices_size_type n0 = 0;
+ BGL_FORALL_VERTICES_T(v, fsg, filteredSeqGraph) {
+ if (out_degree(v, fsg) == 0) ++n0;
+ }
+
+ if (process_id(pg) == 0)
+ std::cerr << "Kernel 4:\n";
+
+ // Run Betweenness Centrality
+ if (full_bc) {
+
+ // Non-Distributed Graph BC
+ start = get_time();
+ non_distributed_brandes_betweenness_centrality(pg, fsg, non_distributed_centrality);
+ extract_max_bc_vertices(pg, fsg, non_distributed_centrality, max_seq_bc_vec);
+ end = get_time();
+
+ edges_size_type nonDistributedExactTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start)));
+
+ if (process_id(pg) == 0)
+ std::cerr << " non-Distributed Graph Exact = " << print_time(end - start) << " ("
+ << nonDistributedExactTEPs << " TEPs)\n";
+ }
+
+ // Non-Distributed Graph Approximate BC
+ std::vector<int> nonDistributedApproxCentralityS(num_vertices(sg), 0);
+ seqCentralityMap nonDistributedApproxCentrality(nonDistributedApproxCentralityS.begin(),
+ get(vertex_index, sg));
+
+ queue<typename graph_traits<filteredSeqGraph>::vertex_descriptor> sources;
+ {
+ minstd_rand gen;
+ uniform_int<vertices_size_type> rand_vertex(0, num_vertices(fsg) - 1);
+ int remaining_sources = floor(pow(2, K4Alpha));
+ std::vector<typename graph_traits<filteredSeqGraph>::vertex_descriptor> temp_sources;
+
+ while (remaining_sources > 0) {
+ typename graph_traits<filteredSeqGraph>::vertex_descriptor v =
+ vertex(rand_vertex(gen), fsg);
+
+ if (out_degree(v, fsg) != 0
+ && std::find(temp_sources.begin(), temp_sources.end(), v) == temp_sources.end()) {
+ temp_sources.push_back(v);
+ --remaining_sources;
+ }
+ }
+
+ for (int i = 0; i < temp_sources.size(); ++i)
+ sources.push(temp_sources[i]);
+ }
+
+ start = get_time();
+ non_distributed_brandes_betweenness_centrality(pg, fsg, buffer(sources).
+ centrality_map(nonDistributedApproxCentrality));
+ extract_max_bc_vertices(pg, fsg, nonDistributedApproxCentrality, max_seq_bc_vec);
+ end = get_time();
+
+ edges_size_type nonDistributedApproxTEPs = edges_size_type(floor(7 * n * pow(2, K4Alpha) / (end - start)));
+
+ if (process_id(pg) == 0)
+ std::cerr << " Non-Distributed Graph Approximate (" << floor(pow(2, K4Alpha)) << " sources) = "
+ << print_time(end - start) << " (" << nonDistributedApproxTEPs << " TEPs)\n";
+
+ // Verify Correctness of Kernel 4
+ if (full_bc && verify && process_id(pg) == 0) {
+
+ std::vector<int> seq_centralityS(num_vertices(fsg), 0);
+ seqCentralityMap seq_centrality(seq_centralityS.begin(), get(vertex_index, fsg));
+
+ max_seq_bc_vec.clear();
+ property_traits<seqCentralityMap>::value_type max_ = 0;
+
+ start = get_time();
+ brandes_betweenness_centrality(fsg, seq_centrality);
+
+ typedef filtered_graph<const seqGraph, edge_weight_not_divisible_by_eight<seqEdgeWeightMap> >
+ filteredSeqGraph;
+
+ BGL_FORALL_VERTICES_T(v, fsg, filteredSeqGraph ) {
+ if (get(seq_centrality, v) == max_)
+ max_seq_bc_vec.push_back(v);
+ else if (get(seq_centrality, v) > max_) {
+ max_ = get(seq_centrality, v);
+ max_seq_bc_vec.clear();
+ max_seq_bc_vec.push_back(v);
+ }
+ }
+
+ end = get_time();
+
+ edges_size_type sequentialTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start)));
+
+ std::cerr << " Sequential = " << print_time(end - start) << " (" << sequentialTEPs << " TEPs)\n";
+
+ typename ProcessGroup::process_id_type id = process_id(pg);
+ typename ProcessGroup::process_size_type p = num_processes(pg);
+
+ assert((double)n/p == floor((double)n/p));
+
+ std::cerr << "\nVerifying non-scalable betweenness centrality...\n";
+
+ {
+ bool passed = true;
+
+ // Verify non-scalable betweenness centrality
+ BGL_FORALL_VERTICES_T(v, sg, seqGraph) {
+ if (get(non_distributed_centrality, v) != get(seq_centrality, v)) {
+ std::cerr << " " << id << ": Error - centrality of " << v
+ << " does not match the sequential result ("
+ << get(non_distributed_centrality, v) << " vs. "
+ << get(seq_centrality, v) << ")\n";
+ passed = false;
+ }
+ }
+
+ if (passed)
+ std::cerr << " PASSED\n";
+ }
+
+ }
+
+}
+
+template <typename RandomGenerator, typename ProcessGroup, typename vertices_size_type,
+ typename edges_size_type>
+void
+run_distributed_graph_tests(RandomGenerator& gen, const ProcessGroup& pg,
+ vertices_size_type n, edges_size_type m,
+ std::size_t maxEdgeWeight, uint64_t seed,
+ int K4Alpha, double a, double b, double c, double d,
+ int subGraphEdgeLength, bool show_degree_dist,
+ bool emit_dot_file, bool full_bc, bool verify)
+{
+#ifdef CSR
+ typedef compressed_sparse_row_graph<directedS, VertexProperties, WeightedEdge, no_property,
+ distributedS<ProcessGroup> > Graph;
+#else
+ typedef adjacency_list<vecS,
+ distributedS<ProcessGroup, vecS>,
+ directedS,
+ // Vertex properties
+ property<vertex_distance_t, int,
+ property<vertex_color_t, default_color_type> >,
+ // Edge properties
+ property<edge_weight_t, int> > Graph;
+#endif
+
+ gen.seed(seed);
+
+ parallel::variant_distribution<ProcessGroup> distrib
+ = parallel::block(pg, n);
+
+ typedef typename ProcessGroup::process_id_type process_id_type;
+ process_id_type id = process_id(pg);
+
+ typedef typename property_map<Graph, vertex_owner_t>::const_type OwnerMap;
+ typedef typename property_map<Graph, vertex_local_t>::const_type LocalMap;
+
+ typedef keep_local_edges<parallel::variant_distribution<ProcessGroup>,
+ process_id_type>
+ EdgeFilter;
+
+ //
+ // Kernel 1 - Graph construction
+ // Nick: The benchmark specifies that we only have to time graph generation from
+ // edge tuples, the generator generates the edge tuples at graph construction
+ // time so we're timing some overhead in the random number generator, etc.
+ synchronize(pg);
+
+ time_type start = get_time();
+
+#ifdef CSR
+// typedef sorted_unique_rmat_iterator<RandomGenerator, Graph, EdgeFilter> RMATIter;
+ typedef sorted_rmat_iterator<RandomGenerator, Graph, keep_all_edges> RMATIter;
+
+ Graph g(//RMATIter(gen, n, m, a, b, c, d, false, true, EdgeFilter(distrib, id)),
+ RMATIter(gen, n, m, a, b, c, d, true, keep_all_edges()),
+ RMATIter(),
+ make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)),
+ n, pg, distrib);
+#else
+ typedef unique_rmat_iterator<RandomGenerator, Graph, EdgeFilter> RMATIter;
+ Graph g(RMATIter(gen, n, m, a, b, c, d, true EdgeFilter(distrib, id)),
+ RMATIter(),
+ make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)),
+ n, pg, distrib);
+#endif
+
+ synchronize(pg);
+
+ time_type end = get_time();
+
+ if (id == 0)
+ std::cerr<< "Kernel 1:\n"
+ << " Distributed Graph: " << print_time(end - start) << std::endl;
+
+ if ( emit_dot_file )
+ write_graphviz("ssca.dot", g);
+
+ //
+ // Kernel 2 - Classify large sets
+ //
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+ std::vector<std::pair<vertex_descriptor, vertex_descriptor> > S;
+
+ if (id == 0)
+ std::cerr << "Kernel 2:\n";
+
+ classify_sets(g,
+#ifdef CSR
+ get(&WeightedEdge::weight, g),
+#else
+ get(edge_weight, g),
+#endif
+ S);
+
+ //
+ // Kernel 3 - Graph Extraction
+ //
+ OwnerMap owner = get(vertex_owner, g);
+ LocalMap local = get(vertex_local, g);
+
+ if (id == 0)
+ std::cerr << "Kernel 3:\n";
+
+#ifdef CSR
+ typedef weight_type weight_t;
+ weight_t unit_weight(1);
+#else
+ int unit_weight(1);;
+#endif
+
+ subgraph_extraction(g, owner, local,
+#ifdef CSR
+// get(&WeightedEdge::weight, g),
+ ref_property_map<typename graph_traits<Graph>::edge_descriptor, weight_t>(unit_weight),
+ get(&VertexProperties::distance, g),
+ get(&VertexProperties::color, g),
+#else
+// get(edge_weight, g),
+ ref_property_map<graph_traits<Graph>::edge_descriptor, int>(unit_weight),
+ get(vertex_distance, g),
+ get(vertex_color, g),
+#endif
+ S, subGraphEdgeLength);
+
+ //
+ // Kernel 4 - Betweenness Centrality
+ //
+
+ // Filter edges with weights divisible by 8
+#ifdef CSR
+ typedef typename property_map<Graph, weight_type WeightedEdge::*>::type EdgeWeightMap;
+ edge_weight_not_divisible_by_eight<EdgeWeightMap> filter(get(&WeightedEdge::weight, g));
+#else
+ typedef typename property_map<Graph, edge_weight_t>::type EdgeWeightMap;
+ edge_weight_not_divisible_by_eight<EdgeWeightMap> filter(get(edge_weight, g));
+#endif
+
+ typedef filtered_graph<const Graph, edge_weight_not_divisible_by_eight<EdgeWeightMap> >
+ filteredGraph;
+ filteredGraph fg(g, filter);
+
+ // Vectors of max BC scores for all tests
+ std::vector<typename graph_traits<Graph>::vertex_descriptor> max_bc_vec;
+
+ // Distributed Centrality Map
+ typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
+ typedef iterator_property_map<std::vector<int>::iterator, IndexMap> CentralityMap;
+
+ std::vector<int> centralityS(num_vertices(g), 0);
+ CentralityMap centrality(centralityS.begin(), get(vertex_index, g));
+
+ // Calculate number of vertices of degree 0
+ vertices_size_type local_n0 = 0, n0;
+ BGL_FORALL_VERTICES_T(v, fg, filteredGraph) {
+ if (out_degree(v, g) == 0) local_n0++;
+ }
+ n0 = boost::parallel::all_reduce(pg, local_n0, std::plus<vertices_size_type>());
+
+ if (id == 0)
+ std::cerr << "Kernel 4:\n";
+
+ // Run Betweenness Centrality
+ if (full_bc) {
+
+ // Distributed Graph Full BC
+ start = get_time();
+ brandes_betweenness_centrality(fg, centrality);
+ extract_max_bc_vertices(pg, g, centrality, max_bc_vec);
+ end = get_time();
+
+ edges_size_type exactTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start)));
+
+ if (id == 0)
+ std::cerr << " Exact = " << print_time(end - start) << " ("
+ << exactTEPs << " TEPs)\n";
+ }
+
+ // Distributed Graph Approximate BC
+ std::vector<int> approxCentralityS(num_vertices(g), 0);
+ CentralityMap approxCentrality(approxCentralityS.begin(), get(vertex_index, g));
+
+ queue<vertex_descriptor> sources;
+ generate_sources(g, sources, vertices_size_type(floor(pow(2, K4Alpha))));
+
+ start = get_time();
+ brandes_betweenness_centrality(fg, buffer(sources).centrality_map(approxCentrality));
+ extract_max_bc_vertices(pg, fg, approxCentrality, max_bc_vec);
+ end = get_time();
+
+ edges_size_type approxTEPs = edges_size_type(floor(7 * n * pow(2, K4Alpha) / (end - start)));
+
+ if (id == 0)
+ std::cerr << " Approximate (" << floor(pow(2, K4Alpha)) << " sources) = "
+ << print_time(end - start) << " (" << approxTEPs << " TEPs)\n";
+
+
+ // Verify Correctness of Kernel 4
+ if (full_bc && verify && id == 0) {
+
+ // Build non-distributed graph to verify against
+ typedef adjacency_list<vecS, vecS, directedS,
+ // Vertex properties
+ property<vertex_distance_t, int,
+ property<vertex_color_t, default_color_type> >,
+ // Edge properties
+ property<edge_weight_t, int> > seqGraph;
+
+ gen.seed(seed);
+
+#ifdef CSR
+ seqGraph sg(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);
+#else
+ seqGraph sg(unique_rmat_iterator<RandomGenerator, seqGraph>(gen, n, m, a, b, c, d),
+ unique_rmat_iterator<RandomGenerator, seqGraph>(),
+ make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)),
+ n);
+#endif
+
+ typedef property_map<seqGraph, edge_weight_t>::type seqEdgeWeightMap;
+ edge_weight_not_divisible_by_eight<seqEdgeWeightMap> sg_filter(get(edge_weight, sg));
+
+ filtered_graph<const seqGraph, edge_weight_not_divisible_by_eight<seqEdgeWeightMap> >
+ fsg(sg, sg_filter);
+
+ // Build sequential centrality map
+ typedef property_map<seqGraph, vertex_index_t>::const_type seqIndexMap;
+ typedef iterator_property_map<std::vector<int>::iterator, seqIndexMap> seqCentralityMap;
+
+ std::vector<int> seq_centralityS(num_vertices(sg), 0);
+ seqCentralityMap seq_centrality(seq_centralityS.begin(), get(vertex_index, sg));
+
+ std::vector<graph_traits<seqGraph>::vertex_descriptor> max_seq_bc_vec;
+
+ max_seq_bc_vec.clear();
+ property_traits<seqCentralityMap>::value_type max_ = 0;
+
+ start = get_time();
+ brandes_betweenness_centrality(fsg, seq_centrality);
+
+ typedef filtered_graph<const seqGraph, edge_weight_not_divisible_by_eight<seqEdgeWeightMap> >
+ filteredSeqGraph;
+
+ BGL_FORALL_VERTICES_T(v, fsg, filteredSeqGraph ) {
+ if (get(seq_centrality, v) == max_)
+ max_seq_bc_vec.push_back(v);
+ else if (get(seq_centrality, v) > max_) {
+ max_ = get(seq_centrality, v);
+ max_seq_bc_vec.clear();
+ max_seq_bc_vec.push_back(v);
+ }
+ }
+
+ end = get_time();
+
+ edges_size_type sequentialTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start)));
+
+ std::cerr << " Sequential = " << print_time(end - start) << " (" << sequentialTEPs << " TEPs)\n";
+
+ typename ProcessGroup::process_size_type p = num_processes(pg);
+
+ assert((double)n/p == floor((double)n/p));
+
+ std::cerr << "\nVerifying betweenness centrality...\n";
+
+ {
+ bool passed = true;
+
+ // Verify exact betweenness centrality
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ if (get(centrality, v) != seq_centralityS[(n/p) * get(owner, v) + get(local, v)]) {
+ std::cerr << " " << id << ": Error - centrality of " << get(local, v) << "@" << get(owner, v)
+ << " does not match the sequential result (" << get(centrality, v) << " vs. "
+ << seq_centralityS[(n/p) * get(owner, v) + get(local, v)] << ")\n";
+ passed = false;
+ }
+ }
+
+ if (passed)
+ std::cerr << " PASSED\n";
+ }
+ }
+}
+
+void usage()
+{
+ std::cerr << "SSCA benchmark.\n\n"
+ << "Usage : ssca [options]\n\n"
+ << "Options are:\n"
+ << "\t--vertices v\t\t\tNumber of vertices in the graph\n"
+ << "\t--edges v\t\t\tNumber of edges in the graph\n"
+ << "\t--seed s\t\t\tSeed for synchronized random number generator\n"
+ << "\t--full-bc\t\t\tRun full (exact) Betweenness Centrality\n"
+ << "\t--max-weight miw\t\tMaximum integer edge weight\n"
+ << "\t--subgraph-edge-length sel\tEdge length of subgraphs to extract in Kernel 3\n"
+ << "\t--k4alpha k\t\t\tValue of K4Alpha in Kernel 4\n"
+ << "\t--scale s\t\t\tSCALE parameter for the SSCA benchmark (sets n, m, and C)\n"
+ << "\t--dot\t\t\t\tEmit a dot file containing the graph\n"
+ << "\t--verify\t\t\tVerify result\n"
+ << "\t--degree-dist\t\t\t Output degree distribution of graph\n"
+ << "\t--no-distributed-graph\t\tOmit distributed graph tests\n";
+}
+
+int test_main(int argc, char* argv[])
+{
+ mpi::environment env(argc, argv);
+
+ using boost::graph::distributed::mpi_process_group;
+
+#ifdef CSR
+ typedef compressed_sparse_row_graph<directedS, VertexProperties, WeightedEdge, no_property,
+ distributedS<mpi_process_group> > Graph;
+#else
+ typedef adjacency_list<vecS,
+ distributedS<mpi_process_group, vecS>,
+ directedS,
+ // Vertex properties
+ property<vertex_distance_t, int,
+ property<vertex_color_t, default_color_type> >,
+ // Edge properties
+ property<edge_weight_t, int> > Graph;
+#endif
+
+ typedef graph_traits<Graph>::vertices_size_type vertices_size_type;
+ typedef graph_traits<Graph>::edges_size_type edges_size_type;
+
+ RandomGenerator gen;
+
+ // Default args
+ vertices_size_type n = 100;
+ edges_size_type m = 8*n;
+ uint64_t seed = 1;
+ int maxEdgeWeight = 100,
+ subGraphEdgeLength = 8,
+ K4Alpha = 0.5;
+ double a = 0.57, b = 0.19, c = 0.19, d = 0.05;
+ bool emit_dot_file = false, verify = false, full_bc = true,
+ distributed_graph = true, show_degree_dist = false,
+ non_distributed_graph = true;
+
+ mpi_process_group pg;
+
+ if (argc == 1) {
+ if (process_id(pg) == 0)
+ usage();
+ exit(-1);
+ }
+
+ // Parse args
+ for (int i = 1; i < argc; ++i) {
+ std::string arg = argv[i];
+
+ if (arg == "--vertices")
+ n = boost::lexical_cast<vertices_size_type>( argv[i+1] );
+
+ if (arg == "--seed")
+ seed = boost::lexical_cast<uint64_t>( argv[i+1] );
+
+ if (arg == "--full-bc")
+ full_bc = (argv[i+1]== "true");
+
+ if (arg == "--max-weight")
+ maxEdgeWeight = boost::lexical_cast<int>( argv[i+1] );
+
+ if (arg == "--subgraph-edge-length")
+ subGraphEdgeLength = boost::lexical_cast<int>( argv[i+1] );
+
+ if (arg == "--edges")
+ m = boost::lexical_cast<edges_size_type>( argv[i+1] );
+
+ if (arg == "--k4alpha")
+ K4Alpha = boost::lexical_cast<int>( argv[i+1] );
+
+ if (arg == "--dot")
+ emit_dot_file = true;
+
+ if (arg == "--verify")
+ verify = true;
+
+ if (arg == "--degree-dist")
+ show_degree_dist = true;
+
+ if (arg == "--no-distributed-graph")
+ distributed_graph = false;
+
+ if (arg == "--no-non-distributed-graph")
+ non_distributed_graph = false;
+
+ if (arg == "--scale") {
+ vertices_size_type scale = boost::lexical_cast<vertices_size_type>( argv[i+1] );
+ maxEdgeWeight = n = vertices_size_type(floor(pow(2, scale)));
+ m = 8 * n;
+ }
+
+ if (arg == "--help") {
+ if (process_id(pg) == 0)
+ usage();
+ exit(-1);
+ }
+ }
+
+ if (non_distributed_graph) {
+ if (process_id(pg) == 0)
+ std::cerr << "Non-Distributed Graph Tests\n";
+
+ run_non_distributed_graph_tests(gen, pg, n, m, maxEdgeWeight, seed, K4Alpha, a, b, c, d,
+ subGraphEdgeLength, show_degree_dist, full_bc, verify);
+ }
+
+ if (distributed_graph) {
+ if (process_id(pg) == 0)
+ std::cerr << "Distributed Graph Tests\n";
+
+ run_distributed_graph_tests(gen, pg, n, m, maxEdgeWeight, seed, K4Alpha, a, b, c, d,
+ subGraphEdgeLength, show_degree_dist, emit_dot_file,
+ full_bc, verify);
+ }
+
+ return 0;
+}