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

ttyuren

UID: 39330
帖子: 36
积分: 82
在线时间: 1 小时

1^# ttyuren 发表于 2007-11-14 23:23

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

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

[Copy to clipboard] [ - ]

CODE:

#!/usr/bin/perl -w

use Graph::Directed;

my $g = Graph::Directed->new();

$g->add_path(qw(a b c d));
$g->add_path(qw(a f e d));
$g->add_edges(qw(a c a d b e f d));

my $sssp = $g->SSSP_Dijkstra("a");

foreach my $u ($sssp->vertices) {
print "$u ", $sssp->get_attribute("weight", $u),
" ", @{$sssp->get_attribute("path", $u)}, "\n"
}

运行结果错误提示：

[Copy to clipboard] [ - ]

CODE:

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

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

[Copy to clipboard] [ - ]

CODE:

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

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

ttyuren

UID: 39330
帖子: 36
积分: 82
在线时间: 1 小时

2^# ttyuren 发表于 2007-11-14 23:31

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

Lonki

UID: 21498
帖子: 1
积分: 2
在线时间: 10 分钟

3^# Lonki 发表于 2007-11-15 01:22

旧版本的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了.

ttyuren

UID: 39330
帖子: 36
积分: 82
在线时间: 1 小时

4^# ttyuren 发表于 2007-11-15 10:52

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

ttyuren

UID: 39330
帖子: 36
积分: 82
在线时间: 1 小时

5^# ttyuren 发表于 2007-11-15 11:13

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

Lonki

UID: 21498
帖子: 1
积分: 2
在线时间: 10 分钟

6^# Lonki 发表于 2007-11-15 20:49

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

http://strawberryperl.com/

看到可爱的大草莓了吗

它号称11月出5.10

alexru

UID: 11790
帖子: 75
积分: 172
在线时间: 8 小时

7^# alexru 发表于 2007-11-16 00:55

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

biginner

UID: 33871
帖子: 1
积分: 2
在线时间: 10 分钟

8^# 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 compatible?

---learning---

Lonki

UID: 21498
帖子: 1
积分: 2
在线时间: 10 分钟

9^# Lonki 发表于 2007-11-16 11:19

QUOTE:

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

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

Lonki

UID: 21498
帖子: 1
积分: 2
在线时间: 10 分钟

10^# Lonki 发表于 2007-11-16 11:21

QUOTE:

原帖由 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的最新版.