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.mentors = {}
  71     self.max_slots_per_org = max_slots_per_org
  72     self.min_slots_per_org = min_slots_per_org
  73     self.orgs = set(orgs)
  74     self.popularity = None
  75     self.total_popularity = None
  76     self.initial_popularity = popularity
  77     self.max = max
  78     self.algorithm = algorithm
  79
  80   def allocate(self, locked_slots):
  81     """Allocates the slots and returns the result.
  82
  83     Args:
  84       locked_slots: a dict with orgs and the number of slots they get
  85     """
  86
  87     self.locked_slots = locked_slots
  88
  89     self.buildSets()
  90
  91     if not sum(self.popularity.values()) or not sum(self.max.values()):
  92       return dict([(i, 0) for i in self.orgs])
  93
  94     if self.algorithm == 1:
  95       return self.preprocessingAllocation()
  96
  97     if self.algorithm == 2:
  98       return self.reliableAlgorithm()
  99
 100     return self.iterativeAllocation()
 101
 102   def buildSets(self):
 103     """Allocates slots with the specified constraints.
 104     """
 105
 106     popularity = self.initial_popularity.copy()
 107
 108     # set s
 109     locked_slots = self.locked_slots
 110
 111     # set a and b
 112     locked_orgs = set(locked_slots.keys())
 113
 114     # set a' and b'
 115     unlocked_orgs = self.orgs.difference(locked_orgs)
 116
 117     # a+o and b+o should be o
 118     locked_orgs_or_orgs = self.orgs.union(locked_orgs)
 119
 120     total_popularity = sum(popularity.values())
 121
 122     # a+o should be o, testing length is enough though
 123     if len(locked_orgs_or_orgs) != len(self.orgs):
 124       raise Error("Unknown org as locked slot")
 125
 126     self.unlocked_orgs = unlocked_orgs
 127     self.locked_orgs = locked_orgs
 128     self.popularity = popularity
 129     self.total_popularity = total_popularity
 130
 131   def rangeSlots(self, slots, org):
 132     """Returns the amount of slots for the org within the required bounds.
 133     """
 134
 135     slots = int(math.floor(float(slots)))
 136     slots = min(slots, self.max_slots_per_org)
 137     slots = max(slots, self.min_slots_per_org)
 138     slots = min(slots, self.max[org])
 139
 140     return slots
 141
 142   def iterativeAllocation(self):
 143     """A simple iterative algorithm.
 144     """
 145
 146     adjusted_orgs = self.adjusted_orgs
 147     adjusted_slots = self.adjusted_slots
 148     locked_orgs = self.locked_orgs
 149     locked_slots = self.locked_slots
 150
 151     unallocated_popularity = self.total_popularity - len(locked_slots)
 152
 153     available_slots = self.slots
 154     allocations = {}
 155
 156     for org in self.orgs:
 157       popularity = self.popularity[org]
 158       mentors = self.mentors[org]
 159
 160       if org in locked_orgs:
 161         slots = locked_slots[org]
 162       elif unallocated_popularity:
 163         weight = float(popularity) / float(unallocated_popularity)
 164         slots = int(math.floor(weight*available_slots))
 165
 166       if org in adjusted_orgs:
 167         slots += adjusted_slots[org]
 168
 169       slots = min(slots, self.max_slots_per_org)
 170       slots = min(slots, mentors)
 171       slots = min(slots, available_slots)
 172
 173       allocations[org] = slots
 174       available_slots -= slots
 175       unallocated_popularity -= popularity
 176
 177     return allocations
 178
 179   def preprocessingAllocation(self):
 180     """An algorithm that pre-processes the input before running as normal.
 181     """
 182
 183     adjusted_orgs = self.adjusted_orgs
 184     adjusted_slots = self.adjusted_slots
 185     locked_orgs = self.locked_orgs
 186     locked_slots = self.locked_slots
 187     unlocked_orgs = self.unlocked_orgs
 188     total_popularity = self.total_popularity
 189
 190     available_slots = self.slots
 191     allocations = {}
 192     slack = {}
 193
 194     for org in locked_orgs:
 195       popularity = self.popularity[org]
 196       slots = locked_slots[org]
 197       slots = self.rangeSlots(slots, org)
 198
 199       total_popularity -= popularity
 200       available_slots -= slots
 201       allocations[org] = slots
 202       del self.popularity[org]
 203
 204     # adjust the orgs in need of adjusting
 205     for org in adjusted_orgs:
 206       slots = float(adjusted_slots[org])
 207
 208       adjustment = (float(total_popularity)/float(available_slots))*slots
 209       adjustment = int(math.ceil(adjustment))
 210       self.popularity[org] += adjustment
 211       total_popularity += adjustment
 212
 213     # adjust the popularity so that the invariants are always met
 214     for org in unlocked_orgs:
 215       popularity = self.popularity[org]
 216       # mentors = self.mentors[org]
 217
 218       slots = (float(popularity)/float(total_popularity))*available_slots
 219       slots = self.rangeSlots(slots, org)
 220
 221       popularity = (float(total_popularity)/float(available_slots))*slots
 222
 223       self.popularity[org] = popularity
 224
 225     total_popularity = sum(self.popularity.values())
 226
 227     # do the actual calculation
 228     for org in unlocked_orgs:
 229       popularity = self.popularity[org]
 230       raw_slots = (float(popularity)/float(total_popularity))*available_slots
 231       slots = int(math.floor(raw_slots))
 232
 233       slack[org] = raw_slots - slots
 234       allocations[org] = slots
 235
 236     slots_left = available_slots - sum(allocations.values())
 237
 238     # add leftover slots, sorted by slack, decending
 239     for org, slack in sorted(slack.iteritems(),
 240         key=lambda (k, v): v, reverse=True):
 241       if slots_left < 1:
 242         break
 243
 244       current = allocations[org]
 245       slots = self.rangeSlots(current + 1, org)
 246
 247       slots_left += slots - current
 248       allocations[org] = slots
 249
 250     return allocations
 251
 252   def reliableAlgorithm(self):
 253     """An algorithm that reliable calculates the slots assignments.
 254     """
 255
 256     # adjusted_orgs = self.adjusted_orgs
 257     # adjusted_slots = self.adjusted_slots
 258     locked_orgs = self.locked_orgs
 259     locked_slots = self.locked_slots
 260     unlocked_orgs = self.unlocked_orgs
 261     total_popularity = self.total_popularity
 262
 263     available_slots = self.slots
 264     allocations = {}
 265     # slack = {}
 266
 267     # take out the easy ones
 268     for org in locked_orgs:
 269       popularity = self.popularity[org]
 270       slots = locked_slots[org]
 271       slots = float(slots)
 272       slots = self.rangeSlots(slots, org)
 273
 274       total_popularity -= popularity
 275       available_slots -= slots
 276       allocations[org] = slots
 277       del self.popularity[org]
 278
 279     total_popularity = sum(self.popularity.values())
 280
 281     # all orgs have been locked, nothing to do
 282     if total_popularity <= 0:
 283       return allocations
 284
 285     pop_per_slot = float(available_slots)/float(total_popularity)
 286
 287     # slack = 0
 288     wanted = {}
 289
 290     # filter out all those that deserve more than their maximum
 291     for org in unlocked_orgs:
 292       popularity = self.popularity[org]
 293       raw_slots = float(popularity)*pop_per_slot
 294       slots = int(math.floor(raw_slots))
 295       slots = self.rangeSlots(slots, org)
 296       max = self.max[org]
 297
 298       if max > slots:
 299         wanted[org] = max - slots
 300
 301       allocations[org] = slots
 302
 303     available_slots = self.slots - sum(allocations.values())
 304
 305     # distribute the slack
 306     while available_slots > 0 and (sum(wanted.values()) > 0):
 307       for org, _ in wanted.iteritems():
 308         available_slots = self.slots - sum(allocations.values())
 309         if available_slots <= 0:
 310           break
 311
 312         if wanted[org] <= 0:
 313           continue
 314
 315         current = allocations[org]
 316         slots = self.rangeSlots(current + 1, org)
 317         extra = current - slots
 318
 319         wanted[org] += extra
 320         allocations[org] = slots
 321
 322     return allocations