c++ - Boost 图：加速 add_edge

Question

我有一个boost图形应用程序，我需要在其中调用函数 add_edge() [此处提供的文档]。

分析此应用程序KCachegrind揭示了以下所用时间的分解：

可以看出，add_edge函数调用占用了父调用者大约 21% 的时间。在这 21% 中，14.49% 只是一些std::vector人的重新分配。

防止此类向量重新分配的建议方法似乎是预先reserve预留一些空间。参见例如线程：如何使用 std::vector 防止内存重新分配

在升压图中保留一些足够空间的等效方法是什么？

因此，对其进行重复调用的底层图形对象add_edge是：

typedef adjacency_list<
    vecS, vecS, directedS,
    property<
    vertex_name_t, std::string,
    property<vertex_index_t, int,
    property<vertex_color_t, boost::default_color_type,
    property<vertex_distance_t, double,
    property<vertex_predecessor_t, Traits::edge_descriptor>
    > > > >,
    property<
    edge_index_t, int,
    property<edge_capacity_t, double,
    property<edge_weight_t, double,
    property<edge_residual_capacity_t, double,
    property<edge_reverse_t, Traits::edge_descriptor>
> > > > >
Graph;

---

编辑添加：这里和这里的类似问题。

对我来说不幸的是，g.m_edges没有功能reserve。

---

编辑以添加指向最小示例的链接（很难完全工作），但编译良好，除了不是主要问题的未定义外部引用。

Answer 1

对我来说不幸的是， g.m_edges 没有功能储备

但m_vertices确实如此。

#include <boost/graph/adjacency_list.hpp>

int main() {
    boost::adjacency_list<> g;
    g.m_vertices.reserve(1024);
}

此外，由于您正在使用，vecS您几乎可以等效地使用预先分配的顶点数进行构造：

boost::adjacency_list<> g(1024);

当然，不同之处在于，这不仅为图形保留空间，而且还调整了图形的大小以包含 1024 个顶点。