[EM] Algorithm to Calculate the Schwartz Set

[Bart Ingles]

With only one level of indentation, the scope of the IF and FOR
statements weren't completely clear, although only one interpretation
appeared to make sense.  Is the following restatement accurate?

BEGIN
    for i : = 1 to N do
    {
       for j : = 1 to N do
       {
          if ( i <> j ) then
          {
             if ( d[i,j] > d[j,i] ) then
             {
                p[i,j] : = true ;
             {
             else
             {
                p[i,j] : = false ;
             }
          }
       }
    }
    for i : = 1 to N do
    {
       for j : = 1 to N do
       {
          if ( ( i <> j ) and
               ( p[j,i] = true ) ) then
          {
             for k : = 1 to N do
             {
                if ( ( i <> k ) and
                     ( j <> k ) and
                     ( p[i,k] = true ) ) then
                {
                    p[j,k] := true ;
                }
             }
          }
       }
    }
    for i : = 1 to N do
    {
       Schwartz[i] : = true ;
    }
    for i : = 1 to N do
    {
       for j : = 1 to N do
       {
          if ( ( i <> j ) and
               ( p[j,i] = true ) and
               ( p[i,j] = false ) ) then
          {
              Schwartz[i] : = false ;
          }
       }
    }
END

Bart



Markus Schulze wrote:
> 
> Hallo,
> 
> the Schwartz set can be calculated with the Floyd algorithm
> in a runtime of O(N^3), where N is the number of candidates.
> It cannot be said frequently enough that the order of the
> indices in the triple-loop of the Floyd algorithm is _not_
> irrelevant.
> 
> Input:  d[i,j] with i <> j is the number of voters who strictly
>         prefer candidate i to candidate j.
> 
> Output: "Schwartz[i] : = true" means that candidate i is
>         a Schwartz winner.
>         "Schwartz[i] : = false" means that candidate i is not
>         a Schwartz winner.
> 
>    for i : = 1 to N do
>    for j : = 1 to N do
>    if ( i <> j ) then
>       {
>        if ( d[i,j] > d[j,i] ) then
>        p[i,j] : = true ;
>        if ( d[i,j] <= d[j,i] ) then
>        p[i,j] : = false ;
>       }
> 
>    for i : = 1 to N do
>    for j : = 1 to N do
>    if ( i <> j ) then
>    if ( p[j,i] = true ) then
>    for k : = 1 to N do
>    if ( i <> k ) then
>    if ( j <> k ) then
>    if ( p[i,k] = true ) then
>    p[j,k] : = true ;
> 
>    for i : = 1 to N do
>    Schwartz[i] : = true ;
> 
>    for i : = 1 to N do
>    for j : = 1 to N do
>    if ( i <> j ) then
>    if ( p[j,i] = true ) then
>    if ( p[i,j] = false ) then
>    Schwartz[i] : = false ;
> 
> Markus Schulze
> ----
> Election-methods mailing list - see http://electorama.com/em for list info