> From: Gervase Lam <[EMAIL PROTECTED]>
> Subject: [EM] MAM algorithm?
> To: election-methods-electorama.com@electorama.com
> Message-ID: <[EMAIL PROTECTED]>
>
> While finding a way to group candidates together in order to find a
> multi-winner pairwise method, I came up with a technique/algorithm for MAM
> that partially works. It should also work for Ranked Pairs, considering
> that RP is almost the same as RP.
You'll find code that does exactly what you describe as part of the
CIVS source code. It's the function TransitiveClosure in the file rp.pm.
Full code below.
# TransitiveClosure(m, winner, loser, n) adds the preference
# for winner over loser to the nxn matrix m and computes the
# transitive closure (in m). If this creates any new cycles,
# returns 1, otherwise 0. It uses a worklist algorithm because
# that is faster than a full Floyd-Warshall when the matrix
# is already pretty much done.
sub TransitiveClosure {
my ($mref, my $winner, my $loser, my $num_choices) = @_;
my $cycle = 0;
my @worklist = ([($winner, $loser)]);
while ($#worklist >= 0) {
my $pair = shift @worklist;
my $winner = $pair->[0];
my $loser = $pair->[1];
if ($mref->[$winner][$loser]) { next; }
$mref->[$winner][$loser] = 1;
if ($winner == $loser) { $cycle = 1; next; }
for (my $j = 0; $j < $num_choices; $j++) {
if ($mref->[$loser][$j]) {
push @worklist, [($winner, $j)];
}
if ($mref->[$j][$winner]) {
push @worklist, [($j, $loser)];
}
}
}
return $cycle;
}
-- Andrew
----
Election-methods mailing list - see http://electorama.com/em for list info
