make_propagator.py

#!/usr/bin/env python3.1

import sys;
import functools;
import operator;
import fractions;

def readAdjlist(file):
	adjlist = []
	with open(file) as f:
		for line in f:
			nodes = [int(n) for n in line.split()]
			if nodes[0] >= len(adjlist):
				adjlist.extend([[]] * (nodes[0]-len(adjlist)--1))
			adjlist[nodes[0]] = nodes[1:]
	return adjlist

def getBitset(neis):
	return functools.reduce(operator.or_, (1 << n for n in neis), 0)

def bitCount(int_type):
	count = 0
	while int_type:
		int_type &= int_type - 1
		count += 1
	return count

if len(sys.argv) < 2:
	print("# Usage: make_propagator.py <adjlist>")
else:
	adjlist = readAdjlist(sys.argv[1])
	netsize = len(adjlist)
	configlen = 1 << netsize
	M = []

	for S1 in range(configlen):
		# pass 1: compute payoffs
		payoffs = [0]*netsize
		for v in range(netsize):
			bitset = getBitset(adjlist[v])
			coops = bitCount(S1 & bitset)
			payoffs[v] = coops * (16 if S1 & 1 << v else 17)
		
		# pass 2: determine possible S2's, and compute the transition probability
		S1_size = fractions.Fraction()
		for v in range(netsize):
			is_coop = (S1 & 1 << v) != 0
			S2 = S1 ^ (1 << v)
			neighbors = adjlist[v]
			neisize = len(neighbors)
			transCount = sum(1 for u in neighbors if is_coop != ((S1 & 1 << u) != 0) and payoffs[v] < payoffs[u])
			nonTransCount = neisize - transCount
			neisize *= netsize
			if transCount:
				M.append((S1,S2, "{}/{}".format(transCount,neisize)))
			S1_size += fractions.Fraction(nonTransCount, neisize)
		M.append((S1,S1, S1_size))
		
	export = ", ".join("{{{}, {}}} -> {}".format(S2+1, S1+1, value) for (S1, S2, value) in M)
	print("M = SparseArray[{", export, "}];")