| Subject: | strongly_connected_components sometimes gives errornous results for directed graphs |
Using Graph-0.201, on both FreeBSD with perl5.005_03 and RH Linux 7.1 with Perl 5.6.0, strongly_connected_components sometimes groups together vertices that are not strongly connected. For example, using the following little program:
#!/usr/bin/perl -w
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;
print "Components count: ".scalar(@cc)."\n";
I get the output "1" whereas the correct result is "2" (since there is no path from neither c or a to b).