# CSPT27 Lecture 13

from collections import deque
class Graph:
    def __init__(self):
        self.adjList = {}
    def __repr__(self):
        return str(self.adjList)
    def addEdge(self, source, destination):
        if source not in self.adjList or destination not in self.adjList:
            return
        self.adjList[source].add(destination)
    def removeEdge(self, source, destination):
        if source not in self.adjList or destination not in self.adjList:
            return
        self.adjList[source].remove(destination)
    def edgeExists(self, source, destination):
        if source not in self.adjList or destination not in self.adjList:
            return
        return destination in self.adjList[source]
    def addVertex(self, newNode):
        if newNode in self.adjList:
            return
        self.adjList[newNode] = set()
    def removeVertex(self, nodeToRemove):
        if nodeToRemove not in self.adjList:
            return
        self.adjList.pop(nodeToRemove)
        for (vertex, neighbors) in self.adjList.items():
            if nodeToRemove in neighbors:
                neighbors.remove(nodeToRemove)
    def dftIterative(self, startingNode):
        stack = deque()
        stack.append(startingNode)
        visited = set()
        while len(stack) > 0:
            curr = stack.pop()
            if curr not in visited:
                print(curr)
                visited.add(curr)
                for neighbor in self.adjList[curr]:
                    stack.append(neighbor)
    def dftRecursive(self, startingNode):
        visited = set()
        self.dftRecursiveHelper(startingNode, visited)
    def dftRecursiveHelper(self, currNode, visited):
        visited.add(currNode)
        print(currNode)
        for neighbor in self.adjList[currNode]:
            if neighbor not in visited:
                self.dftRecursiveHelper(neighbor, visited)
    def bfsIterative(self, startingNode, destinationNode):
        queue = deque()
        visited = set()
        visited.add(startingNode)
        queue.append(startingNode)
        while len(queue) > 0:
            curr = queue.popleft()
            if curr == destinationNode:
                return curr
            for neighbor in self.adjList[curr]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
    def bftIterative(self, startingNode):
        queue = deque()
        visited = set()
        visited.add(startingNode)
        queue.append(startingNode)
        res = []
        while len(queue) > 0:
            curr = queue.popleft()
            res.append(curr)
            for neighbor in self.adjList[curr]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return res
g = Graph()
g.addVertex(1)
g.addVertex(2)
g.addVertex(3)
g.addVertex(4)
g.addEdge(1, 2)
g.addEdge(2, 4)
g.addEdge(1, 3)
g.addEdge(3, 4)
g.addEdge(4, 1)
print(g.bftIterative(1))