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
|
use Graph::Directed;
my $g = Graph::Directed->new();
print "1..8\n";
my @scc;
$g->add_edges( qw|a b|);
@scc = sort $g->strongly_connected_graph;
print "ok 1\n" if @scc == 1 && $scc[0] eq 'a-b';
$g->add_edges( qw|b a|);
@scc = sort $g->strongly_connected_graph;
print "ok 2\n" if @scc == 1 && $scc[0] eq 'a+b';
$g = new Graph::Directed;
$g->add_vertex("a");
$g->add_vertex("b");
$g->add_vertex("c");
$g->add_edge("a","c");
$g->add_edge("b","c");
$g->add_edge("c","a");
@scc = $g->strongly_connected_components;
print "ok 3\n" if @scc == 2;
$g = new Graph::Directed;
$g->add_edge(qw(g c));
$g->add_edge(qw(e b));
$g->add_edge(qw(a d));
$g->add_path(qw(b c f));
$g->add_path(qw(c b h));
@scc = $g->strongly_connected_components();
print "ok 4\n" if @scc == 7;
my @sccv = $g->strongly_connected_graph->vertices;
print "ok 5\n" if grep { $_ eq 'b+c' || $_ eq 'c+b' } @sccv;
{
my $g = Graph::Directed->new;
$g->add_edge(qw(b c));
$g->add_edge(qw(b f));
$g->add_edge(qw(b a));
$g->add_edge(qw(b d));
$g->add_edge(qw(b a));
$g->add_edge(qw(b d));
$g->add_edge(qw(c e));
$g->add_edge(qw(e a));
$g->add_edge(qw(e d));
$g->add_edge(qw(f e));
$g->add_edge(qw(f a));
$g->add_edge(qw(a f));
my $s = $g->strongly_connected_graph;
print "ok 6\n" if $s eq "a+e+f-d,b-a+e+f,b-c,b-d,c-a+e+f";
}
{
my $g = new Graph::Directed;
$g->add_vertex( 'a' );
$g->add_vertex( 'b' );
my $gd = $g->strongly_connected_graph;
print "ok 7\n" if $g eq $gd;
print "ok 8\n" if $g eq "a,b";
}
|
