[Boost-users] [BGL] BFS < given distance.

Subject: [Boost-users] [BGL] BFS < given distance.
From: Adam Spargo (aws_at_[hidden])
Date: 2010-11-25 07:39:23

Hi,
I have finally managed to implement my genome assembly algorithm! Except 
one part is too slow. I'm doing a breadth first search starting from each 
vertex i in an undirected graph, looking for its mate-pair (another 
given vertex j, of approximately known distance, where distance is the 
same as summed edge weight). Ideally I want to follow the BFS until either

(i) I find the mate-pair vertex j

(ii) I have visited all vertices up to some given distance away from the 
source vertex i.

I want to bail out of the algorithm at the first occurrance of either (i) 
or (ii) and not carry on to search through the rest of the graph, which is 
very large.

So I'm wondering if anybody has had a similar requirement and if they 
implemented a BFS visitor which accomplishes it?

I have managed to limit it to the same connected component, but it still 
takes too long. The limiting distance is small and so I could just write 
something, but it would obviously be more elegant to use a BFS visitor.

Thanks for any advice,

Adam.

--
Dr Adam Spargo
High Performance Assembly Group   email: aws_at_[hidden]
Wellcome Trust Sanger Institute   Tel: [phone] x7728
Hinxton, Cambridge CB10 1SA       Fax: [phone]
-- 
 The Wellcome Trust Sanger Institute is operated by Genome Research 
 Limited, a charity registered in England with number 1021457 and a 
 company registered in England with number 2742969, whose registered 
 office is 215 Euston Road, London, NW1 2BE.