Bug#987095: transitive_closure corrupted results, after vertex deleted
Package: libgraph-perl
Version: 1:0.9716-1
Severity: grave
The attached script, which tests the transitive closure function,
prints this output on testing:
input: A-NOTA,B-A,B-NOTA
Use of uninitialized value $_ in exists at /usr/share/perl5/Graph.pm line 362.
Use of uninitialized value $_ in exists at /usr/share/perl5/Graph.pm line 362.
output: A-A,A-B,B-B,NOTA-NOTA
output: A-B,NOTA-NOTA
The correct output, as seen on buster:
input: A-NOTA,B-A,B-NOTA
output: A-A,A-NOTA,B-A,B-B,B-NOTA,NOTA-NOTA
output: A-NOTA,B-A,B-NOTA,NOTA-NOTA
Empirically, the delete_vertex call is necessary for the repro.
I think this is certainly release critical. I chose "grave" rather
than "serious" since this can produce corrupted output in data
processing situations, where the corrupted output might not be
detected.
In my Debian tally sheet processing program
https://www.chiark.greenend.org.uk/ucgi/~ian/git?p=appendix-a6.git
(`compute`, there), this can produce totally wrong answers for the
winner of votes.
Ian.
#!/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: $output\n";
foreach my $x (qw(A B C N)) {
$output->delete_edge($x,$x);
}
print "output: $output\n";
--
Ian JacksonThese opinions are my own.
Pronouns: they/he. If I emailed you from @fyvzl.net or @evade.org.uk,
that is a private address which bypasses my fierce spamfilter.
Bug#987095: transitive_closure corrupted results, after vertex deleted
Hi On Sat, 17 Apr 2021 12:59:40 +0100 Ian Jackson <> The correct output, as seen on buster: > > input: A-NOTA,B-A,B-NOTA > output: A-A,A-NOTA,B-A,B-B,B-NOTA,NOTA-NOTA > output: A-NOTA,B-A,B-NOTA,NOTA-NOTA I've bisected this regression to: 3ded9c7a25bf190fda5add1a13ed4f9b54082db7 is the first bad commit commit 3ded9c7a25bf190fda5add1a13ed4f9b54082db7 Author: Ed J Date: Mon Dec 14 13:34:32 2020 + all AdjacencyMap store _i as array-refs lib/Graph/AdjacencyMap.pm| 6 +- lib/Graph/AdjacencyMap/Heavy.pm | 10 -- lib/Graph/AdjacencyMap/Light.pm | 9 ++--- lib/Graph/AdjacencyMap/Vertex.pm | 8 ++-- lib/Graph/AdjacencyMatrix.pm | 17 ++-- lib/Graph/BitMatrix.pm | 42 + +-- 6 files changed, 34 insertions(+), 58 deletions(-) All the best
Bug#987095: transitive_closure corrupted results, after vertex deleted
I've created a bug upstream: https://github.com/graphviz-perl/Graph/issues/20 All the best
Bug#987095: transitive_closure corrupted results, after vertex deleted
On Sat, 17 Apr 2021 15:38:32 +0200, Dominique Dumont wrote: > I've created a bug upstream: > https://github.com/graphviz-perl/Graph/issues/20 Thanks. The issue is fixed upstream, and a new 0.9721 has been made. As we have 0.9716 in testing and unstable (and 0.9720 in master) and shouldn't upload all the changes since 0.9716 during the hard freeze, I've created and pushed a "bullseye" branch with a quilt patch for this issue, which contains basically the diff between 0.9720 and 0.9721. The changes also contain a new test based on Ian's reproducer, and all other tests still pass, so I'm quite confident that this should be ok to upload. Still, I'd appreciate if Ian and/or Dominique could take a look at this branch/patch. Cheers, gregor -- .''`. https://info.comodo.priv.at -- Debian Developer https://www.debian.org : :' : OpenPGP fingerprint D1E1 316E 93A7 60A8 104D 85FA BB3A 6801 8649 AA06 `. `' Member VIBE!AT & SPI Inc. -- Supporter Free Software Foundation Europe `- NP: Element of Crime: Moonlight signature.asc Description: Digital Signature
