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,lowerFROM 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/
