
Boost : 
From: Robert Smallshire (robert_at_[hidden])
Date: 20010920 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]
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk