ADV_2.py

from collections import defaultdict
import sys

class Graph():
    '''
    Class which stores a weighted undirected graph and method for finding shortest path between two graph nodes using Dijsktra's algorithm
    '''
    def __init__(self, size):
        self.edges = defaultdict(list)                              #dictionary of all connected nodes e.g. {'X': ['A', 'B', 'C', 'E'], ...}
        self.weights = {}                                           #dictionary of edges and weights e.g. {('X', 'A'): 7, ('X', 'B'): 2, ...}
        self.size = size                                            #number of nodes inside the graph
        self.dist = []                                              #list of all distances from the starting node to node under the same index inside unpoppedQ list
        for i in range(size):                                       #repeat number of nodes inside the graph times
            self.dist.append(sys.maxsize)                           #set distance to that node to maximum size of python data structure
        self.previous = []                                          #list of previous nodes in the path set by Dijsktra's algorithm 
        for i in range(size):                                       #repeat number of nodes inside the graph times
            self.previous.append(None)                              #append the previous list with None
        
    
    def add_edge(self, from_node, to_node, weight):                 #bidirectional
        '''
        Class method for adding edges into the graph
        Input: string,string,integer. two nodes to be connected with an edge and weight of that connection
        Output: no output, edges and weights attributes are modified instead
        '''
        self.edges[from_node].append(to_node)                       #create edge connecting from_node with to_node
        self.edges[to_node].append(from_node)                       #create edge connecting to_node with from_node
        self.weights[(from_node, to_node)] = weight                 #set weight of the edge connecting from_node with to_node to the value of weight parameter
        self.weights[(to_node, from_node)] = weight                 #set weight of the edge connecting to_node with from_node to the value of weight parameter


    def findSmallestNode(self):
        '''
        Class method for linearly searching for the node inside Q list with smallest distance from starting node
        Input: no input
        Output:integer. Index of a node inside Q list with smallest distance from the starting node
        ''' 
        smallest = self.dist[self.getIndex(self.Q[0])]              #set value of smallest distance to the distance of the node at the beggining of the Q list 
        result = self.getIndex(self.Q[0])                           #set the node at the beggining of the Q list as the node with the smallest distance
        for i in range(len(self.dist)):                             #loop length of distance list ammount of times
            if self.dist[i] < smallest:                             #if distance under i index in distance list is smaller than current smallest distance
                node = self.unpoppedQ[i]                            #create node variable and set it to the node inside unpoppedQ list under i index
                if node in self.Q:                                  #if node is inside Q list
                    smallest = self.dist[i]                         #set value inside distance list under i index as the current smallest distance
                    result = self.getIndex(node)                    #set value of result variable to index of a node inside node variable
        return result                                               #return index of a node with the smallest distance from the starting node
            

    def getIndex(self, neighbour):
        '''
        Class method for linearly searching the index of a graph node inside the unpoppedQ list
        Input: string. a node inside the graph
        Output: integer. index of neighbour node inside unpoppedQ list
        '''
        for i in range(len(self.unpoppedQ)):                        #loop length of unpoppedQ list ammount of times
            if neighbour == self.unpoppedQ[i]:                      #if neighbour parameter node is equal to value under i index inside unpoppedQ list
                return i                                            #return i value


    def getPopPosition(self, uNode):
        '''
        Class method that indicates position of uNode inside Q list
        Input: string. a node inisde the graph 
        Output: integer. index of uNode inside Q list
        '''
        result = 0                                                  #innitiate the result value and set it to 0
        for i in range(len(self.Q)):                                #loop length of Q list ammount of times
            if self.Q[i] == uNode:                                  #if value under i index inside Q list is equal to uNode parameter
                return i                                            #return the i value
        return result                                               #return 0


    def getUnvisitedNodes(self, uNode):
        '''
        Class method for finding all of the unvisited nodes bordering uNode
        Input: string. node inside the graph
        Output: list. all of the unvisited nodes adjacent to uNode node argument
        '''
        resultList = []                                             #list of all unvisited nodes bordering uNode 
        allNeighbours = self.edges[uNode]                           #set value of allNeighbours variable to all nodes which have an edge with uNode
        for neighbour in allNeighbours:                             #for each node that has an edge with uNode
            if neighbour in self.Q:                                 #if the Node is inside Q list attribute
                resultList.append(neighbour)                        #append the node to resultList list
        return resultList                                           #return the resultList list     


    def dijsktra(self, start, end):
        '''
        Class method for finding path with lowest cost between two nodes inside the graph using djikstra algorithm
        Input: string. two nodes inside the graph
        Output: list,integter. nodes inside the path with lowest cost between two nodes, cost of the path 
        '''                                 
        self.Q = []                                                 #list of all the unvisited nodes
        for key in self.edges:                                      #for key value in edges dictionary attribute
            self.Q.append(key)                                      #append the key value to Q list
        for i in range(len(self.Q)):                                #repeat loop times length of list Q	
            if self.Q[i] == start:                                  #if i element of list Q 
                self.dist[i] = 0
        self.unpoppedQ = self.Q[0:]                                 #set unpoppedQ list to the copy of Q list 

        while self.Q:                                               #while Q list is not empty                                                   
            u = self.findSmallestNode()                             #set value u to the return value of findSmallestNode() function  
            if self.dist[u] == sys.maxsize:                         #if current smallest distance is equal to maximum size of python data structure
                break                                           
            if self.unpoppedQ[u] == end:                            #if value under u index inside unpoppedQ is the end node
                break

            uNode = self.unpoppedQ[u]                               #set value of uNode variable to a value of the element in unpoppedQ list attribute under u index
            for i in self.getUnvisitedNodes(uNode):                 #loops that goes through all Nodes adjacent to uNode
                iIdx = self.getIndex(i)                             #create i index variable and set it to index of i Node inside unpoppedQ list attribute
                NewINodeDist = self.dist[u] + self.weights[(uNode,i)] #create variable new distance from start node to I node and set it to the sum of distance from start to uNode and weight od edge connecting uNode and i Node  
                if NewINodeDist < self.dist[iIdx]:                  #if new distance from start to i node is smaller than current distance from start to i node 
                    self.dist[iIdx] = NewINodeDist                  #set current distance to i node to new distance to i node 
                    self.previous[iIdx] = uNode                     #set uNode as Node previous to i node
                
            self.Q.remove(uNode) # remove uNode from Q list
            


            
        shortest_path = []                                          #list with nodes indicating shortest path from start node to end node
        shortest_path.insert(0, end)                                #insert end node to the begining of the shortest_path list
        u = self.getIndex(end)                                      #set u variable to return value of getIndex function with end Node as passed argument                                                  
        while self.previous[u] != None:                             #while u Node has a previous value
            shortest_path.insert(0, self.previous[u])               #insert into the begining of the shortest path list the value inside previous list attribute under u index                       
            u = self.getIndex(self.previous[u])                     #set value of u to return value of getIndex function with passed argument being the value inside previous list attribute under u index
        return shortest_path,self.dist[self.getIndex(end)]          #return shortest path from start parameter to end parameter and total weight of this path


