# CSPT 19 Lecture 11

from collections import deque

def breadthFirstTraversal(graph, startingNode):
    queue = deque()
    queue.append(startingNode)
    visited = set()
    while len(queue) > 0:
        currNode = queue.popleft()
        if currNode not in visited:
            visited.add(currNode)
            print(currNode)
            for neighbor in graph[currNode]:
                queue.append(neighbor)

def recursiveDepthFirstTraversal(graph, startingNode):
    visited = set()
    recursiveDepthFirstTraversalHelper(graph, starting, visited)

def recursiveDepthFirstTraversalHelper(graph, currNode, visited):
    visited.add(currNode)
    print(currNode)
    for neighbor in graph[currNode]:
        if neighbor not in visited:
            recursiveDepthFirstTraversalHelper(graph, neighbor, visited)

"""
{ 1: {(2, WEIGHT),(3, WEIGHT),(4, WEIGHT)}}
"""  
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]

adjList = {1: {2, 3}, 2: {4, 5}, 3:{4}, 4:{1}, 5: {}}
depthFirstTraversal(adjList, 1)