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

Subject: Re: [Boost-users] [BGL] BFS < given distance.
From: Adam Spargo (aws_at_[hidden])
Date: 2010-11-29 07:50:26

Hi Alex,
Thanks for the tip, I've implemented something similar. The only thing I 
don't understand is why you throw the exception when you finish the target 
vertex rather than when you discover it?

Cheers,

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]
On Thu, 25 Nov 2010, Alex Hagen-Zanker wrote:
> Hi Adam,
>
> I had a very similar situation for the Dijkstra shortest path algorithm. The 
> solution that I found was recommended on this list and on the doc pages. It 
> is to throw an exception when the termination criterion is met.
>
> I used the code below, but be aware this is only a Dijkstra visitor and only 
> for the target  vertex criterion. For the distance criterion it is necessary 
> to still add a (pointer to a) distance property map and the target distance.
>
> Of course you also still need to catch the exception.
>
> Kind regards, Alex
>
> struct dijkstra_early_exit
> {};
>
> template<class Graph>
> class dijkstra_target_visitor
> {
>    typedef Graph G;
>    typedef typename G::vertex_descriptor U;
>    typedef typename G::edge_descriptor E;
>
> public:
>    dijkstra_target_visitor(const U& target) : t(target)
>    {}
>
>    void initialize_vertex( const U& u, const G& g) { return; }
>    void examine_vertex( const U& u, const G& g) { return; }
>    void examine_edge( const E& e, const G& g) { return; }
>    void discover_vertex( const U& u, const G& g) { return; }
>    void edge_relaxed( const E& e, const G& g) { return; }
>    void edge_not_relaxed( const E& e, const G& g) { return; }
>
>    void finish_vertex( const U& u, const G& g)
>    {
>       if(u == target)
>            throw dijkstra_early_exit();
>    }
>
> private:
>    U target;
> };
> On 25/11/2010 12:39, Adam Spargo wrote:
>> 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.