Boost graph: speeding up add_edge

Question

I have a boost graph application where I need to call the function add_edge( ) [documentation available here].

Profiling this application with KCachegrind reveals the following breakup of time spent:

As can be seen, the add_edge function call takes up roughly 21% of the time of the parent caller. Out of this 21%, 14.49% is simply some std::vector's reallocation.

The suggested way to prevent such vector reallocations seems to be to upfront reserve some amount of space. See for e.g., thread: How to prevent memory reallocation using std::vector

What is the equivalent way to do this reservation of some sufficient amount of space in boost graph?

The underlying graph object over which this repeated calls to add_edge are made is thus:

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;

---

Edited to add: Similar questions here and here.

Unfortunately for me, g.m_edges does NOT have function reserve.

---

Edited to add link to a minimal example (that is difficult to get to work fully) but compiles fine except for an undefined external reference that is not the main issue.

Answer 1

Unfortunately for me, g.m_edges does NOT have function reserve

But m_vertices does.

#include <boost/graph/adjacency_list.hpp>

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

Also, since you're using vecS you could almost equivalently just construct with a pre-allocated number of vertices:

boost::adjacency_list<> g(1024);

The difference is, of course, that this doesn't just reserve space for, but resizes the graph to contain 1024 vertices.