Service Dependency Resolver (C)
Topics: graphs, topological sort, cycle detection
Problem
Order services so that every service comes after the ones it depends on — a
deterministic topological sort. If the graph has a cycle, report the nodes that
can't be ordered.
typedef enum { DR_OK, DR_CYCLE } DepStatus;
typedef struct { const char *name; const char *const *deps; int ndeps; } DepNode;
DepStatus dep_resolve(const DepNode *nodes, int n, const char **out, int *out_len);
DR_OK — out[0..out_len) is a valid order (dependencies first). Break ties
lexicographically for a deterministic result.DR_CYCLE — out[0..out_len) is the sorted set of nodes in or downstream of
a cycle.
A name that only appears as a dependency (never a key) is still a node — an
implicit leaf. A self-dependency (a depends on a) is a cycle.
Key concepts
- Kahn's algorithm: a node's in-degree is its number of distinct
dependencies. Repeatedly take a node with in-degree 0, emit it, and decrement the
in-degree of everything that depended on it.
- Deterministic ties: when several nodes are ready (in-degree 0), always take
the lexicographically smallest, so the output is stable.
- Cycle = leftovers: if you emit fewer than all nodes, the ones you couldn't
reach (in-degree never hit 0) are exactly the cycle and its downstream.
- Dedupe edges: a repeated dependency counts once; a self-edge counts and
makes the node unorderable.
Intern the names into a fixed table and use a bool edge matrix — no allocation.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/deps && /tmp/deps
Sign in to submit your solution.