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

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 12 comments