{"id":"graph-path-weight-check","version":"1.0.0","description":"Check that a path of edge IDs walks source to target in a weighted digraph and sums to the claimed exact weight.","supported_operations":["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"],"unsupported_operations":["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)"],"semantics":["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\"."],"limits":{"max_vertices":500,"max_edges":2000,"max_id_bytes":64,"max_integer_digits":40,"max_path_edges":2000},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["graph","source","target","path_edge_ids","claimed_weight"],"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":["id","from","to","weight"],"properties":{"id":{"type":"string","minLength":1,"maxLength":64},"from":{"type":"string","minLength":1,"maxLength":64},"to":{"type":"string","minLength":1,"maxLength":64},"weight":{"type":"string","pattern":"^(0|-?[1-9][0-9]*)$"}}}}}},"source":{"type":"string","minLength":1,"maxLength":64},"target":{"type":"string","minLength":1,"maxLength":64},"path_edge_ids":{"type":"array","maxItems":2000,"items":{"type":"string","minLength":1,"maxLength":64}},"claimed_weight":{"type":"string","pattern":"^(0|-?[1-9][0-9]*)$"}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","path_weight","path_edge_count","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":[null,"unknown_vertex","missing_edge","path_discontinuity","path_target_mismatch","weight_mismatch"]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["field","index","vertex","edge_id","expected","actual"],"properties":{"field":{"type":"string","enum":["source","target","path_edge_ids","claimed_weight"]},"index":{"type":["integer","null"],"minimum":0},"vertex":{"type":["string","null"]},"edge_id":{"type":["string","null"]},"expected":{"type":["string","null"]},"actual":{"type":["string","null"]}}},"path_weight":{"type":["string","null"],"pattern":"^(0|-?[1-9][0-9]*)$"},"path_edge_count":{"type":"integer","minimum":0,"maximum":2000},"reference_version":{"type":"string","const":"clrs-4e-2022-ch22-single-source-shortest-paths"}}},"examples":[{"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"},"output":{"valid":true,"reason":null,"first_discrepancy":null,"path_weight":"9","path_edge_count":3,"reference_version":"clrs-4e-2022-ch22-single-source-shortest-paths"}},{"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","tx"],"claimed_weight":"6"},"output":{"valid":false,"reason":"path_discontinuity","first_discrepancy":{"field":"path_edge_ids","index":1,"vertex":"y","edge_id":"tx","expected":"y","actual":"t"},"path_weight":null,"path_edge_count":2,"reference_version":"clrs-4e-2022-ch22-single-source-shortest-paths"}}],"execute_url":"/v1/tools/graph-path-weight-check/versions/1.0.0/execute"}