[EM] Re: Election-methods Digest, Vol 12, Issue 10

[Andrew Myers]

> From: Gervase Lam <gervase.lam at group.force9.co.uk>
> Subject: [EM] MAM algorithm?
> To: election-methods-electorama.com at electorama.com
> Message-ID: <20050605025337.A54359F1A5 at sara.dreamhost.com>
> 
> 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