use Test::More tests => 57; use Graph; use Graph::Undirected; my \$g0 = Graph->new; \$g0->add_cycle(qw(a b)); \$g0->add_edge(qw(b c)); 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)); \$g1->add_path(qw(f d)); 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; \$g2->add_cycle(qw(a b c)); \$g2->add_cycle(qw(a d e)); 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; \$g3->add_path(qw(a b c)); \$g3->add_vertices(qw(d e f)); 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); \$g3->add_cycle('d', 'a'); \$g3->add_cycle('e', 'f'); 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([ 5, 4]); \$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]); \$g4->add_edges([10, 12]); \$g4->add_edges([11, 12]); \$g4->add_edges([12, 9]); 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; \$graph->add_vertex("a"); \$graph->add_vertex("b"); \$graph->add_vertex("c"); \$graph->add_edge("a","c"); \$graph->add_edge("b","c"); \$graph->add_edge("c","a"); @cc = \$graph->strongly_connected_components; is(@cc, 2); }