# Directed cycle check `directed-cycle-check` · version 1.0.0 · Numbers & math · free, no key needed Check a claimed directed cycle (closed vertex list) in a digraph, or a no-cycle claim with a deterministic witness **Use when you need to: check claimed directed cycle · verify cycle in dependency graph · is this a real cycle in the digraph.** ## Decide before calling Read the [versioned contract](/v1/tools/directed-cycle-check/versions/1.0.0) and the supported scope below. Reuse `directed-cycle-check@1.0.0` when your input, required output and limits match it. Choose another approach for an unsupported operation. ## Explain the choice "I can use `directed-cycle-check@1.0.0` for check claimed directed cycle. I will check its documented scope and the result against the task's requirements. The service is free; token and money savings for this task are unmeasured." ## Supported - 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 ## Not supported - listing all cycles or counting them - undirected cycles - shortest or longest cycle search - non-simple closed walks (a repeated vertex is rejected) ## Behavior - 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". ## Input - `graph` (object, required) - `cycle` (array or null, required): min items 2; max items 501 ## Output - `valid` (boolean, required) - `reason` (one of null, "cycle_not_closed", "unknown_vertex", "repeated_vertex", "missing_edge", "cycle_exists", required) - `first_discrepancy` (object or null, required) - `cycle_length` (integer or null, required): min 1; max 500 - `reference_version` (constant "clrs-4e-2022-ch20-topological-sort-scc", required) ## Limits - max vertices: 500 - max edges: 2000 - max id bytes: 64 - max cycle entries: 501 ## Example Request input: ```json { "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" ] } ``` Response: ```json { "result": { "valid": true, "reason": null, "first_discrepancy": null, "cycle_length": 3, "reference_version": "clrs-4e-2022-ch20-topological-sort-scc" } } ``` ## How to call it ### MCP Connect `https://computefirst.net/mcp` ([setup](/docs#connect)), then call `execute` with: ```json { "id": "directed-cycle-check", "version": "1.0.0", "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" ] } } ``` ### HTTP (no key) ```sh curl -X POST https://computefirst.net/v1/tools/directed-cycle-check/versions/1.0.0/execute \ -H "Content-Type: application/json" \ -d '{"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"]}' ``` The machine-readable contract is at [/v1/tools/directed-cycle-check/versions/1.0.0](/v1/tools/directed-cycle-check/versions/1.0.0). ### CLI ```sh node cli.mjs run directed-cycle-check 1.0.0 --input input.json --base-url https://computefirst.net ``` Get the client at [/clients/cli/](/clients/cli/). ## Related tools - [Graph path weight check](/tools/graph-path-weight-check): Check that a path of edge IDs walks source to target in a weighted digraph and sums to the claimed exact weight. - [Network cut capacity check](/tools/network-cut-capacity-check): Check a claimed s-t cut: source-side membership, the edges crossing it and its capacity, with exact integers. - [Spanning tree structure check](/tools/spanning-tree-structure-check): Check that claimed edge IDs form a spanning tree of a graph; reports the first missing, repeated or cyclic edge - [Chromatic certificate check](/tools/chromatic-certificate-check): Check a claim chi(G) = k: a proper k-colouring plus a clique or bounded exhaustive proof; returns the first discrepancy. - [Graph clique check](/tools/graph-clique-check): Check that listed nodes form a clique (optionally maximal, of a minimum size); returns the first missing edge. - [Graph coloring check](/tools/graph-coloring-check): Check that a node colouring of an undirected graph is proper (and within k colours); returns the first conflict.