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-29 08:18:16

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