#! /usr/bin/python

# HSIM  Copyright (C) 2016  Michael Stensby, Mate Verunica
#
# This software may be modified and distributed under the terms
# of the MIT license.  See the LICENSE file for details.

from __future__ import print_function

from random import randint

import sys, math, time, Queue


def path_count(nodeCount):
        count = 0
        for i in range(1,nodeCount+1):
                count += (nodeCount-i)
        return count

def trans_count(nodeArray,nodeCount,index,sentBroadcast):
    transCount = 0
    for neighbour in nodeArray[index]:
        neighbour = int(neighbour)
        if neighbour == index:
             continue
        elif neighbour in sentBroadcast:
            transCount += 1
        else:
            sentBroadcast.append(neighbour)
            transCount += 1
            count, sentBroadcast = trans_count(nodeArray, nodeCount, neighbour, sentBroadcast)
            transCount += count

    return transCount, sentBroadcast

def avg_trans_count(nodeArray,nodeCount):
    avgTrans = 0
    for nodeIndex in range(nodeCount):
        count, visited = trans_count(nodeArray, nodeCount, nodeIndex, [nodeIndex])
        avgTrans += count
    avgTrans /= nodeCount
    avgTrans /= 2

    return avgTrans

# Shortest Path by yanhan, taken from http://stackoverflow.com/a/17164833 on March 1, 2016
def get_shortest_path(par, src, dest):
    '''
    Returns the shortest path as a list of integers
    par - parent information
    src - source vertex
    dest - destination vertex
    '''
    if dest == src:
        return [src]
    else:
        ret = get_shortest_path(par, src, par[dest])
        ret.append(dest)
        return ret

def bfs(edgeList, src, dest):
    '''
    Breadth first search routine. Returns (distance, shortestPath) pair from src to dest. Returns (-1, []) if there is no path from src to dest
    edgeList - adjacency list of graph. Either list of lists or dict of lists
    src - source vertex
    dest - destination vertex
    '''
    vis = set() # stores the vertices that have been visited
    par = {} # stores parent information. vertex -> parent vertex in BFS tree
    distDict = {} # stores distance of visited vertices from the source. This is the number of edges between the source vertex and the given vertex
    q = Queue.Queue()
    q.put((src, 0)) # enqueue (source, distance) pair
    par[src] = -1 # source has no parent
    vis.add(src) # minor technicality, will explain later
    while not q.empty():
        (v,dist) = q.get() # grab vertex in queue
        distDict[v] = dist # update the distance
        if v == dest:
            break # reached destination, done
        nextDist = dist+1
        for nextV in edgeList[v]:
            nextV = int(nextV)
            # visit vertices adjacent to the current vertex
            if nextV not in vis:
                # not yet visited
                par[nextV] = v # update parent of nextV to v
                q.put((nextV, nextDist)) # add into queeu
                vis.add(nextV) # mark as visited
    # obtained shortest path now
    return (distDict[dest], get_shortest_path(par, src, dest))


#Link State Routing
def link_state(nodeArray, nodeCount):

    paths = []
    transmissions = 0
    pathsIndex = 0
    pathCount = 0
    sourceNode = 0
    destNode = 1
    while pathsIndex != path_count(nodeCount):
        if pathCount < (nodeCount - 1 - sourceNode):
            (dist, shortestPath) = bfs(nodeArray, sourceNode, destNode)
            paths.append(dist)
            destNode += 1
            pathCount += 1
            pathsIndex += 1
        else:
            sourceNode += 1
            pathCount = 0
            destNode = (sourceNode + 1)

    transmissionAvg = 0.00
    pathLenAvg = 0.00

    for path in paths:
        pathLenAvg += path
    pathLenAvg = pathLenAvg / len(paths)


    transmissionAvg = avg_trans_count(nodeArray,nodeCount)

    return transmissionAvg, pathLenAvg

#Vector Distance Routing
def vector_distance(nodeArray, nodeCount):
    paths = []
    transmissions = 0
    pathsIndex = 0
    pathCount = 0
    sourceNode = 0
    destNode = 1
    maxShortestPath = 0;
    while pathsIndex != path_count(nodeCount):
        if pathCount < (nodeCount - 1 - sourceNode):
            (dist, shortestPath) = bfs(nodeArray, sourceNode, destNode)
            if len(shortestPath)-1 > maxShortestPath:
                maxShortestPath = len(shortestPath)-1
            paths.append(dist)
            destNode += 1
            pathCount += 1
            pathsIndex += 1
        else:
            sourceNode += 1
            pathCount = 0
            destNode = (sourceNode + 1)

    transmissionAvg = 0.00
    pathLenAvg = 0.00

    for path in paths:
        pathLenAvg += path
    pathLenAvg /= len(paths)

    for node in nodeArray:
        transmissionAvg += (len(node) * maxShortestPath)
    transmissionAvg /= float(nodeCount)

    return transmissionAvg, pathLenAvg

