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

Subject: Re: [Boost-users] [Graph] Adjacency list scalability with a Dijkstra algorithm
From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2009-03-25 12:23:24

On Wed, Mar 25, 2009 at 12:08 PM,  <Florian.PONROY_at_[hidden]> wrote:
> Hi,
>
> Assuming that I want a graph made of 6 nodes, numbered 1, 2, 3, 4, 5 and
> 4242. I build the graph this way:

<snip>

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

With vecS storage, vertex numbering begins at 0, just like an array.
So if you only did:

MyGraph graph;
add_edge(3, 11, graph);

num_vertices(graph); // returns 12
num_edges(graph); // returns 1

--Michael Fawcett