1package govote 2 3import ( 4 "errors" 5) 6 7// SchulzePoll is a Condorcet poll using the Schulze method 8type SchulzePoll struct { 9 candidates []string 10 ballots [][]string 11 PP map[CPair]int // pairwise preferences 12 SP map[CPair]int // strongest path 13} 14 15// Evaluate poll; returns list of winners as slice of candidate names and 16// ranking as slice of CScores 17func (p *SchulzePoll) Evaluate() ([]string, []CScore, error) { 18 if p.candidates == nil || p.ballots == nil { 19 return []string{}, []CScore{}, errors.New("no candidates or no ballots") 20 } 21 winners, ranks := p.getWinners() 22 return winners, ranks, nil 23} 24 25// AddBallot submits a ballot to the poll, returns true on success, false on failure 26func (p *SchulzePoll) AddBallot(ballot []string) (ok bool) { 27 removeDuplicates(&ballot) 28 for _, bv := range ballot { 29 ok = false; for _, cv := range p.candidates { 30 if cv == bv { ok = true; break } 31 } 32 if !ok { return } // false / bad candidate 33 } 34 if !ok { return } // false / empty ballot 35 p.ballots = append(p.ballots, ballot) 36 return // true 37} 38 39// Returns the rank of a candidate on a specific ballot or -1 if unranked 40func (p SchulzePoll) getBallotRank(idx, i int) int { 41 ballot := p.ballots[idx] 42 for k, v := range ballot { 43 if v == p.candidates[i] { return k } 44 } 45 return -1 46} 47 48// Returns number of voters strictly prefering candidate i to j 49func (p SchulzePoll) comparePref(i, j int) (ct int) { 50 for k := range p.ballots { 51 ri, rj := p.getBallotRank(k, i), p.getBallotRank(k, j) 52 if ri == -1 || rj == -1 { continue } 53 if ri < rj { ct++ } 54 } 55 return 56} 57 58func (p *SchulzePoll) getWinners() (winners []string, ranks []CScore) { 59 p.PP = make(map[CPair]int) // pairwise preferences 60 p.SP = make(map[CPair]int) // strongest paths 61 won := make([]bool, len(p.candidates)) // winners marked true by index 62 ct := len(p.candidates) // number of candidates 63 tally := make(map[string]int) // scores keyed by candidate name 64 65 // compute pairwise preferences 66 for i := 0; i < ct; i++ { 67 for j := 0; j < ct; j++ { 68 if i != j { 69 p.PP[CPair{i, j}] = p.comparePref(i, j) 70 } 71 } 72 } 73 74 // compute strongest paths 75 for i := 0; i < ct; i++ { 76 for j := 0; j < ct; j++ { 77 if i != j { 78 if p.PP[CPair{i, j}] > p.PP[CPair{j, i}] { 79 p.SP[CPair{i, j}] = p.PP[CPair{i, j}] 80 } else { 81 p.SP[CPair{i, j}] = 0 82 } 83 } 84 } 85 } 86 87 for i := 0; i < ct; i++ { 88 for j := 0; j < ct; j++ { 89 if i != j { 90 for k := 0; k < ct; k++ { 91 if i != k && j != k { 92 var( 93 SPjk = p.SP[CPair{j, k}] 94 SPji = p.SP[CPair{j, i}] 95 SPik = p.SP[CPair{i, k}] 96 ) 97 p.SP[CPair{j, k}] = max(SPjk, min(SPji, SPik)) 98 } 99 } 100 } 101 } 102 } 103 104 // mark winners 105 for i := 0; i < ct; i++ { 106 won[i] = true 107 } 108 109 for i := 0; i < ct; i++ { 110 for j := 0; j < ct; j++ { 111 if i != j { 112 if p.SP[CPair{j, i}] > p.SP[CPair{i, j}] { 113 won[i] = false 114 tally[p.candidates[i]] += 0 // creates entry for Condorcet loser 115 } else { 116 tally[p.candidates[i]]++ // candidate preferred to x others 117 } 118 } 119 } 120 } 121 ranks = sortScoresDesc(tally) 122 123 // make winners list 124 for i := 0; i < ct; i++ { 125 if won[i] == true { 126 winners = append(winners, p.candidates[i]) 127 } 128 } 129 return 130} 131