Scc partition check

scc-partition-check · version 1.0.0 · Numbers & math · free, no key needed

Check a claimed strongly connected component partition of a digraph: coverage, reachability, maximality, order

Use when you need to: check strongly connected components · verify scc partition · are these the strongly connected components.

Decide before calling

Read the versioned contract and the supported scope below. Reuse scc-partition-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 scc-partition-check@1.0.0 for check strongly connected components. 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 strongly connected components
• verify scc partition
• are these the strongly connected components
• check condensation order of components
• validate component grouping of directed graph
• scc certificate check
• find components that should be merged

Not supported

• computing the components (use graph-strongly-connected-components)
• weakly connected or biconnected components
• a specific order inside a component (members may be listed in any order; the first is the root)

Behavior

• Order of checks: (1) partition, components in array order and members in order: empty_component, unknown_vertex, duplicate_vertex (a vertex already used anywhere earlier); index = component index, vertex_position = position inside the component; (2) every graph vertex in graph.vertices order appears (missing_vertex).
• (3) Mutual reachability, per component in order with root = first member: every member is reachable from the root in the whole graph (not_reachable_from_root), then every member reaches the root (cannot_reach_root); other_vertex = root.
• (4) Maximality: the component graph (claimed components as nodes in claim order, edges between different components in graph.edges order) must be acyclic, else components_should_merge with witness_vertices = the closed cycle of component roots, index and vertex = the first component on it, other_vertex = the next root. Witness procedure: Kahn-peel nodes of in-degree 0; from the first remaining node step to the tail of the first arc entering it from a remaining node until a node repeats; reverse the repeated stretch into arc direction and close it.
• (5) When order is "topological", every edge between different components, in graph.edges order, must go from an earlier to a later component (condensation_order_violated; vertex_position and other_position are the component indexes). order "any" skips this step; order is required.
• component_count is the number of claimed components. 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, 500 components or 500 members in total throws limit_exceeded before per-item work.
• Reference: CLRS 4th ed. (2022) section 20.5; reference_version "clrs-4e-2022-ch20-topological-sort-scc".

Input

• graph (object, required)
• components (array of array of string, required): max items 500; each max items 500; each each min length 1; each each max length 64
• order (one of "any", "topological", required)

Output

• valid (boolean, required)
• reason (one of null, "empty_component", "unknown_vertex", "duplicate_vertex", "missing_vertex", "not_reachable_from_root", "cannot_reach_root", "components_should_merge", "condensation_order_violated", required)
• first_discrepancy (object or null, required)
• component_count (integer, required): min 0; 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 components: 500
• max component entries: 500

Example

Request input:

{
  "graph": {
    "vertices": [
      "p",
      "q",
      "r",
      "s"
    ],
    "edges": [
      {
        "from": "p",
        "to": "q"
      },
      {
        "from": "q",
        "to": "p"
      },
      {
        "from": "q",
        "to": "r"
      },
      {
        "from": "r",
        "to": "s"
      },
      {
        "from": "s",
        "to": "r"
      }
    ]
  },
  "components": [
    [
      "p",
      "q"
    ],
    [
      "r",
      "s"
    ]
  ],
  "order": "topological"
}

Response:

{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "component_count": 2,
    "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": "scc-partition-check",
  "version": "1.0.0",
  "input": {
    "graph": {
      "vertices": [
        "p",
        "q",
        "r",
        "s"
      ],
      "edges": [
        {
          "from": "p",
          "to": "q"
        },
        {
          "from": "q",
          "to": "p"
        },
        {
          "from": "q",
          "to": "r"
        },
        {
          "from": "r",
          "to": "s"
        },
        {
          "from": "s",
          "to": "r"
        }
      ]
    },
    "components": [
      [
        "p",
        "q"
      ],
      [
        "r",
        "s"
      ]
    ],
    "order": "topological"
  }
}

HTTP (no key)

curl -X POST https://computefirst.net/v1/tools/scc-partition-check/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"graph":{"vertices":["p","q","r","s"],"edges":[{"from":"p","to":"q"},{"from":"q","to":"p"},{"from":"q","to":"r"},{"from":"r","to":"s"},{"from":"s","to":"r"}]},"components":[["p","q"],["r","s"]],"order":"topological"}'

The machine-readable contract is at /v1/tools/scc-partition-check/versions/1.0.0.

CLI

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

Get the client at /clients/cli/.

Related 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: Check that a node colouring of an undirected graph is proper (and within k colours); returns the first conflict.
• Regression normal equations check: Check that claimed coefficients and residuals satisfy X^T e = 0 exactly; rejects singular, ambiguous designs.
• Chromatic certificate check: Check a claim chi(G) = k: a proper k-colouring plus a clique or bounded exhaustive proof; returns the first discrepancy.
• Contingency expected check: Check claimed expected counts (row total x column total / N) of a count table exactly; returns the first wrong cell.
• Contingency margins check: Check claimed row, column and grand totals of a count table exactly; returns the first wrong total.