
Boost Users : 
Subject: [Boostusers] [Graph] Adjacency list scalability with a Dijkstra algorithm
From: Florian.PONROY_at_[hidden]
Date: 20090325 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. : +33(0)1 41 304 363 Fax : +33(0)1 41 303 560 Email : florian.ponroy_at_[hidden]
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net