from Node import *

def create_graph(data):
    if len(data) == 0:
        return Node(1)
    nodes = []
    for i in range(len(data)):
        nodes.append(Node(i+1))
    
    for i, node in enumerate(nodes):
        for neighbor in data[i]:
            node.neighbors.append(nodes[neighbor-1])
    return nodes[0] 

def create_2D_list(root):
    # Initialize a queue for breadth-first traversal
    queue = [root]
    # Initialize a dict to keep track of visited nodes
    visited = {}
    # Initialize a 2D list to store the graph
    graph = []
    # Initialize a dict to store the index of each node
    node_index = {}
    # Perform breadth-first traversal
    while queue:
        # Get the next node in the queue
        node = queue.pop(0)
        # Create a new list to store the neighbors of the current node
        neighbors = []
        # Iterate through the neighbors of the current node
        for neighbor in node.neighbors:
            # Append the neighbor's value to the list of neighbors
            neighbors.append(visited.get(neighbor, neighbor).data)
            # Add the neighbor to the queue if it hasn't been visited yet
            if neighbor not in visited and neighbor not in queue:
                visited[neighbor] = neighbor
                queue.append(neighbor)
        # Sort the list of neighbors
        neighbors.sort()
        # Append the current node's value and its neighbors to the 2D list
        if node not in node_index:
            node_index[node] = len(graph)
            graph.append([node.data, neighbors])
        else:
            graph[node_index[node]][1] = neighbors
    # Sort the graph by node value
    graph.sort(key=lambda x: x[0])
    # return second sublist
    return [sublist[1] for sublist in graph]

def print_graph_rec(root, visited_nodes):
    if root == None or root in visited_nodes:
        return

    visited_nodes.add(root)
    print("\t", str(root.data), end = ": {")
    for n in root.neighbors:
        print(str(n.data), end = " ")
    print("}")

    for n in root.neighbors:
        print_graph_rec(n, visited_nodes)

def print_graph(root):
    visited_nodes = set()
    print_graph_rec(root, visited_nodes)