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

On Wednesday, 12. January 2011 11:07:04 Nicholas Mario Wardhana wrote:

On 12 January 2011 16:36, Cedric Laczny 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* pEdge = Graph::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