# [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