Boost图:加速add_edge
Boost图:加速add_edge
提问于 2021-06-07 19:09:05
我有一个boost图形应用程序，其中需要调用函数add_edge( ) documentation available [here]。
使用KCachegrind分析此应用程序时，会显示所用时间的以下细分：
可以看出，add_edge函数调用占用了父调用者大约21%的时间。在这21%中，14.49%仅仅是一些std::vector的重新分配。
防止这种向量重新分配的建议方法似乎是预先reserve一定数量的空间。例如，有关线程：How to prevent memory reallocation using std::vector，请参见
在boost图中保留足够的空间的等效方法是什么？
对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函数。
编辑以添加到minimal example的链接(这很难完全工作)，但编译良好，除了未定义的外部引用，这不是主要问题。
回答 1
Stack Overflow用户
发布于 2021-06-07 20:29:46
对我来说不幸的是，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个顶点。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/67870513
复制相关文章
相似问题
腾讯云开发者
