{"id":"spanning-tree-structure-check","version":"1.0.0","description":"Check that claimed edge IDs form a spanning tree of a graph; reports the first missing, repeated or cyclic edge","supported_operations":["check spanning tree claim","is this edge set a spanning tree","verify tree spans all vertices","detect cycle in claimed tree edges","check tree edges connect every vertex","spanning tree structure validation","find first redundant edge in tree"],"unsupported_operations":["spanning forests of disconnected graphs","directed arborescences (rooted out-trees)","finding a spanning tree (the caller supplies the claim)","weight or minimality checks (see spanning-tree-weight-check and minimum-spanning-tree-certificate-check)"],"semantics":["tree_edge_ids is processed in array order: each ID must exist in graph.edges (missing_edge), must not repeat (duplicate_edge, at the second occurrence) and must join two different components of the edges accepted so far (cycle_edge).","For cycle_edge, witness_edge_ids is the cycle: the unique path of earlier claimed edges from the edge's u to its v, then the edge itself (a self-loop is the one-edge cycle).","After the claim, every vertex must be connected to graph.vertices[0]; otherwise disconnected at the first unreached vertex in graph.vertices order, with expected = |V| - 1 and actual = claimed edge count.","Edges are undirected {id, u, v, weight}; parallel edges and self-loops are allowed because each edge has its own ID. IDs are 1..64 UTF-8 bytes, compared code unit for code unit (no normalization).","Graph errors (duplicate vertex or edge IDs, unknown endpoints, malformed integer weights, unknown fields) throw invalid_input; counts and sizes over the limits throw limit_exceeded first.","Reference: CLRS 4th ed. (2022) section 21.1 and Appendix B.5.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"],"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}}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","tree_edge_count","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":[null,"missing_edge","duplicate_edge","cycle_edge","disconnected"]},"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"]},"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_edge_count":{"type":"integer","minimum":0,"maximum":2000},"reference_version":{"type":"string","const":"clrs-4e-2022-ch21-minimum-spanning-trees"}}},"examples":[{"input":{"graph":{"vertices":["a","b","c","d"],"edges":[{"id":"ab","u":"a","v":"b","weight":"1"},{"id":"bc","u":"b","v":"c","weight":"2"},{"id":"cd","u":"c","v":"d","weight":"3"},{"id":"da","u":"d","v":"a","weight":"4"}]},"tree_edge_ids":["ab","bc","cd"]},"output":{"valid":true,"reason":null,"first_discrepancy":null,"tree_edge_count":3,"reference_version":"clrs-4e-2022-ch21-minimum-spanning-trees"}},{"input":{"graph":{"vertices":["a","b","c","d"],"edges":[{"id":"ab","u":"a","v":"b","weight":"1"},{"id":"bc","u":"b","v":"c","weight":"2"},{"id":"cd","u":"c","v":"d","weight":"3"},{"id":"da","u":"d","v":"a","weight":"4"}]},"tree_edge_ids":["ab","bc","cd","da"]},"output":{"valid":false,"reason":"cycle_edge","first_discrepancy":{"field":"tree_edge_ids","index":3,"vertex":null,"edge_id":"da","expected":null,"actual":null,"witness_edge_ids":["cd","bc","ab","da"]},"tree_edge_count":4,"reference_version":"clrs-4e-2022-ch21-minimum-spanning-trees"}},{"input":{"graph":{"vertices":["a","b","c","d"],"edges":[{"id":"ab","u":"a","v":"b","weight":"1"},{"id":"bc","u":"b","v":"c","weight":"2"},{"id":"cd","u":"c","v":"d","weight":"3"},{"id":"da","u":"d","v":"a","weight":"4"}]},"tree_edge_ids":["ab","cd"]},"output":{"valid":false,"reason":"disconnected","first_discrepancy":{"field":"graph.vertices","index":2,"vertex":"c","edge_id":null,"expected":"3","actual":"2","witness_edge_ids":null},"tree_edge_count":2,"reference_version":"clrs-4e-2022-ch21-minimum-spanning-trees"}}],"execute_url":"/v1/tools/spanning-tree-structure-check/versions/1.0.0/execute"}