Graph.py

import queue, sys
import GraphExceptions

# I'll be using adjacency list to hold my graph

def addNode(graph, node): # O(1)
    ''' Adds a node to the graph '''
    if(graph==None):
        # If our graph is empty, initialize it with an empty dictionary
        graph = {}
    # Add a new entry in graph dictionary with our "node" as key
    # and empty list as the value
    graph[node] = []
    return graph

def addEdge(graph, pointA, pointB): # O(1)
    ''' Add an edge to the graph '''
    if(graph==None):
        # We can't add an edge to an empty graph
        print("You can't add an edge to an empty graph")
        raise GraphExceptions.NoGraph
    # Find nodes that hold pointA and pointB
    A = graph.get(pointA)
    B = graph.get(pointB)
    # If any of the nodes do not exist in the graph, we can't add an edge
    if(A==None):
        print(pointA, "does not exist in the graph")
        raise GraphExceptions.NotInGraph(pointA)
    if(B==None):
        print(pointB, "does not exist in the graph")
        raise GraphExceptions.NotInGraph(pointB)
    # If edge already exists, ignore it, as we don't want duplicates in an
    # undirected, unweighted graph
    if(pointB in A and pointA in B):
        print("This edge is already in the graph")
        return graph
    # Append the other end of the edge to according nodes adjacency list
    A.append(pointB)
    B.append(pointA)
    return graph

def addWeightedEdge(graph, pointA, pointB, weight): # O(1)
    ''' Add an edge to the graph '''
    if(graph==None):
        # We can't add an edge to an empty graph
        print("You can't add an edge to an empty graph")
        raise GraphExceptions.NoGraph
    # Find nodes that hold pointA and pointB
    A = graph.get(pointA)
    B = graph.get(pointB)
    # If any of the nodes do not exist in the graph, we can't add an edge
    if(A==None):
        print(pointA, "does not exist in the graph")
        raise GraphExceptions.NotInGraph(pointA)
    if(B==None):
        print(pointB, "does not exist in the graph")
        raise GraphExceptions.NotInGraph(pointB)
    # Append the other end of the edge to according nodes adjacency list
    A.append([pointB, weight])
    B.append([pointA, weight])
    return graph

def printGraph(graph): # O(n^2)
    ''' Prints the graph in a readable format '''
    if(graph==None):
        # If graph does not exist, we can not print it
        print("None Object can not be printed as graph")
        raise GraphExceptions.NoGraph
    # Look at every node in the graph
    for node in graph:
        # From list of edges, generate a string of format "first-edge, second-edge, ..., last-edge"
        edges = ', '.join(str(edge) for edge in graph[node])
        print(node,"connected to:",edges)
    return graph

def isPath(graph, nodeA, nodeB): # O(n^2)
    ''' Finds a path between 2 nodes and prints it to a text file '''
    path, found = BFS(graph, nodeA, nodeB) # O(n^2)
    if(not found):
        print("Path has not been found")
        return None
    actualPath = reconstructPath(path, nodeB) # O(n)
    saveListToFile(actualPath, nodeA+"_to_"+nodeB+".txt") # O(n)
    return actualPath

def BFS(graph, start, end=None): # O(n^2)
    ''' Modified Breadth first search that will also find the shortest path between 2 nodes '''
    if(graph==None):
        # Graph has to be specified
        print("A graph object has to be specified for BFS")
        raise GraphExceptions.NoGraph
    if(graph.get(start)==None):
        # Start object has to be in the graph
        print("Start node has to be in the graph")
        raise GraphExceptions.NotInGraph(start)
    # We initialize a queue with only our start node as first parameter,
    # and the node it came from as second. We set the node it came from as itself,
    # a visited list, a boolean to track if the end node has been found and
    # a path that is going to hold the node and previous node it came from 
    q = queue.Queue()
    visited = []
    path = {}
    q.put((start,start))
    found = False
    while not q.empty():
        # Taking one node from the queue at a time, while no more items remain
        node, cameFrom = q.get()
        if(node not in visited):
            # If we haven't yet looked at this node, add it to the visited list
            # and append it to the path list along the node it came from
            visited.append(node)
            path[node] = cameFrom
            if(node == end):
                # If node matches our end node, we have found a path
                # and so we can end the loop and return the path
                found = True
                break
            for edge in graph[node]:
                # We put each end of the edge as a tuple in the queue
                q.put((edge, node))
    # If path to the end node has been found, return path, otherwise
    # return visited. If we specify end=None, then BFS function works
    # the way it was intended to, ignoring my modifications
    if(found):
        return path, found
    else:
        return visited, found

