[Pollen-devel] Implantation Condorcet dans Glasnost (2003 y'a 9 ans :))

25 Jun 2012


      class ElectionCondorcet(ElectionMixin, ElectionCondorcetCommon):
    def compute(self):
        virtualServerId = self.getServer().computeVirtualServerId(self.id)
        self.candidateIds = getSetContainedIds(self.candidatesSet)
        voterIds = self.getVoterIds(virtualServerId)

        if not self.canCompute():
            if self.pairwiseMatrix is not None:
                del self.pairwiseMatrix
            if self.ratings is not None:
                del self.ratings
            if self.winnerIds is not None:
                del self.winnerIds
            return

        # Compute the pairwise matrix.
        pairwiseMatrix = {}
        for candidateId in self.candidateIds:
            pairwiseMatrix[candidateId] = row = {}
            for candidateId2 in self.candidateIds:
                row[candidateId2] = 0
        votes = getProxyForServerRole('ballots').getElectionVotes(
                self.voteTokens, voterIds)
        if self.weightingsGradeId is not None:
            weightingsGrade = getProxyForServerRole('grades').getObject(
                    self.weightingsGradeId)
            weightingsById = weightingsGrade.repairMarks(
                    weightingsGrade.marks, voterIds)
            weightings = getProxyForServerRole('ballots'
                    ).getElectionWeightings(self.voteTokens, weightingsById)
        else:
            weightings = None
        for vote in votes:
            if not vote.isAbstention() and not vote.isBlank(self.candidateIds):
                if weightings is not None:
                    weighting = weightings[vote.voterToken]
                else:
                    weighting = 1
                marks = vote.repairMarks(vote.marks, self.candidateIds)
                for candidateId, mark in marks.items():
                    for candidateId2, mark2 in marks.items():
                        if candidateId == candidateId2:
                            continue
                        if mark == mark2:
                            pairwiseMatrix[candidateId][candidateId2] += \
                                weighting / 2.0
                        elif mark < mark2:
                            pairwiseMatrix[candidateId][candidateId2] += \
                                weighting
        self.pairwiseMatrix = pairwiseMatrix

        # Compute the ratings.
        ratings = {}
        for candidateId in self.candidateIds:
            rating = {
                'wins': [],
                'losses': [],
                'ties': [],
                'worstDefeat': 0,
                }
            for candidateId2 in self.candidateIds:
                if candidateId == candidateId2:
                    continue
                delta = pairwiseMatrix[candidateId][candidateId2] \
                        - pairwiseMatrix[candidateId2][candidateId]
                if delta > 0:
                    rating['wins'].append(candidateId2)
                elif delta < 0:
                    rating['losses'].append(candidateId2)
                    if delta < rating['worstDefeat']:
                        rating['worstDefeat'] = -delta
                else:
                    rating['ties'].append(candidateId2)
            ratings[candidateId] = rating
        self.ratings = ratings

        # Compute the winners.
        if self.winnersCount >= len(self.candidateIds):
            self.winnerIds = self.candidateIds[:]
        elif self.winnersCount > 0:
            winnerIds = []
            remaining = self.candidateIds[:]
            for k in range(self.winnersCount):
                if len(winnerIds) >= self.winnersCount:
                    break
                # If there is a candidate with no loss and no tie, then it is a
                # winner.
                for remainingId in remaining:
                    remainingRating = ratings[remainingId]
                    isWinner = 1
                    for lossId in remainingRating['losses']:
                        if lossId not in winnerIds:
                            isWinner = 0
                            break
                    if not isWinner:
                        continue
                    for tieId in remainingRating['ties']:
                        if tieId not in winnerIds:
                            isWinner = 0
                            break
                    if not isWinner:
                        continue
                    winnerIds.append(remainingId)
                    remaining.remove(remainingId)
                    break
                else:
                    # If there is a group of candidates who lose only between
                    # them and if this group is smaller or equal to the
                    # remaining winners to find, add this group to the winners.
                    smallestGroup = remaining[:]
                    for remainingId in remaining:
                        newWinnerIds = []
                        _addToPotentialWinners(remainingId, newWinnerIds,
                                               winnerIds, ratings)
                        if len(newWinnerIds) < len(smallestGroup):
                            smallestGroup = newWinnerIds[:]
                        if len(winnerIds) + len(newWinnerIds) \
                           <= self.winnersCount:
                            for winnerId in newWinnerIds:
                                winnerIds.append(winnerId)
                                remaining.remove(winnerId)
                            break
                    else:
                        # No candidate respects the Condorcet criterion.
                        # Choose the ones with the narrowest worst defeat.
                        narrowestWorstDefeat = None
                        newWinnerIds = None
                        for remainingId in smallestGroup:
                            remainingRating = ratings[remainingId]
                            if narrowestWorstDefeat is None \
                               or remainingRating['worstDefeat'] \
                               < narrowestWorstDefeat:
                                narrowestWorstDefeat = remainingRating[
                                    'worstDefeat']
                                newWinnerIds = [remainingId]
                            elif remainingRating['worstDefeat'] \
                                 == narrowestWorstDefeat:
                                newWinnerIds.append(remainingId)
##                         if len(winnerIds) + len(newWinnerIds) \
##                            <= self.winnersCount:
                        for winnerId in newWinnerIds:
                            winnerIds.append(winnerId)
                            remaining.remove(winnerId)
            self.winnerIds = winnerIds
        elif self.winnerIds is not None:
            del self.winnerIds

        # Update the winners' group, if it exists.
        if self.winnerIds and self.winnersGroupId is not None:
            group = getProxyForServerRole('groups').getObject(
                    self.winnersGroupId)
            group.membersSet = self.winnerIds
            group.nonMembersSet = []
            getProxyForServerRole('groups').modifyObject(group)
register(ElectionCondorcet)


-- 
Benjamin POUSSIN
--------------------
tél: +33 (0) 2 40 50 29 28
email: poussin@codelutin.com
http://www.codelutin.com