Re: [boost] BGL record_distances

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-09-21 12:13:39

Hi Rob,

Could you send the complete program (including the graph data) that you
are having trouble with (otherwise I may have trouble reproducing the
problem).

Cheers,
Jeremy

On Thu, 20 Sep 2001, Robert Smallshire wrote:

robert> Graph Library gurus...
robert>
robert> I'm having problems getting sensible results from the breadth_first_search()
robert> algorithm in the BGL.  I'm attempting to compute Bacon Numbers (i.e.
robert> distances between vertices) for my undirected graph.
robert>
robert> I'm using the breath_first_search() algorithm rather than the
robert> dijkstra_shortest_paths() as I can't persuade the latter to build with
robert> MSVC6.0sp5.
robert>
robert> My problem is as follows.  When calculated the distances between vertices
robert> I'm getting incorrect results including :
robert>
robert> 1) Distance a->b != distance b->a
robert>
robert> 2) Incomplete sequences of consecutive distances.  e.g. I have nodes with
robert> distances from the source node of 0, 2 and 3 but none with a distance of 1 -
robert> surely this cannot be correct ?
robert>
robert> My example graph contains 37 vertices, what follows are examples of
robert> inconsistent results obtained using the algorthm multiple times on the same
robert> data structure:
robert>
robert> Distances from vertex 32 (-1 indicates not connected)
robert> (32,0) = -1
robert> (32,1) = 2
robert> (32,2) = 2
robert> (32,3) = 2
robert> (32,4) = -1
robert> (32,5) = -1
robert> (32,6) = -1
robert> (32,7) = -1
robert> (32,8) = -1
robert> (32,9) = 2
robert> (32,10) = -1
robert> (32,11) = 2
robert> (32,12) = -1
robert> (32,13) = -1
robert> (32,14) = -1
robert> (32,15) = -1
robert> (32,16) = -1
robert> (32,17) = -1
robert> (32,18) = -1
robert> (32,19) = -1
robert> (32,20) = 2
robert> (32,21) = -1
robert> (32,22) = -1
robert> (32,23) = -1
robert> (32,24) = -1
robert> (32,25) = 3
robert> (32,26) = -1
robert> (32,27) = -1
robert> (32,28) = -1
robert> (32,29) = -1
robert> (32,30) = -1
robert> (32,31) = -1
robert> (32,32) = 0
robert> (32,33) = -1
robert> (32,34) = -1
robert> (32,35) = -1
robert> (32,36) = -1
robert> (32,37) = -1
robert>
robert> Distances from vertex 25
robert> (25,0) = -1
robert> (25,1) = 2
robert> (25,2) = 0
robert> (25,3) = 0
robert> (25,4) = -1
robert> (25,5) = -1
robert> (25,6) = -1
robert> (25,7) = -1
robert> (25,8) = -1
robert> (25,9) = 2
robert> (25,10) = -1
robert> (25,11) = 0
robert> (25,12) = -1
robert> (25,13) = -1
robert> (25,14) = -1
robert> (25,15) = -1
robert> (25,16) = -1
robert> (25,17) = -1
robert> (25,18) = -1
robert> (25,19) = -1
robert> (25,20) = 0
robert> (25,21) = -1
robert> (25,22) = -1
robert> (25,23) = -1
robert> (25,24) = -1
robert> (25,25) = 0
robert> (25,26) = -1
robert> (25,27) = -1
robert> (25,28) = -1
robert> (25,29) = -1
robert> (25,30) = -1
robert> (25,31) = -1
robert> (25,32) = 1
robert> (25,33) = -1
robert> (25,34) = -1
robert> (25,35) = -1
robert> (25,36) = -1
robert> (25,37) = -1
robert>
robert> Take a look at how the distance from 25->32 and 32->25 differ, and also note
robert> the lack of a vertex with a distance of 1 from vertex 32.
robert>
robert> My graph is definitely undirected :
robert>
robert> typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
robert> VertexColorProperty ,EdgeWeightProperty> Graph;
robert>
robert> and the code fragment used to compute the distances (Bacon Numbers) looks
robert> like this :
robert>
robert> m_predecessor.clear();
robert> m_bacon_number.clear();
robert> m_predecessor.resize(  boost::num_vertices(G) , -1);
robert> m_bacon_number.resize( boost::num_vertices(G) , -1);
robert>
robert> boost::breadth_first_search(
robert> 	G, src,
robert>       	boost::visitor(
robert>         		boost::make_bfs_visitor(
robert>         			boost::make_list(
robert>         				boost::record_predecessors(&m_predecessor[0],
robert> boost::on_examine_edge()),
robert> 			  			boost::record_distances(   &m_bacon_number[0],
robert> boost::on_examine_edge())
robert> 			  		)
robert> 			 	)
robert> 		  	)
robert>         );
robert>
robert> I then index the vector<int> m_bacon_number using a vertex descriptor which
robert> seems to work correctly.
robert>
robert> Any ideas or help gratefully received!
robert>
robert> Many thanks,
robert>
robert> Rob
robert>
robert> ~~~~~~~~~~~~~~~~~
robert>
robert> Dr Rob Smallshire
robert> Senior Development Engineer
robert> & Structural Geologist
robert> Midland Valley
robert> rob_at_[hidden]
robert>
robert>
robert> Info: http://www.boost.org  Unsubscribe: <mailto:boost-unsubscribe_at_[hidden]>
robert>
robert> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
robert>
robert>

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------