Bug #43969 for Graph: ->all_successors() stringifies blessed nodes

On Mon Mar 09 12:58:50 2009, PERLER wrote: Show quoted text
No, it's not as simple as that. _all_successors uses ye olde trick "implement a set of objects as a hash with the stringified objects as keys and the objects themselves as values". But it clobbers the values in two places :( Patch attached (fixes all_successors and all_predecessors). I've also attached a simple test program. Output showing the problem: vertices: $VAR1 = [ \'e', \'b', \'d', \'a', \'c' ]; successors of SCALAR(0xf9d548): $VAR1 = [ \'b', \'d' ]; all_successors of SCALAR(0xf9d548): $VAR1 = [ 'SCALAR(0xf9d500)', 'SCALAR(0xf9d470)', 'SCALAR(0xf9d4a0)', 'SCALAR(0xf9d4d0)' ]; Correct would have been: vertices: $VAR1 = [ \'e', \'b', \'d', \'a', \'c' ]; successors of SCALAR(0xfa2410): $VAR1 = [ \'b', \'d' ]; all_successors of SCALAR(0xfa2410): $VAR1 = [ \'d', \'c', \'b', \'e' ];

use strict; use warnings; use Graph; use Data::Dumper; my $g = Graph->new(directed => 1, refvertexed => 1); my ($a, $b, $c, $d, $e) = \qw(a b c d e); $g->add_path($a, $b, $c); $g->add_path($a, $d, $e); print "vertices: ", Dumper([$g->vertices]); print "successors of $a: ", Dumper([$g->successors($a)]); print "all_successors of $a: ", Dumper([$g->all_successors($a)]);

--- Graph-0.91-ORIG/lib/Graph.pm 2009-10-30 19:10:27.000000000 +0100 +++ Graph-0.91/lib/Graph.pm 2009-10-30 19:08:04.000000000 +0100 @@ -874,10 +874,9 @@ while (keys %todo) { my @todo = keys %todo; for my $t (@todo) { - delete $todo{$t}; - $seen{$t} = $t; + $seen{$t} = delete $todo{$t}; for my $s ($g->successors($t)) { - $todo{$s}++ unless exists $seen{$s}; + $todo{$s} = $s unless exists $seen{$s}; } } } @@ -900,10 +899,9 @@ while (keys %todo) { my @todo = keys %todo; for my $t (@todo) { - delete $todo{$t}; - $seen{$t} = $t; + $seen{$t} = delete $todo{$t}; for my $p ($g->predecessors($t)) { - $todo{$p}++ unless exists $seen{$p}; + $todo{$p} = $p unless exists $seen{$p}; } } }

On Fri Oct 30 14:34:18 2009, RSCHUPP wrote: Show quoted text
Rats, I missed another place where an object and its stringification get mixed up. The previous patch fixed my example, but only because of the following erroneous behaviour: If you have a refvertexed graph $g containing a vertex $foo that stringifies as "FOO(0x123)" then both $g->successors($foo) $g->successors("FOO(0x123)") return the actual successors of $foo (the latter should return the empty list since the string "FOO(0x123)" is not a vertex of $g). But this doesn't hold if $foo has stringification overloaded such that "$foo" ne "FOO(0x123)".

diff -ubr Graph-0.91/lib/Graph.pm Graph-0.91-rt43969/lib/Graph.pm --- Graph-0.91/lib/Graph.pm 2009-01-17 02:53:59.000000000 +0100 +++ Graph-0.91-rt43969/lib/Graph.pm 2009-11-02 09:09:19.000000000 +0100 @@ -872,12 +872,11 @@ @todo{@init} = @init; my %seen; while (keys %todo) { - my @todo = keys %todo; + my @todo = values %todo; for my $t (@todo) { - delete $todo{$t}; - $seen{$t} = $t; + $seen{$t} = delete $todo{$t}; for my $s ($g->successors($t)) { - $todo{$s}++ unless exists $seen{$s}; + $todo{$s} = $s unless exists $seen{$s}; } } } @@ -898,12 +897,11 @@ @todo{@init} = @init; my %seen; while (keys %todo) { - my @todo = keys %todo; + my @todo = values %todo; for my $t (@todo) { - delete $todo{$t}; - $seen{$t} = $t; + $seen{$t} = delete $todo{$t}; for my $p ($g->predecessors($t)) { - $todo{$p}++ unless exists $seen{$p}; + $todo{$p} = $p unless exists $seen{$p}; } } }