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.
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. 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?
For my case it was important to know the correct distance for the target vertex (and not just that it is below the threshold). After being discovered the distance can still reduce. I could have have opted for "examine vertex u", but also wanted the color map to be up to date when exiting, hence "finish vertex u". It seems that in your case you can exit on "discover vertex" for finding the mate, but for the distance criterion you should exit on "examine vertex"; only once the examined vertex is further away than the threshold distance you can be sure that you covered all vertices within the distance. Kind regards, Alex