Computation / Dependency Graph Validation and Pruning

Implement graph operations such as inserting nodes, configuring dependencies, validating structural requirements, detecting cycles, and pruning unneeded branches from a neural-network computation graph. Requirements The prompt appears in two related forms. Form A: Generic graph manager Implement a small graph API: class Graph: def insert_node(self, node_id: str) -> None: ... def add_dependency(self, src: str, dst: str) -> None: ... def validate(self) -> bool: ... Validation may include: All referenced nodes exist. No directed cycles. Dependencies appear before consumers in execution order. Required input / output nodes are present. Structural constraints are satisfied. Form B: Computation graph pruning Given a computation graph where nodes are neural-network operators such as convolution or activation, and given one requested output, return the optimal path or remove branches that are not needed to compute that output. Notes For validation, maintain adjacency lists plus in-degree counts. Cycle detection can be done with either DFS colors (unvisited / visiting / done) or Kahn's topological sort. Kahn also gives a valid execution order when the graph is acyclic. For pruning, reverse the graph from the requested output and mark every ancestor required to compute it. Any unmarked node can be removed. If the graph is a tree, this reduces to a DFS from the target; if it is a DAG, use reverse adjacency and a visited set. A clean answer usually separates three concerns: Mutation API: add node / add edge. Validation API: structural checks and cycle detection. Execution API: topological order or pruned subgraph. Preparation Implement DFS-color cycle detection and Kahn topological sort from memory. Add precise error messages instead of returning only False: missing node, cycle, duplicate edge, disconnected output. Practice explaining why inference graph pruning is reachability on reverse dependencies.