Re: [PerlChina] Re: DNA,DG值。

图论解法：

找最大完全连通子图，可以用Graph::Clique，当然应该还有更好的算法；

这里只举了个10x10的小例子

用非零数的平方根作为最大子图顶点数的上限

use strict;

use Graph::Clique;

my @edges;

my %h;

my $nnz;  # num of non-zeros

# build up undirected graph

while(<DATA>){

my $i = $.+1;

 my @a = split(/ /,$_);

 for my $j (0..$#a){

  if ($a[$j]){

   $nnz++;

my $e = $i <= $j ? $i.",".$j : $j.",".$i;

$h{$e}++;

  }

 }

}

foreach my $key (sort keys %h){

my @a = split(/\,/, $key);

push @edges, [@a];

}

# find maximal clique

my @cliques;

for (my $k=int(sqrt($nnz)); $k>3; $k--){

 @cliques = getcliques($k,\@edges);

 if ($#cliques >=0){

  last;

 }

}

print join("\n", @cliques),"\n";

__DATA__

0 0 1 0 1 0 0 0 0 0

0 1 1 0 0 0 0 0 0 0

1 1 1 0 1 0 0 1 0 0

1 1 1 0 0 0 0 0 0 0

1 1 1 0 1 0 0 1 0 1

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 1 0 1 0 0 1 0 1

0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 1 0 0

--
您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。
要向此网上论坛发帖，请发送电子邮件至 perlchina@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 perlchina+unsubscribe@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。