INVALID_NODE = -1
INFINITY = 1000000

class Node:
    previous = INVALID_NODE
    distFromSource = INFINITY
    visited = False


def PopulateNetwork(filename):
    network = []
    networkfile = open(filename, "r")
    for line in networkfile:
        line = line.replace("\n","")
        line = line.split(',')
        line = map(int, line)
        network.append(line)
    return network


def PopulateNodeTable(network, startNode):
    nodeTable = []

    for node in network:
        nodeTable.append(Node())

    nodeTable[startNode].distFromSource = 0
    nodeTable[startNode].visited = True
    return nodeTable


def FindNearest(network, nodeTable, currentNode):
    nearestNeighbour = []
    columnIndex = 0

    for entry in network[currentNode]:
        if entry != 0 and nodeTable[columnIndex].visited == False:
            nearestNeighbour.append(columnIndex)
        columnIndex += 1
    return nearestNeighbour

def CalculateTentative(nodeTable, network, currentNode, nearestNeighbours):

#calculate the distance from currentNode to each node in neighborous list
#work out distance from source for each node
#if lower than current entry in nodeTable for that node, update

    for neighbour in nearestNeighbours:
        tentativeDistance = nodeTable[currentNode].distFromSource + network[currentNode][neighbour]
        if nodeTable[neighbour].distFromSource > tentativeDistance:
            nodeTable[neighbour].distFromSource = tentativeDistance
            nodeTable[neighbour].previous = currentNode
    return nodeTable

def FindNextNode(nodeTable, currentNode, destination):
    nodeTable[currentNode].visited = True

    distance = 100000
    count = 0

    if currentNode != destination:
        for entry in nodeTable:
            if entry.visited == False and entry.distFromSource < distance:
                distance = entry.distFromSource
                currentNode = count
        count = count + 1

    else:
        print "This is your destination: "
        print currentNode


    return currentNode




network = PopulateNetwork("network.txt")
startNode = 1
currentNode = startNode
nodeTable = PopulateNodeTable(network, startNode)

print "Network file: \n"
for line in network:
    print line

nearestNeighbour = FindNearest(network, nodeTable, currentNode)

print "\nNearest neighbour \n"
for neighbour in nearestNeighbour:
    print neighbour

newDistance = CalculateTentative(nodeTable, network, currentNode, nearestNeighbour)

print "\nTentativce distance \n"
for newNode in newDistance:
    print newNode.distFromSource
    print newNode.previous
    print newNode.visited
    print "\n"

destination = 3

currentNode = FindNextNode(nodeTable, currentNode, destination)

print currentNode

##