{"id":"graph-transitive-reduction","version":"1.0.0","description":"Compute the transitive reduction of a DAG: keep an edge u→v iff the original graph has no directed path from u to v of length at least 2.","supported_operations":["graph transitive reduction","DAG transitive reduction","remove redundant DAG edges"],"unsupported_operations":["reduction of cyclic graphs","undirected transitive reduction","minimum equivalent graph on cycles","counting paths"],"semantics":["Input is a directed simple graph that must be a DAG; self-loops and other cycles throw invalid_input with a message containing cycle.","Output nodes is the input node array in declared order.","A directed edge u→v is kept iff the original graph has no directed path from u to v of length at least 2.","Kept edges appear in original declared edge order.","Empty graph {nodes:[], edges:[]} is unchanged.","Reachability is directed; this is not an undirected reduction."],"limits":{"max_nodes":2000,"max_edges":10000,"max_node_id_bytes":256},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["nodes","edges"],"properties":{"nodes":{"type":"array","maxItems":2000,"items":{"type":"string","minLength":1,"maxLength":256}},"edges":{"type":"array","maxItems":10000,"items":{"type":"object","additionalProperties":false,"required":["from","to"],"properties":{"from":{"type":"string","minLength":1,"maxLength":256},"to":{"type":"string","minLength":1,"maxLength":256}}}}}},"output_schema":{"type":"object","additionalProperties":false,"required":["nodes","edges"],"properties":{"nodes":{"type":"array","maxItems":2000,"items":{"type":"string","minLength":1,"maxLength":256}},"edges":{"type":"array","maxItems":10000,"items":{"type":"object","additionalProperties":false,"required":["from","to"],"properties":{"from":{"type":"string","minLength":1,"maxLength":256},"to":{"type":"string","minLength":1,"maxLength":256}}}}}},"examples":[{"input":{"nodes":["build","test","deploy"],"edges":[{"from":"build","to":"test"},{"from":"test","to":"deploy"},{"from":"build","to":"deploy"}]},"output":{"nodes":["build","test","deploy"],"edges":[{"from":"build","to":"test"},{"from":"test","to":"deploy"}]}}],"execute_url":"/v1/tools/graph-transitive-reduction/versions/1.0.0/execute"}