Editing Smith set (section)

==Computing the Smith set==
The Smith set can be calculated with the [[Floyd–Warshall algorithm]] in time '''[[Big O notation|Θ]]'''(''n''<sup>3</sup>) or [[Kosaraju's algorithm]] in time '''Θ'''(''n''<sup>2</sup>).

=== Detailed algorithm ===
The algorithm can be presented in detail through an example. Suppose that the results matrix is as follows:
{| class="wikitable"
! {{diagonal split header|1st|2nd}}
!A
!B
!C
!D
!E
!F
!G
| rowspan="8" |
!score
|-
!A
|–
|1
|1
|1
|1
|1
|0
|5
|-
!B
|0
|–
|0
|0
|1
|0
|0
|1
|-
!C
|0
|1
|–
|0
|1
|{{sfrac|1|2}}
|1
|3{{sfrac|1|2}}
|-
!D
|0
|1
|1
|–
|1
|1
|1
|5
|-
!E
|0
|0
|0
|0
|–
|0
|0
|0
|-
!F
|0
|1
|{{sfrac|1|2}}
|0
|1
|–
|0
|2{{sfrac|1|2}}
|-
!G
|1
|1
|0
|0
|1
|1
|–
|4
|}
Here an entry in the main table is 1 if the first candidate was preferred to the second by more voters than preferred the second to the first; 0 if the opposite relation holds; and {{sfrac|1|2}} if there is a tie. The final column gives the Copeland score of the first candidate.

The algorithm to compute the Smith set is agglomerative: it starts with the Copeland set, which is guaranteed to be a subset of it but will often be smaller, and adds items until no more are needed. The first step is to sort the candidates according to score:
{| class="wikitable"
! {{diagonal split header|1st|2nd}}
!A
!D
!G
!C
!F
!B
!E
| rowspan="8" |
!score
|-
!A
|–
|1
|0
|1
|1
|1
|1
|5
|-
!D
|0
|–
|1
|1
|1
|1
|1
|5
|-
!G
|1
|0
|–
|0
|1
|1
|1
|4
|-
!C
|0
|0
|1
|–
|{{sfrac|1|2}}
|1
|1
|3{{sfrac|1|2}}
|-
!F
|0
|0
|0
|{{sfrac|1|2}}
|–
|1
|1
|2{{sfrac|1|2}}
|-
!B
|0
|0
|0
|0
|0
|–
|1
|1
|-
!E
|0
|0
|0
|0
|0
|0
|–
|0
|}
We look at the highest score (5) and consider the candidates (Copeland winners) whose score is at least this high, i.e. {A,D}. These certainly belong to the Smith set, and any candidates whom they do not defeat will need to be added. To find undefeated candidates we look at the cells in the table below the top-left 2×2 square containing {A,D} (this square is shown with a broken border): the cells in question are shaded yellow in the table. We need to find the lowest (positionally) non-zero entry among these cells, which is the cell in the G row. All candidates as far down as this row, and any lower rows with the same score, need to be added to the set, which expands to {A,D,G}.

Now we look at any new cells which need to be considered, which are those below the top-left square containing {A,D,G}, but excluding those in the first two columns which we have already accounted for. The cells which need attention are shaded pale blue. As before we locate the positionally lowest non-zero entry among the new cells, adding all rows down to it, and all rows with the same score as it, to the expanded set, which now comprises {A,D,G,C}.

We repeat the operation for the new cells below the four members which are known to belong to the Smith set. These are shaded pink, and allow us to find any candidates not defeated by any of {A,D,G,C}. Again there is just one, F, whom we add to the set.

The cells which come into consideration are shaded pale green, and since all their entries are zero we do not need to add any new candidates to the set, which is therefore fixed as {A,D,G,C,F}. And by noticing that all the entries in the black box are zero, we have confirmation that all the candidates above it defeat all the candidates within it.

The following C function illustrates the algorithm by returning the cardinality of the Smith set for a given doubled results matrix ''r'' and array ''s'' of doubled Copeland scores. There are ''n'' candidates; ''r<sub>i&nbsp;j</sub>'' is 2 if more voters prefer ''i'' to ''j'' than prefer ''j'' to ''i'', 1 if the numbers are equal, and 0 if more voters prefer ''j'' to ''i'' than prefer ''i'' to ''j''&nbsp;; ''s<sub>i</sub>'' is the sum over ''j'' of the ''r<sub>i&nbsp;j&nbsp;</sub>''. The candidates are assumed to be sorted in decreasing order of Copeland score.<syntaxhighlight lang="c">
int smithset(int ** r, int * s, int n) {
  int row, col, lhs, rhs;
  for (rhs = 1, lhs = 0; lhs < rhs; lhs = rhs, rhs = row + 1) {
    for (; rhs < n && s[rhs] == s[rhs - 1]; rhs++); /* this line optional */
    for (col = rhs, row = n; col == rhs && row >= rhs; row--)
      for (col = lhs; col < rhs && r[row - 1][col] == 0; col++);
  }
  return lhs;
}
</syntaxhighlight>