附件忘加了，在这个邮件里 2011/7/14 jie liu <[email protected]>
>
> 朱岩，出了一些状况. 我造了一个 无向图 的矩阵数据。
> ――――――data――――――――
> 0 0 0 0 0 0 0 0 0 0
> 1 0 0 0 0 0 0 0 0 0
> 1 0 0 0 0 0 0 0 0 0
> 1 1 0 0 0 0 0 0 0 0
> 1 1 1 0 0 0 0 0 0 0
> 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 0 0 0
> 0 0 0 0 0 0 0 0 0 0
> 0 0 0 0 1 0 0 1 0 0
> ――――――――――
> 我用matlab可视化了这个graph，请见附件。
>
> 之后我用你的程序（我把K值改成了K>1）处理这个矩阵，显示的结果是：2，6，9这个节点。这与附件的图矛盾啊，2，6，9实际不是完全连通图啊。怎么回事？我先把结果反馈给大家，同时我也想想
>
> ―――――― perl script――――――――――
>
> use strict;
> use Graph::Clique;
>
> my @edges;
> my %h;
> my $nnz; # num of non-zeros
>
> # build up undirected graph
> open FASTA, "<@ARGV";
> while (<FASTA>) {
> 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 > 1 ; $k-- ) {
> @cliques = getcliques( $k, \@edges );
> if ( $#cliques >= 0 ) {
> last;
> }
> }
>
> print join( "\n", @cliques ), "\n";
>
> ――――――end――――――――――――――――
> 2011/7/14 朱岩 <[email protected]>
>
>> 读文件把while(<DATA>)换成while(<F>)就可以了
>>
>>
>> 在 2011年7月14日 下午4:02，jie liu <[email protected]>写道：
>>
>>> 我刚刚也看到了，还去了作者给的一个地址（http://home.hiwaay.net/~gbacon/perl/clique.html
>>> ）看来一下，很激动！就是我要找的，谢谢大家了哈。
>>>
>>> 但是，我都perl不熟，现在我把矩阵存在txt里了（1代表有边，0代表无边），我怎么把矩阵读进去，然后形成graph，然后用clique呢...朱岩的程序我使了下，没成功。朱岩的程序里我没有看到读入的操作啊（实在是对perl不熟悉...）
>>>
>>>
>>> 2011/7/14 nixin <[email protected]>
>>>
>>>> 果然有现成的库。clique这个关键词没有掌握，搜了好一会全连通图，啥也没搜到。呵呵。
>>>>
>>>> On 7月14日, 下午1时28分, 朱岩 <[email protected]> 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 讨论组”论坛。
>>>> 要向此网上论坛发帖，请发送电子邮件至 [email protected]。
>>>> 要取消订阅此网上论坛，请发送电子邮件至 [email protected]。
>>>> 若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。
>>>>
>>>>
>>>
>>>
>>> --
>>> Best regards,
>>> Liu Jie
>>>
>>> 020-32015312
>>> Guangzhou Institutes of Biomedicine and Health, Chinese Academy of
>>> Sciences
>>> http://www.gibh.cas.cn/
>>>
>>> --
>>> 您收到此邮件是因为您订阅了 Google 网上论坛的“PerlChina Mongers 讨论组”论坛。
>>> 要向此网上论坛发帖，请发送电子邮件至 [email protected]。
>>> 要取消订阅此网上论坛，请发送电子邮件至 [email protected]。
>>> 若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。
>>>
>>
>>
>>
>> --
>> Yours, Yan Zhu
>>
>> Institute of Microbiology, Chinese Academy of Sciences
>>
>> Datun Rd.
>> Chaoyang District
>> Beijing 100101
>> P. R. China
>>
>> --
>> 您收到此邮件是因为您订阅了 Google 网上论坛的“PerlChina Mongers 讨论组”论坛。
>> 要向此网上论坛发帖，请发送电子邮件至 [email protected]。
>> 要取消订阅此网上论坛，请发送电子邮件至 [email protected]。
>> 若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。
>>
>
>
>
> --
> Best regards,
> Liu Jie
>
> 020-32015312
> Guangzhou Institutes of Biomedicine and Health, Chinese Academy of
> Sciences
> http://www.gibh.cas.cn/
>
>
--
Best regards,
Liu Jie
020-32015312
Guangzhou Institutes of Biomedicine and Health, Chinese Academy of Sciences
http://www.gibh.cas.cn/
--
您收到此邮件是因为您订阅了 Google 网上论坛的“PerlChina Mongers 讨论组”论坛。
要向此网上论坛发帖，请发送电子邮件至 [email protected]。
要取消订阅此网上论坛，请发送电子邮件至 [email protected]。
若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。
<<attachment: Graph.jpg>>
