Trouble with Topological Sorting in Python - Cycle Detection optimization guide as Expected
Quick question that's been bugging me - I'm working on a personal project and I'm currently implementing a topological sort for a directed acyclic graph (DAG) in Python using Kahn's algorithm. However, I'm working with a question where the algorithm seems to be returning unexpected results when the graph has cycles, even though it is supposed to detect and handle them. Here's what I have so far: ```python from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) self.indegree = defaultdict(int) def add_edge(self, u, v): self.graph[u].append(v) self.indegree[v] += 1 if u not in self.indegree: self.indegree[u] = 0 def topological_sort(self): queue = [] for node in self.indegree: if self.indegree[node] == 0: queue.append(node) sorted_order = [] while queue: current = queue.pop(0) sorted_order.append(current) for neighbor in self.graph[current]: self.indegree[neighbor] -= 1 if self.indegree[neighbor] == 0: queue.append(neighbor) # Cycle detection if len(sorted_order) != len(self.indegree): raise Exception('Graph has at least one cycle!') return sorted_order ``` In this implementation, I add edges to the graph and attempt to perform a topological sort. I expect it to raise an exception if it detects a cycle, but sometimes when I input a graph with a cycle, it still returns a sorted order without raising an exception. For instance, when I run the following code: ```python g = Graph() g.add_edge(1, 2) g.add_edge(2, 3) g.add_edge(3, 1) # This creates a cycle try: print(g.topological_sort()) except Exception as e: print(e) ``` Instead of catching the cycle, I often see the output like `[1, 2, 3]`, which is incorrect. I suspect the scenario might be in how I'm updating the indegree of nodes or the way I'm handling the queue. I've tried debugging by printing the indegree values and the queue state, but I need to pinpoint the behavior. Any insights on what might be going wrong or how to effectively handle cycle detection in this context would be greatly appreciated! Has anyone else encountered this? I'd really appreciate any guidance on this. This is happening in both development and production on CentOS. I'd really appreciate any guidance on this.