Dependency order with graph traversal: BFS, DFS and topological sort

Goal

Given items that depend on each other (build targets, database migrations, deployment steps, modules), compute an order in which every item comes after all of its dependencies, report cycles explicitly, and find the set of items affected by a change.

Prerequisites

A list of nodes and directed edges with one fixed reading, for example "A must run before B". Both directions work as long as the whole program uses one. Node identities must be unique and comparable so that ties can be broken deterministically.

Steps

1. Build two adjacency lists (dependencies of each node, dependants of each node) and an in-degree count per node; include nodes that have no edges at all.
2. Affected set by traversal: starting from a changed node, follow dependant edges and collect visited nodes. Breadth-first search with a queue visits by distance, which separates direct from transitive dependants; depth-first search with an explicit stack is equivalent for the set. Mark nodes visited before enqueuing them so shared subgraphs and cycles do not loop.
3. Order with Kahn's algorithm: enqueue every node with in-degree zero; pop one, emit it, decrement the in-degree of each dependant and enqueue those reaching zero. Nodes never emitted lie on or behind a cycle; report them by name.
4. Alternative order with DFS post-order: visit a node, recurse into its dependencies, then append it. A node encountered while still "in progress" closes a cycle; record the path for the error message. The append order is a valid dependency order.
5. Parallel scheduling: the nodes ready at the same time in Kahn's algorithm can run concurrently. Python's graphlib.TopologicalSorter exposes this as prepare(), get_ready() and done(), and prepare() raises CycleError when a cycle exists. GNU tsort reads pairs and writes a total order consistent with the partial ordering it is given.
6. Make ties deterministic by sorting the ready set by name; otherwise each run may produce a different valid order and builds become irreproducible.
7. Test with a diamond (A before B and C, both before D), a cycle, an isolated node and a large chain to check depth handling.

Expected result

A reproducible order, a cycle report that names the nodes involved, and an affected set usable for incremental builds or targeted test runs.

Limits and test basis

Only acyclic graphs have a topological order; a cycle is a modelling error to fix, not to route around. Undeclared dependencies produce an order that looks valid and is wrong; the algorithm cannot detect missing edges. Recursive DFS is depth-limited on long chains; prefer the iterative form. Library behaviour is as described in the cited documentation.