[PerlChina] Re: DNA,DG值。

果然有现成的库。clique这个关键词没有掌握，搜了好一会全连通图，啥也没搜到。呵呵。

On 7月14日, 下午1时28分, 朱岩 <riye...@gmail.com> wrote:
> 图论解法：
>
> 找最大完全连通子图，可以用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 访问此网上论坛。