import random

CONST_INFTY = 5000

class Graph():

    "The class Graph that encodes an undirected graph. For this implementation, the graph is represented as an Adjacency Matrix."
    "The graph is initialised as an empty graph (A_{ij}=0 for all i, j) with numNodes nodes. The nodeSet contains the indices of the nodes, namely [0, ..., numNodes]."
    "It has methods add_edge and delete_edge for adding and deleting edges. The __str__ method has been defined to print the Adjacency Matrix."

    def __init__(self, numNodes):
        self.numNodes = numNodes
        self.AdjacencyMatrix = [[0 for col in range(numNodes)] for row in range(numNodes)]
        self.nodeSet = set(i for i in range(numNodes))

    def __str__(self):
        return str(self.AdjacencyMatrix)

    def add_edge(self,node1, node2):
        self.AdjacencyMatrix[node1][node2] = 1
        self.AdjacencyMatrix[node2][node1] = 1

    def delete_edge(self,node1,node2):
        self.AdjacencyMatrix[node1][node2] = 0
        self.AdjacencyMatrix[node2][node1] = 0

class diGraph(Graph):

    "The class digraph is a subclass of graph for directed graphs. It overloads the methods add_edge and delete_edge to ensure that the edges are directed."

    def add_edge(self,node1, node2):
        self.AdjacencyMatrix[node1][node2] = 1

    def delete_edge(self,node1,node2):
        self.AdjacencyMatrix[node1][node2] = 0

class wdiGraph(diGraph):

    "The class wdigraph (for weighted digraph) is a subclass of digraph. It overloads the method add_edge to also specify the length of the edge. The adjacency matrix"
    "now is not a binary matrix, but a matrix with numbers corresponding to the weights. It also adds the new method 'edge length' for finding the length of an edge, given by its endpoints."

    def __init__(self, numNodes):
        self.numNodes = numNodes
        self.AdjacencyMatrix = [[CONST_INFTY for col in range(numNodes)] for row in range(numNodes)]
        self.nodeSet = set(i for i in range(numNodes))

    def add_edge(self,node1, node2, length):
        self.AdjacencyMatrix[node1][node2] = length

    def delete_edge(self,node1,node2):
        self.AdjacencyMatrix[node1][node2] = 0

    def edge_length(self, node1, node2):
        return self.AdjacencyMatrix[node1][node2]


def findNextNode(graph, S, spDistances):
    "Function that finds the next node to be considered by Dijsktra"
    "S is the set of explored nodes, feel free to use 'explored' instead if you find it more informative. spDistances is the list of shortest path distances from the start_node of Dijsktra."

    unexploredNodes = graph.nodeSet.difference(S) # The set of nodes that have not been explored yet, i.e., V-S
    #nextNode = random.choice(list(unexploredNodes))

    minDist = 1e7 # Set the distances to a sufficiently large value
    nextNode = random.choice(list(unexploredNodes)) # Set an arbitrary (here random) node to be the current node. This will be updated in the nested for loops below.
    
    # The for loops consider every node in V-S and for that, every edge to any node in S. The node u for which the value dist (i.e., d'(u) in the slides/KT book) is minimized is chosen as the next node.
    # The distance is also return because this will be spDistances[u] (i.e., d(u) in the slides/KT book).
    for newNode in unexploredNodes:
        for oldNode in S:
            if graph.edge_length(oldNode,newNode)!=0:  # If there is an edge (oldNode, newNode) - note that all edges will be strictly positive, '0' indicates the non-existence of an edge. 
                dist = spDistances[oldNode] + graph.edge_length(oldNode, newNode)
                if (dist < minDist):
                    nextNode = newNode
                    minDist = dist
    
    return nextNode, minDist

def BellmanFord(G,t):

    bigNum = 1000

    #2-D array M to store the costs of the min-cost paths from nodes to node t that use at most i edges.
    M = []
    M = [[] for i in range(G.numNodes)]

    # Initialisation, all costs set to a very big number (simulating infinity)
    for i in range(0,G.numNodes):
        for node in G.nodeSet:
            M[i].append(0)
    
    # M[0,t] is inistialised to 0
    M[0][t] = 0

    for node in G.nodeSet:
        if node != t:
            M[0][node] = bigNum

    for i in range(1,G.numNodes):
        for node in G.nodeSet:
            print("Node considered now:", node)
            neighbourMinCost, neighbour = minReachableNode(G,node,M,i)
            if neighbour != -1:
                M[i][node] = min(M[i-1][node], neighbourMinCost)
            else: 
                M[i][node] = M[i-1][node]
    return M

def minReachableNode(G,v,M,i):

    "A function that finds the cost of the second term of the recurence relation, as well as the neighbour of v that"
    "results in that cost."

    bigNum = 1000
    minCost = 8000
    currentNode = -1

    for node in G.nodeSet:
        if G.edge_length(v,node) != CONST_INFTY:
            print("Possible neighbour:", node)
            if M[i-1][node] == bigNum:
                cost = bigNum
            else:
                cost = G.edge_length(v,node) + M[i-1][node]

            if minCost > cost:
                minCost = cost
                currentNode = node
        print("Chosen neighbour is", currentNode)
    
    return minCost, currentNode




# Empty graph with 6 nodes, for the KT Figure 5.7. example the mapping will be
# s->0, u->1, v->2, x->3, y->4, z->5
myGraph = wdiGraph(6)

# Adding the edges with weights as in the example from the lectures.
myGraph.add_edge(0,1,-4)
myGraph.add_edge(0,5,-3)
myGraph.add_edge(1,3,-1)
myGraph.add_edge(1,4,-2)
myGraph.add_edge(2,1,8)
myGraph.add_edge(2,5,3)
myGraph.add_edge(3,0,6)
myGraph.add_edge(3,5,4)
myGraph.add_edge(4,2,-3)
myGraph.add_edge(4,5,2)


M=BellmanFord(myGraph,5)

print(M)