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: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2011-01-12 07:32:47

On Wednesday, 12. January 2011 13:06:43 Nicholas Mario Wardhana wrote:
> 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.
> 

Now, real-time applications are of course a quite specific field and rely 
heavily on the constraint of performance... It would be intersting to see the 
differences if you are going to swich to listS, therefore it would be kind of 
you to provide some runtime-results to this mailinglist when you're done :)
Changing vecS to listS should be fairly straightforward, basically only 
requiring a valid vertex index property-map.

> Thank you for the explanation.

You are welcome.

> Best regards,
> Nicholas Mario Wardhana

Good luck with your project.

Best,

Cedric