Re: Transitive closure of a directed graph

On Wed, Nov 02, 2005 at 06:31:56PM +0100, Steinar H. Gunderson wrote:
> I was asked to post this here for any interested parties -- please Cc me on
> any comments/followups as I'm not subscribed to -hackers.

...and here's a version with another algorithm, in PL/Perl (in PL/PgSQL, the
same algorithm is too slow, but PL/Perl does it rather nicely). It's not
as polished code-wise, but on my data set, it's about ten times as fast (!),
and it needs no temporary table:

CREATE FUNCTION transitive_closure() RETURNS SETOF edges AS
$$
sub dfs {
my ($i, $g, $done, $working) = @_;

die "Loop found!" if (defined($working->{$i}));
return if (defined($done->{$i}));

$working->{$i} = 1;

my @nodes = @{$g->{$i}};
my %outgoing = map { $_ => 1 } @nodes;

for my $j (@nodes) {
dfs($j, $g, $done);

for my $k (@{$g->{$j}}) {
$outgoing{$k} = 1;
}
}

$g->{$i} = [ keys %outgoing ];
delete $working->{$i};
$done->{$i} = 1;
}

# fetch all connections belonging to active groups
my %g = ();
my $q = spi_exec_query('SELECT upper,lower FROM edges');

my $numrows = $q->{'processed'};

for my $i (0..$numrows-1) {
my $row = $q->{rows}[$i];

if (!defined($g{$row->{'upper'}})) {
$g{$row->{'upper'}} = [];
}
push @{$g{$row->{'upper'}}}, $row->{'lower'};
}

my %done = ();
my %working = ();

# Repth-first search from all elements
for my $i (keys %g) {
dfs($i, \%g, \%done, \%working);
for my $j (@{$g{$i}}) {
return_next({ upper => $i, lower => $j });
}
}

return;
$$ LANGUAGE plperl;

As with the previous post, I'm not on the list, so please Cc me on any
comments.

/* Steinar */
--
Homepage: http://www.sesse.net/