{"id":"network-flow-feasibility-check","version":"1.0.0","description":"Check a claimed s-t flow for capacity bounds and conservation with exact integers; returns the first bad edge or node.","supported_operations":["check if a network flow is feasible","verify flow conservation at every node","validate edge flows against capacities","check claimed value of an s-t flow","find the first node where flow is not conserved","audit a flow assignment for a capacitated graph"],"unsupported_operations":["computing a maximum flow (use maximum-flow-certificate-check to verify one)","flows with lower bounds, costs or multiple commodities","fractional or floating-point flow values","undirected edges"],"semantics":["Reference: CLRS 4th ed. (2022) section 24.1, flow network, capacity constraint 0 <= f(u,v) <= c(u,v), flow conservation at every vertex other than s and t, value |f| = flow out of s minus flow into s; reference_version is returned with every result.","Network: nodes are 2-2000 unique strings (1-64 code points, exact comparison, no Unicode normalization); edges are 0-10000 directed {from, to, capacity} entries identified by their array index; parallel, antiparallel and self-loop edges are allowed; source and sink are distinct declared nodes.","Integers: capacities are non-negative, flows may be signed; each is a JSON safe integer or a canonical decimal string of at most 30 digits; arithmetic is exact (BigInt).","claim.flows lists one flow per edge in edge order; claim.value (optional) is the claimed flow value.","Check order: flows length (reason flow_length_mismatch), then edges by index (negative_flow, then capacity_exceeded), then nodes in declared order except source and sink (conservation_violated, with inflow and outflow), then the value (value_mismatch).","first_discrepancy.kind is claim, edge, node or value; flow_value is the exact net flow out of the source whenever the flow is feasible, else null."],"limits":{"max_nodes":2000,"max_edges":10000,"max_id_chars":64,"max_integer_digits":30},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["nodes","edges","source","sink","claim"],"properties":{"nodes":{"type":"array","minItems":2,"maxItems":2000,"items":{"type":"string","minLength":1,"maxLength":64}},"edges":{"type":"array","maxItems":10000,"items":{"type":"object","additionalProperties":false,"required":["from","to","capacity"],"properties":{"from":{"type":"string","minLength":1,"maxLength":64},"to":{"type":"string","minLength":1,"maxLength":64},"capacity":{"anyOf":[{"type":"integer","minimum":0},{"type":"string","minLength":1,"maxLength":30,"pattern":"^(0|[1-9][0-9]*)$"}]}}}},"source":{"type":"string","minLength":1,"maxLength":64},"sink":{"type":"string","minLength":1,"maxLength":64},"claim":{"type":"object","additionalProperties":false,"required":["flows"],"properties":{"flows":{"type":"array","maxItems":10000,"items":{"anyOf":[{"type":"integer"},{"type":"string","minLength":1,"maxLength":31,"pattern":"^(0|-?[1-9][0-9]*)$"}]}},"value":{"anyOf":[{"type":"integer"},{"type":"string","minLength":1,"maxLength":31,"pattern":"^(0|-?[1-9][0-9]*)$"}]}}}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","flow_value","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":[null,"flow_length_mismatch","negative_flow","capacity_exceeded","conservation_violated","value_mismatch"]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["kind"],"properties":{"kind":{"type":"string","enum":["claim","edge","node","value"]},"edge_index":{"type":"integer","minimum":0},"from":{"type":"string"},"to":{"type":"string"},"node":{"type":"string"},"position":{"type":"integer","minimum":0},"flow":{"type":"string"},"capacity":{"type":"string"},"inflow":{"type":"string"},"outflow":{"type":"string"},"claimed":{"type":"string"},"actual":{"type":"string"},"path":{"type":"array","maxItems":2000,"items":{"type":"object","additionalProperties":false,"required":["edge_index","direction"],"properties":{"edge_index":{"type":"integer","minimum":0},"direction":{"type":"string","enum":["forward","backward"]}}}},"path_nodes":{"type":"array","maxItems":2001,"items":{"type":"string"}},"residual_capacity":{"type":"string"}}},"flow_value":{"type":["string","null"]},"reference_version":{"type":"string"}}},"examples":[{"input":{"nodes":["s","v1","v2","v3","v4","t"],"edges":[{"from":"s","to":"v1","capacity":16},{"from":"s","to":"v2","capacity":13},{"from":"v2","to":"v1","capacity":4},{"from":"v1","to":"v3","capacity":12},{"from":"v3","to":"v2","capacity":9},{"from":"v2","to":"v4","capacity":14},{"from":"v4","to":"v3","capacity":7},{"from":"v3","to":"t","capacity":20},{"from":"v4","to":"t","capacity":4}],"source":"s","sink":"t","claim":{"flows":[11,8,1,12,4,11,7,15,4],"value":19}},"output":{"valid":true,"reason":null,"first_discrepancy":null,"flow_value":"19","reference_version":"CLRS 4th ed. (2022) ch. 24 Maximum Flow: flow networks, cuts, residual networks, max-flow min-cut theorem; r55-flow-certificate-verifiers@1.0.0"}},{"input":{"nodes":["s","v1","v2","v3","v4","t"],"edges":[{"from":"s","to":"v1","capacity":16},{"from":"s","to":"v2","capacity":13},{"from":"v2","to":"v1","capacity":4},{"from":"v1","to":"v3","capacity":12},{"from":"v3","to":"v2","capacity":9},{"from":"v2","to":"v4","capacity":14},{"from":"v4","to":"v3","capacity":7},{"from":"v3","to":"t","capacity":20},{"from":"v4","to":"t","capacity":4}],"source":"s","sink":"t","claim":{"flows":[11,8,1,12,4,11,7,16,4]}},"output":{"valid":false,"reason":"conservation_violated","first_discrepancy":{"kind":"node","node":"v3","inflow":"19","outflow":"20"},"flow_value":null,"reference_version":"CLRS 4th ed. (2022) ch. 24 Maximum Flow: flow networks, cuts, residual networks, max-flow min-cut theorem; r55-flow-certificate-verifiers@1.0.0"}}],"execute_url":"/v1/tools/network-flow-feasibility-check/versions/1.0.0/execute"}