[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