Graphs and Shortest Distance Between Nodes

arunhorne has asked for the wisdom of the Perl Monks concerning the following question:

Monks...

I find myself needing to create a graph, as in a collection of nodes connected to one another by directed arcs. Despite the availability of suitable libraries in Java, I have no wish to turn away from Perl for this task. I have search CPAN and Google for a library to aid me with the following requirements but find the results to vague. Does anyone know/have any code snippets/modules that would allow me to:

Easily create a graph data structure in memory - i.e. some form of API to add nodes and connect them using directed edges.
Calculate the shortest (arcs are unweighted - i.e. constanst cost to traverse) distance between two arbitrary nodes.

Any suggestions are welcomed - the more ideas the better :)

Best wishes,

____________
Arun

Comment on Graphs and Shortest Distance Between Nodes

Replies are listed 'Best First'.
Re: Graphs and Shortest Distance Between Nodes by kvale (Monsignor) on Jul 18, 2002 at 22:46 UTC
The Graph::Directed module allows one to easily set up directed graphs and contains Dijkstra's algorithm for shortest paths. To understand what is going on under the hood, look at the chapter on graphs in the book "Mastering Algorithms in Perl" published by O'Reilly. -Mark	[reply]
Re: Graphs and Shortest Distance Between Nodes by thelenm (Vicar) on Jul 18, 2002 at 22:39 UTC
There are some code snippets in the O'Reilly book Mastering Algorithms with Perl. All the example programs are available online here. Download "examples.tar.gz" or "examples.zip", and the examples you'll probably want will be in the "ch08" subdirectory. I don't know for sure that you'll find exactly what you need, but hopefully it will put you on the right track. Good luck! -- Mike `-- just,my${.02}`	[reply]
Re: Graphs and Shortest Distance Between Nodes by FoxtrotUniform (Prior) on Jul 18, 2002 at 22:55 UTC
To calculate distances, have a look at all-pairs shortest path algorithms. `-- The hell with paco, vote for Erudil! :wq`	[reply]
Re: Graphs and Shortest Distance Between Nodes by larsen (Parson) on Jul 18, 2002 at 22:59 UTC
Not efficient, but interesting, the tecnique described in this thread: Transitive closure	[reply]