Graphs and Shortest Distance Between Nodes

[arunhorne]

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

[thelenm]

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}

[kvale]

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

[FoxtrotUniform]

To calculate distances, have a look at all-pairs shortest path algorithms.

--
The hell with paco, vote for Erudil!
:wq

[larsen]

Not efficient, but interesting, the tecnique described in this thread: Transitive closure