Re: [Boost-users] [Graph] Adjacency list scalability with a Dijks tra algorithm

Subject: Re: [Boost-users] [Graph] Adjacency list scalability with a Dijks tra algorithm
From: Florian.PONROY_at_[hidden]
Date: 2009-03-26 04:28:38

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_at_[hidden] [mailto:boost-users-bounces_at_[hidden]]De la part de Juan Antonio Farré Basurte
Envoyé : mercredi 25 mars 2009 19:27
À : boost-users_at_[hidden]
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_list<boost::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_at_[hidden] [mailto:boost-users-bounces_at_[hidden]]De la part de Andrew Sutton
> Envoyé : mercredi 25 mars 2009 17:25
> À : boost-users_at_[hidden]
> 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_at_[hidden] <mailto:andrew.n.sutton_at_[hidden]>
> 
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users