def reconstructPath(path, end): # O(n)
    ''' Reconstructs path returned by BFS to be used in isPath() function
    and Dijkstra's algorithm '''
    # Starting at the end and going through each node that the current node
    # came from
    node = end
    cameFrom = path[end]
    actualPath = [node]
    while node != cameFrom:
        # Stop when the node came from itself, as this is how we
        # initialised our starting node
        node = cameFrom
        cameFrom = path[cameFrom]
        actualPath.append(node)
    # We return the path reversed, because we reconstructed it from the end
    return actualPath[::-1]

def isConnected(graph): # O(1)
    ''' Output "Yes" if the graph is strongly connected and "No" otherwise '''
    # I'll be using BFS algorithm to traverse through the tree and then
    # comparing the number of edges found by it to the total number of
    # edges in the graph
    if(graph==None):
        # Graph has to be specified
        print("A graph object has to be specified for isConnected")
        raise GraphExceptions.NoGraph
    totalNumberOfNodes = len(graph)
    # Getting any node in the graph to start traversing the graph
    start = None
    for node in graph:
        start = node
        break
    # If start is still None, this means that the graph is empty
    if(start==None):
        print("Graph is empty")
        return True
    # Apply the BFS algorithm to the graph
    visited, waste = BFS(graph, start)
    # Count the number of visited nodes
    visitedCount = len(visited)
    if(totalNumberOfNodes==visitedCount):
        # Every node is connected, therefore graph is strongly connnected
        print("Yes")
        return True
    else:
        # Graph is not strongly connected
        print("NO")
        return False

def DFS(graph, start): # O(n^2)
    ''' Depth first search '''
    if(graph==None):
        # Graph has to be specified
        print("A graph object has to be specified for BFS")
        raise GraphExceptions.NoGraph
    if(graph.get(start)==None):
        # Start object has to be in the graph
        print("Start node has to be in the graph")
        raise GraphExceptions.NotInGraph(start)
    # Initialised with a stack, that is a list, because while we add items
    # with .append() and remove them with .pop(), it behaves exactly like
    # a stack. Also keep track of visited nodes with a visited list
    stack = []
    visited = []
    stack.append(start)
    # While stack is not empty
    while stack:
        node = stack.pop()
        if(node not in visited):
            visited.append(node)
            for edge in graph[node]:
                #Append each edge of the current node to the stack
                stack.append(edge)
    return visited

def saveBFS(graph, start): # O(n^2)
    ''' Saves path traversed by BFS algorithm to a file '''
    visited, waste = BFS(graph, start) # O(n^2)
    saveListToFile(visited, "BFS.txt") # O(n)

def saveDFS(graph, start): # O(n^2)
    ''' Saves path traversed by DFS algorithm to a file '''
    visited = DFS(graph, start) # O(n^2)
    saveListToFile(visited, "DFS.txt") # O(n)

def saveListToFile(l, fileName): # O(n)
    ''' Saves list l to file with name fileName '''
    with open(fileName, "w") as f:
        for item in l:
            f.write(item)
            f.write("\n")

