from typing import Tuple
from typing import Union
from typing import Dict
from typing import List
from typing import Set


def build_reverse_graph(graph: dict) -> Tuple[Union[list, set], Dict[int, List[int]]]:
    """Take the data from a Tracks layer graph and reverse it.

    Parameters
    ----------
    graph : dict
        A dictionary encoding the graph, taken from the napari.Tracks layer.


    Returns
    -------
    roots : int, None
        A sorted list of integers represent the root node IDs
    reverse_graph : dict
        A reversed graph representing children of each parent node.
    """
    reverse_graph = {}
    roots: Set[int] = set()

    # iterate over the graph, reverse it and find the root nodes
    for node, parents in graph.items():
        for parent in parents:
            if parent not in reverse_graph:
                reverse_graph[parent] = [node]
            else:
                reverse_graph[parent].append(node)

            if parent not in graph.keys():
                roots.add(parent)

    # sort the roots
    sorted_roots = sorted(list(roots))

    return sorted_roots, reverse_graph