An AMD ROCm dynamic neural network execution graph is represented as a directed graph. An edge A -> B means operation A must execute before operation B. Cyclic dependencies prevent scheduling. Detect each cycle, resolve it by removing one deterministic back edge, and return the repaired graph's execution order.
Use a repeated DFS strategy. During each DFS, process nodes and neighbors in lexicographic order. When DFS encounters an edge from the current node to an active ancestor, record the cycle and remove that back edge. Continue until the graph is acyclic. Then return a lexicographically smallest topological ordering using Kahn's algorithm with a min-heap.
Implement resolve_dependencies(graph), where graph is a dictionary mapping string node names to lists of string neighbors. Nodes that appear only as neighbors are valid nodes with no outgoing edges. Return a dictionary with:
cycles: detected cycles, each represented as a list beginning and ending at the same node.removed_edges: back edges removed in detection order.order: the repaired graph's lexicographically smallest topological ordering.def resolve_dependencies(graph):