Topological Sorting – Python 3 (Week 14 – 06)

"""
Definition for a Directed graph node
class DirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []
"""


class Solution:
    """
    @param: graph: A list of Directed graph node
    @return: Any topological order for the given graph.
    """
    def topSort(self, graph):
        # write your code here
        node_in_degree = self.get_in_degree(graph)
        
        queue = collections.deque([node for node in graph if node_in_degree[node] == 0])
        torder = []
        while queue:
            cur_node = queue.popleft()
            torder.append(cur_node)
            for neighbor in cur_node.neighbors:
                node_in_degree[neighbor] -= 1
                if node_in_degree[neighbor] == 0:
                    queue.append(neighbor)
                    
        if len(torder) != len(graph):
            return[]
        
        return torder
        

        
    def get_in_degree(self, graph):
        node_in_degree = {x: 0 for x in graph}
        for node in graph:
            for neighbor in node.neighbors:
                node_in_degree[neighbor] += 1
        return node_in_degree