Paul Crowley (ciphergoth) wrote in trustmetrics,
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
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

  • 12 comments