Graph modules

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

Hi Monks, there are a number of perl modules for dealing with graph data structures. I'm trying to calculate 'betweeness centrality' for a particular node P where this is the number of times shortest paths between pairs of nodes on a graph pass through node P.

I've tried to do this by calculating shortest paths between each pair of nodes but have the problem that implementations of shortest path algorithms will only return one path where there are multiple shortest paths of the same length. I need all shortest paths. For example, there a 2 paths of length 3 between nodes 1 and 4 in the following example. This bit of code will only return one of them

#!/usr/bin/perl

use Boost::Graph;
my $graph = new Boost::Graph(directed=>0, net_name=>'Graph Name', net_
+id=>1000); 

# add edges
$graph->add_edge(node1=>'1', node2=>'2', weight=>1);
$graph->add_edge(node1=>'1', node2=>'3', weight=>1);
$graph->add_edge(node1=>'2', node2=>'4', weight=>1);
$graph->add_edge(node1=>'3', node2=>'4', weight=>1);
my $path=$graph->dijkstra_shortest_path('1','4');

print @{$path->{'path'}};
[download]

Anybody have any ideas?
cheers
ps
Algorithm::SocialNetwork won't install so this is out.

Comment on Graph modules Download Code

Replies are listed 'Best First'.
Re: Graph modules by tachyon-II (Chaplain) on May 19, 2008 at 13:22 UTC
Implementing the Dijkstra algorithm is pretty trivial but Paths::Graph has a shortest path method that returns all the shortest paths if there are more than one. It is pure Perl so installation should not be an issue.	[reply]
Re^2: Graph modules by lima1 (Curate) on May 19, 2008 at 14:01 UTC
Yes, but there are better solutions than running N * (N+1)/2 times Dijkstra... (google All Pairs Shortest Path Problem) I'd be surprised if the boost library has not all the required functionality. It's probably just not implemented in the Perl bindings. If speed is an issue, then maybe just use the C++ library directly, otherwise try Graph as suggested. Update: Graph also returns a "random" shortest graph.	[reply]
Re^3: Graph modules by nosbod (Scribe) on May 19, 2008 at 15:34 UTC
Indeed, boost does have an implementation of the betweenness centrality measure. It might be the way to go, thanks	[reply]
Re^2: Graph modules by nosbod (Scribe) on May 19, 2008 at 15:44 UTC
ahha, thanks	[reply]
Re: Graph modules by psini (Deacon) on May 19, 2008 at 11:08 UTC
It is not difficult find all shortest paths between two nodes in a grapd, it is lengthy. As far as I know the only way to do so is to check all the (open) paths from node1 of length=minimun length and choose those arriving to node2 I have no idea if there is an implementation in some graph library but if you have the description of your graph in a data structure I daresay it is quite easy to implement Rule One: Do not act incautiously when confronting a little bald wrinkly smiling man.	[reply]
Re: Graph modules by dragonchild (Archbishop) on May 19, 2008 at 13:38 UTC
What's wrong with Graph? My criteria for good software: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply]
Re^2: Graph modules by nosbod (Scribe) on May 19, 2008 at 15:31 UTC
It only returns one of the paths if multiple paths of the same length exist	[reply]
Re^3: Graph modules by dragonchild (Archbishop) on May 19, 2008 at 16:06 UTC
So patch it. The code is easy to understand and the maintainer is very open to patches. My criteria for good software: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply]