random_graph: edges empty inside random_edge subroutine (changed behaviour of module)

[kester-habermann]

I have some old code that used to work in 0.96 and no longer works in the current version. Either this got broken or I misundertand how this is supposed to work and it only worked for me by accident in the past.

#!/usr/bin/perl

use Graph;

sub d($$$$) {
    my ($g, $u, $v, $p) = @_;

    print("edges: ", scalar $g->edges(), "\n");
    my $result = 1;

    $result = 0 if $g->out_degree($u) > 0;
    $result = 0 if $g->in_degree($v) > 0;

    return $result;
}

my @verts = qw/A B C D E/;

my $g = Graph->random_graph(vertices => \@verts,
    random_edge => \&d,
    edges => scalar @verts,
    random_seed => 1234);

print "$g\n";

Inside of the code passed to random_edge, the graph has no edges. This breaks the checks that follow. The code is supposed to generate a random graph with each node having exactly one incoming and one outgoing edge.

Result using version: 0.9732:

edges: 0
edges: 0
edges: 0
edges: 0
edges: 0
C-A,C-B,C-D,C-E,E-C

C has four outgoing edges. The last version this worked as expected was version: 0.9716:

edges: 0
edges: 1
edges: 1
edges: 1
edges: 1
edges: 2
edges: 2
edges: 2
edges: 2
edges: 2
edges: 2
edges: 3
edges: 3
edges: 3
edges: 3
edges: 4
edges: 4
edges: 4
edges: 4
edges: 4
A-B,B-A,C-D,D-E,E-C

Each vertex has exactly one outgoing and one incoming edge and we see that edges inside the subroutine is not empty. Version 0.9717 shows the same behaviour as the latest version.

[mohawk2]

Thanks for the report! git bisect indicates this got broken in EDIT corrected commit 79a65a0

[mohawk2]

What happened is that for performance reasons, I changed random_graph so it would save up all its edges, and add them at the end. However, your expectation that they would be added as you went along is perfectly reasonable, so I've restored that behaviour. This will be getting released very shortly.