# Maximal elements algorithms

Versions of Kosaraju's algorithm and the Floyd-Warshall algorithm can each be used to calculate the Schwartz set and the Smith set for an election. When there are N candidates, Kosaraju's algorithm runs in Θ(N2) time with Θ(N2) space, while the Floyd-Warshall algorithm runs in Θ(N3) time with Θ(N2) space.

## Background

The general problem is identifying the members of the maximal elements of an order generated from a binary relation. The order is the natural partial order generated from the preorder that is the transitive-reflexive closure of the relation.

The Schwartz set is associated with the beatpath order on the set of beatpath cycle equivalence classes, which are generated from the Beat relation defined by:

(X,Y) is in Beat if and only if candidate X pair-wise beats candidate Y

The Smith set is associated with the beat-or-tie order on the set of beat-or-tie cycle equivalence classes, which are generated from the Beat-or-tie relation defined by:

(X,Y) is in Beat-or-tie if and only if candidate X pair-wise beats or ties candidate Y

From a graph-theoretic perspective, these algorithms identify which vertices in the maximal strongly connected components of the directed graph of the given relation.

The algorithms are started with a typical approach to summarizing the pair-wise contests between candidates: with a voting matrix such that `Votes[i,j]` is the number of votes for candidate `i` in a pair-wise contest against candidate `j`. The final result of each algorithm is an boolean array, such that `IsInMaximal[i]` is true if and only if candidate `i` is in (one of) the maximal cycle equivalence classes, that is, if and only if the candidate is in the requested set, either the Schwartz set or the Smith Set.

Pseudo-code for the algorithms starts with:

``` function FindMaximalCandidates(number [1..N,1..N] Votes, string Set, string Algorithm)
boolean [1..N,1..N] Relation
// Initialize Relation
for i from 1 to N
for j from 1 to N
Relation[i,j] = true
else
Relation[i,j] = false
boolean [1..N] IsInMaximal

// Call the requested algorithm
if Algorithm == "Kosaraju"
IsInMaximal = KosarajuMaximal(Relation)
if Algorithm == "Floyd-Warshall"
IsInMaximal = FloydWarshallMaximal(Relation)
```

## Kosaraju's algorithm

Kosaraju's algorithm does two depth-first searches (DFS) of the `Relation`. The first search records the search finish times, which are then reversed to be used as a search order for the second search using the transpose of the `Relation`. The second search partitions the candidates into search trees which are actually cycle equivalence classes, and also identifies which candidates are in maximal cycle equivalence classes. While the first and second searches have slightly different requirements, for the purposes of presentation here, the pseudo-code for both searches have been consolidated into a single set of functions.

``` function KosarajuMaximal(boolean [1..N,1..N] Relation)
// SearchOrder[i] == j means candidate j is in position i of the search order
integer [1..N] SearchOrder
for i from 1 to N
SearchOrder[i] = i
StartDFS(Relation, SearchOrder)

//The second DFS is performed with
//   a search order that is the reverse finish order from first search
integer [1..N] SecondSearchOrder
for i from 1 to N
SecondSearchOrder[i] = FinishOrder[N+1 - i]
// ... and with the transposed Relation
boolean [1..N,1..N] RelationTranspose
for i from 1 to N
for j from 1 to N
RelationTranspose[i,j] = Relation[j,i]
StartDFS(RelationTranspose, SecondSearchOrder)

bool [1..N] IsInMaximal
for i from 1 to N
if TreeConnectsToAnyPriorTree[Tree[i]] == true
IsInMaximal[i] = false
else
IsInMaximal[i] = true
return IsInMaximal
```
``` // This function initializes several variables that are globally shared
// between the KosarajuMaximal, StartDFS, and VisitDFS functions
function InitDFS(int N)
integer [1..N] FinishOrder
FinishOrderCnt = 0
boolean [1..N] Visited
integer [1..N] Tree
// The variable TreeConnectsToAnyPriorTree is only relevant in the second DFS.
// Since the second DFS is based on the transpose of the original relation,
//    and in the second search, trees correspond to cycle equivalence classes
//    aka strongly connected components, this is really tracking whether under
//    the original relation this tree is dominated by another one and hence
//    is not maximal.
boolean [1..N] TreeConnectsToAnyPriorTree
TreeCnt = 0
for i from 1 to N
Visited[i] = false
TreeConnectsToAnyPriorTree[i] = false
```
``` function StartDFS(boolean [1..N,1..N] Relation, integer [1..N] SearchOrder)
InitDFS(N)
for srchIx from 1 to N
rootIx = SearchOrder[srchIx]
if Visited[rootIx] == false
// Note:  when translating to zero-based array indexes,
//   reverse the order of the next two lines
TreeCnt = TreeCnt + 1
VisitDFS(Relation, SearchOrder, rootIx)

function VisitDFS(boolean [1..N,1..N] Relation, integer [1..N] SearchOrder, integer visitIx)
Tree[visitIx] = TreeCnt
Visited[visitIx] = true
for srchIx from 1 to N
probeIx = SearchOrder[srchIx]
if Relation[visitIx,probeIx] == true
if Visited[probeIx] == false
VisitDFS(Relation, SearchOrder, probeIx)
else
if Tree[probeIx] < Tree[TreeCnt]
TreeConnectsToAnyPriorTree[TreeCnt] = true
FinishCnt = FinishCnt + 1
FinishOrder[FinishCnt] = visitIx
```

Kosaraju's algorithm always starts the second depth-first search with a tree that is a maximal cycle equivalence class. So if conditions hold that guarantee that the relation-induced partial ordering has exactly one maximal cycle equivalence class, and only the maximal candidates need to be identified, then a specialized version of StartDFS can be used for the second depth-first search that only executes the for loop one time. In that case, the test for whether to set `IsInMaximal[i] = true` is simply whether `Visited[i] == true`.

## Floyd-Warshall algorithm

This version of the Floyd-Warshall algorithm calculates whether there is a path between any two candidates, and then uses the results to see if each candidate is in a maximal cycle equivalence class.

Floyd Algorithm to calculate the Schwartz winners:

``` function Floyd-WarshallMaximal(boolean [1..N,1..N] Relation)
boolean [1..N] IsInMaximal
for i from 1 to N
IsInMaximal[i] = true

// Eventually, HasPath[i,j] == true iff there is a path from i to j
boolean [1..N,1..N] HasPath
// Initialize HasPath for paths of length 1
for i from 1 to N
for j from 1 to N
if i <> j
if Relation[i,j] == true
HasPath[i,j] = true
else
HasPath[i,j] = false

// Expand consideration to paths that have intermediate nodes from 1 to k
for k from 1 to N
for i from 1 to N
if k <> i
for j from 1 to N
if k <> j and i <> j
if HasPath[i,k] == true and HasPath[k,j] == true
HasPath[i,j] = true

// Disqualify as maximal any candidates that have paths to them,
//     but no path back to complete a cycle
for i from 1 to N
for j from 1 to N
if i <> j
if HasPath[j,i] == true and HasPath[i,j] == false
IsInMaximal[i] = false;
return IsInMaximal
```