[求助]Graph_module中的SSSP_Dijkstra算法出问题

ttyuren

最近写了一个程序用到了Graph这个module， 调用SSSP_Dijkstra这个method的时候总是出问题，请大家帮忙看一下

1. 
   
2. 
   
3. #!/usr/bin/perl -w
   
4. 
   
5. 
   
6. use Graph::Directed;
   
7. 
   
8. my $g = Graph::Directed->new();
   
9. 
   
10. $g->add_path(qw(a b c d));
    
11. $g->add_path(qw(a f e d));
    
12. $g->add_edges(qw(a c a d b e f d));
    
13. 
    
14. my $sssp = $g->SSSP_Dijkstra("a");
    
15. 
    
16. foreach my $u ($sssp->vertices) {
    
17.         print "$u ", $sssp->get_attribute("weight", $u),
    
18.                 " ", @{$sssp->get_attribute("path", $u)}, "\n"
    
19. }
    
20. 
    

复制代码

运行结果错误提示：

1. 
   
2. Not an ARRAY reference at C:/Perl/site/lib/Heap/Elem.pm line 31.
   

复制代码

然后我去找这个Elem.pm文件看了一下，第三十一行是：

1. 
   
2. sub heap {                                                  #line 30th
   
3.     @_ > 1 ? ($_[0][1] = $_[1]) : $_[0][1];   #line 31st
   
4. }                                                                  #line 32nd
   
5. 
   

复制代码

请问可能会是哪里出问题呢？会不会是Graph这个模块的bug？谢谢大家！

[ 本帖最后由 ttyuren 于 2007-11-14 23:29 编辑 ]

ttyuren

我起初怀疑是不是因为这个graph是unweighted的，但是在Graph模块的文档里面说了 “If no weight is defined for an edge, 1 (one) is assumed.”啊，糊涂了...

Lonki

旧版本的BUG吧


在 ActivePerl 5.8.8 Graph 0.79下测试(CPAN最新是0.84)

my $g = Graph::Directed->new;
$g->add_path(qw(a b)); ### a-->b
$g->set_edge_weight('a', 'b', 2);
# my $sssp = $g->SSSP_Dijkstra('a'); ### 同LZ的错误提示.
my $sssp = $g->SSSP_Dijkstra('b'); ### OK


刚才又在Strawberry Perl 5.8.8中用Graph 0.84测试, 一切OK... 看来是旧版本的BUG了.

[ 本帖最后由 Lonki 于 2007-11-15 01:57 编辑 ]

ttyuren

我是在windows下用activeperl测试的，ppm安装的最高版本是graph 0.80。我可以从cpan下载graph 0.84解压后makefile么？

ttyuren

ok了，谢谢Lonki，真佩服你。
的确是老版本问题。ppm可安装的版本还没有更新。我直接下载解压makefile后考过去的，不知道windows下还有没有更好的模块安装方法？

Lonki

Windows下你不想手工下载再make的话, 就用Strawberry Perl吧, 另一个Perl发行部,
100% CPAN兼容, 非常不错.

http://strawberryperl.com/

看到可爱的大草莓了吗

它号称11月出5.10

alexru

http://strawberryperl.com/
链接是广告，不会期为赚钱忽悠的吧？

biginner

I updated Graph using CPAN, but it still gor:
"get_attribute: not a compat02 graph at /usr/lib/perl5/site_perl/5.8.0/Graph.pm line 2380.  "

Does this mean the attribute still not back compatible?

---learning---

Lonki

原帖由 alexru 于 2007-11-16 00:55 发表
http://strawberryperl.com/
链接是广告，不会期为赚钱忽悠的吧？

兄弟, 哪儿有广告, 告诉我?

Lonki

原帖由 biginner 于 2007-11-16 11:09 发表
I updated Graph using CPAN, but it still gor:
"get_attribute: not a compat02 graph at /usr/lib/perl5/site_perl/5.8.0/Graph.pm line 2380.  "

Does this mean the attribute still not back compati ...

文档有说, GET_ATTRIBUTE是老的了, 不推荐使用.

另外, 尽量使用5.8.6以上的PERL, 以及CPAN上MODULE的最新版.