[EM] PHP Source now posted
Markus Schulze
markus.schulze at alumni.tu-berlin.de
Wed Jan 14 03:59:01 PST 2004
Dear Eric,
I have just read your implementation of the beatpath method:
http://www.ericgorr.net/condorcet/beatpath/beatpath.txt
Here are some suggestions:
1) Those d[i,j] with d[i,j] <= d[j,i] have to be zeroed out
at the beginning of the calculations.
2) The Floyd algorithm needs only one pass through the
triple-loop.
3) The strength of a pairwise defeat should be measured
secondarily by its margin.
******
Your implementation:
$changed = true;
while ( $changed )
{
$changed = false;
for ( $i = 0; $i < $nOptions; $i++ )
{
for ( $j = 0; $j < $nOptions; $j++ )
{
for ( $k = 0; $k < $nOptions; $k++ )
{
$least = MinValue( $defeats[$i][$j], $defeats[$j][$k] );
if ( $least > $defeats[$i][$k] )
{
$defeats[$i][$k] = $least;
$changed = true;
}
}
}
}
}
for ( $x = 0; $x < $nOptions; $x++ )
{
$winners[$x] = 1;
for ( $y = 0; $y < $nOptions; $y++ )
{
if ( $defeats[$y][$x] > $defeats[$x][$y] )
$winners[$x] = 0;
}
}
******
My implementation:
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
{
p2[i,j] : = d[i,j] - d[j,i] ;
if ( d[i,j] > d[j,i] ) then
p1[i,j] : = d[i,j] ;
if ( d[i,j] <= d[j,i] ) then
p1[i,j] : = 0 ;
}
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
for k : = 1 to N do
if ( i <> k ) then
if ( j <> k ) then
{
s : = p1[j,i] ;
t : = p2[j,i] ;
if ( ( p1[i,k] < s ) or
( ( p1[i,k] = s ) and ( p2[i,k] < t ) ) ) then
{
s : = p1[i,k] ;
t : = p2[i,k] ;
}
if ( ( p1[j,k] < s ) or
( ( p1[j,k] = s ) and ( p2[j,k] < t ) ) ) then
{
p1[j,k] : = s ;
p2[j,k] : = t ;
}
}
for i : = 1 to N do
w[i] : = true ;
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
if ( ( p1[j,i] > p1[i,j] ) or
( ( p1[j,i] = p1[i,j] ) and ( p2[j,i] > p2[i,j] ) ) ) then
w[i] : = false ;
Markus Schulze
More information about the Election-Methods
mailing list