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
...

...ここで、最初の列はソースノードのラベル、2番目の列はターゲットノードのラベル、3番目の列はエッジラベルです。いくつかのデータファイルがあり、それぞれに数万のエッジがあります。

このquick-n-dirtyスクリプトは仕事を成し遂げましたが、持っていれば良かったと思われることがいくつかありました。

  • weakly_connected_componentsメソッドによって返される連結成分は、単にノードラベルの配列であったため、これらのノード間の接続は失われます。
  • メソッドがノードのセットとエッジのセットを返した場合でも、ライブラリは各エッジに関連付けられたラベルまたはデータの保存を許可しないため、不便です。

これらの機能のいずれかまたは両方を含む代替のグラフライブラリはありますか？実装の言語はそれほど重要ではありません。私はC/C ++、Python、Perl、Rなどを受け入れています。

4

1 に答える 1

2

変化する

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

to (エッジごとにゼロまたは 1 つのラベル)

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

または (エッジごとに任意の数のラベル)

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

必要なときにラベルを検索するだけです。

(無向グラフの場合、各ラベルを 2 回追加します。1 回はソース -> ターゲット用、もう 1 回はターゲット -> ソース用です。)

于 2012-11-06T19:11:40.740 に答える