Boost logo

Boost Users :

Subject: Re: [Boost-users] [Graph] Adjacency list scalability with a Dijks tra algorithm
From: Juan Antonio Farré Basurte (jafb_at_[hidden])
Date: 2009-03-25 14:27:29

It's as easy as instantiating the adjacency_list template with mapS for the vertex list selector.
This is the second template
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.


> 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
> À :
> 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
> andrew.n.sutton_at_[hidden] <mailto:andrew.n.sutton_at_[hidden]>
> Boost-users mailing list
> Boost-users_at_[hidden]

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at