Hi Juan, Thanks for your answer. I definitly agree with the map overhead, I will try to better understand how the property map works in order to implement your solution. Florian -----Message d'origine----- De : boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org]De la part de Juan Antonio Farré Basurte Envoyé : mercredi 25 mars 2009 19:27 À : boost-users@lists.boost.org Objet : Re: [Boost-users] [Graph] Adjacency list scalability with a Dijks tra algorithm Hi, It's as easy as instantiating the adjacency_list template with mapS for the vertex list selector. This is the second template argument. For example, typedef boost::adjacency_listboost::vecS,boost::mapS myGraph; Anyway, remember that a map is more expensive than a vector in terms of both space and time (access time to an element is logarithmic). Another option is that you stay with the default vector for the vertex list, and you use a property to store the vertex id. This way, your vertex 4242 would have descriptor 6 and you'd store 4242 as its id-property value. Cheers, Juan

Hi Andrew,

Would you please tell me which part of the documentation I should rely on to use a std::map as you'd suggested? I should actually admit I'm not yet familiar with the BGL :-)

-----Message d'origine-----

De : boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org]De la part de Andrew Sutton

Envoyé : mercredi 25 mars 2009 17:25 À : boost-users@lists.boost.org Objet : Re: [Boost-users] [Graph] Adjacency list scalability with a Dijkstra algorithm

Here is the problem: I would have imagined that, in my case, boost::num_vertices(graph) would have returned 6, but it actually returns the higher vertex number + 1, that is... 4243 ! So each of my vector has a size of 4243 * sizeof(tVertex) bytes... Is there a way to handle that? I probably misuse the API, but it would be better if the container would be dimensioned to the actual number of vertices, since I am in a CPU and memory constraint environment...

You're confusing the notions of "index" and "descriptor". With the vertex set using vecS, the descriptor of a vertex is the same as its index -- hence the confusion. Therefore, when you call add_edge(4242, 1, ...), the graph thinks you mean the vertex whose descriptor is 4242 and resizes itself accordingly.

You have to remember - whatever the examples may indicate - that you should never actually use a literal value and descriptors interchangeably. This isn't documented very well, either.

You could use a std::map to associate your own identifiers with vertex descriptors.

Andrew Sutton andrew.n.sutton@gmail.com mailto:andrew.n.sutton@gmail.com

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users