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, /);
|