@@ -0,0 +1,3241 @@
+from collections import deque, defaultdict%0A%0A%0APENDING = 0%0APROCESSED = 1%0AIN_PROGRESS = -1%0A%0A%22%22%22%0AThis code shows how to get a topological sort of a DAG, using two%0Aimplementations:%0A%0A1. Kahn's algorithm%0A2. DFS%0A%0ASee: https://en.wikipedia.org/wiki/Topological_sorting#Algorithms%0A%0ATo illustrate how to use this algorithm, I took the following problem from LeetCode:%0Ahttps://leetcode.com/problems/course-schedule/%0A%22%22%22%0Aclass Solution:%0A    def canFinish(self, num_courses: int, prerequisites: list%5Blist%5Bint%5D%5D) -%3E bool:%0A        if not prerequisites:%0A            return True%0A        self.graph = self.to_graph(num_courses, prerequisites)%0A        taken_courses, found_cycle = self.get_topological_sort_kahn()%0A        return not found_cycle and len(taken_courses) == num_courses%0A%0A    def to_graph(self, num_courses: int, prerequisites: list%5B(int, int)%5D) -%3E dict%5Bint, list%5Bint%5D%5D:%0A        graph = defaultdict(list)%0A        # Add independent courses%0A        for i in range(num_courses):%0A            graph%5Bi%5D%0A        # Add courses with prerequisites%0A        for (course, prereq) in prerequisites:%0A            graph%5Bcourse%5D.append(prereq)%0A        return graph%0A%0A    # --------------------------------------------------%0A    # Topological sort Kahn's algorithm%0A    # --------------------------------------------------%0A%0A    def get_topological_sort_kahn(self) -%3E list%5Bint%5D:%0A        order = %5B%5D%0A        nodes = self.get_nodes_to_edges()%0A        no_incoming_nodes = self.get_no_incoming_nodes(nodes)%0A        while no_incoming_nodes:%0A            node = no_incoming_nodes.pop()%0A            order.append(node)%0A            neighbors = self.graph%5Bnode%5D%0A            for neig in neighbors:%0A                nodes%5Bneig%5D -= 1%0A                if nodes%5Bneig%5D == 0:%0A                    no_incoming_nodes.append(neig)%0A%0A        return order, len(order) != len(self.graph)%0A%0A    def get_no_incoming_nodes(self, nodes: dict%5Bint, int%5D) -%3E list%5Bint%5D:%0A        no_incoming_nodes = %5B%5D%0A        for node, edges in nodes.items():%0A            if edges == 0:%0A                no_incoming_nodes.append(node)%0A%0A        return no_incoming_nodes%0A%0A    def get_nodes_to_edges(self) -%3E dict:%0A        nodes = defaultdict(int)%0A        for node, neighbors in self.graph.items():%0A            nodes%5Bnode%5D%0A            for neig in neighbors:%0A                nodes%5Bneig%5D += 1%0A        return nodes%0A%0A    # --------------------------------------------------%0A    # Topological sort DFS%0A    # --------------------------------------------------%0A%0A    def get_topological_sort_dfs(self) -%3E list:%0A        order = deque()%0A        visited = %5BPENDING%5D * len(self.graph)%0A        self.found_cycle = False%0A        for node in self.graph:%0A            if self.found_cycle:%0A                break%0A            self.dfs(node, order, visited)%0A%0A        return list(order), self.found_cycle%0A%0A    def dfs(self, node: int, order: deque%5Bint%5D, visited: list%5Bint%5D) -%3E None:%0A        if visited%5Bnode%5D == PROCESSED:%0A            return%0A%0A        if visited%5Bnode%5D == IN_PROGRESS:%0A            self.found_cycle = True%0A            return%0A%0A        visited%5Bnode%5D = IN_PROGRESS%0A        neighbors = self.graph%5Bnode%5D%0A        for neig in neighbors:%0A            self.dfs(neig, order, visited)%0A%0A        order.appendleft(node)%0A        visited%5Bnode%5D = PROCESSED%0A

Add two implementations of topological sort