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-25 12:46:02

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]>