#Hot Potato I Routing
def hot_potato_I(nodeArray, nodeCount):
    paths = []
    transmissions = [0]*10
    pathLens = [0]*10
    pathsIndex = 0
    pathCount = 0
    sourceNode = 0
    destNode = 1
    while pathsIndex != path_count(nodeCount):
        if pathCount < ( nodeCount - 1 - sourceNode):
            paths.append([])
            for trial in range(10):
                route = []
                prevNode = sourceNode
                node = int(nodeArray[sourceNode][randint(0,len(nodeArray[sourceNode])-1)])
                route.append(node)
                while node != destNode:
                    nextNode = int(nodeArray[node][randint(0,len(nodeArray[node])-1)])
                    if nextNode == prevNode and len(nodeArray[node])!=1:
                        continue
                    prevNode = node
                    node = nextNode
                    route.append(node)
                paths[pathsIndex].append(len(route)) # path transmission count including loops
                transmissions[trial] += len(route)
                i = 0
                retRoute = route
                for node in route:
                    if node == sourceNode:
                        retRoute = route[(i+1):]
                    i += 1
                paths[pathsIndex][trial] += len(retRoute)  # return path transmission count without loops
                transmissions[trial] += len(retRoute)
                pathLens[trial] += len(retRoute)
            destNode += 1
            pathCount += 1
            pathsIndex += 1
        else:
            sourceNode += 1
            pathCount = 0
            destNode = (sourceNode + 1)

    transmissionAvg = 0.00
    pathLenAvg = 0.00

    for trialNum in range(10):
        transmissions[trialNum] = transmissions[trialNum] / float(nodeCount)
        transmissionAvg += transmissions[trialNum]
        pathLens[trialNum] = pathLens[trialNum] / float(path_count(nodeCount))
        pathLenAvg += pathLens[trialNum]

    transmissionAvg = transmissionAvg / 10.0
    pathLenAvg = pathLenAvg / 10.0
    stdDevTrans = 0
    stdDevPathLen = 0

    for trial in range(10):
        stdDevTrans += ((transmissions[trial]-transmissionAvg)**2)
        stdDevPathLen += ((pathLens[trial]-pathLenAvg)**2)
    stdDevTrans = (stdDevTrans/(9.0))** 0.5
    stdDevPathLen = (stdDevPathLen/(9.0)) ** 0.5

    # calculate confidence intervals
    transInterval = (transmissionAvg-(2.262*stdDevTrans/(10**0.5)),transmissionAvg+(2.262*stdDevTrans/(10**0.5)))
    pathLenInterval = (pathLenAvg-(2.262*stdDevPathLen/(10**0.5)),pathLenAvg+(2.262*stdDevPathLen/(10**0.5)))
    return transmissionAvg, transInterval, pathLenAvg, pathLenInterval

#Hot Potato II Routing
def hot_potato_II(nodeArray, nodeCount):
    paths = []
    transmissions = [0]*10
    pathLens = [0]*10
    pathsIndex = 0
    pathCount = 0
    sourceNode = 0
    destNode = 1
    while pathsIndex != path_count(nodeCount):
        if pathCount < ( nodeCount - 1 - sourceNode):
            paths.append([])
            for trial in range(10):
                route = []
                prevNode = sourceNode
                if str(destNode) in nodeArray[sourceNode]:
                        node = destNode
                else:
                    node = int(nodeArray[sourceNode][randint(0,len(nodeArray[sourceNode])-1)])
                route.append(node)
                while node != destNode:
                    if str(destNode) in nodeArray[node]:
                        nextNode = destNode
                    else:
                        nextNode = int(nodeArray[node][randint(0,len(nodeArray[node])-1)])
                        if nextNode == prevNode and len(nodeArray[node])!=1:
                            continue
                    prevNode = node
                    node = nextNode
                    route.append(node)
                paths[pathsIndex].append(len(route)) # path transmission count including loops
                transmissions[trial] += len(route)
                i = 0
                retRoute = route
                for node in route:
                    if node == sourceNode:
                        retRoute = route[(i+1):]
                    i += 1
                paths[pathsIndex][trial] += len(retRoute)  # return path transmission count without loops
                transmissions[trial] += len(retRoute)
                pathLens[trial] += len(retRoute)
            destNode += 1
            pathCount += 1
            pathsIndex += 1
        else:
            sourceNode += 1
            pathCount = 0
            destNode = (sourceNode + 1)

    transmissionAvg = 0.00
    pathLenAvg = 0.00

    for trialNum in range(10):
        transmissions[trialNum] = transmissions[trialNum] / float(nodeCount)
        transmissionAvg += transmissions[trialNum]
        pathLens[trialNum] = pathLens[trialNum] / float(path_count(nodeCount))
        pathLenAvg += pathLens[trialNum]

    transmissionAvg = transmissionAvg / 10.0
    pathLenAvg = pathLenAvg / 10.0

    stdDevTrans = 0
    stdDevPathLen = 0
    for trial in range(10):
        stdDevTrans += ((transmissions[trial]-transmissionAvg)**2)
        stdDevPathLen += ((pathLens[trial]-pathLenAvg)**2)
    stdDevTrans = (stdDevTrans/(9.0))** 0.5
    stdDevPathLen = (stdDevPathLen/(9.0)) ** 0.5

    # calculate confidence intervals
    transInterval = (transmissionAvg-(2.262*stdDevTrans/(10**0.5)),transmissionAvg+(2.262*stdDevTrans/(10**0.5)))
    pathLenInterval = (pathLenAvg-(2.262*stdDevPathLen/(10**0.5)),pathLenAvg+(2.262*stdDevPathLen/(10**0.5)))

    return transmissionAvg, transInterval, pathLenAvg, pathLenInterval

def main():
    if (len(sys.argv) < 2):
        raise ValueError('Invalid arguments')

    inputFile = open(sys.argv[1])
    nodeArray = []
    for line in inputFile:
        nodeArray.append(line.rstrip("\n").split(" "))
    nodeCount = int(nodeArray.pop(0).pop(0))

    avgDegree = 0
    for node in nodeArray:
        avgDegree += len(node)

    avgDegree /= float(nodeCount)