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 filtered_graph. Hope that helps, 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.