Detect cycles in a dependency graph using Tarjan's algorithm to find strongly connected components. Args: graph: A dependency graph represented as adjacency lists (node -> set of dependencies) Returns: A list of lists, where each inner list c
(graph: Dict[str, Set[str]])
| 16 | filter_leaf_nodes, |
| 17 | ) |
| 18 | from codewiki.src.be.dependency_analyzer.models.core import Node |
| 19 | |
| 20 | logger = logging.getLogger(__name__) |
| 21 | |
| 22 | |
| 23 | def detect_cycles(graph: dict[str, set[str]]) -> list[list[str]]: |
| 24 | """ |
| 25 | Detect cycles in a dependency graph using Tarjan's algorithm to find |
| 26 | strongly connected components. |
| 27 | |
| 28 | Args: |
| 29 | graph: A dependency graph represented as adjacency lists |
| 30 | (node -> set of dependencies) |
| 31 | |
| 32 | Returns: |
| 33 | A list of lists, where each inner list contains the nodes in a cycle |
| 34 | """ |
| 35 | # Implementation of Tarjan's algorithm |
| 36 | index_counter = [0] |
| 37 | index = {} # node -> index |
| 38 | lowlink = {} # node -> lowlink value |
| 39 | onstack = set() # nodes currently on the stack |
| 40 | stack = [] # stack of nodes |
| 41 | result = [] # list of cycles (strongly connected components) |
| 42 | |
| 43 | def strongconnect(node): |
| 44 | # Set the depth index for node |
| 45 | index[node] = index_counter[0] |
| 46 | lowlink[node] = index_counter[0] |
| 47 | index_counter[0] += 1 |
| 48 | stack.append(node) |
| 49 | onstack.add(node) |
| 50 | |
| 51 | # Consider successors |
| 52 | for successor in graph.get(node, set()): |
| 53 | if successor not in index: |
| 54 | # Successor has not yet been visited; recurse on it |
| 55 | strongconnect(successor) |
| 56 | lowlink[node] = min(lowlink[node], lowlink[successor]) |
| 57 | elif successor in onstack: |
| 58 | # Successor is on the stack and hence in the current SCC |
| 59 | lowlink[node] = min(lowlink[node], index[successor]) |
| 60 | |
| 61 | # If node is a root node, pop the stack and generate an SCC |
| 62 | if lowlink[node] == index[node]: |
| 63 | # Start a new strongly connected component |
| 64 | scc = [] |
| 65 | while True: |
| 66 | successor = stack.pop() |
| 67 | onstack.remove(successor) |
| 68 | scc.append(successor) |
| 69 | if successor == node: |
| 70 | break |
| 71 | |
| 72 | # Only include SCCs with more than one node (actual cycles) |
| 73 | if len(scc) > 1: |
| 74 | result.append(scc) |
| 75 |
no test coverage detected