graph = Graph(8)


edges = [
    ('O', 'A', 2),
    ('O', 'B', 5),
    ('O', 'C', 4),
    ('A', 'B', 2),
    ('A', 'D', 7),
    ('A', 'F', 12),
    ('B', 'C', 1),
    ('B', 'D', 4),
    ('B', 'E', 3),
    ('C', 'E', 4),
    ('D', 'E', 1),
    ('D', 'T', 5),
    ('E', 'T', 7),
    ('F', 'T', 3),
]
    

for edge in edges:
    graph.add_edge(*edge)

print(graph.dijsktra('O', 'T'))


graph2 = Graph(9)
edges2 = [
    ('A','B',22),    
    ('A','C',9),
    ('A','D',12),
    ('B','C',35),
    ('B','F',36),
    ('B','H',34),
    ('C','D',4),
    ('C','E',65),
    ('C','F',39),
    ('D','E',33),
    ('D','I',30),
    ('E','F',18),
    ('E','G',23),
    ('F','G',39),
    ('F','H',24),
    ('G','H',25),
    ('G','I',21),
    ('H','I',19)
]
for edge in edges2:
    graph2.add_edge(*edge)

print(graph2.dijsktra('A', 'G'))



#notes
#instead of using the provided getPopPosition() method i am using built in python remove method instead, which does the same thing and makes the class method obsolete