使用 Boost::graph 随机访问顶点
Random access of Vertices using Boost::graph
我正在尝试使用 OpenMP 并行迭代提升图的顶点。这似乎需要有一个支持元素随机访问的迭代器(例如,itr[i]
获取第 i
个元素)。但是vertices(g)
returns(avertex_iterator
)的迭代器好像不支持这个。有没有一种高效、干净的方法来实现这一点?理想情况下,我只想要一个标准的 for 循环,例如:
for (int i = 0; i < num_vertices; i++) {
vertex v = itr[i];
// Compute on vertex
}
将与OpenMP合作。谢谢!
使用 adjacency_list<..., vecS, ...>
或 adjacency_matrix
将通过具有整数类型的顶点描述符来实现这一点。
稍微跳出框框,看看 Parallel Boost Graph Library(并行 BGL)。它很可能会做你想要的(甚至更多)但更好?
微型演示
示例输出(在我的系统上):
Generated 50000000 vertices in 1879ms
Using 8 threads.
Sum of volumes for 50000000 vertices in 94ms: 2.5603e+10
完整列表:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <chrono>
#include <iostream>
#include <omp.h>
#include <random>
static std::mt19937 prng { std::random_device{}() };
struct MyVertex {
uintmax_t volume = [] { static std::uniform_int_distribution<int> pick(0, 1024); return pick(prng); }();
};
using namespace boost;
using G = adjacency_list<vecS, vecS, directedS, MyVertex>;
G generate() {
using namespace std::chrono;
auto start = high_resolution_clock::now();
G g;
generate_random_graph(g, 50000000, 0, prng);
auto end = high_resolution_clock::now();
std::cerr << "Generated " << num_vertices(g) << " vertices " << "in " << duration_cast<milliseconds>(end-start).count() << "ms\n";
return g;
}
int main() {
auto const g = generate();
using namespace std::chrono;
auto start = high_resolution_clock::now();
double sum = 0;
#pragma omp parallel
{
#pragma omp single
std::cerr << "Using " << omp_get_num_threads() << " threads.\n";
#pragma omp for reduction(+:sum)
for (G::vertex_descriptor u = 0; u < num_vertices(g); ++u) {
sum += g[vertex(u, g)].volume;
}
}
auto end = high_resolution_clock::now();
std::cerr << "Sum of volumes for " << num_vertices(g) << " vertices "
<< "in " << duration_cast<milliseconds>(end-start).count() << "ms: " << sum << "\n";
}
我正在尝试使用 OpenMP 并行迭代提升图的顶点。这似乎需要有一个支持元素随机访问的迭代器(例如,itr[i]
获取第 i
个元素)。但是vertices(g)
returns(avertex_iterator
)的迭代器好像不支持这个。有没有一种高效、干净的方法来实现这一点?理想情况下,我只想要一个标准的 for 循环,例如:
for (int i = 0; i < num_vertices; i++) {
vertex v = itr[i];
// Compute on vertex
}
将与OpenMP合作。谢谢!
使用 adjacency_list<..., vecS, ...>
或 adjacency_matrix
将通过具有整数类型的顶点描述符来实现这一点。
稍微跳出框框,看看 Parallel Boost Graph Library(并行 BGL)。它很可能会做你想要的(甚至更多)但更好?
微型演示
示例输出(在我的系统上):
Generated 50000000 vertices in 1879ms
Using 8 threads.
Sum of volumes for 50000000 vertices in 94ms: 2.5603e+10
完整列表:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <chrono>
#include <iostream>
#include <omp.h>
#include <random>
static std::mt19937 prng { std::random_device{}() };
struct MyVertex {
uintmax_t volume = [] { static std::uniform_int_distribution<int> pick(0, 1024); return pick(prng); }();
};
using namespace boost;
using G = adjacency_list<vecS, vecS, directedS, MyVertex>;
G generate() {
using namespace std::chrono;
auto start = high_resolution_clock::now();
G g;
generate_random_graph(g, 50000000, 0, prng);
auto end = high_resolution_clock::now();
std::cerr << "Generated " << num_vertices(g) << " vertices " << "in " << duration_cast<milliseconds>(end-start).count() << "ms\n";
return g;
}
int main() {
auto const g = generate();
using namespace std::chrono;
auto start = high_resolution_clock::now();
double sum = 0;
#pragma omp parallel
{
#pragma omp single
std::cerr << "Using " << omp_get_num_threads() << " threads.\n";
#pragma omp for reduction(+:sum)
for (G::vertex_descriptor u = 0; u < num_vertices(g); ++u) {
sum += g[vertex(u, g)].volume;
}
}
auto end = high_resolution_clock::now();
std::cerr << "Sum of volumes for " << num_vertices(g) << " vertices "
<< "in " << duration_cast<milliseconds>(end-start).count() << "ms: " << sum << "\n";
}