On 12 January 2011 18:54, Cedric Laczny
If you look at the algorithms or visitors that the BGL provides (e.g. Dijkstra's shortest path(s) or BFS), these algorithms almost all rely in some way on an indexing of the vertices. I can't really explain you what each algorithm's special purpose of the indices is, but I think that this is not that important right now ;) Probably for sorting or such... However, these algorithm rely on either an internal vertex_index_t, which is automatically created and updated when adding vertices, _if_ vecS is used as the vertex container. At the moment I am not sure how this behaves when removing vertices, so I will leave this out for now (iterator invalidation also plays a role here, just for your notes). If you decide to use listS, setS (or others) you need to maintain a vertex-index on your own, e.g. as an attribute of your wrapper. This index must then be passed to the BFS, as otherwise, it will try to retrieve it automatically via vertex_index_t, which will result in compile errors.
I think this is also one of the never-ending stories: Which is best to choose for which purpose. In theory, a list is usually faster than a vector, especially when inserting a lot. This might very well be the case in practice also. I think it strongly depends on your application. However, I did not experience dramatically worse performance using vecS. The STL vector container is probably one of the most optimized linear containers (at least in the STL) and thus is IMHO generally comparable to a list.
Do you expect to have very large graphs? I actually work with graphs having around 30k vertices and 500k edges and I use vecS and setS respectively. I did not experience that the traversal of the graph was slow; usually other things (algorithms, copying etc.) require most of the runtime. Except for testing it out yourself for your particular purposes, I don't think there is a way for you to know which choice would be better. Choosing vecS might (conditinal here :) slow down your program while benefiting from the automatic vertex indexing. The automatic indexing of course also costs you space, because the adjacency_list must also store that information. All in all, if you don't have a very critically limited application, vecS would be the best choice IMHO, especially when just starting to work with the BGL.
Best,
Cedric
Hi Cedric, Actually, I will use the wrapper for motion planning for real-time application, therefore searching algorithms like Dijkstra and A* will be heavily used. This is also the reason why I use BGL, as it comes with these searching algorithms. I'm dealing with a huge environment, so I also expect the graph to be big, although maybe not as big as yours, probably with around 1-10k vertices and 50k edges. Of course planning time is crucial here, taking the real-time constraint into account. Nevertheless, I think for now I will just resort to vecS, and I will compare listS and vecS later on. If switching to listS is not worth the implementation effort, considering the performance of vecS, I will stick to vecS. Thank you for the explanation. Best regards, Nicholas Mario Wardhana