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

Subject: [Boost-users] [Graph] Adjacency list scalability with a Dijkstra algorithm
From: Florian.PONROY_at_[hidden]
Date: 2009-03-25 12:08:50

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:

        typedef boost::adjacency_list<boost::listS,
                                      boost::vecS,
                                      boost::directedS,
                                      boost::no_property,
                                      boost::property<boost::edge_weight_t,
int>
	                             > tGraphShortestpath;

        tGraphShortestpath graph;

        boost::add_edge(1, 2, 1234); // 1234 is the weight
        boost::add_edge(1, 3, 412);
        ...
        boost::add_edge(5, 2, 29);
        boost::add_edge(5, 4242, 84);
        boost::add_edge(4242, 2, 456);
        boost::add_edge(4242, 5, 680);

Now, I want to apply the Dijkstra algorithm on this graph. I create a
distance and a predecessor vector, as I have seen on the documentation
online :

        typedef tGraphShortestpath::vertex_descriptor tVertex;
        std::vector<tVertex> predecessors(boost::num_vertices(graph));
        std::vector<int> distances(boost::num_vertices(graph));

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

Thank you very much for your help!

-- 
Florian PONROY
Thales Land & Joint France
Tel. : [phone]
Fax : [phone]
Email : florian.ponroy_at_[hidden]