Graph Topological Order Verifier
Verify an explicit proposed topological order against every directed edge occurrence; unlike topological sorting it does not produce a replacement order.
Description
Verify an explicit proposed topological order against every directed edge occurrence; unlike topological sorting it does not produce a replacement order.
A topological ordering must place every directed edge's source before its target. Missing endpoints also invalidate that proposed order.
When to use this tool
Verify an explicit proposed topological order against every directed edge occurrence; unlike topological sorting it does not produce a replacement order.
- Prepare the supplied edgesJson, order fields for this operation.
- Compare the complete example with the representation used by your own input before carrying the result into another step.
How to use the tool and how it works
- Enter edgesJson, order. Use the exact text syntax, units and index conventions explained below.
- Run the tool. If input validation fails, correct the supplied fields before interpreting any result.
- Read result.valid, result.violations. Interpret false, null and empty lists using the distinctions below; they can be valid outputs.
Require unique order labels and valid edge records. Report every edge whose endpoint is absent or whose source position is not strictly earlier than its target; valid means no violations.1
| Input field | Meaning and representation | Accepted input |
|---|---|---|
| edgesJson | JSON text, entered as one text field. The decoded structure is illustrated below; it is not a separate file. | Text |
| order | order. | List of strings; at most 128 entries |
For the JSON text fields, the following decoded structures show the example records before they are serialized into input strings. Keep field names, list nesting and value types as shown.
[
{
"field": "edgesJson",
"decoded": [
{
"id": "a",
"source": "u",
"target": "v",
"weight": 2
},
{
"id": "b",
"source": "v",
"target": "u",
"weight": 4
},
{
"id": "c",
"source": "u",
"target": "u",
"weight": 1
}
]
}
]| Output field | Interpretation |
|---|---|
| result | Object containing the named outputs below. |
| result.valid | Flag for valid under the exact condition described above. |
| result.violations | Source positions or records that fail the specific screen above; an empty list means no such violation. |
{
"input": {
"edgesJson": "[{\"id\":\"a\",\"source\":\"u\",\"target\":\"v\",\"weight\":2},{\"id\":\"b\",\"source\":\"v\",\"target\":\"u\",\"weight\":4},{\"id\":\"c\",\"source\":\"u\",\"target\":\"u\",\"weight\":1}]",
"order": [
"u",
"v"
]
},
"output": {
"result": {
"valid": false,
"violations": [
1,
2
]
}
}
}Limitations and assumptions
- Extra isolated labels in order are allowed. The tool checks a supplied order rather than generating one or proving a complete declared vertex universe is covered.
- Every edge record requires unique string id, string source/target and finite numeric weight, even when this operation does not use the weight. Parallel endpoints and loops are retained unless explicitly filtered.
- Every declared top-level field is required and unexpected fields are rejected. Numeric inputs must be finite; ordinary text fields are bounded to 8,192 UTF-16 code units, with tighter operation-specific limits where stated.
- Lists are limited to 128 entries. JSON text must meet bounded size and depth checks, and numeric outputs beyond the safe finite magnitude are rejected. Exact large integers use decimal strings.
- Indexes are zero-based and spans have an exclusive end unless explicitly stated otherwise. A valid false, null or empty-list result is distinct from malformed input.
Alternative or Complementary methods
Choose edge identities, directedness and vertex coverage explicitly. Local edge-list audits and transformations do not replace a graph algorithm with the required connectivity, path or ordering guarantees.
References
Similar or alternative tools
- Graph Declared Bipartition Edge Audit
Verify a supplied disjoint bipartition against each edge occurrence, reporting unknown endpoints and within-side edges rather than finding a new coloring.
- Graph Complement Edge List
Build the loop-free complement on an explicit bounded vertex set; parallel edges count as one adjacency and directed complements use ordered pairs.