(no subject)

[ciphergoth]

Been looking at Bram's proposal, trying to understand it. Here it is in two forms: a new, object-oriented implementation, and his original one commented.

I could have got either of these completely wrong.

class Person:
def __init__(self, name):
self.name = name
self.arcs = []
self.already_selected = False

def connect(self, people):
self.arcs += [[0, p] for p in people]

def _rank_single(self, passed):
if passed.has_key(self):
return None
passed[self] = True
if not self.already_selected:
return self
arcs = self.arcs[:]
arcs.sort()
for arc in arcs:
result = arc[1]._rank_single(passed)
if result is not None:
arc[0] += 1
return result
return None

def ranks(self):
result = []
while True:
next = self._rank_single({})
if next is None:
return result
next.already_selected = True
result.append(next)



def rank(seed, certs):
already_selected = {}
# numhits augments each arc with a number, initially zero.
# That number represents how often that arc was used to list someone
numhits = {}
for key, value in certs.items():
numhits[key] = [0] * len(value)
def rank_single(current, passed):
# If we've seen this node before on this run of rank_single
if passed.has_key(current):
return None
passed[current] = 1
# if we've got to a node not yet listed, it is the answer.
if not already_selected.has_key(current):
return current
cs = certs.get(current, [])
numhit = numhits.get(current, [])
# sort the arcs leaving this node in increasing numhits order
nexts = [(numhit[i], i, cs[i]) for i in xrange(len(cs))]
nexts.sort()
# Follow each arc in turn looking for someone to list
for garbage, i, next in nexts:
result = rank_single(next, passed)
if result is not None:
numhit[i] += 1
return result
return None
result = []
while True:
next = rank_single(seed, {})
if next is None:
return result
result.append(next)
already_selected[next] = True