{"id":"topological-order-check","version":"1.0.0","description":"Check that a claimed vertex order is a permutation and topological order of a digraph; reports the first backward edge","supported_operations":["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"],"unsupported_operations":["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)"],"semantics":["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\"."],"limits":{"max_vertices":500,"max_edges":2000,"max_id_bytes":64,"max_order_entries":500},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["graph","order"],"properties":{"graph":{"type":"object","additionalProperties":false,"required":["vertices","edges"],"properties":{"vertices":{"type":"array","minItems":1,"maxItems":500,"items":{"type":"string","minLength":1,"maxLength":64}},"edges":{"type":"array","maxItems":2000,"items":{"type":"object","additionalProperties":false,"required":["from","to"],"properties":{"from":{"type":"string","minLength":1,"maxLength":64},"to":{"type":"string","minLength":1,"maxLength":64}}}}}},"order":{"type":"array","maxItems":500,"items":{"type":"string","minLength":1,"maxLength":64}}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","vertex_count","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":[null,"unknown_vertex","duplicate_vertex","missing_vertex","edge_order_violated"]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["field","index","vertex","other_vertex","vertex_position","other_position","witness_vertices"],"properties":{"field":{"type":"string","enum":["order","graph.vertices","graph.edges"]},"index":{"type":["integer","null"],"minimum":0},"vertex":{"type":["string","null"]},"other_vertex":{"type":["string","null"]},"vertex_position":{"type":["integer","null"],"minimum":0},"other_position":{"type":["integer","null"],"minimum":0},"witness_vertices":{"type":["array","null"],"maxItems":501,"items":{"type":"string","minLength":1,"maxLength":64}}}},"vertex_count":{"type":"integer","minimum":1,"maximum":500},"reference_version":{"type":"string","const":"clrs-4e-2022-ch20-topological-sort-scc"}}},"examples":[{"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"]},"output":{"valid":true,"reason":null,"first_discrepancy":null,"vertex_count":4,"reference_version":"clrs-4e-2022-ch20-topological-sort-scc"}},{"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","dress","shower","leave"]},"output":{"valid":false,"reason":"edge_order_violated","first_discrepancy":{"field":"graph.edges","index":1,"vertex":"shower","other_vertex":"dress","vertex_position":2,"other_position":1,"witness_vertices":null},"vertex_count":4,"reference_version":"clrs-4e-2022-ch20-topological-sort-scc"}}],"execute_url":"/v1/tools/topological-order-check/versions/1.0.0/execute"}