Re: [Boost-users] BGL: Problem with dijkstra_shortest_paths

Subject: Re: [Boost-users] BGL: Problem with dijkstra_shortest_paths
From: Stephen Woodbridge (woodbri_at_[hidden])
Date: 2011-06-30 16:47:08

On 6/30/2011 11:47 AM, Alex Hagen-Zanker wrote:

...

> Also I noticed that you set the number of nodes to 1. Note that add_edge
> assumes your nodes to be present, and does not add nodes if the required
> nodes are not there.

...

OK, I just noticed this comment. I think to create a graph you need to 
allocate at least one node. I don't have a good way to get the number of 
unique nodes from the data that I'm building the graph from, short of 
scanning it all first and getting the min and max node ids. I actually 
do have to scan for the minimum node id because I renumber them, so also 
picking up the max node id at the same time could be done also. I assume 
if I create the graph with max-min+1 number of nodes, that that will 
speed it up because the container will not need to be extended when new 
edges with new nodes are added.

That said, I assume add_edge does add the nodes if they do not exist in 
the graph when the edge is added and that when an edge is added and one 
or both nodes exist it uses them, since the code works and I appear to 
be getting the correct answers.

Thanks,
   -Steve