File: 09scc.t

package info (click to toggle)
libgraph-perl 0.20102-1
  • links: PTS
  • area: main
  • in suites: sarge
  • size: 184 kB
  • ctags: 132
  • sloc: perl: 1,455; makefile: 38
file content (45 lines) | stat: -rw-r--r-- 885 bytes parent folder | download
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
use Graph::Directed;
my $g = Graph::Directed->new();

print "1..5\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;