# Topological order check

`topological-order-check` · version 1.0.0 · Numbers & math · free, no key needed

Check that a claimed vertex order is a permutation and topological order of a digraph; reports the first backward edge

**Use when you need to: check topological order · verify dependency order · is this a valid topological sort.**

## Decide before calling

Read the [versioned contract](/v1/tools/topological-order-check/versions/1.0.0) and the supported scope below. Reuse `topological-order-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 `topological-order-check@1.0.0` for check topological order. 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 topological order
- verify dependency order
- is this a valid topological sort
- check build order against dependencies
- validate task ordering for a dag
- find first dependency violated by an order
- topological sort certificate check

## Not supported

- producing a topological order (use graph-topological-sort)
- partial orders over a subset of vertices
- reporting the cycle that makes ordering impossible (use directed-cycle-check with cycle null)

## Behavior

- Permutation before edges: order entries in array order must be listed vertices (unknown_vertex) and must not repeat (duplicate_vertex at the second occurrence, other_position = earlier position); then every graph vertex in graph.vertices order must appear (missing_vertex).
- Then every edge in graph.edges order must go forward, position(from) < position(to); the first that does not is edge_order_violated with index = edge position, vertex = from, other_vertex = to, vertex_position and other_position = their positions in order. A self-loop or any cycle makes every order fail.
- Edges are directed {from, to}; parallel edges and self-loops are allowed. Vertex IDs are 1..64 UTF-8 bytes, compared code unit for code unit (no normalization).
- Graph errors (duplicate vertex IDs, unknown edge endpoints, wrong types, unknown fields) throw invalid_input; more than 500 vertices or order entries, or 2000 edges, throws limit_exceeded before per-item work.
- Reference: CLRS 4th ed. (2022) section 20.4; reference_version "clrs-4e-2022-ch20-topological-sort-scc".

## Input

- `graph` (object, required)
- `order` (array of string, required): max items 500; each min length 1; each max length 64

## Output

- `valid` (boolean, required)
- `reason` (one of null, "unknown_vertex", "duplicate_vertex", "missing_vertex", "edge_order_violated", required)
- `first_discrepancy` (object or null, required)
- `vertex_count` (integer, 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 order entries: 500

## Example

Request input:

```json
{
  "graph": {
    "vertices": [
      "wake",
      "shower",
      "dress",
      "leave"
    ],
    "edges": [
      {
        "from": "wake",
        "to": "shower"
      },
      {
        "from": "shower",
        "to": "dress"
      },
      {
        "from": "wake",
        "to": "dress"
      },
      {
        "from": "dress",
        "to": "leave"
      }
    ]
  },
  "order": [
    "wake",
    "shower",
    "dress",
    "leave"
  ]
}
```

Response:

```json
{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "vertex_count": 4,
    "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": "topological-order-check",
  "version": "1.0.0",
  "input": {
    "graph": {
      "vertices": [
        "wake",
        "shower",
        "dress",
        "leave"
      ],
      "edges": [
        {
          "from": "wake",
          "to": "shower"
        },
        {
          "from": "shower",
          "to": "dress"
        },
        {
          "from": "wake",
          "to": "dress"
        },
        {
          "from": "dress",
          "to": "leave"
        }
      ]
    },
    "order": [
      "wake",
      "shower",
      "dress",
      "leave"
    ]
  }
}
```

### HTTP (no key)

```sh
curl -X POST https://computefirst.net/v1/tools/topological-order-check/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"graph":{"vertices":["wake","shower","dress","leave"],"edges":[{"from":"wake","to":"shower"},{"from":"shower","to":"dress"},{"from":"wake","to":"dress"},{"from":"dress","to":"leave"}]},"order":["wake","shower","dress","leave"]}'
```

The machine-readable contract is at [/v1/tools/topological-order-check/versions/1.0.0](/v1/tools/topological-order-check/versions/1.0.0).

### CLI

```sh
node cli.mjs run topological-order-check 1.0.0 --input input.json --base-url https://computefirst.net
```

Get the client at [/clients/cli/](/clients/cli/).

## Related tools

- [Precedence order check](/tools/precedence-order-check): Check whether a claimed node order is exactly a precedence-respecting linear extension of a caller-supplied DAG.
- [Lp optimality certificate check](/tools/lp-optimality-certificate-check): Check an LP optimum claim from a primal x and dual y: feasibility, complementary slackness and zero duality gap.
- [Maximum flow certificate check](/tools/maximum-flow-certificate-check): Check a claimed max flow with a min-cut certificate or residual search; reports the first failure or augmenting path.
- [Network flow feasibility check](/tools/network-flow-feasibility-check): Check a claimed s-t flow for capacity bounds and conservation with exact integers; returns the first bad edge or node.
- [Cnf assignment check](/tools/cnf-assignment-check): Check a claimed truth assignment against a DIMACS-style CNF; report the first bad literal or unsatisfied clause.
- [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.