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

Subject: Re: [Boost-users] [BGL] BFS < given distance.
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2010-11-25 08:46:53

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]
>
>