{"id":"directed-cycle-check","version":"1.0.0","description":"Check a claimed directed cycle (closed vertex list) in a digraph, or a no-cycle claim with a deterministic witness","supported_operations":["check claimed directed cycle","verify cycle in dependency graph","is this a real cycle in the digraph","verify graph is acyclic","prove there is no cycle","circular dependency claim check","deadlock cycle verification"],"unsupported_operations":["listing all cycles or counting them","undirected cycles","shortest or longest cycle search","non-simple closed walks (a repeated vertex is rejected)"],"semantics":["A cycle claim is a closed list [v0, ..., vk] with vk = v0 and k >= 1 (2..501 entries; fewer than 2 throw invalid_input). Closure before membership: (1) last entry equals first (cycle_not_closed: index = last position, vertex = last, other_vertex = first), (2) entries 0..k-1 are listed vertices (unknown_vertex), (3) no vertex repeats among them (repeated_vertex at the second occurrence, other_position = earlier position), (4) each edge v_i -> v_(i+1) exists, i = 0..k-1 in order (missing_edge, vertex = v_i, other_vertex = v_(i+1)).","cycle null claims the graph is acyclic: valid when it is, otherwise cycle_exists with witness_vertices = the deterministic witness, vertex and other_vertex = its first edge and index null.","Witness procedure: peel vertices of in-degree 0 (Kahn) until none remain to peel; the remaining set R is non-empty exactly when a cycle exists. From the first vertex of R in graph.vertices order, repeatedly step to the tail of the first edge (graph.edges order) entering the current vertex from R until a vertex repeats; the repeated stretch reversed into edge direction is the cycle, listed closed.","cycle_length is k for a cycle claim (also when invalid) and null for a null claim; a self-loop [v, v] has length 1. 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 or 501 cycle entries throws limit_exceeded before per-item work.","Reference: CLRS 4th ed. (2022) section 20.3 (Lemma 20.11); reference_version \"clrs-4e-2022-ch20-topological-sort-scc\"."],"limits":{"max_vertices":500,"max_edges":2000,"max_id_bytes":64,"max_cycle_entries":501},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["graph","cycle"],"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}}}}}},"cycle":{"type":["array","null"],"minItems":2,"maxItems":501,"items":{"type":"string","minLength":1,"maxLength":64}}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","cycle_length","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":[null,"cycle_not_closed","unknown_vertex","repeated_vertex","missing_edge","cycle_exists"]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["field","index","vertex","other_vertex","vertex_position","other_position","witness_vertices"],"properties":{"field":{"type":"string","enum":["cycle"]},"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}}}},"cycle_length":{"type":["integer","null"],"minimum":1,"maximum":500},"reference_version":{"type":"string","const":"clrs-4e-2022-ch20-topological-sort-scc"}}},"examples":[{"input":{"graph":{"vertices":["auth","db","cache","api"],"edges":[{"from":"api","to":"auth"},{"from":"auth","to":"db"},{"from":"db","to":"cache"},{"from":"cache","to":"auth"}]},"cycle":["auth","db","cache","auth"]},"output":{"valid":true,"reason":null,"first_discrepancy":null,"cycle_length":3,"reference_version":"clrs-4e-2022-ch20-topological-sort-scc"}},{"input":{"graph":{"vertices":["auth","db","cache","api"],"edges":[{"from":"api","to":"auth"},{"from":"auth","to":"db"},{"from":"db","to":"cache"},{"from":"cache","to":"auth"}]},"cycle":["auth","cache","db","auth"]},"output":{"valid":false,"reason":"missing_edge","first_discrepancy":{"field":"cycle","index":0,"vertex":"auth","other_vertex":"cache","vertex_position":null,"other_position":null,"witness_vertices":null},"cycle_length":3,"reference_version":"clrs-4e-2022-ch20-topological-sort-scc"}},{"input":{"graph":{"vertices":["auth","db","cache","api"],"edges":[{"from":"api","to":"auth"},{"from":"auth","to":"db"},{"from":"db","to":"cache"},{"from":"cache","to":"auth"}]},"cycle":null},"output":{"valid":false,"reason":"cycle_exists","first_discrepancy":{"field":"cycle","index":null,"vertex":"auth","other_vertex":"db","vertex_position":null,"other_position":null,"witness_vertices":["auth","db","cache","auth"]},"cycle_length":null,"reference_version":"clrs-4e-2022-ch20-topological-sort-scc"}}],"execute_url":"/v1/tools/directed-cycle-check/versions/1.0.0/execute"}