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 05:54:46

On Wednesday, 12. January 2011 11:07:04 Nicholas Mario Wardhana wrote:
> On 12 January 2011 16:36, Cedric Laczny <cedric.laczny_at_[hidden]> wrote:
> > Hi,
> > 
> > it seems to me, that you are very well adding an edge, but forgetting to
> > insert its properties, that you want to retrieve.
> > 
> > Please s. code below.
> 
> Hi Cedric,
> 
> Thank you for your quick reply.
> 
> > You do add an edge, but this in the same as for vertices, it is only an
> > edge descriptor. There is no additional information (as the properties)
> > associated with it, yet.
> > 
> > This information has not yet been set! I would expect the same as in
> > AddNode() here:
> > m_graph[edgeDescriptor] = pEdge;
> > Retrieving this information when first adding an edge is
> > counter-intuitive. Of course you need to pass pEdge as an argument to
> > AddEdge().
> 
> My bad! Now I realise that I forget to assign pEdge to the edge
> descriptor. So at the beginning of the function I add this line, which
> basically calls the parent class' AddEdge function to retrieve the
> corresponding Edge information:
> 
> Edge<NodeData, EdgeData>* pEdge = Graph<NodeData,
> EdgeData>::AddEdge(pNode1, pNode2);
> 
> and in Step 3 of BoostGraphWrapper::AddEdge(), I add:
> 
> m_graph[edgeDescriptor] = pEdge;
> 
> This solves the problem. Thank you for your suggestion.
> 
> > Hope that helps.
> > BTW, have you already thought about using vecS for the VertexList
> > (instead of listS)? It has the advantage of automatically creating
> > vertex indices which are crucial to most BGL algorithms.
> 
> I think I am clueless about this issue. After searching around, I
> found about that in
> 
> http://www.systomath.com/include/Boost-1_36/libs/graph/doc/quick_tour.html
> 
> I am a new BGL user, and haven't noticed how automatically created
> vertex indices can be useful. Could you please give some information?

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.

> Currently I choose listS over vecS because in some operations, listS
> is faster than vecS, as written in:
> 
> http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/using_adjacency_list.ht
> ml
> 

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.

> Thank you for bringing that up.
>

You are welcome.

> > Best,
> > 
> > Cedric
> 
> Best regards,
> Nicholas Mario Wardhana

Best,

Cedric