# CSPT23 Lecture 13
## Sandbox

from collections import deque
class Graph:
    def __init__(self):
        self.graph = {}
    def __repr__(self):
        return str(self.graph)
    def addNode(self, node):
        if node not in self.graph:
            self.graph[node] = set()
    def removeNode(self, node):
        if node in self.graph:
            self.graph.pop(node)
            for otherNode in self.graph:
                if node in self.graph[otherNode]:
                    self.graph[otherNode].remove(node)
    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):
        if fromNode not in self.graph:
            return False
        return toNode in self.graph[fromNode]
    def bft(self, startingNode):
        queue = deque()
        queue.append(startingNode)
        visited = set()
        while len(queue) > 0:
            curr = queue.popleft()
            if curr not in visited:
                visited.add(curr)
                print(curr)
                for neighbor in self.graph[curr]:
                    queue.append(neighbor)
    def dftIterative(self, startingNode):
        stack = deque()
        stack.append(startingNode)
        visited = set()
        while len(stack) > 0:
            curr = stack.pop()
            if curr not in visited:
                visited.add(curr)
                print(curr)
                for neighbor in self.graph[curr]:
                    stack.append(neighbor)
    def dftRecursive(self, startingNode):
        visited = set()
        self.dftRecursiveHelper(startingNode, visited)
    def dftRecursiveHelper(self, node, visited):
        visited.add(node)
        print(node)
        for neighbor in self.graph[node]:
            if neighbor not in visited:
                self.dftRecursiveHelper(neighbor, visited)
    
graph = Graph()
graph.addNode(1)
graph.addNode(2)
graph.addNode(3)
graph.addNode(4)
graph.addEdge(1, 2)
graph.addEdge(1, 3)
graph.addEdge(2, 4)
graph.addEdge(3, 4)
graph.addEdge(4, 1)
graph.bft(1)