How to implement guide with finding strongly connected components in a directed graph using tarjan's algorithm in python
Hey everyone, I'm running into an issue that's driving me crazy. I'm converting an old project and I've been struggling with this for a few days now and could really use some help. I'm trying to implement Tarjan's algorithm to find strongly connected components (SCCs) in a directed graph using Python. I've followed the pseudocode closely, but I keep working with an scenario where my results don't match expected outputs on certain graphs, specifically graphs with cycles. Here's a simplified version of my code: ```python class Graph: def __init__(self, vertices): self.V = vertices # No. of vertices self.graph = {} # adjacency list for i in range(vertices): self.graph[i] = [] def add_edge(self, u, v): self.graph[u].append(v) def tarjan_scc(self): index = 0 stack = [] low_link = [-1] * self.V index_mapping = [-1] * self.V on_stack = [False] * self.V sccs = [] def strongconnect(v): nonlocal index index_mapping[v] = index low_link[v] = index index += 1 stack.append(v) on_stack[v] = True for w in self.graph[v]: if index_mapping[w] == -1: strongconnect(w) low_link[v] = min(low_link[v], low_link[w]) elif on_stack[w]: low_link[v] = min(low_link[v], index_mapping[w]) if low_link[v] == index_mapping[v]: scc = [] while True: w = stack.pop() on_stack[w] = False scc.append(w) if w == v: break sccs.append(scc) for i in range(self.V): if index_mapping[i] == -1: strongconnect(i) return sccs # Example usage G = Graph(5) G.add_edge(0, 1) G.add_edge(1, 2) G.add_edge(2, 0) G.add_edge(1, 3) G.add_edge(3, 4) print(G.tarjan_scc()) # Expected [[4], [0, 1, 2], [3]] ``` My scenario arises because when I run the above code, I get a different result than expected for graphs with cycles. Specifically, it outputs `[[4], [1, 2, 0], [3]]` instead of `[[4], [0, 1, 2], [3]]`. I suspect there might be an scenario with how I'm calculating `low_link`, as I notice it doesn't seem to be correctly identifying the roots of the SCCs. I've tried debugging by printing out the index and low_link values at each recursive call, but I need to seem to isolate the question. Can anyone point me in the right direction to fix this? I'm using Python 3.9 and testing with simple graphs that have a few cycles. Has anyone else encountered this? What are your experiences with this? This issue appeared after updating to Python latest. Is this even possible? Any ideas what could be causing this? Could someone point me to the right documentation? I've been using Python for about a year now.