Re: [Boost-users] Boost Graph Library: edge retrieval using edge descriptor between square brackets fails

Subject: Re: [Boost-users] Boost Graph Library: edge retrieval using edge descriptor between square brackets fails
From: Nicholas Mario Wardhana (mario.wardhana_at_[hidden])
Date: 2011-01-12 07:06:43

On 12 January 2011 18:54, Cedric Laczny <cedric.laczny_at_[hidden]> wrote:
>
> 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