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
|
#!/usr/bin/env perl
use strict;
use warnings;
use Test::More tests => 48;
use Test::Deep;
use Graph::Implicit;
sub is_tree {
my ($graph, $start) = @_;
# a tree is an acyclic graph with E=V-1
my $v = keys %$graph;
my $e = (grep { defined } values %$graph);
VERTEX: for my $vertex (keys %$graph) {
next unless defined $graph->{$vertex};
my %visited;
$visited{$vertex} = 1;
my $iter = $vertex;
while (1) {
$iter = $graph->{$iter};
next VERTEX if !defined $iter;
return 0 if $visited{$iter};
$visited{$iter} = 1;
}
}
return $e == $v - 1;
}
my %graph = (
a => [qw/ b c /],
b => [qw/ d f h/],
c => [qw/a e h/],
d => [qw/a b c d e f g h/],
e => [qw/ c d /],
f => [qw/ /],
g => [qw/ g /],
h => [qw/ f g /],
);
my %reachable = (
a => [qw/a b c d e f g h/],
b => [qw/a b c d e f g h/],
c => [qw/a b c d e f g h/],
d => [qw/a b c d e f g h/],
e => [qw/a b c d e f g h/],
f => [qw/ f /],
g => [qw/ g /],
h => [qw/ f g h/],
);
my $edge_calculator = sub {
my $vertex = shift;
return map { [$_, 1] } @{ $graph{$vertex} };
};
my $graph = Graph::Implicit->new($edge_calculator);
for my $traversal (qw/bfs dfs/) {
for my $vertex (qw/a b c d e f g h/) {
my @visited;
my $tree = $graph->$traversal($vertex, sub { push @visited, $_[1] });
cmp_bag(\@visited, $reachable{$vertex},
"$traversal visits each node exactly once from $vertex");
ok(is_tree($tree),
"$traversal creates a tree from $vertex");
SKIP: {
skip "don't know a good algorithm for this", 1;
no strict 'refs';
ok(&{ "check_$traversal" }($tree),
"$traversal is in the correct order from $vertex");
}
}
}
|