1

今天早上我偶然发现了Perl 的图形库。我曾经编写一个快速程序来查找有向图中的所有（弱）连接组件。这是程序。

use strict;
use Graph;
use Data::Dumper;

my $g = Graph->new();
foreach my $file(@ARGV)
{
  open(my $IN, "<", $file) or die("cannot open '$file'");
  while(my $line = <$IN>)
  {
    chomp($line);
    my($source, $target, $edge_label) = split(/\t/, $line);
    $g->add_edge($source, $target);
  }
  close($IN);
}

my @clusters = $g->weakly_connected_components();
print Dumper(\@clusters);

...输入数据文件看起来像这样。

n1  n2  some_data_encoded_in_a_label
n1  n3  some_data_encoded_in_a_label
n4  n5  some_data_encoded_in_a_label
...

...其中第一列是源节点标签，第二列是目标节点标签，第三列是边缘标签。我有几个数据文件，每个文件都有数万条边。

这个 quick-n-dirty 脚本完成了工作，但有一些东西本来很好。

  • weakly_connected_components方法返回的连接组件只是节点标签的数组，因此这些节点之间的连接丢失了。
  • 即使该方法返回一组节点和一组边，该库也不允许存储与每条边相关的标签或数据，这是不方便的。

是否有任何替代图形库包含这些功能中的一个或两个？实现的语言不是很重要——我对 C/C++、Python、Perl、R 等开放。

4

1 回答 1

2

改变

 $g->add_edge($source, $target);

到（每条边零个或一个标签）

 $g->add_edge($source, $target);
 $labels{$source}{$target} = $edge_label;

或（每条边任意数量的标签）

 $g->add_edge($source, $target);
 push @{ $labels{$source}{$target} }, $edge_label;

只需在需要时查找标签。

（对于无向图，每个标签添加两次，一次用于源->目标，一次用于目标->源。）

于 2012-11-06T19:11:40.740 回答