Migration Step Ordering with Optional Steps (C)
Topics: topological sort, backtracking, constraint satisfaction
Problem
Compute a valid execution order for migration steps that have dependencies,
alternatives, and mutual exclusions — a topological sort where some of the
nodes still have to be chosen.
typedef struct { const char *const *opts; int n; } Group;
typedef struct {
const char *name;
const Group *depends; int ndepends; // each group: enable >=1, scheduled before this step
const char *const *excludes; int nexcludes; // symmetric mutual exclusion
} Step;
bool mig_plan(const Step *steps, int n, const char *const *required, int nreq,
const char **order, int *order_len);
Find an order that includes every required step (plus whatever depends pulls
in) such that every included step's depends groups and excludes are satisfied
and each dependency runs before the step needing it. On success write the order
into order[0..*order_len) and return true; otherwise return false.
Key concepts
- Two phases woven together: a backtracking search chooses which optional
steps to include (satisfying each
depends choice group and recording an
ordering edge "dep before owner"), and once nothing is left to decide, a
topological sort of the included steps produces the order — or reports a
cycle.
- A cycle is a dead end, not a hard failure: if a chosen alternative creates a
cycle (
a depends on cutover, which depends on a), the topo sort fails and
the search must back up and try the other option in the group.
- Excludes are symmetric and checked in both directions, exactly as in the
feature-flag solver.
- Deterministic ties: when several steps are ready at once, emit them in
alphabetical order.
A bool enabled[] set and an edges[from][to] adjacency matrix track state — no
allocation.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/migration && /tmp/migration
Sign in to submit your solution.