{"id":"spanning-tree-weight-check","version":"1.0.0","description":"Check that claimed edge IDs form a spanning tree and that their exact total weight equals the claimed weight.","supported_operations":["check spanning tree total weight","verify claimed tree cost","sum weights of tree edges exactly","validate spanning tree weight claim","tree weight audit","check cost of chosen network links"],"unsupported_operations":["minimality (use minimum-spanning-tree-certificate-check)","decimal or floating-point weights","weights of arbitrary non-tree edge sets"],"semantics":["Structural stage first, exactly as spanning-tree-structure-check (missing_edge, duplicate_edge, cycle_edge with a cycle witness, disconnected), in tree_edge_ids order.","Then the exact big-integer sum of the claimed edge weights must equal claimed_weight (weight_mismatch; expected = computed sum, actual = claim).","Weights and claimed_weight are canonical integer strings ^(0|-?[1-9][0-9]*)$ of at most 40 digits; tree_weight is the computed sum when the structure is valid, otherwise null.","Undirected edges {id, u, v, weight}; parallel edges and self-loops allowed; IDs compared code unit for code unit.","Graph errors throw invalid_input; counts and sizes over the limits throw limit_exceeded first.","Reference: CLRS 4th ed. (2022) section 21.1; reference_version \"clrs-4e-2022-ch21-minimum-spanning-trees\"."],"limits":{"max_vertices":500,"max_edges":2000,"max_tree_edges":2000,"max_id_bytes":64,"max_integer_digits":40},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["graph","tree_edge_ids","claimed_weight"],"properties":{"graph":{"type":"object","additionalProperties":false,"required":["vertices","edges"],"properties":{"vertices":{"type":"array","minItems":1,"maxItems":500,"items":{"type":"string","minLength":1,"maxLength":64}},"edges":{"type":"array","maxItems":2000,"items":{"type":"object","additionalProperties":false,"required":["id","u","v","weight"],"properties":{"id":{"type":"string","minLength":1,"maxLength":64},"u":{"type":"string","minLength":1,"maxLength":64},"v":{"type":"string","minLength":1,"maxLength":64},"weight":{"type":"string","pattern":"^(0|-?[1-9][0-9]*)$"}}}}}},"tree_edge_ids":{"type":"array","maxItems":2000,"items":{"type":"string","minLength":1,"maxLength":64}},"claimed_weight":{"type":"string","pattern":"^(0|-?[1-9][0-9]*)$"}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","tree_weight","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":[null,"missing_edge","duplicate_edge","cycle_edge","disconnected","weight_mismatch"]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["field","index","vertex","edge_id","expected","actual","witness_edge_ids"],"properties":{"field":{"type":"string","enum":["tree_edge_ids","graph.vertices","claimed_weight"]},"index":{"type":["integer","null"],"minimum":0},"vertex":{"type":["string","null"]},"edge_id":{"type":["string","null"]},"expected":{"type":["string","null"]},"actual":{"type":["string","null"]},"witness_edge_ids":{"type":["array","null"],"maxItems":500,"items":{"type":"string","minLength":1,"maxLength":64}}}},"tree_weight":{"type":["string","null"],"pattern":"^(0|-?[1-9][0-9]*)$"},"reference_version":{"type":"string","const":"clrs-4e-2022-ch21-minimum-spanning-trees"}}},"examples":[{"input":{"graph":{"vertices":["x","y","z"],"edges":[{"id":"xy","u":"x","v":"y","weight":"-2"},{"id":"yz","u":"y","v":"z","weight":"15"},{"id":"xz","u":"x","v":"z","weight":"40"}]},"tree_edge_ids":["xy","yz"],"claimed_weight":"13"},"output":{"valid":true,"reason":null,"first_discrepancy":null,"tree_weight":"13","reference_version":"clrs-4e-2022-ch21-minimum-spanning-trees"}},{"input":{"graph":{"vertices":["x","y","z"],"edges":[{"id":"xy","u":"x","v":"y","weight":"-2"},{"id":"yz","u":"y","v":"z","weight":"15"},{"id":"xz","u":"x","v":"z","weight":"40"}]},"tree_edge_ids":["xy","yz"],"claimed_weight":"17"},"output":{"valid":false,"reason":"weight_mismatch","first_discrepancy":{"field":"claimed_weight","index":null,"vertex":null,"edge_id":null,"expected":"13","actual":"17","witness_edge_ids":null},"tree_weight":"13","reference_version":"clrs-4e-2022-ch21-minimum-spanning-trees"}}],"execute_url":"/v1/tools/spanning-tree-weight-check/versions/1.0.0/execute"}