Performance Problem with Incremental Graph Design

Question

I am working on software where I need to create a graph (using boost :: adjacency_list). Incremental insertion of vertices takes a lot of time. So far, I have not worked on this problem because using STLport fixed this problem. Now I have transferred my work to Visual Studio 2008, but I can’t spend time using STLport (the difficulty in supporting compilation of enhancement libraries using STLport).

I would prefer not to store the vertices of the graph in the list, because I often use vertex identifiers, as if they were integers.

What other options should I solve this problem (in debug mode, as well as in release mode)?

Answer 1

Do you know in advance how many nodes you have? If so, this will drastically reduce the time it takes to create a chart.

For example, for a graph containing 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; 

Choosing OutEdgeListS and VertexListS has a big impact on the time complexity of graph algorithms implemented through boost adjacency_list.

• add_vertex () is an amortized constant time for both vecS and listS (implemented using push_back ()). However, when the VertexListS type is vecS, the time for this operation is sometimes long because the vector will be redistributed and the entire graph will be copied.
• remove_vertex () - constant time for listS and O (V + E) for vecS.

As you can see above, the default is for vecS. Thus, you can expect some improvement over time if you use listS for VertexListS (with a lot of overhead)

Answer 3

Have you really tried profiling code that takes a lot of time? You may be surprised and find something unexpected (implicit conversion / conversion constructor, more comparisons than expected, data copying, etc.). In addition, profiling can give you an idea of ​​what part of the insertion algorithm takes a lot of time, and the possibilities (for example: changing the constructor arguments of adjacency_list) to fix it.

Answer 4

I would prefer not to store the vertex graph in the list, because I often use vertex identifiers as if they were integers.

Maybe you can use listS in the end. Just declaring the vertex index as a property (check http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/using_adjacency_list.html #sec: list-property adjacencies ). But, if you delete a vertex, you may have to renumber the vertices. In addition, if you add a vertex, you must assign its vertex index value.