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

Subject: Re: [Boost-users] [Graph] Adjacency list scalability with a Dijkstra algorithm
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-03-25 12:25:29

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