使用Boost :: graph随机访问顶点 [英] Random access of Vertices using Boost::graph

问题描述

我正在尝试使用OpenMP并行遍历提升图的顶点.这似乎需要具有支持元素随机访问的迭代器(例如，itr[i]获取第i个元素).但是，vertices(g)返回的迭代器(a vertex_iterator)似乎不支持此功能.有没有一种有效，干净的方法来实现这一目标?理想情况下，我只想要这样的标准for循环:

I am trying to iterate over my boost graph's vertices in parallel using OpenMP. This seems to require having an iterator that supports random access of elements (e.g., itr[i] gets the ith element). However, the iterator that vertices(g) returns (a vertex_iterator) does not seem to support this. Is there an efficient, clean way to accomplish this? Ideally, I just want a standard for loop such as this:

for (int i = 0; i < num_vertices; i++) {
  vertex v = itr[i];
  // Compute on vertex
}

将与OpenMP合作.谢谢！

which will cooperate with OpenMP. Thanks!

推荐答案

使用adjacency_list<..., vecS, ...>或adjacency_matrix将通过具有整数类型的顶点描述符来启用此功能.

Using a adjacency_list<..., vecS, ...> or adjacency_matrix would enable this by having integral-type vertex descriptors.

稍微想一下，看看并行Boost图形库(并行BGL).很有可能它可以满足您的要求(甚至更多)，但效果更好?

Thinking slightly out of the box, have a look at the Parallel Boost Graph Library (Parallel BGL). It's very likely that it does what you want (and more) but better?

在Coliru上直播

样本输出(在我的系统上):

Sample output (on my system):

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";
}

这篇关于使用Boost :: graph随机访问顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！