Dependency Order Planner

Turn prerequisite lists into deterministic execution layers and expose blocked dependencies.

Version: 1.0.0. License: MIT. Status: tested reference baseline; no comparative ranking is claimed.

Contract

Require unique nonempty task IDs and existing dependency IDs. Repeated dependencies are deduplicated. Repeatedly select all tasks with no remaining prerequisites, sorted by ID, as a layer. Return unresolved IDs if no progress is possible; these include cycles and tasks downstream of cycles.

The exact required input fields and types are in input.schema.json. Extra fields are rejected at declared object boundaries. JSON duplicate keys and non-finite numbers are rejected by the CLI. Input strings are case-sensitive unless stated otherwise. Array order is preserved unless the contract specifies sorting.

Use

Unpack the ZIP, enter its directory, and run:

python3 baseline.py < example.input.json
python3 -m unittest -v

Python 3.10 or newer, standard library only. The reference implementation exposes run(input_dict) and accepts one JSON object on standard input. Success returns {"ok": true, "result": ...} with exit code 0. Invalid input returns {"ok": false, "error": "..."} with exit code 1. example.output.json contains the result without the CLI envelope. Import callers receive exceptions for invalid input.

Example input

{
  "tasks": [
    {
      "id": "publish",
      "needs": [
        "test"
      ]
    },
    {
      "id": "test",
      "needs": [
        "build"
      ]
    },
    {
      "id": "build",
      "needs": []
    },
    {
      "id": "docs",
      "needs": []
    }
  ]
}

Example result

{
  "layers": [
    [
      "build",
      "docs"
    ],
    [
      "test"
    ],
    [
      "publish"
    ]
  ],
  "blocked": [],
  "acyclic": true
}

Boundaries

Layers express dependency independence, not permission to run tasks concurrently. No scheduler, concurrency limit, resource model, or task execution is supplied.

This package performs no network calls, executes no submitted commands, and writes no user files. Host applications own authorization, resource budgets, and persistence. Example values are fixtures, not recommended policies or limits.

Acceptance and provenance

cases.json records named expected results and rejection cases. test_baseline.py runs those cases and checks the command-line contract. manifest.json records file digests. The specification, implementation, and evidence are separate files so a replacement implementation can target the same contract.

Original code and examples generated for this Arcomm collection. No third-party code is bundled. Read LICENSE for reuse terms.

Download

Download the file

SHA-256: d87a6bbae9e3bf512d13b7292523dc33bb2802a45424a7f1353786ae4ab2282c

Size: 6779 bytes.

Revisions

Revision history