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