Regression on transitive_closure()

[dod38fr]

Hi

Ian Jackson is reporting in Debian bug #987095 project that the result of transitive_closure() is wrong. It used to be correct in version 0.9704.

I've bisected this issue to commit 3ded9c7 with the following script:

#!/usr/bin/perl -w

use strict;
use Graph::Directed;

my $input = Graph::Directed->new;

foreach my $e (qw(
		  A-C
		  A-NOTA
		  B-A
		  B-C
		  B-NOTA
		)) {
  my ($x,$y) = split /-/, $e;
  $input->add_edge($x,$y); 
}

$input->delete_vertex('C');

print "input: $input\n";

my $output = $input->transitive_closure();
print "output 1: $output\n";

exit (1) unless $output eq 'A-A,A-NOTA,B-A,B-B,B-NOTA,NOTA-NOTA';

foreach my $x (qw(A B C N)) {
  $output->delete_edge($x,$x);
}
print "output 2: $output\n";
exit (1) unless $output eq 'A-NOTA,B-A,B-NOTA,NOTA-NOTA';

All the best

[mohawk2]

Thanks for the report! I've reduced that down to this, which will be in the test suite hereafter:

use strict;
use Test::More;
use Graph::Directed;
my $g = Graph::Directed->new(edges => [
  [qw(A C)], [qw(A NOTA)], [qw(B A)], [qw(B C)], [qw(B NOTA)],
]);
$g->delete_vertex('C');
diag "input: $g\n";
my $tc = $g->transitive_closure;
is $tc, 'A-A,A-NOTA,B-A,B-B,B-NOTA,NOTA-NOTA';
$tc->delete_edge($_,$_) for qw(A B C N);
is $tc, 'A-NOTA,B-A,B-NOTA,NOTA-NOTA';
done_testing;

There are a couple of optimisations that looked inside data structures, which fail if people delete vertices, which they are entitled to do. This should have caught the last of them. As soon as it's fixed, I will follow up here.

[mohawk2]

Released as 0.9721. Please let the downstream know.

[dod38fr]

This fix has been already integrated in Debian package by debian-perl team and will be part of next Debian release.

Thanks a bunch for fixing this so quickly.

All the best