File: 64_mst.t

package info (click to toggle)
libgraph-perl 1%3A0.96-2
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 1,316 kB
  • ctags: 938
  • sloc: perl: 6,094; sh: 8; makefile: 2
file content (73 lines) | stat: -rw-r--r-- 1,860 bytes parent folder | download | duplicates (6)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
use Test::More tests => 22;

use Graph::Undirected;
use Graph::Directed;

my $g0 = Graph::Undirected->new;

$g0->add_weighted_edge(qw(a b 1));
$g0->add_weighted_edge(qw(a c 2));
$g0->add_weighted_edge(qw(a d 1));
$g0->add_weighted_edge(qw(b d 2));
$g0->add_weighted_edge(qw(b e 2));
$g0->add_weighted_edge(qw(c d 2));
$g0->add_weighted_edge(qw(c f 1));
$g0->add_weighted_edge(qw(d e 1));
$g0->add_weighted_edge(qw(d f 1));
$g0->add_weighted_edge(qw(d g 2));
$g0->add_weighted_edge(qw(e g 1));

my $g1 = $g0->deep_copy;

my $g0t = $g0->MST_Kruskal;

ok($g0t->is_undirected);
is($g0t->vertices, $g0->vertices);
is($g0t->edges, $g0->vertices - 1);
is($g0t, "a=b,a=d,c=f,d=e,d=f,e=g");

$g0->add_weighted_edge(qw(c f 3));

my $g0u = $g0->MST_Kruskal;

ok($g0u->is_undirected);
is($g0u->vertices, $g0->vertices);
is($g0u->edges, $g0->vertices - 1);
ok($g0u eq "a=b,a=c,a=d,d=e,d=f,e=g" ||
   $g0u eq "a=b,a=d,c=d,d=e,d=f,e=g" ||
   $g0u eq "a=b,a=c,c=f,d=e,e=g");

my $g1t = $g1->MST_Prim;

ok($g1t->is_undirected);
is($g1t->vertices, $g0->vertices);
is($g1t->edges, $g0->vertices - 1);
ok($g1t eq "a=b,a=d,c=f,d=e,d=f,e=g" ||
   $g1t eq "a=b,a=c,a=d,d=e,d=f,e=g");

my $g1u = $g1->MST_Prim(first_root => "g");

ok($g1u->is_undirected);
is($g1u->vertices, $g0->vertices);
is($g1u->edges, $g0->vertices - 1);
ok($g1u eq "a=b,a=d,c=f,d=e,d=f,e=g" ||
   $g1u eq "a=b,a=c,a=d,d=e,d=f,e=g");

$g1->add_weighted_edge(qw(c f 3));

my $g1v = $g1->MST_Kruskal;

ok($g1v->is_undirected);
is($g1v->vertices, $g1->vertices);
is($g1v->edges, $g1->vertices - 1);
ok($g1v eq "a=b,a=c,a=d,d=e,d=f,e=g" ||
   $g1v eq "a=b,a=d,c=d,d=e,d=f,e=g");

my $g2 = Graph::Directed->new;

eval { $g2->MST_Kruskal };
like($@, qr/Graph::MST_Kruskal: expected undirected graph, got directed, /);

eval { $g2->MST_Prim };
like($@, qr/Graph::MST_Prim: expected undirected graph, got directed, /);