[Bioperl-l] OT: Breadth-First Search Algorithm - BFS

[Jeremy Semeiks]

On Fri, Feb 27, 2004 at 04:55:21AM +0100, Jose M? Glez Izarzugaza wrote:
> Hello everyone,
> 
> I'm working with a graph and I need to calculate the values of C and L, to do so, I need an algorithm to calculate the distance to the other elements. 
> 
> A good one is BFS algorithm. 
> 
> I tried to write the script (the algorithm itself) in Perl but I got absolutely lost. 
> 
> Can anyone help me?

Hi Jose,

One solution is to use the Graph::Base module on CPAN:

http://search.cpan.org/~jhi/Graph-0.20101/lib/Graph/Base.pm

This module includes Dijkstra's shortest path algorithm. Dijkstra's is
a few times slower than BFS, but you shouldn't see a difference for
small graphs. (And in my experience, if you're trying to run search
algorithms on large graphs, Perl is too slow anyway -- consider
something like the C++ Boost Graph library instead.)

HTH,
Jeremy