Re: [boost] Using dijkstra on unconnected graph

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-01-11 09:54:32

On Wed, 10 Jan 2001 aalness_at_[hidden] wrote:
aalnes> I am using dijkstra_shortest_paths() on an unconnected
aalnes> graph, in order to find out if the source and dest im
aalnes> looking at are even connected is the correct thing to do
aalnes> to check for a black_color value for the dest color?

Yes, checking for black will tell you if there is a path from the source
to the destination. Also, the distance value for the destination will be
numeric_limits::max() if there were no paths.

Note that if the only information you need is the connectivity, a breadth
first or depth first search may be a bit faster.

aalnes> Also, if I create an undirected adjacency_list that uses
aalnes> vectors for both my vertex and edge data structures will
aalnes> add_edge()'s bool return value be set to false if I try
aalnes> and do a duplicate add?

With vecS for the EdgeList, the adjacency_list allows parallel edges. So
the bool return value will true, and the edge will be added. Use setS for
EdgeList if you want to disallow parallel edges.

You can check this by looking at the type of 
graph_traits< adjacency_list<...> >::edge_parallel_category 

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------