id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
1980,[Boost Graph library] functionality to reserve memory,marc.albers@…,Jeremiah Willcock,"Hi,

I would like to propose a feature for the Boost Graph library.

Summary:

For large std::vector containers reserving memory in advance can improve performance significantly if many objects are added. I'd like to have this option for the boost::adjacency_list when using selector type vecS for storage of vertices and edges. This option would help to avoid frequent reallocations when using add_vertex() and add_edge().

My Problem:

I am using the Boost Graph library for a large-scale railway crew scheduling problem.  The graph is defined as boost::adjecency_list with vecS as storage selection for vertices and edges, i.e., std::vector is used. For some problem instances, the graph can have 35,000 vertices and 4,000,000 edges. The vertex descriptors have a size of up to 40 bytes and edge descriptors have a size of up to 100 bytes. The graph is created using the add_vertex() and add_edge() methods. Creating this graph requires several hours on my Pentium M 1.7 GHz which seems too long.

My Solution:

The file \boost\graph\detail\adjecency_list.hpp is modified as follows. Class vec_adj_list_impl gets 3 new methods:

inline void v_reserve(const vertices_size_type& nv) {
  m_vertices.reserve(nv);
}

inline void oe_reserve(vertex_descriptor& v, const edges_size_type& ne) {
  m_vertices[v].m_out_edges.reserve(ne);
}

inline void ie_reserve(vertex_descriptor& v, const edges_size_type& ne) {
  m_vertices[v].m_in_edges.reserve(ne);
}

Using these methods, the time to create a large-scale graph drops to minutes (factor >10). I also modified the method copy_impl to speed-up copying.

I attached my modification in a file. 

Comment:

These methods are only a workaround. Since the documentation of add_vertex() and add_edge() mentions the problem of reallocations, I suspect that the authors have already thought about reserving memory, but for some reasons did not implement it. As my example shows, there are situations where reserving memory is very useful. This feature is desirable for any user working with large-scale graphs that require an implementation with std::vector.

Marc",Feature Requests,closed,To Be Determined,graph,Boost 1.35.0,Optimization,wontfix,"Boost Graph library, std::vector, reserve memory",