adjacency_list 上的 Boost Graph 函数 vertex() 的时间复杂度

Question

在

vertex()

上操作时，我对 Boost Graph 函数

adjacency_list

的时间复杂度感到困惑。

手册中的页面似乎声称，即使模板参数

vertex()

为

VertexList

，函数

listS

也会以恒定时间运行。

• vertex()

  对于 vecS 和 listS，此操作是恒定时间。

但是，当底层数据结构是

std::list

时，该函数如何实现恒定时间操作对我来说是一个谜。我查看了生成的目标代码，看起来函数

vertex()

在

VertexList=listS

时编译为迭代循环，而在

VertexList=vecS

时编译为常量查找。

最后，我创建了一个小型测试程序，该程序确认运行时间与使用

vertex()

时传递给

listS

的索引值成比例。

这加起来怎么样？ 是否有一些特殊的方法可以使

vertex()

在恒定时间内运行，或者我是否误解了文档，或者文档根本就是错误的？

// Sample code showing non-constant run time of vertex()
boost::adjacency_list<
    boost::vecS,
    boost::listS,  // program is fast when I change this to vecS
    boost::undirectedS> g;

// Generate random graph with 10000 vertices.
std::mt19937 rng(1234);
boost::generate_random_graph(g, 10000, 20000, rng, false);

// Repeated lookup of vertex in graph
//   takes 10 seconds for listS, 0.02 seconds for vecS
int result = 0;
std::uniform_int_distribution vdist{0, int(boost::num_vertices(g) - 1)};
for (int i = 0; i < 1000000; ++i) {
    int v = vdist(rng);
    result += boost::out_degree(boost::vertex(v, g), g);
}
std::cout << result << std::endl;

Answer 1

文档是错误的。相关重载已正确注释

O(V)

:

// O(V)
template < class Derived, class Config, class Base >
inline typename Config::vertex_descriptor vertex(
    typename Config::vertices_size_type n,
    const adj_list_impl< Derived, Config, Base >& g_)
{
    const Derived& g = static_cast< const Derived& >(g_);
    typename Config::vertex_iterator i = vertices(g).first;
    while (n--)
        ++i; // std::advance(i, n); (not VC++ portable)
    return *i;
}

您可以使用外部索引来模拟恒定时间查找，但我确信您知道如何操作。

这是简化并独立的示例：

住在Coliru

// Compile: g++ -std=c++17 -O3 -o test test.cpp
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <iostream>
#include <random>
#include <chrono>
using namespace std::chrono_literals;
static inline auto now() { return std::chrono::high_resolution_clock::now(); };

template <typename VertexContainerSelector, size_t Seed = 1234> void bench_mark(size_t N = 1'000'000) {
    using G = boost::adjacency_list<boost::vecS, VertexContainerSelector, boost::undirectedS>;
    using V = G::vertex_descriptor;
    G g;

    std::mt19937 rng{Seed};
    generate_random_graph(g, 10'000, 20'000, rng, false);

    auto get = [&] { return [&g](size_t n) { return vertex(n, g); }; }();

    size_t result = 0;
    auto   vdist  = bind(std::uniform_int_distribution{0ul, num_vertices(g) - 1}, ref(rng));

    auto s = now();
    for (size_t i = 0; i < N; ++i) {
        int  n  = vdist();
        auto u  = get(n);
        result += out_degree(u, g);
    }
    std::cout << __PRETTY_FUNCTION__ << " " << result << " " << (now() - s) / 1.s << "s" << std::endl;
}

int main() {
    bench_mark<boost::vecS>();
    bench_mark<boost::listS>();
}

打印（在我的机器上）：

void bench_mark(size_t) [with VertexContainerSelector = boost::vecS...] 4000918 0.0035862s
void bench_mark(size_t) [with VertexContainerSelector = boost::listS...] 4000918 5.23695s

解决方法

建议的解决方法的可能实施：

std::vector<V> index; // only used for listS
auto  get = [&] {
    if constexpr (std::is_same_v<VertexContainerSelector, boost::vecS>) {
        return [&g](size_t n) { return vertex(n, g); };
    } else {
        auto [b, e] = vertices(g);
        index.assign(b, e);
        return [&index](size_t n) { return index[n]; };
    }
}();

打印（比较 Live On Coliru）

void bench_mark(size_t) [with VertexContainerSelector = boost::vecS...] 4000918 0.00360215s
void bench_mark(size_t) [with VertexContainerSelector = boost::listS...] 4000918 0.00436193s