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 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:

{
  "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:

{
  "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), then call execute with:

{
  "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)

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.

CLI

node cli.mjs run directed-cycle-check 1.0.0 --input input.json --base-url https://computefirst.net

Get the client at /clients/cli/.

Related 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: Check a claimed s-t cut: source-side membership, the edges crossing it and its capacity, with exact integers.
• 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: Check a claim chi(G) = k: a proper k-colouring plus a clique or bounded exhaustive proof; returns the first discrepancy.
• Graph clique check: Check that listed nodes form a clique (optionally maximal, of a minimum size); returns the first missing edge.
• Graph coloring check: Check that a node colouring of an undirected graph is proper (and within k colours); returns the first conflict.