# 63_scc.t   [plain text]

```use Test::More tests => 57;

use Graph;
use Graph::Undirected;

my \$g0 = Graph->new;

my @c0 = \$g0->strongly_connected_components;

is(@c0, 2);
@c0 = sort { @\$a <=> @\$b } @c0;
is("@{\$c0[0]}", 'c');
is("@{[sort @{\$c0[1]}]}", 'a b');

is(\$g0->strongly_connected_graph, "a+b-c");

ok(!\$g0->is_strongly_connected);

my \$g1 = Graph->new;

\$g1->add_path(qw(f f b a c b));
\$g1->add_path(qw(c e d e g h g));

my @c1 = \$g1->strongly_connected_components;

is(@c1, 4);
@c1 = sort { @\$a <=> @\$b } @c1;
is("@{[sort @{\$c1[0]}]}", 'f');
is("@{[sort @{\$c1[1]}]}", 'd e');
is("@{[sort @{\$c1[2]}]}", 'g h');
is("@{[sort @{\$c1[3]}]}", 'a b c');

my \$g1s = \$g1->strongly_connected_graph;

is(\$g1s, "a+b+c-d+e,d+e-g+h,f-a+b+c,f-d+e");

is("@{[sort @{\$g1s->get_vertex_attribute('a+b+c', 'subvertices')}]}",
"a b c");
is("@{[sort @{\$g1s->get_vertex_attribute('d+e', 'subvertices')}]}",
"d e");
is("@{[sort @{\$g1s->get_vertex_attribute('f', 'subvertices')}]}",
"f");
is("@{[sort @{\$g1s->get_vertex_attribute('g+h', 'subvertices')}]}",
"g h");
is(\$g1s->get_vertex_attribute('h+g', 'subvertices'), undef);

ok(!\$g1->is_strongly_connected);

my \$g2 = Graph->new;

my @c2 = \$g2->strongly_connected_components;

is(@c2, 1);
@c2 = sort { @\$a <=> @\$b } @c2;
is("@{[sort @{\$c2[0]}]}", 'a b c d e');

is(\$g2->strongly_connected_graph, "a+b+c+d+e");

ok(\$g2->is_strongly_connected);

my \$g3 = Graph->new;

my @c3 = \$g3->strongly_connected_components;

is(@c3, 6);
@c3 = sort { @\$a <=> @\$b || "@\$a" cmp "@\$b" } @c3;
is("@{[sort @{\$c3[0]}]}", 'a');
is("@{[sort @{\$c3[1]}]}", 'b');
is("@{[sort @{\$c3[2]}]}", 'c');
is("@{[sort @{\$c3[3]}]}", 'd');
is("@{[sort @{\$c3[4]}]}", 'e');
is("@{[sort @{\$c3[5]}]}", 'f');

is(\$g3->strongly_connected_graph, "a-b,b-c,d,e,f");

ok(!\$g3->is_strongly_connected);

is(\$g3->strongly_connected_graph(hypervertex =>
sub { my @v = sort @{ \$_[0] };
"(" . join(",", @v) . ")" } ),
"(a,d)-(b),(b)-(c),(e,f)");

is(\$g3->strongly_connected_graph(super_component =>
sub { my @v = sort @_;
"(" . join("|", @v) . ")" } ),
"(a|d)-(b),(b)-(c),(e|f)");

eval '\$g3->strongly_connected_graph(foobar => 1)';
like(\$@, qr/Graph::strongly_connected_graph: Unknown option: 'foobar' /);

# Example from Sedgewick Algorithms in C Third Edition 19.1 Figure 19.8 (p 150)
my \$g4 = Graph->new;
\$g4->add_edges([ 0,  1], [ 0,  5], [0,  6]);
\$g4->add_edges([ 2,  0], [ 2,  3]);
\$g4->add_edges([ 3,  2], [ 3,  5]);
\$g4->add_edges([ 4,  2], [ 4,  3], [4, 11]);
\$g4->add_edges([ 6,  4], [ 6,  9]);
\$g4->add_edges([ 7,  6], [ 7,  8]);
\$g4->add_edges([ 8,  7], [ 8,  9]);
\$g4->add_edges([ 9, 10], [ 9, 11]);
my @g4s = sort { \$a->[0] <=> \$b->[0] } map { [sort { \$a <=> \$b} @\$_] } \$g4->strongly_connected_components;
is(@g4s, 4);
is("@{\$g4s[0]}", "0 2 3 4 5 6");
is("@{\$g4s[1]}", "1");
is("@{\$g4s[2]}", "7 8");
is("@{\$g4s[3]}", "9 10 11 12");

ok( \$g4->same_strongly_connected_components('0',  '2'));
ok( \$g4->same_strongly_connected_components('0',  '6'));
ok(!\$g4->same_strongly_connected_components('0',  '1'));
ok( \$g4->same_strongly_connected_components('7',  '8'));
ok( \$g4->same_strongly_connected_components('9', '10'));
ok( \$g4->same_strongly_connected_components('9', '12'));
ok(!\$g4->same_strongly_connected_components('0',  '7'));
ok(!\$g4->same_strongly_connected_components('0',  '9'));

is( \$g4->strongly_connected_component_by_vertex('0'),
\$g4->strongly_connected_component_by_vertex('2'));

isnt(\$g4->strongly_connected_component_by_vertex('0'),
\$g4->strongly_connected_component_by_vertex('1'));

my @s = \$g4->strongly_connected_components();
is( "@{[ sort \$g4->strongly_connected_component_by_index(0) ]}",
"@{[ sort @{ \$s[0] } ]}" );
is( "@{[ sort \$g4->strongly_connected_component_by_index(1) ]}",
"@{[ sort @{ \$s[1] } ]}" );
is( "@{[ sort \$g4->strongly_connected_component_by_index(2) ]}",
"@{[ sort @{ \$s[2] } ]}" );
is( "@{[ sort \$g4->strongly_connected_component_by_index(3) ]}",
"@{[ sort @{ \$s[3] } ]}" );
is( \$g4->strongly_connected_component_by_index(4),
undef );

my \$g5 = Graph::Undirected->new;

eval '\$g5->strongly_connected_components';
like(\$@, qr/Graph::strongly_connected_components: expected directed graph, got undirected/);

eval '\$g5->strongly_connected_component_by_vertex';
like(\$@, qr/Graph::strongly_connected_component_by_vertex: expected directed graph, got undirected/);

eval '\$g5->strongly_connected_component_by_index';
like(\$@, qr/Graph::strongly_connected_component_by_index: expected directed graph, got undirected/);

{
# http://rt.cpan.org/NoAuth/Bug.html?id=1193
use Graph::Directed;

\$graph = new Graph::Directed;