Maximal elements algorithms

From Electowiki
Jump to: navigation, search

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.

Contents

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
             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

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

References

See Also