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
|
#!/usr/bin/env perl
use strict;
use warnings;
use Test::More tests => 24;
use Test::Deep;
use Graph::Implicit;
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 $edge_calculator = sub {
my $vertex = shift;
return map { [$_, 1] } @{ $graph{$vertex} };
};
my $graph = Graph::Implicit->new($edge_calculator);
for my $vertex (qw/a b c d e f g h/) {
cmp_bag([$graph->neighbors($vertex)], $graph{$vertex},
"calculated neighbors of $vertex correctly");
}
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/],
);
for my $vertex (qw/a b c d e f g h/) {
cmp_bag([$graph->vertices($vertex)], $reachable{$vertex},
"calculated vertices reachable from $vertex correctly");
}
my %edges = (
a => [map { [a => $_] } @{ $graph{a} }],
b => [map { [b => $_] } @{ $graph{b} }],
c => [map { [c => $_] } @{ $graph{c} }],
d => [map { [d => $_] } @{ $graph{d} }],
e => [map { [e => $_] } @{ $graph{e} }],
f => [map { [f => $_] } @{ $graph{f} }],
g => [map { [g => $_] } @{ $graph{g} }],
h => [map { [h => $_] } @{ $graph{h} }],
);
my %reachable_edges = (
a => [map { @{ $edges{$_} } } @{ $reachable{a} }],
b => [map { @{ $edges{$_} } } @{ $reachable{b} }],
c => [map { @{ $edges{$_} } } @{ $reachable{c} }],
d => [map { @{ $edges{$_} } } @{ $reachable{d} }],
e => [map { @{ $edges{$_} } } @{ $reachable{e} }],
f => [map { @{ $edges{$_} } } @{ $reachable{f} }],
g => [map { @{ $edges{$_} } } @{ $reachable{g} }],
h => [map { @{ $edges{$_} } } @{ $reachable{h} }],
);
for my $vertex (qw/a b c d e f g h/) {
cmp_bag([$graph->edges($vertex)], $reachable_edges{$vertex},
"calculated edges reachable from $vertex correctly");
}
|
