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@sanger.ac.uk Wellcome Trust Sanger Institute Tel: +44 (0)1223 834244 x7728 Hinxton, Cambridge CB10 1SA Fax: +44 (0)1223 494919 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@sanger.ac.uk Wellcome Trust Sanger Institute Tel: +44 (0)1223 834244 x7728 Hinxton, Cambridge CB10 1SA Fax: +44 (0)1223 494919

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