app/soc/logic/allocations.py

   1 #!/usr/bin/python2.5
   2 #
   3 # Copyright 2009 the Melange authors.
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #   http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17 """Slot allocation logic.
  18 """
  19
  20 __authors__ = [
  21   '"Sverre Rabbelier" <sverre@rabbelier.nl>',
  22   ]
  23
  24
  25 import math
  26
  27
  28 class Error(Exception):
  29   """Error class for the Allocation module.
  30   """
  31
  32   pass
  33
  34
  35 class Allocator(object):
  36   """A simple student slots allocator.
  37
  38   The buildSets method is used to validate the allocation data as well as
  39   construct the sets that the algorithm then uses to distribute the slots.
  40   By separating these steps it is possible to write a different allocation
  41   algorithm but re-use the sets and validation logic.
  42   """
  43
  44   # I tried to write explicit code that does not require any
  45   # additional comments (with the exception of the set notation for
  46   # the convenience of any mathematicians that happen to read this
  47   # piece of code ;).
  48
  49   def __init__(self, orgs, popularity, max, slots,
  50                max_slots_per_org, min_slots_per_org, algorithm):
  51     """Initializes the allocator.
  52
  53     Args:
  54       orgs: a list of all the orgs that need to be allocated
  55       popularity: the amount of applications per org
  56       max: the amount of assigned mentors per org
  57       slots: the total amount of available slots
  58       max_slots_per_org: how many slots an org should get at most
  59       min_slots_per_org: how many slots an org should at least get
  60       algorithm: the algorithm to use
  61     """
  62
  63     self.locked_slots = {}
  64     self.adjusted_slots = {}
  65     self.adjusted_orgs = []
  66     self.locked_orgs = []
  67     self.unlocked_orgs = []
  68     self.unlocked_applications = []
  69     self.slots = slots
  70     self.max_slots_per_org = max_slots_per_org
  71     self.min_slots_per_org = min_slots_per_org
  72     self.orgs = set(orgs)
  73     self.popularity = None
  74     self.total_popularity = None
  75     self.initial_popularity = popularity
  76     self.max = max
  77     self.algorithm = algorithm
  78
  79   def allocate(self, locked_slots):
  80     """Allocates the slots and returns the result.
  81
  82     Args:
  83       locked_slots: a dict with orgs and the number of slots they get
  84     """
  85
  86     self.locked_slots = locked_slots
  87
  88     self.buildSets()
  89
  90     if not sum(self.popularity.values()) or not sum(self.max.values()):
  91       return dict([(i, 0) for i in self.orgs])
  92
  93     if self.algorithm == 1:
  94       return self.preprocessingAllocation()
  95
  96     return self.iterativeAllocation()
  97
  98   def buildSets(self):
  99     """Allocates slots with the specified constraints.
 100     """
 101
 102     popularity = self.initial_popularity.copy()
 103
 104     # set s
 105     locked_slots = self.locked_slots
 106
 107     # set a and b
 108     locked_orgs = set(locked_slots.keys())
 109
 110     # set a' and b'
 111     unlocked_orgs = self.orgs.difference(locked_orgs)
 112
 113     # a+o and b+o should be o
 114     locked_orgs_or_orgs = self.orgs.union(locked_orgs)
 115
 116     total_popularity = sum(popularity.values())
 117
 118     # a+o should be o, testing length is enough though
 119     if len(locked_orgs_or_orgs) != len(self.orgs):
 120       raise Error("Unknown org as locked slot")
 121
 122     self.unlocked_orgs = unlocked_orgs
 123     self.locked_orgs = locked_orgs
 124     self.popularity = popularity
 125     self.total_popularity = total_popularity
 126
 127   def rangeSlots(self, slots, org):
 128     """Returns the amount of slots for the org within the required bounds.
 129     """
 130
 131     slots = int(math.floor(float(slots)))
 132     slots = min(slots, self.max_slots_per_org)
 133     slots = max(slots, self.min_slots_per_org)
 134     slots = min(slots, self.max[org])
 135
 136     return slots
 137
 138   def iterativeAllocation(self):
 139     """A simple iterative algorithm.
 140     """
 141
 142     adjusted_orgs = self.adjusted_orgs
 143     adjusted_slots = self.adjusted_slots
 144     locked_orgs = self.locked_orgs
 145     locked_slots = self.locked_slots
 146
 147     unallocated_popularity = self.total_popularity - len(locked_slots)
 148
 149     available_slots = self.slots
 150     allocations = {}
 151
 152     for org in self.orgs:
 153       popularity = self.popularity[org]
 154       mentors = self.mentors[org]
 155
 156       if org in locked_orgs:
 157         slots = locked_slots[org]
 158       elif unallocated_popularity:
 159         weight = float(popularity) / float(unallocated_popularity)
 160         slots = int(math.floor(weight*available_slots))
 161
 162       if org in adjusted_orgs:
 163         slots += adjusted_slots[org]
 164
 165       slots = min(slots, self.max_slots_per_org)
 166       slots = min(slots, mentors)
 167       slots = min(slots, available_slots)
 168
 169       allocations[org] = slots
 170       available_slots -= slots
 171       unallocated_popularity -= popularity
 172
 173     return allocations
 174
 175   def preprocessingAllocation(self):
 176     """An algorithm that pre-processes the input before running as normal.
 177     """
 178
 179     adjusted_orgs = self.adjusted_orgs
 180     adjusted_slots = self.adjusted_slots
 181     locked_orgs = self.locked_orgs
 182     locked_slots = self.locked_slots
 183     unlocked_orgs = self.unlocked_orgs
 184     total_popularity = self.total_popularity
 185
 186     available_slots = self.slots
 187     allocations = {}
 188     slack = {}
 189
 190     for org in locked_orgs:
 191       popularity = self.popularity[org]
 192       slots = locked_slots[org]
 193       slots = self.rangeSlots(slots, org)
 194
 195       total_popularity -= popularity
 196       available_slots -= slots
 197       allocations[org] = slots
 198       del self.popularity[org]
 199
 200     # adjust the orgs in need of adjusting
 201     for org in adjusted_orgs:
 202       slots = float(adjusted_slots[org])
 203
 204       adjustment = (float(total_popularity)/float(available_slots))*slots
 205       adjustment = int(math.ceil(adjustment))
 206       self.popularity[org] += adjustment
 207       total_popularity += adjustment
 208
 209     # adjust the popularity so that the invariants are always met
 210     for org in unlocked_orgs:
 211       popularity = self.popularity[org]
 212       # mentors = self.mentors[org]
 213
 214       slots = (float(popularity)/float(total_popularity))*available_slots
 215       slots = self.rangeSlots(slots, org)
 216
 217       popularity = (float(total_popularity)/float(available_slots))*slots
 218
 219       self.popularity[org] = popularity
 220
 221     total_popularity = sum(self.popularity.values())
 222
 223     # do the actual calculation
 224     for org in unlocked_orgs:
 225       popularity = self.popularity[org]
 226       raw_slots = (float(popularity)/float(total_popularity))*available_slots
 227       slots = int(math.floor(raw_slots))
 228
 229       slack[org] = raw_slots - slots
 230       allocations[org] = slots
 231
 232     slots_left = available_slots - sum(allocations.values())
 233
 234     # add leftover slots, sorted by slack, decending
 235     for org, slack in sorted(slack.iteritems(),
 236         key=lambda (k, v): v, reverse=True):
 237       if slots_left < 1:
 238         break
 239
 240       current = allocations[org]
 241       slots = self.rangeSlots(current + 1, org)
 242
 243       slots_left += slots - current
 244       allocations[org] = slots
 245
 246     return allocations