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[edit | edit source]
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.
- (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
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 if (Set == "Schwartz" and Votes[i,j] > Votes[j,i]) or (Set == "Smith" and i <> j and Votes[i,j] >= Votes[j,i]) 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[edit | edit source]
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[edit | edit source]
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
References[edit | edit source]
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms, first edition, MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
- Section 23.5, "Strongly connected components", pp. 488–493;
- Section 26.2, "The Floyd-Warshall algorithm", pp. 558–565;