breadth first search of nodes

distancesBetweenNodes.py

'''course: https://www.coursera.org/learn/algorithms-on-graphs#about'''


class Node:
    def __init__(self, key, next=None):
        self.key = key
        self.next = next


class SinglyLinkedList:

    def __init__(self):
        self.head = None
        self.tail = None


    def pushFront(self, key):
        node = Node(key=key, next=self.head)
        self.head = node

        if self.tail == None:
            self.tail = self.head


    def topFront(self):
        return self.head.key


    def popFront(self):
        if self.head == None:
            raise Exception("Empty list")

        poppedKey = self.head.key
        self.head = self.head.next

        if self.head == None:
            self.tail = None

        return poppedKey


    def pushBack(self, key):
        node = Node(key=key)

        if self.tail == None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node


    def empty(self):
        return self.head == None



    def __str__(self):
        head = self.head
        string = "["+str(head.key) + ", "

        while head.next.next != None:
            head = head.next
            string += str(head.key) + ", "

        string += str(head.next.key) + "]"
        return string



class Queue:

    def __init__(self):
        self.collection = SinglyLinkedList()

    def enqueue(self, key):
        self.collection.pushBack(key)

    def dequeue(self):
        return self.collection.popFront()

    def empty(self):
        return self.collection.empty()


############################################################################################




def breadthFirstSearch(adjacencyList, origin):
    '''constructs shortest path tree from origin to all other nodes.

    distances contains min number of segments (for example, flight segments)
    from origin node to other nodes.

    previous is used to store previous of each node which is used to construct the
    shortest path in reconstructShortestPath() below'''


    INFINITY = 10000
    distances = {}
    previous = {}

    for node in adjacencyList:
        distances[node] = INFINITY
        previous[node] = None
    distances[origin] = 0

    queue = Queue()
    queue.enqueue(origin)

    while not queue.empty():

        fromNode = queue.dequeue()
        for toNode in adjacencyList[fromNode]:
            if distances[toNode] == INFINITY:

                queue.enqueue(toNode)
                distances[toNode] = distances[fromNode] + 1
                previous[toNode] = fromNode

    return distances, previous




def reconstructShortestPath(origin, toNode, previous):
    '''returns a list of nodes between origin and toNode
    such that it is the shortest path'''

    result = []

    while toNode != origin:
        result.append(toNode)
        toNode = previous[toNode]

    result.append(origin)
    result.reverse()
    return result




if __name__ == '__main__':

    adjacencyList = {'A': {'B', 'C'},
                     'B': {'A'},
                     'C': {'A', 'D'},
                     'D': {'C'},
                     'E': {'F'},
                     'F': {'E'}}

    distancesFromA, previous = breadthFirstSearch(adjacencyList, 'A')
    print('\nDistances from A to other nodes is:', distancesFromA)

    print("\nShortest path between A to D is:", reconstructShortestPath('A', 'D', previous))