BGL record_distances

From: Robert Smallshire (robert_at_[hidden])
Date: 2001-09-20 11:18:07

Graph Library gurus...

I'm having problems getting sensible results from the breadth_first_search()
algorithm in the BGL.  I'm attempting to compute Bacon Numbers (i.e.
distances between vertices) for my undirected graph.

I'm using the breath_first_search() algorithm rather than the
dijkstra_shortest_paths() as I can't persuade the latter to build with
MSVC6.0sp5.

My problem is as follows.  When calculated the distances between vertices
I'm getting incorrect results including :

1) Distance a->b != distance b->a

2) Incomplete sequences of consecutive distances.  e.g. I have nodes with
distances from the source node of 0, 2 and 3 but none with a distance of 1 -
surely this cannot be correct ?

My example graph contains 37 vertices, what follows are examples of
inconsistent results obtained using the algorthm multiple times on the same
data structure:

Distances from vertex 32 (-1 indicates not connected)
(32,0) = -1
(32,1) = 2
(32,2) = 2
(32,3) = 2
(32,4) = -1
(32,5) = -1
(32,6) = -1
(32,7) = -1
(32,8) = -1
(32,9) = 2
(32,10) = -1
(32,11) = 2
(32,12) = -1
(32,13) = -1
(32,14) = -1
(32,15) = -1
(32,16) = -1
(32,17) = -1
(32,18) = -1
(32,19) = -1
(32,20) = 2
(32,21) = -1
(32,22) = -1
(32,23) = -1
(32,24) = -1
(32,25) = 3
(32,26) = -1
(32,27) = -1
(32,28) = -1
(32,29) = -1
(32,30) = -1
(32,31) = -1
(32,32) = 0
(32,33) = -1
(32,34) = -1
(32,35) = -1
(32,36) = -1
(32,37) = -1

Distances from vertex 25
(25,0) = -1
(25,1) = 2
(25,2) = 0
(25,3) = 0
(25,4) = -1
(25,5) = -1
(25,6) = -1
(25,7) = -1
(25,8) = -1
(25,9) = 2
(25,10) = -1
(25,11) = 0
(25,12) = -1
(25,13) = -1
(25,14) = -1
(25,15) = -1
(25,16) = -1
(25,17) = -1
(25,18) = -1
(25,19) = -1
(25,20) = 0
(25,21) = -1
(25,22) = -1
(25,23) = -1
(25,24) = -1
(25,25) = 0
(25,26) = -1
(25,27) = -1
(25,28) = -1
(25,29) = -1
(25,30) = -1
(25,31) = -1
(25,32) = 1
(25,33) = -1
(25,34) = -1
(25,35) = -1
(25,36) = -1
(25,37) = -1

Take a look at how the distance from 25->32 and 32->25 differ, and also note
the lack of a vertex with a distance of 1 from vertex 32.

My graph is definitely undirected :

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
VertexColorProperty ,EdgeWeightProperty> Graph;

and the code fragment used to compute the distances (Bacon Numbers) looks
like this :

m_predecessor.clear();
m_bacon_number.clear();
m_predecessor.resize(  boost::num_vertices(G) , -1);
m_bacon_number.resize( boost::num_vertices(G) , -1);

boost::breadth_first_search(
        G, src,
              boost::visitor(
                        boost::make_bfs_visitor(
                                boost::make_list(
                                        boost::record_predecessors(&m_predecessor[0],
boost::on_examine_edge()),
                                                  boost::record_distances(   &m_bacon_number[0],
boost::on_examine_edge())
                                          )
                                 )
                          )
        );

I then index the vector<int> m_bacon_number using a vertex descriptor which
seems to work correctly.

Any ideas or help gratefully received!

Many thanks,

Rob

~~~~~~~~~~~~~~~~~

Dr Rob Smallshire
Senior Development Engineer
& Structural Geologist
Midland Valley
rob_at_[hidden]