#Topological Sorting

from subprocess import getstatusoutput
from collections import defaultdict
import json
def topological_sort(digraph):
    # digraph is a dictionary:
    #   key: a node
    # value: a set of adjacent neighboring nodes
    print("initial len of dic ",len(digraph))
    # construct a dictionary mapping nodes to their
    # indegrees
    dic = digraph.copy()  # we need to make a shallow copy otherwise we change the length of dic while iterating over it which will raise an exception
    indegrees = {node : 0 for node in digraph}
    #indegrees = defaultdict(int)


    for node in dic:
        for neighbor in dic[node]:

            # to check if the node is present in the input dict as well as indedrees
            if neighbor not in indegrees:
                indegrees[neighbor]=0
            if neighbor not in digraph:
                digraph[neighbor]=''
            indegrees[neighbor] += 1
    #print("indegrees  ",indegrees)
    print("Total number of variables present ",len(digraph))
    # track nodes with no incoming edges
    nodes_with_no_incoming_edges = []
    for node in digraph:
        if indegrees[node] == 0:
            nodes_with_no_incoming_edges.append(node)
    #print("nodes_with_no_incoming_edges ",len(nodes_with_no_incoming_edges))

    # initially, no nodes in our ordering
    topological_ordering = [] 

    # as long as there are nodes with no incoming edges
    # that can be added to the ordering 
    while len(nodes_with_no_incoming_edges) > 0:

        # add one of those nodes to the ordering
        node = nodes_with_no_incoming_edges.pop()
        topological_ordering.append(node)
        #print("topological_ordering.append ",node)

        # decrement the indegree of that node's neighbors
        for neighbor in digraph[node]:
            indegrees[neighbor] -= 1
            if indegrees[neighbor] == 0:
                nodes_with_no_incoming_edges.append(neighbor)
    #print("status of top searhc  ",indegrees)
    # we've run out of nodes with no incoming edges
    # did we add all the nodes or find a cycle?
    if len(topological_ordering) == len(digraph):
        #print(len(digraph), topological_ordering)
        return topological_ordering[::-1]  # got them all
    else:
        #print(topological_ordering[::-1])
        print("digraaph",len(digraph))
        print(len(dic))
        print("len_topo" ,len(topological_ordering))
        #print("topo ", topological_ordering[::-1])
        raise Exception("Graph has a cycle! No topological ordering exists.")

#print(topological_sort({'E':'D','A': ['B','C'], 'D': ['E','C'], 'B':'F','F':'E'}))




a,b=(getstatusoutput('python ./convert_txtfile_dict.py'))
print(type(b))
str_d=b[28:-1]
str_d= str_d.replace("'",'"')
final_dic=json.loads(str_d)
print(topological_sort(final_dic))