Bug #93278 for Graph: SPT_Dijkstra sometimes returns a wrong answer

Sun Feb 23 05:23:27 2014 CHOROBA [...] cpan.org - Ticket created

Subject:

SPT_Dijkstra sometimes returns a wrong answer

SPT_Dijkstra sometimes returns wrong answers. The simplest example I was able to find is attached.

Subject:

graph-bug.pl

#!/usr/bin/perl use warnings; use strict; use Graph::Directed; my %results; for (1 .. 100) { my $g = 'Graph::Directed'->new; $g->add_vertex for 1 .. 5; $g->add_weighted_edge(@$_) for [1, 2, 1], [2, 3, 1], [4, 3, 1], [5, 4, 2]; my $d = $g->SPT_Dijkstra(1); $results{$d->get_vertex_attribute(4, 'weight') || 'undef'}++; } for my $r (keys %results) { print "$r: $results{$r}x\n"; } # 1 -> 2 -> 3 <- 4 <- 5 # 1 1 1 2

Sun Feb 23 05:26:14 2014 CHOROBA [...] cpan.org - Severity Important added

Sun Feb 23 05:26:14 2014 CHOROBA [...] cpan.org - Broken in 0.96 added

Tue Sep 22 18:26:56 2015 JHI [...] cpan.org - Correspondence added

Firstly, the $g->add_vertex for 1 .. 5; is odd. It doesn't do what one may think it does: it doesn't implicitly add the $_ as a vertex to the $g. None of the Graph APIs use the $_. (Well, at least they should not. I hope they don't). Maybe you intended the explicit version $g->add_vertex($_) for 1 .. 5; This $g->add_vertex for 1 .. 5; did do something, but that something was something very different... in short, it tried to add a hypervertex of NO VERTICES to the graph, five times. As it turns out, this esoteric code was wrong, and corrupted the graph (you probably saw a bunch of "unitialized" warnings, that was the corruption). But that corruption didn't actually affect the APSP side of things at all. I fixed now the hypervertex code, and made it harder to accidentally misuse add_vertex (and add_edge) like this. Secondly, the APSP. My fault, not yours: what I hadn't documented properly was that the APSP_Dijkstra attempts to visit all the vertices, not just the ones reachable from the first root. I now documented this. In this particular case, what you wanted would be: my $d = $g->SPT_Dijkstra(first_root => 1, next_root => sub { undef }); Meaning: start from the vertex '1', and when it comes time to select a next root, stop.

Tue Sep 22 18:26:57 2015 The RT System itself - Status changed from 'new' to 'open'

Tue Sep 22 18:26:58 2015 JHI [...] cpan.org - Status changed from 'open' to 'resolved'

Wed Sep 23 04:20:41 2015 CHOROBA [...] cpan.org - Correspondence added

Adding the ($_) didn't change the behaviour. Using first_root and next_root did, though. Thanks. Ch. On Tue Sep 22 18:26:56 2015, JHI wrote: Show quoted text

> Firstly, the > > $g->add_vertex for 1 .. 5; > > is odd. It doesn't do what one may think it does: it doesn't > implicitly add the $_ as a vertex to the $g. None of the Graph APIs > use the $_. (Well, at least they should not. I hope they don't). > Maybe you intended the explicit version > > $g->add_vertex($_) for 1 .. 5; > > This > > $g->add_vertex for 1 .. 5; > > did do something, but that something was something very different... > in short, it tried to add a hypervertex of NO VERTICES to the graph, > five times. As it turns out, this esoteric code was wrong, and > corrupted the graph (you probably saw a bunch of "unitialized" > warnings, that was the corruption). But that corruption didn't > actually affect the APSP side of things at all. I fixed now the > hypervertex code, and made it harder to accidentally misuse add_vertex > (and add_edge) like this. > > Secondly, the APSP. My fault, not yours: what I hadn't documented > properly was that the APSP_Dijkstra attempts to visit all the > vertices, not just the ones reachable from the first root. I now > documented this. In this particular case, what you wanted would be: > > my $d = $g->SPT_Dijkstra(first_root => 1, next_root => sub { undef }); > > Meaning: start from the vertex '1', and when it comes time to select a > next root, stop.