Find the nodes that contribute to output_id by following parent IDs backward. Include the output itself and exclude disconnected nodes. Each input node is a dictionary with id, data, grad, op, and parents; only id and parents determine reachability.
Return a tuple containing two lists: reachable node IDs as strings in original node-list order, then edges as two-item lists containing the parent ID followed by the child ID. Order edges by each reachable child’s position in nodes, then by its parent-list order; retain repeated edges.
Input: nodes=[{'id':'a','data':2.0,'grad':0.0,'op':'','parents':[]},{'id':'b','data':-3.0,'grad':0.0,'op':'','parents':[]},{'id':'c','data':10.0,'grad':0.0,'op':'','parents':[]},{'id':'f','data':-2.0,'grad':0.0,'op':'','parents':[]},{'id':'unused','data':99.0,'grad':0.0,'op':'','parents':[]},{'id':'e','data':-6.0,'grad':0.0,'op':'*','parents':['a','b']},{'id':'d','data':4.0,'grad':0.0,'op':'+','parents':['e','c']},{'id':'L','data':-8.0,'grad':0.0,'op':'*','parents':['d','f']}], output_id='L'
Output: (['a','b','c','f','e','d','L'],[['a','e'],['b','e'],['e','d'],['c','d'],['d','L'],['f','L']])
Explanation: The unused leaf has no path to L, while the remaining records form L's dependency closure.
Input: nodes=[{'id':'x','data':1.0,'grad':0.0,'op':'','parents':[]},{'id':'y','data':2.0,'grad':0.0,'op':'','parents':[]}], output_id='y'
Output: (['y'],[])
Input: nodes=[{'id':'x','data':2.0,'grad':0.0,'op':'','parents':[]},{'id':'y','data':3.0,'grad':0.0,'op':'','parents':[]},{'id':'sum','data':5.0,'grad':0.0,'op':'+','parents':['x','y']},{'id':'out','data':10.0,'grad':0.0,'op':'*','parents':['sum','x']}], output_id='out'
Output: (['x','y','sum','out'],[['x','sum'],['y','sum'],['sum','out'],['x','out']])
A set can track node IDs already visited through shared paths.
List iteration preserves the original node and parent order.
Accepts: array
Accepts: string
Find the nodes that contribute to output_id by following parent IDs backward. Include the output itself and exclude disconnected nodes. Each input node is a dictionary with id, data, grad, op, and parents; only id and parents determine reachability.
Return a tuple containing two lists: reachable node IDs as strings in original node-list order, then edges as two-item lists containing the parent ID followed by the child ID. Order edges by each reachable child’s position in nodes, then by its parent-list order; retain repeated edges.
Input: nodes=[{'id':'a','data':2.0,'grad':0.0,'op':'','parents':[]},{'id':'b','data':-3.0,'grad':0.0,'op':'','parents':[]},{'id':'c','data':10.0,'grad':0.0,'op':'','parents':[]},{'id':'f','data':-2.0,'grad':0.0,'op':'','parents':[]},{'id':'unused','data':99.0,'grad':0.0,'op':'','parents':[]},{'id':'e','data':-6.0,'grad':0.0,'op':'*','parents':['a','b']},{'id':'d','data':4.0,'grad':0.0,'op':'+','parents':['e','c']},{'id':'L','data':-8.0,'grad':0.0,'op':'*','parents':['d','f']}], output_id='L'
Output: (['a','b','c','f','e','d','L'],[['a','e'],['b','e'],['e','d'],['c','d'],['d','L'],['f','L']])
Explanation: The unused leaf has no path to L, while the remaining records form L's dependency closure.
Input: nodes=[{'id':'x','data':1.0,'grad':0.0,'op':'','parents':[]},{'id':'y','data':2.0,'grad':0.0,'op':'','parents':[]}], output_id='y'
Output: (['y'],[])
Input: nodes=[{'id':'x','data':2.0,'grad':0.0,'op':'','parents':[]},{'id':'y','data':3.0,'grad':0.0,'op':'','parents':[]},{'id':'sum','data':5.0,'grad':0.0,'op':'+','parents':['x','y']},{'id':'out','data':10.0,'grad':0.0,'op':'*','parents':['sum','x']}], output_id='out'
Output: (['x','y','sum','out'],[['x','sum'],['y','sum'],['sum','out'],['x','out']])
A set can track node IDs already visited through shared paths.
List iteration preserves the original node and parent order.
Accepts: array
Accepts: string