Performance issue with graph incremental construction

Question

I am working on a software where i have to create a graph (using boost::adjacency_list). The incremental insertion of vertices takes an extremely long time. Until now, i hadn't worked on the issue, because the use of STLport made this problem go away. I have now migrated my work to Visual Studio 2008, but can't take the time to go on using STLport (difficulty to maintain compilation of boost libraries using STLport).

I'd rather not store the graph vertices in a list, because i am often using vertex identifiers as if they were integers.

What other options do i have to solve this issue (in debug as well as release mode) ?

Answer 1

Do you know in advance how many nodes you have ? If yes, this will drasticaly reduce the graph creation time.

For example for a graph that has 10 000 nodes:

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, > Graph_t;
Graph_t g(10000);

Answer 2

template<class OutEdgeListS = vecS, class VertexListS = vecS,.....> adjacency_list;

The choice of OutEdgeListS and VertexListS has great influence on the time complexity of graph algorithms implemented via boost adjacency_list.

• add_vertex() is amortized constant time for both vecS and listS (implemented with push_back()). However, when the VertexListS type is vecS the time for this operation is occasionally large because the vector will be reallocated and the whole graph copied.
• remove_vertex() is constant time for listS and O(V + E) for vecS.

As you can see above, the default for both is vecS. So you can expect some improvement in time if you use listS for VertexListS (with higher space overhead)

Answer 3

Have you actually tried profiling the code that takes a long time to execute? You may be surprised and find something unexpected (implicit conversion/converting constructor, more comparisons than expected, data copying, etc). Additionally the profiling might give you an idea about which part of the insert algorithm is taking a long time and the possibilities (ex: change the adjacency_list constructor args) for correcting it.