{"id":"scc-partition-check","version":"1.0.0","description":"Check a claimed strongly connected component partition of a digraph: coverage, reachability, maximality, order","supported_operations":["check strongly connected components","verify scc partition","are these the strongly connected components","check condensation order of components","validate component grouping of directed graph","scc certificate check","find components that should be merged"],"unsupported_operations":["computing the components (use graph-strongly-connected-components)","weakly connected or biconnected components","a specific order inside a component (members may be listed in any order; the first is the root)"],"semantics":["Order of checks: (1) partition, components in array order and members in order: empty_component, unknown_vertex, duplicate_vertex (a vertex already used anywhere earlier); index = component index, vertex_position = position inside the component; (2) every graph vertex in graph.vertices order appears (missing_vertex).","(3) Mutual reachability, per component in order with root = first member: every member is reachable from the root in the whole graph (not_reachable_from_root), then every member reaches the root (cannot_reach_root); other_vertex = root.","(4) Maximality: the component graph (claimed components as nodes in claim order, edges between different components in graph.edges order) must be acyclic, else components_should_merge with witness_vertices = the closed cycle of component roots, index and vertex = the first component on it, other_vertex = the next root. Witness procedure: Kahn-peel nodes of in-degree 0; from the first remaining node step to the tail of the first arc entering it from a remaining node until a node repeats; reverse the repeated stretch into arc direction and close it.","(5) When order is \"topological\", every edge between different components, in graph.edges order, must go from an earlier to a later component (condensation_order_violated; vertex_position and other_position are the component indexes). order \"any\" skips this step; order is required.","component_count is the number of claimed components. Edges are directed {from, to}; parallel edges and self-loops allowed; IDs compared code unit for code unit.","Graph errors throw invalid_input; more than 500 vertices, 2000 edges, 500 components or 500 members in total throws limit_exceeded before per-item work.","Reference: CLRS 4th ed. (2022) section 20.5; reference_version \"clrs-4e-2022-ch20-topological-sort-scc\"."],"limits":{"max_vertices":500,"max_edges":2000,"max_id_bytes":64,"max_components":500,"max_component_entries":500},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["graph","components","order"],"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":["from","to"],"properties":{"from":{"type":"string","minLength":1,"maxLength":64},"to":{"type":"string","minLength":1,"maxLength":64}}}}}},"components":{"type":"array","maxItems":500,"items":{"type":"array","maxItems":500,"items":{"type":"string","minLength":1,"maxLength":64}}},"order":{"type":"string","enum":["any","topological"]}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","component_count","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":[null,"empty_component","unknown_vertex","duplicate_vertex","missing_vertex","not_reachable_from_root","cannot_reach_root","components_should_merge","condensation_order_violated"]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["field","index","vertex","other_vertex","vertex_position","other_position","witness_vertices"],"properties":{"field":{"type":"string","enum":["components","graph.vertices","graph.edges"]},"index":{"type":["integer","null"],"minimum":0},"vertex":{"type":["string","null"]},"other_vertex":{"type":["string","null"]},"vertex_position":{"type":["integer","null"],"minimum":0},"other_position":{"type":["integer","null"],"minimum":0},"witness_vertices":{"type":["array","null"],"maxItems":501,"items":{"type":"string","minLength":1,"maxLength":64}}}},"component_count":{"type":"integer","minimum":0,"maximum":500},"reference_version":{"type":"string","const":"clrs-4e-2022-ch20-topological-sort-scc"}}},"examples":[{"input":{"graph":{"vertices":["p","q","r","s"],"edges":[{"from":"p","to":"q"},{"from":"q","to":"p"},{"from":"q","to":"r"},{"from":"r","to":"s"},{"from":"s","to":"r"}]},"components":[["p","q"],["r","s"]],"order":"topological"},"output":{"valid":true,"reason":null,"first_discrepancy":null,"component_count":2,"reference_version":"clrs-4e-2022-ch20-topological-sort-scc"}},{"input":{"graph":{"vertices":["p","q","r","s"],"edges":[{"from":"p","to":"q"},{"from":"q","to":"p"},{"from":"q","to":"r"},{"from":"r","to":"s"},{"from":"s","to":"r"}]},"components":[["p"],["q"],["r","s"]],"order":"any"},"output":{"valid":false,"reason":"components_should_merge","first_discrepancy":{"field":"components","index":0,"vertex":"p","other_vertex":"q","vertex_position":null,"other_position":null,"witness_vertices":["p","q","p"]},"component_count":3,"reference_version":"clrs-4e-2022-ch20-topological-sort-scc"}}],"execute_url":"/v1/tools/scc-partition-check/versions/1.0.0/execute"}