# Graph path weight check

`graph-path-weight-check` · version 1.0.0 · Numbers & math · free, no key needed

Check that a path of edge IDs walks source to target in a weighted digraph and sums to the claimed exact weight.

**Use when you need to: check path weight in weighted graph · verify claimed route cost · does this path exist in the directed graph.**

## Decide before calling

Read the [versioned contract](/v1/tools/graph-path-weight-check/versions/1.0.0) and the supported scope below. Reuse `graph-path-weight-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 `graph-path-weight-check@1.0.0` for check path weight in weighted graph. 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 path weight in weighted graph
- verify claimed route cost
- does this path exist in the directed graph
- sum edge weights along a path exactly
- validate path continuity edge by edge
- check walk from source to target
- path weight claim checker

## Not supported

- finding the shortest path (use shortest-path-certificate-check to verify one you already have)
- paths given as vertex sequences without edge IDs
- floating-point or decimal weights
- undirected graphs (list both directions as separate edges)

## Behavior

- Check order: source listed, target listed, then each path_edge_ids[i] in order must exist (missing_edge) and leave the current vertex, which starts at source (path_discontinuity); then the walk must end at target (path_target_mismatch); then the exact weight sum must equal claimed_weight (weight_mismatch).
- Weights and claims are canonical integer strings ^(0|-?[1-9][0-9]*)$ of at most 40 digits, summed exactly with big integers; there is no floating point.
- Edges are identified by their own IDs, so parallel edges and self-loops are allowed; walks may repeat edges and the empty path is the zero-weight walk from source to itself.
- Vertex and edge IDs are compared code unit for code unit (no Unicode normalization or case folding); IDs are 1..64 UTF-8 bytes.
- path_weight is the exact sum when the walk is structurally valid, otherwise null; first_discrepancy names the input field, the path index, and expected (from the graph) versus actual (from the claim).
- Graph errors (duplicate vertex or edge IDs, unknown endpoints, malformed integers, unknown fields) throw invalid_input; counts and sizes over the limits throw limit_exceeded first.
- Reference: CLRS 4th ed. (2022) chapter 22 path weight; reference_version "clrs-4e-2022-ch22-single-source-shortest-paths".

## Input

- `graph` (object, required)
- `source` (string, required): min length 1; max length 64
- `target` (string, required): min length 1; max length 64
- `path_edge_ids` (array of string, required): max items 2000; each min length 1; each max length 64
- `claimed_weight` (string, required): pattern `^(0|-?[1-9][0-9]*)$`

## Output

- `valid` (boolean, required)
- `reason` (one of null, "unknown_vertex", "missing_edge", "path_discontinuity", "path_target_mismatch", "weight_mismatch", required)
- `first_discrepancy` (object or null, required)
- `path_weight` (string or null, required): pattern `^(0|-?[1-9][0-9]*)$`
- `path_edge_count` (integer, required): min 0; max 2000
- `reference_version` (constant "clrs-4e-2022-ch22-single-source-shortest-paths", required)

## Limits

- max vertices: 500
- max edges: 2000
- max id bytes: 64
- max integer digits: 40
- max path edges: 2000

## Example

Request input:

```json
{
  "graph": {
    "vertices": [
      "s",
      "y",
      "t",
      "x"
    ],
    "edges": [
      {
        "id": "sy",
        "from": "s",
        "to": "y",
        "weight": "5"
      },
      {
        "id": "yt",
        "from": "y",
        "to": "t",
        "weight": "3"
      },
      {
        "id": "tx",
        "from": "t",
        "to": "x",
        "weight": "1"
      }
    ]
  },
  "source": "s",
  "target": "x",
  "path_edge_ids": [
    "sy",
    "yt",
    "tx"
  ],
  "claimed_weight": "9"
}
```

Response:

```json
{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "path_weight": "9",
    "path_edge_count": 3,
    "reference_version": "clrs-4e-2022-ch22-single-source-shortest-paths"
  }
}
```

## How to call it

### MCP

Connect `https://computefirst.net/mcp` ([setup](/docs#connect)), then call `execute` with:

```json
{
  "id": "graph-path-weight-check",
  "version": "1.0.0",
  "input": {
    "graph": {
      "vertices": [
        "s",
        "y",
        "t",
        "x"
      ],
      "edges": [
        {
          "id": "sy",
          "from": "s",
          "to": "y",
          "weight": "5"
        },
        {
          "id": "yt",
          "from": "y",
          "to": "t",
          "weight": "3"
        },
        {
          "id": "tx",
          "from": "t",
          "to": "x",
          "weight": "1"
        }
      ]
    },
    "source": "s",
    "target": "x",
    "path_edge_ids": [
      "sy",
      "yt",
      "tx"
    ],
    "claimed_weight": "9"
  }
}
```

### HTTP (no key)

```sh
curl -X POST https://computefirst.net/v1/tools/graph-path-weight-check/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"graph":{"vertices":["s","y","t","x"],"edges":[{"id":"sy","from":"s","to":"y","weight":"5"},{"id":"yt","from":"y","to":"t","weight":"3"},{"id":"tx","from":"t","to":"x","weight":"1"}]},"source":"s","target":"x","path_edge_ids":["sy","yt","tx"],"claimed_weight":"9"}'
```

The machine-readable contract is at [/v1/tools/graph-path-weight-check/versions/1.0.0](/v1/tools/graph-path-weight-check/versions/1.0.0).

### CLI

```sh
node cli.mjs run graph-path-weight-check 1.0.0 --input input.json --base-url https://computefirst.net
```

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

## Related tools

- [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.
- [Directed cycle check](/tools/directed-cycle-check): Check a claimed directed cycle (closed vertex list) in a digraph, or a no-cycle claim with a deterministic witness
- [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.
- [Spanning tree weight check](/tools/spanning-tree-weight-check): Check that claimed edge IDs form a spanning tree and that their exact total weight equals the claimed weight.
- [Lp primal feasibility check](/tools/lp-primal-feasibility-check): Check that a claimed LP point satisfies x >= 0 and Ax <= b exactly; report the first violated bound or row.