trustprotocol.py

trustmap = """
alastairparvin -> indy_johar jimmygreer jonisteiner martinluff nick_diaconou tav thruflo tsalfield
chrmoment -> alastairparvin joe tav tsalfield
indy_johar -> alastairparvin jonisteiner nick_diaconou tav
jimmygreer -> alastairparvin nick_diaconou
jonisteiner -> indy_johar lyntonpepper nick_diaconou tav thruflo
lyntonpepper -> alastairparvin jonisteiner nick_diaconou
martinluff -> alastairparvin nick_diaconou
micrypt -> alastairparvin tav tsalfield
nick_diaconou -> alastairparvin jimmygreer jonisteiner lyntonpepper martinluff tav thruflo tsalfield
tav -> alastairparvin chrmoment indy_johar jonisteiner martinluff micrypt nick_diaconou thruflo tsalfield
thruflo -> alastairparvin indy_johar nick_diaconou
tsalfield -> alastairparvin chrmoment indy_johar nick_diaconou tav thruflo
""".strip()

certs = {}
fills = {}

for line in trustmap.split('\n'):
    sline = line.strip().split()
    if len(sline) < 3:
        print "SKIPPING:", line
        continue
    user = sline[0]
    cur = certs[user] = []
    for tgt in sline[2:]:
        if tgt not in certs:
            certs[tgt] = []
        if tgt == user:
            continue
        cur.append(tgt)

for user in certs:
    fills[user] = {0: 0.0}

certs["-"] = ['alastairparvin', 'nick_diaconou', 'tav', 'thruflo']
fills["-"] = {0: 100.0 + (100.0 / len(certs["-"]))}

seen = set()
stack = [("-", 0)]; to_see = stack.append

def calc((user, level), seen=seen, fills=fills, certs=certs, keepback_factor=0.1, to_see=to_see):
    seen.add(user)
    tgts = certs[user]
    if not tgts:
        return
    amount = 0.0
    for lev, val in fills[user].items():
        if lev <= level:
            amount += val
    keepback = amount / (len(tgts) + 1)
    issue = keepback
    for tgt in tgts:
        levelup = level + 1
        if levelup not in fills[tgt]:
            fills[tgt][levelup] = issue
        else:
            fills[tgt][levelup] += issue
        if tgt not in seen:
            to_see((tgt, level+1))
            seen.add(tgt)
    fills[user][level] = keepback

while stack:
    calc(stack.pop(0))

del fills["-"]

totals = {}

for user in fills:
    totals[user] = sum(fills[user].values())

for user in sorted(totals, key=lambda k: totals[k], reverse=True):
    print "%20s\t%.2f" % (user, totals[user])