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/
---------------------------(end of broadcast)---------------------------
TIP 1: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to [EMAIL PROTECTED] so that your
message can get through to the mailing list cleanly
