implementing Topological Sorting of Directed Acyclic Graphs in Python - Cycle Detection
I'm maintaining legacy code that I'm trying to debug I've encountered a strange issue with I'm stuck on something that should probably be simple. I'm currently implementing a topological sort algorithm for a directed acyclic graph (DAG) in Python, but I'm working with an scenario where my algorithm incorrectly identifies the graph as containing cycles. My implementation is based on Kahn's algorithm, and it seems to unexpected result on certain graphs that I believe are actually acyclic. Here’s the code I have so far: ```python from collections import defaultdict, deque class Graph: def __init__(self): self.graph = defaultdict(list) self.in_degree = defaultdict(int) def add_edge(self, u, v): self.graph[u].append(v) self.in_degree[v] += 1 if u not in self.in_degree: self.in_degree[u] = 0 def topological_sort(self): queue = deque([node for node in self.in_degree if self.in_degree[node] == 0]) sorted_order = [] while queue: node = queue.popleft() sorted_order.append(node) for neighbor in self.graph[node]: self.in_degree[neighbor] -= 1 if self.in_degree[neighbor] == 0: queue.append(neighbor) if len(sorted_order) != len(self.in_degree): print("Graph has at least one cycle!") return sorted_order # Sample graph g = Graph() g.add_edge(5, 2) g.add_edge(5, 0) g.add_edge(4, 0) g.add_edge(4, 1) g.add_edge(2, 3) g.add_edge(3, 1) result = g.topological_sort() print("Topological Sort:", result) ``` When I run this code with the sample edges I provided, it outputs "Graph has at least one cycle!" even though I believe the graph is acyclic. I suspect it might be related to how I'm detecting the cycle, especially at the point where I check the length of `sorted_order`. Here's the output I receive for the provided edges: ``` Graph has at least one cycle! Topological Sort: [5, 4, 2, 3, 1, 0] ``` I've tried debugging by printing the contents of the `queue` and `in_degree` at various stages, but I’m not seeing anything obvious. Could someone guide to identify what might be going wrong? Are there any edge cases I should be aware of? Alternatively, is there a better way to approach cycle detection in this context? I’m using Python 3.9.7 with no additional libraries. Thank you! My development environment is Linux. Any ideas what could be causing this? I'm on Debian using the latest version of Python. Thanks for taking the time to read this! Any pointers in the right direction? I'm using Python 3.11 in this project.