import numpy as np
import matplotlib.pyplot as plt
from numpy.random import choice, rand 
import networkx as nx
%matplotlib inline

def GenKnightNetwork(boardSize):
    G = nx.Graph()
    pos = {}
    for row in xrange(boardSize):
        for col in xrange(boardSize):
            nodeId = row + col*boardSize
            pos[nodeId] = np.array([1.0*row/boardSize, 1.0*col/boardSize])
            newPos = GetLegalMoves(row, col, boardSize)
            for e in newPos:
                nid = e[0] + e[1]*boardSize
                G.add_edge(nodeId, nid)
    return G, pos

def GetLegalMoves(x,y,boardSize):
    newMoves = []
    moveOffsets = [(-1,-2),(-1,2),(-2,-1),(-2,1),
                   ( 1,-2),( 1,2),( 2,-1),( 2,1)]
    for i in moveOffsets:
        newX = x + i[0]
        newY = y + i[1]
        if isLegalCoord(newX,boardSize) and \
                        isLegalCoord(newY,boardSize):
            newMoves.append((newX,newY))
    return newMoves

def isLegalCoord(x,boardSize):
    if x >= 0 and x < boardSize:
        return True
    else:
        return False

boardSize = 8
(G,pos) = GenKnightNetwork(boardSize)

nx.draw(G, pos)

def RandomWalk(G, xi, n, till_first_return = False):
    nodeSeq = []
    nodeSeq.append(xi)
    if till_first_return:
        xInit = xi
        while True:
            neig = np.array(G.neighbors(xi))
            xi = choice(G.neighbors(xi),1)[0]       
            nodeSeq.append(xi)
            if xi == xInit:
                return nodeSeq
    else:
        for i in xrange(n):
            neig = np.array(G.neighbors(xi))
            xi = choice(G.neighbors(xi),1)[0]       
            nodeSeq.append(xi)
        return nodeSeq


nodeSeq = RandomWalk(G, 0, 100)
edgeSeq = [(nodeSeq[i-1], nodeSeq[i]) for i in xrange(1,len(nodeSeq))]

nodeSeq = RandomWalk(G, 0, 100, True)
edgeSeq = [(nodeSeq[i-1], nodeSeq[i]) for i in xrange(1,len(nodeSeq))]
nx.draw(G, pos)
nx.draw(G, pos, edgelist = edgeSeq, edge_color='blue', width=2)

nodeSeq = []
for xi in xrange(G.number_of_nodes()):
    nodeSeq.append(RandomWalk(G, xi, 1000))

h = plt.hist(nodeSeq, bins = G.number_of_nodes())

plt.bar(range(0,64), G.degree().values())

returnTime = []
for i in xrange(1000):
    returnTime.append(len(RandomWalk(G, 27, 0, True)))

plt.boxplot(returnTime)