Boost logo

Boost Users :

Subject: Re: [Boost-users] BGL: interrupting breadth_first_search() at a certain distance/predicate?
From: Adam Spargo (aws_at_[hidden])
Date: 2010-08-03 05:30:25

> On Aug 2, 2010, at 10:46 AM, Anders Wallin wrote:
>> Hi all,
>> I have a graph where I start at a certain vertex and want to find the
>> next undiscovered vertex at a maximum distance of 5 or so from the
>> source vertex.
>> Now I am running breadth_first_search() using a record_distances()
>> visitor and I get the distances to all other vertices (say 10 000 of
>> them) in my graph. This makes my algorithm slow, since I only need to
>> know about vertices at a max distance of 5-6, not all of them.
>> Is there a way of interrupting the algorithm when a certain predicate
>> function supplied by me evaluates to true? (e.g. max distance reached,
>> or a new interesting/valid vertex found, etc)
> For this particular job I think I'd build a wrapper around your graph that
> presents the nearby sub-graph. I think there may already be a
> filtered_graph adaptor you can leverage in the BGL.

Yes, I've been working with filtered_graph recently. It is lightweight and
quick, so you could just filter on distance from the vertex and do the
search on the filtered_graph. I'm sure that the filtering would be quicker
than searching all other vertices. See recent thread for example code on

Hope that helps,


Dr Adam Spargo
High Performance Assembly Group   email: aws_at_[hidden]
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. 

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at