def dijkstra(graph, start, end): # O(n^2)
    ''' Dijkstra's algorithm to find the shortest path from start to end '''
    if(graph==None):
        # Graph has to be specified
        print("A graph object has to be specified for BFS")
        raise GraphExceptions.NoGraph
    if(graph.get(start)==None):
        # Start object has to be in the graph
        print("Start node has to be in the graph")
        raise GraphExceptions.NotInGraph(start)
    if(graph.get(end)==None):
        # End object has to be in the graph
        print("End node has to be in the graph")
        raise GraphExceptions.NotInGraph(end)
    # Helper values to be used as edge[value] and edge[weight] to
    # access the according element in the list that hold either 
    # value or weight
    value = 0
    weight = 1
    # We initialise current node as our starting point
    current = start
    # TotalWeight will hold the total calculated weight for each node
    totalWeight = {}
    # Set totalWeight of every node as infinity(or biggest possible number)
    for node in graph:
        totalWeight[node] = sys.maxsize
    # Set totalWeight of starting node as 0
    totalWeight[start] = 0
    # Initialise path with starting node that points to itself
    path = {start:start}
    visited = []
    # Keep track of previous current node to avoid infinite loops
    last = None
    # While end is not reached
    while current != end and last != current:
        # For every edge that is connected to current node
        for edge in graph[current]:
            tempWeight = totalWeight[current] + edge[weight]
            if(tempWeight < totalWeight[edge[value]]):
                # If new weight smaller that existing weight, update it
                totalWeight[edge[value]] = tempWeight
                # Also add this as the better path
                path[edge[value]] = current
        visited.append(current)
        # Find the node with the smallest total weight and set
        # it as the current node
        smallest = sys.maxsize
        last = current
        for node in graph:
            if node not in visited and totalWeight[node] < smallest:
                current = node
                smallest = totalWeight[node]
    if(last==current):
        # End node was not found, there is no path
        print("Path between",start,"and",end,"could not be found")
        raise GraphExceptions.NoPath(start, end)
    # Reconstruct path and return it as a list
    return reconstructPath(path, end), totalWeight[end]





# --------------------Samples--------------------
def simpleGraph():
    g = addNode(None, "a")
    addNode(g,"b")
    addNode(g,"c")
    addNode(g,"d")
    addNode(g,"e")
    addNode(g,"f")
    addNode(g,"g")
    addNode(g,"h")
    addNode(g,"s")
    
    addEdge(g,"a","b")
    addEdge(g,"a","s")
    addEdge(g,"s","c")
    addEdge(g,"c","d")
    addEdge(g,"c","e")
    addEdge(g,"c","f")
    addEdge(g,"f","g")
    addEdge(g,"s","g")
    addEdge(g,"e","h")
    addEdge(g,"g","h")
    return g

def samplePrint():
    g = simpleGraph()
    printGraph(g)

def sampleIsPath():
    g = simpleGraph()
    isPath(g, "a", "h")

def sampleIsConnected():
    g = simpleGraph()
    isConnected(g)

def sampleBfsAndDfs():
    g = simpleGraph()
    saveBFS(g, "a")
    saveDFS(g, "a")

def weightedGraph():
    g = addNode(None, "a")
    addNode(g,"b")
    addNode(g,"c")
    addNode(g,"d")
    addNode(g,"e")
    addNode(g,"f")
    addNode(g,"g")
    addNode(g,"h")
    addNode(g,"s")

    addWeightedEdge(g,"a","b",1)
    addWeightedEdge(g,"a","s",5)
    addWeightedEdge(g,"s","c",20)
    addWeightedEdge(g,"c","d",1)
    addWeightedEdge(g,"c","e",10)
    addWeightedEdge(g,"c","f",30)
    addWeightedEdge(g,"f","g",3)
    addWeightedEdge(g,"s","g",2)
    addWeightedEdge(g,"e","h",5)
    addWeightedEdge(g,"g","h",40)
    return g

def sampleDijkstra():
    g = weightedGraph()
    path, totalWeight = dijkstra(g, "a", "h")
    print(path, totalWeight)

#--------------------------Main------------------------------

if __name__ == "__main__":
    samplePrint() # Task 3
    sampleIsPath() # Task 3
    sampleIsConnected() # Task 4
    sampleBfsAndDfs() # Task 5
    sampleDijkstra() # Task 6