https://svn.boost.org/trac10/ticket/1980 <p> Hi, </p> <p> I would like to propose a feature for the Boost Graph library. </p> <p> Summary: </p> <p> 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(). </p> <p> My Problem: </p> <p> 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. </p> <p> My Solution: </p> <p> The file \boost\graph\detail\adjecency_list.hpp is modified as follows. Class vec_adj_list_impl gets 3 new methods: </p> <p> inline void v_reserve(const vertices_size_type&amp; nv) { </p> <blockquote> <p> m_vertices.reserve(nv); </p> </blockquote> <p> } </p> <p> inline void oe_reserve(vertex_descriptor&amp; v, const edges_size_type&amp; ne) { </p> <blockquote> <p> m_vertices[v].m_out_edges.reserve(ne); </p> </blockquote> <p> } </p> <p> inline void ie_reserve(vertex_descriptor&amp; v, const edges_size_type&amp; ne) { </p> <blockquote> <p> m_vertices[v].m_in_edges.reserve(ne); </p> </blockquote> <p> } </p> <p> Using these methods, the time to create a large-scale graph drops to minutes (factor &gt;10). I also modified the method copy_impl to speed-up copying. </p> <p> I attached my modification in a file. </p> <p> Comment: </p> <p> 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. </p> <p> Marc </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/1980 Trac 1.4.3 marc.albers@… Sun, 01 Jun 2008 18:27:20 GMT https://svn.boost.org/trac10/ticket/1980#comment:2 https://svn.boost.org/trac10/ticket/1980#comment:2 <ul> <li><strong>owner</strong> changed from <span class="trac-author">Douglas Gregor</span> to <span class="trac-author">Jeremiah Willcock</span> </li> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">assigned</span> </li> </ul> <p> Do you have the edges of your graph in advance? Are you mutating the structure of the graph? If you have the entire structure before creating the graph, and will not change it afterwards, please use compressed_sparse_row_graph instead of adjacency_list. </p> Ticket Jeremiah Willcock Sat, 23 May 2009 16:13:43 GMT https://svn.boost.org/trac10/ticket/1980#comment:3 https://svn.boost.org/trac10/ticket/1980#comment:3 <ul> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">wontfix</span> </li> </ul> <p> Closing because submitter did not respond. The CSR graph is a better choice when the size of the graph is known in advance. </p> Ticket Antony Polukhin Thu, 13 Oct 2011 18:50:15 GMT