schulze-test.py

#!/usr/bin/env python3

import unittest
import schulze

class SchulzeTestCase(unittest.TestCase):
    def test_electoramaExample1(self):
        preferences = [
            (5, 'ACBED'),
            (5, 'ADECB'),
            (8, 'BEDAC'),
            (3, 'CABED'),
            (7, 'CAEBD'),
            (2, 'CBADE'),
            (7, 'DCEBA'),
            (8, 'EBADC'),
        ]
        self.assertEqual(schulze.schulze(preferences), {'E'})
    def test_electoramaExample2(self):
        preferences = [
            (5, 'ACBD'),
            (2, 'ACDB'),
            (3, 'ADCB'),
            (4, 'BACD'),
            (3, 'CBDA'),
            (3, 'CDBA'),
            (1, 'DACB'),
            (5, 'DBAC'),
            (4, 'DCBA'),
        ]
        self.assertEqual(schulze.schulze(preferences), {'D'})
    def test_electoramaExample3(self):
        preferences = [
            (3, 'ABDEC'),
            (5, 'ADEBC'),
            (1, 'ADECB'),
            (2, 'BADEC'),
            (2, 'BDECA'),
            (4, 'CABDE'),
            (6, 'CBADE'),
            (2, 'DBECA'),
            (5, 'DECAB'),
        ]
        self.assertEqual(schulze.schulze(preferences), {'B'})
    def test_electoramaExample4(self):
        preferences = [
            (3, 'ABCD'),
            (2, 'DABC'),
            (2, 'DBCA'),
            (2, 'CBDA'),
        ]
        self.assertEqual(schulze.schulze(preferences), {'B', 'D'})
    def test_wikipedia(self):
        preferences = [
            (5, 'acbed'),
            (5, 'adecb'),
            (8, 'bedac'),
            (3, 'cabed'),
            (7, 'caebd'),
            (2, 'cbade'),
            (7, 'dceba'),
            (8, 'ebadc')
        ]
        self.assertEqual(schulze.schulze(preferences), {'e'})

if __name__ == '__main__':
    unittest.main()

schulze.py

#!/usr/bin/env python3


def swap(pair):
    return pair[1], pair[0]

def schulze(preferences):
    candidates = set(preferences[0][1])
    d = dict.fromkeys([(a,b) for a in candidates for b in candidates if a != b], 0)

    for (weight, relation) in preferences:
        localWinnings = [(relation[index], localLoser) for index in range(len(relation) - 1) for localLoser in relation[index+1:]]
        for pair in localWinnings:
            d[pair] += weight

    for pair in d:
        if d[pair] <= d[swap(pair)]:
            d[pair] = 0

    for (i, j, k) in [(a,b,c) for a in candidates for b in candidates for c in candidates if a != b and a != c and b != c]:
        indirectPathWidth = min(d[i, j], d[j,k])
        directPathWidth = d[i,k]
        if indirectPathWidth > directPathWidth:
            d[i,k] = indirectPathWidth

    return candidates - {pair[0] for pair in d if d[pair] < d[swap(pair)]}