# CSPT19 Lecture 13

 class Graph:
    def __init__(self):
        self.graph = {}
    
    def __repr__(self):
        return str(self.graph)
        
    def addNode(self, value):
        if value not in self.graph:
            self.graph[value] = set()
    
    def removeNode(self, value):
        if value in self.graph:
            self.graph.pop(value)
            for otherNode in self.graph:
                if value in self.graph[otherNode]:
                    self.graph[otherNode].remove(value)
    
    def addEdge(self, fromNode, toNode):
        self.graph[fromNode].add(toNode)
    
    def removeEdge(self, fromNode, toNode):
        self.graph[fromNode].remove(toNode)
    
    def edgeExists(self, fromNode, toNode):
        return toNode in self.graph[fromNode]
    
    def dft(self, startingNode):
        stack = deque()
        stack.append(startingNode)
        visited = set()
        traversalList = []
        while len(stack) > 0:
            currNode = stack.pop()
            if currNode not in visited:
                traversalList.append(currNode)
                visited.add(currNode)
                for neighbor in self.adjList[currNode]:
                    stack.append(neighbor)
        print(traversalList)
        
    def recursiveDFT(self, startingNode):
        visited = set()
        self.recursiveDFTHelper(startingNode, visited)
        
    def recursiveDFTHelper(self, currNode, visited):
        visited.add(currNode)
        print(currNode)
        for neighbor in self.adjList[currNode]:
            if neighbor not in visited:
                self.recursiveDFTHelper(neighbor, visited)
                
    def bft(self, startingNode):
        queue = deque()
        queue.append(startingNode)
        visited = set()
        while len(queue) > 0:
            currNode = queue.popleft()
            if currNode not in visited:
                print(currNode)
                visited.add(currNode)
                for neighbor in self.graph[currNode]:
                    queue.append(neighbor)

    def bfs(self, startingNode, goalNode):
        queue = deque()
        visited = set()
        visited.add(startingNode)
        queue.append([startingNode])
        while len(queue) > 0:
            currPath = queue.popleft()
            currVertex = currPath[-1]
            if currVertex == goalNode:
                return currPath
            for neighbor in self.graph[currVertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    newPath = currPath.copy()
                    newPath.append(neighbor)
                    queue.append(newPath)

myGraph = Graph()
myGraph.addNode(1)
myGraph.addNode(2)
myGraph.addNode(3)
myGraph.addNode(4)
myGraph.addEdge(1, 2)
myGraph.addEdge(1, 3)
myGraph.addEdge(2, 4)
myGraph.addEdge(3, 4)
myGraph.addEdge(4, 1)
print(myGraph.bft(1))