#!/usr/bin/python2.5
#
# Copyright 2009 the Melange authors.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""Slot allocation logic.
"""
__authors__ = [
'"Sverre Rabbelier" <sverre@rabbelier.nl>',
]
import math
class Error(Exception):
"""Error class for the Allocation module.
"""
pass
class Allocator(object):
"""A simple student slots allocator.
The buildSets method is used to validate the allocation data as well as
construct the sets that the algorithm then uses to distribute the slots.
By separating these steps it is possible to write a different allocation
algorithm but re-use the sets and validation logic.
"""
# I tried to write explicit code that does not require any
# additional comments (with the exception of the set notation for
# the convenience of any mathematicians that happen to read this
# piece of code ;).
def __init__(self, orgs, popularity, max, slots,
max_slots_per_org, min_slots_per_org, algorithm):
"""Initializes the allocator.
Args:
orgs: a list of all the orgs that need to be allocated
popularity: the amount of applications per org
max: the amount of assigned mentors per org
slots: the total amount of available slots
max_slots_per_org: how many slots an org should get at most
min_slots_per_org: how many slots an org should at least get
algorithm: the algorithm to use
"""
self.locked_slots = {}
self.adjusted_slots = {}
self.adjusted_orgs = []
self.locked_orgs = []
self.unlocked_orgs = []
self.unlocked_applications = []
self.slots = slots
self.mentors = {}
self.max_slots_per_org = max_slots_per_org
self.min_slots_per_org = min_slots_per_org
self.orgs = set(orgs)
self.popularity = None
self.total_popularity = None
self.initial_popularity = popularity
self.max = max
self.algorithm = algorithm
def allocate(self, locked_slots):
"""Allocates the slots and returns the result.
Args:
locked_slots: a dict with orgs and the number of slots they get
"""
self.locked_slots = locked_slots
self.buildSets()
if not sum(self.popularity.values()) or not sum(self.max.values()):
return dict([(i, 0) for i in self.orgs])
if self.algorithm == 1:
return self.preprocessingAllocation()
if self.algorithm == 2:
return self.reliableAlgorithm()
return self.iterativeAllocation()
def buildSets(self):
"""Allocates slots with the specified constraints.
"""
popularity = self.initial_popularity.copy()
# set s
locked_slots = self.locked_slots
# set a and b
locked_orgs = set(locked_slots.keys())
# set a' and b'
unlocked_orgs = self.orgs.difference(locked_orgs)
# a+o and b+o should be o
locked_orgs_or_orgs = self.orgs.union(locked_orgs)
total_popularity = sum(popularity.values())
# a+o should be o, testing length is enough though
if len(locked_orgs_or_orgs) != len(self.orgs):
raise Error("Unknown org as locked slot")
self.unlocked_orgs = unlocked_orgs
self.locked_orgs = locked_orgs
self.popularity = popularity
self.total_popularity = total_popularity
def rangeSlots(self, slots, org):
"""Returns the amount of slots for the org within the required bounds.
"""
slots = int(math.floor(float(slots)))
slots = min(slots, self.max_slots_per_org)
slots = max(slots, self.min_slots_per_org)
slots = min(slots, self.max[org])
return slots
def iterativeAllocation(self):
"""A simple iterative algorithm.
"""
adjusted_orgs = self.adjusted_orgs
adjusted_slots = self.adjusted_slots
locked_orgs = self.locked_orgs
locked_slots = self.locked_slots
unallocated_popularity = self.total_popularity - len(locked_slots)
available_slots = self.slots
allocations = {}
for org in self.orgs:
popularity = self.popularity[org]
mentors = self.mentors[org]
if org in locked_orgs:
slots = locked_slots[org]
elif unallocated_popularity:
weight = float(popularity) / float(unallocated_popularity)
slots = int(math.floor(weight*available_slots))
if org in adjusted_orgs:
slots += adjusted_slots[org]
slots = min(slots, self.max_slots_per_org)
slots = min(slots, mentors)
slots = min(slots, available_slots)
allocations[org] = slots
available_slots -= slots
unallocated_popularity -= popularity
return allocations
def preprocessingAllocation(self):
"""An algorithm that pre-processes the input before running as normal.
"""
adjusted_orgs = self.adjusted_orgs
adjusted_slots = self.adjusted_slots
locked_orgs = self.locked_orgs
locked_slots = self.locked_slots
unlocked_orgs = self.unlocked_orgs
total_popularity = self.total_popularity
available_slots = self.slots
allocations = {}
slack = {}
for org in locked_orgs:
popularity = self.popularity[org]
slots = locked_slots[org]
slots = self.rangeSlots(slots, org)
total_popularity -= popularity
available_slots -= slots
allocations[org] = slots
del self.popularity[org]
# adjust the orgs in need of adjusting
for org in adjusted_orgs:
slots = float(adjusted_slots[org])
adjustment = (float(total_popularity)/float(available_slots))*slots
adjustment = int(math.ceil(adjustment))
self.popularity[org] += adjustment
total_popularity += adjustment
# adjust the popularity so that the invariants are always met
for org in unlocked_orgs:
popularity = self.popularity[org]
# mentors = self.mentors[org]
slots = (float(popularity)/float(total_popularity))*available_slots
slots = self.rangeSlots(slots, org)
popularity = (float(total_popularity)/float(available_slots))*slots
self.popularity[org] = popularity
total_popularity = sum(self.popularity.values())
# do the actual calculation
for org in unlocked_orgs:
popularity = self.popularity[org]
raw_slots = (float(popularity)/float(total_popularity))*available_slots
slots = int(math.floor(raw_slots))
slack[org] = raw_slots - slots
allocations[org] = slots
slots_left = available_slots - sum(allocations.values())
# add leftover slots, sorted by slack, decending
for org, slack in sorted(slack.iteritems(),
key=lambda (k, v): v, reverse=True):
if slots_left < 1:
break
current = allocations[org]
slots = self.rangeSlots(current + 1, org)
slots_left += slots - current
allocations[org] = slots
return allocations
def reliableAlgorithm(self):
"""An algorithm that reliable calculates the slots assignments.
"""
# adjusted_orgs = self.adjusted_orgs
# adjusted_slots = self.adjusted_slots
locked_orgs = self.locked_orgs
locked_slots = self.locked_slots
unlocked_orgs = self.unlocked_orgs
total_popularity = self.total_popularity
available_slots = self.slots
allocations = {}
# slack = {}
# take out the easy ones
for org in locked_orgs:
popularity = self.popularity[org]
slots = locked_slots[org]
slots = float(slots)
slots = self.rangeSlots(slots, org)
total_popularity -= popularity
available_slots -= slots
allocations[org] = slots
del self.popularity[org]
total_popularity = sum(self.popularity.values())
# all orgs have been locked, nothing to do
if total_popularity <= 0:
return allocations
pop_per_slot = float(available_slots)/float(total_popularity)
# slack = 0
wanted = {}
# filter out all those that deserve more than their maximum
for org in unlocked_orgs:
popularity = self.popularity[org]
raw_slots = float(popularity)*pop_per_slot
slots = int(math.floor(raw_slots))
slots = self.rangeSlots(slots, org)
max = self.max[org]
if max > slots:
wanted[org] = max - slots
allocations[org] = slots
available_slots = self.slots - sum(allocations.values())
# distribute the slack
while available_slots > 0 and (sum(wanted.values()) > 0):
for org, _ in wanted.iteritems():
available_slots = self.slots - sum(allocations.values())
if available_slots <= 0:
break
if wanted[org] <= 0:
continue
current = allocations[org]
slots = self.rangeSlots(current + 1, org)
extra = current - slots
wanted[org] += extra
allocations[org] = slots
return allocations