shannon-capacity.py

import random
import bisect
from array import array

def decode(n):
    return INDEX[n] 

class VertexSet(object):
    def __init__(self):
        self.items = array('H') 

    def add(self, v):
        bisect.insort_left(self.items, v)

    def remove(self, v):
        items = self.items
        i = bisect.bisect_left(items, v)
        items.pop(i)

    def replace(self, u, v):
        items = self.items
        i = bisect.bisect_left(items, u)
        items.pop(i)
        bisect.insort_left(self.items, v)

    def __len__(self):
        return len(self.items)
    
def buildGraph():
    def verticies():
        for a in range(0,7):
            for b in range(0,7):
                for c in range(0,7):
                    for d in range(0,7):
                        for e in range(0,7):
                            yield (a,b,c,d,e)

    def adj(v):
        (x,y,z,w,t) = v
        for a in range(-1,2):
            for b in range(-1,2):
                for c in range(-1,2):
                    for d in range(-1,2):
                        for e in range(-1,2):
                                yield ((x+a) % 7, (y+b) % 7, (z+c) % 7, (w+d) % 7, (t+e) % 7)

    index = {}
    backwards = {}
    for i, v in enumerate(verticies()):
        index[v] = i
        backwards[i] = v

    graph = {}
    for v in verticies():
        edges = [index[e] for e in adj(v) ]
        edges.sort()
        arr = array('H', edges) # unsigned short
        graph[index[v]] = arr
    return graph, backwards 


#
# the actuall algorithm goes here
#

# constants

LAMBDA = 1.0 / (2*float(242) - 3)
REMOVE = (1.0 - 1.0 / (1.0 + LAMBDA)) * 1e-4
ADD = 1.0 - LAMBDA / (1.0 + LAMBDA)
DRAG = 1.0 - LAMBDA / 4*(1.0 + LAMBDA)

#
# the possible random walks
#

def doRemove(s, u, v):
    if random.random() > REMOVE: return
    s.remove(v)

def doDrag(s, u,  v):
    if random.random() > DRAG: return
    s.replace(u, v)

def doAdd(s, u, v):
    if random.random() > ADD: return
    s.add(v)
    printSet(s)

def doNothing(s,u,v):
    # troll face.
    pass

def printSet(s):
    global largestSet
    if len(s) > largestSet:
        largestSet = len(s)
        print len(s)
        for i, w in enumerate(s.items):
            print "%03d\t%s" % (i + 1, decode(w))
        print "-" * 40

largestSet = 0

# move:
#  3: v has no nighbhors in the independent set, doAddition.
#  2: v has exactly one nighbhor in the i.s, doDrag.
#  1: v has at least two neighbors in the i.s, doNothing.
#  0: v itself is present in the i.s, doRemove
def selectMove(a,b,v):
        i,j = 0,0
        u = 0
        move = 3
        while i < len(a) and j < len(b):
            if a[i] < b[j]:
                i = bisect.bisect_left(a, b[j], lo=i)
            elif a[i] > b[j]:
                j = bisect.bisect_left(b, a[i], lo=j) 
            else:
                u = a[i]
                i += 1
                j += 1
                if u == v:
                    move = 0 
                    break
                if move == 2:
                    move = 1
                    break
                move = 2
        return move, u
      
GRAPH, INDEX = buildGraph()

def randomWalk():
    state = VertexSet()
    moves = [doRemove, doNothing, doDrag, doAdd]
    graph = GRAPH
    while True:
        v = random.randint(0, 7**5 - 1)
        move, u = selectMove(state.items, graph[v], v)
        moves[move](state,u,v)

if __name__ == "__main__":
    randomWalk()