{"id":"graph-dag-longest-path","version":"1.0.0","description":"Return a longest node-weighted path in a DAG, where path weight is the sum of node durations.","supported_operations":["graph dag longest path","longest node-weighted path in a dag","dag longest duration chain"],"unsupported_operations":["edge weights","longest path in cyclic graphs","negative durations","k shortest paths"],"semantics":["Path weight is the sum of node durations along the path, not edge weights.","The graph must be a DAG under Kahn order (smallest declared index among remaining indegree-0 nodes); a cycle including a self-loop is rejected.","Empty graph returns path [] and length 0.","In Kahn order, dist[v] equals duration[v] plus the maximum dist of its predecessors, or duration[v] if it has none.","When several predecessors share that incoming maximum, the parent is the predecessor with the smallest declared index.","The reported path ends at a maximum-dist node, breaking ties by smallest declared index, and is reconstructed through those parents.","Duration values and the path length are canonical non-negative base-10 integer strings with at most 18 digits."],"limits":{"max_nodes":2000,"max_edges":10000,"max_node_id_bytes":256,"max_duration_digits":18},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["nodes","edges","durations"],"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}}}},"durations":{"type":"object","additionalProperties":{"type":"string","pattern":"^(0|[1-9][0-9]*)$","maxLength":18}}}},"output_schema":{"type":"object","additionalProperties":false,"required":["path","length"],"properties":{"path":{"type":"array","items":{"type":"string"}},"length":{"type":"string","pattern":"^(0|[1-9][0-9]*)$","maxLength":18}}},"examples":[{"input":{"nodes":["design","build","test","ship"],"edges":[{"from":"design","to":"build"},{"from":"build","to":"test"},{"from":"design","to":"test"},{"from":"test","to":"ship"}],"durations":{"design":"3","build":"5","test":"2","ship":"1"}},"output":{"path":["design","build","test","ship"],"length":"11"}}],"execute_url":"/v1/tools/graph-dag-longest-path/versions/1.0.0/execute"}