Dependency resolution

intermediateCommon atAnthropicGoogleStripeMetaRead firstTopological sortGraph representationDFSPractise in the Sandbox →

Packages, build steps, spreadsheet cells and jobs form a directed acyclic graph (DAG): an edge says “this must happen before that”. A valid run order is a topological order, found in O(V + E) by repeatedly taking something with no unmet dependencies (Kahn) or by DFS post-order. If you run out of ready nodes before you run out of nodes, there is a cycle, and you must report it rather than pick an order.

The idea in plain words

Getting dressed: socks before shoes, shirt before jacket, but socks and shirt in either order. Nobody writes out the full sequence. You keep a mental list of “things I can put on right now”, pick one, and that may unlock more.

That is dependency resolution. Three questions come up again and again:

• Order. In what sequence can I do everything so each item comes after the things it needs?
• Cycles. Is there a loop (web needs auth, auth needs session, session needs web) that makes any order impossible?
• Parallelism. Which items could run at the same time, and how long is the shortest possible run with unlimited workers?

A fourth shows up in package managers: versions. A dependency is not just “log” but “log at ^1.4”, and two packages may want incompatible ranges.

See it

Type your own packages as name: dep, dep; … or pick a preset. Step through Kahn’s algorithm. Each node shows how many dependencies it still waits on. Switch the mode to parallel waves to see the shortest build with unlimited workers, then load with a cycle and watch the algorithm get stuck.

Install order with Kahn's algorithm

step through

package: its deps; …

ready[http, log]

order[]

ready (waits on 0)installing nowinstalledstuck (cycle)

Arrows point from a dependency to the package that needs it.

Count what each package waits on (its unmet dependencies). Packages with 0 are ready now: http, log.

↺◀▶ Play▶1 / 8

Notice two things. First, log is shared by three packages but installed once: a diamond is not a cycle. Second, in wave mode the number of waves equals the length of the longest chain. That chain is the critical path, and no amount of extra workers can beat it.

When to reach for it

The problem says…	Why this fits
“X must run / be built / be taken before Y”	Each rule is a directed edge; you need a topological order.
“detect whether this is possible” / “reject circular references”	A topological sort that can’t finish has found a cycle.
“how long with unlimited workers” / “what can run in parallel”	Group by waves (levels); duration is the longest path through the DAG.
“when X changes, what must be recomputed”	Follow edges forward from X; recompute in topological order so each cell sees fresh inputs.
“install the minimum needed for target T”	DFS from T only; ignore the rest of the graph.
“pick versions that satisfy all constraints”	Version resolution: a search problem layered on top of the graph.

How it works

Kahn’s algorithm (queue of ready nodes)

1. Build the graph in the direction “dependency → dependent”, and count each node’s unmet dependencies (its in-degree).
2. Put every node with count 0 into a ready queue.
3. Pop a node, append it to the order, and decrement the count of each dependent. Any that reach 0 join the queue.
4. When the queue is empty: if the order holds every node you are done; otherwise the leftovers are on, or downstream of, a cycle.

The choice of queue is a lever. A FIFO queue gives one valid order. A min-heap gives the lexicographically smallest order. A priority queue keyed by importance gives “most important ready task first”. Taking the whole ready set at once gives the parallel waves.

DFS post-order (install one target)

Kahn needs the whole graph up front. When you only care about one target, a depth-first search from it is simpler: visit every dependency first, then emit the node. Three colours track state: white (unseen), grey (on the current path), black (finished). Reaching a grey node again means you walked in a circle, and the current path is the cycle, which makes a far better error message than “cycle detected”.

Python

install_order.py

# Install order for ONE target: only what it needs, dependencies first (DFS post-order).
# deps maps a package to the packages it needs. Raises with the cycle path if there is one.
WHITE, GREY, BLACK = 0, 1, 2  # unseen / on the current path / finished


def install_order(deps: dict[str, list[str]], target: str) -> list[str]:
    color: dict[str, int] = {}
    order: list[str] = []
    path: list[str] = []  # the current DFS path, for a readable error

    def visit(pkg: str) -> None:
        state = color.get(pkg, WHITE)
        if state == BLACK:
            return  # 1. already placed (shared dependency, e.g. a diamond)
        if state == GREY:  # 2. back to a package still on the path: a cycle
            cycle = path[path.index(pkg):] + [pkg]
            raise ValueError("cycle: " + " -> ".join(cycle))
        color[pkg] = GREY
        path.append(pkg)
        for d in deps.get(pkg, []):  # 3. everything this needs goes first
            visit(d)
        path.pop()
        color[pkg] = BLACK
        order.append(pkg)  # 4. post-order: placed after all of its deps

    visit(target)
    return order


if __name__ == "__main__":
    deps = {"app": ["web", "db"], "web": ["http", "log"], "db": ["log"], "cli": ["log"]}
    assert install_order(deps, "app") == ["http", "log", "web", "db", "app"]  # no "cli"
    assert install_order(deps, "log") == ["log"]
    try:
        install_order({"a": ["b"], "b": ["c"], "c": ["a"]}, "a")
        assert False, "expected a cycle"
    except ValueError as e:
        assert str(e) == "cycle: a -> b -> c -> a"
    print("ok")

TypeScript

install_order.ts

import assert from "node:assert/strict";

// Install order for ONE target: only what it needs, dependencies first (DFS post-order).
// deps maps a package to the packages it needs. Throws with the cycle path if there is one.
const enum Color { White, Grey, Black } // unseen / on the current path / finished

export function installOrder(deps: Map<string, string[]>, target: string): string[] {
  const color = new Map<string, Color>();
  const order: string[] = [];
  const path: string[] = []; // the current DFS path, for a readable error

  const visit = (pkg: string): void => {
    const state = color.get(pkg) ?? Color.White;
    if (state === Color.Black) return; // 1. already placed (shared dependency)
    if (state === Color.Grey) { // 2. back to a package still on the path: a cycle
      const cycle = [...path.slice(path.indexOf(pkg)), pkg];
      throw new Error("cycle: " + cycle.join(" -> "));
    }
    color.set(pkg, Color.Grey);
    path.push(pkg);
    for (const d of deps.get(pkg) ?? []) visit(d); // 3. everything this needs goes first
    path.pop();
    color.set(pkg, Color.Black);
    order.push(pkg); // 4. post-order: placed after all of its deps
  };

  visit(target);
  return order;
}

const deps = new Map([["app", ["web", "db"]], ["web", ["http", "log"]], ["db", ["log"]], ["cli", ["log"]]]);
assert.deepEqual(installOrder(deps, "app"), ["http", "log", "web", "db", "app"]); // no "cli"
assert.deepEqual(installOrder(deps, "log"), ["log"]);
assert.throws(() => installOrder(new Map([["a", ["b"]], ["b", ["c"]], ["c", ["a"]]]), "a"),
  { message: "cycle: a -> b -> c -> a" });
console.log("ok");

C#

install_order.cs

// Install order for ONE target: only what it needs, dependencies first (DFS post-order).
var deps = new Dictionary<string, string[]>
{
    ["app"] = ["web", "db"], ["web"] = ["http", "log"], ["db"] = ["log"], ["cli"] = ["log"],
};
var got = string.Join(",", Installer.InstallOrder(deps, "app"));
if (got != "http,log,web,db,app") throw new Exception($"got {got}"); // no "cli"
try
{
    Installer.InstallOrder(new() { ["a"] = ["b"], ["b"] = ["c"], ["c"] = ["a"] }, "a");
    throw new Exception("expected a cycle");
}
catch (InvalidOperationException e) when (e.Message == "cycle: a -> b -> c -> a") { }
Console.WriteLine("ok");

static class Installer
{
    enum Color { White, Grey, Black } // unseen / on the current path / finished

    public static List<string> InstallOrder(Dictionary<string, string[]> deps, string target)
    {
        var color = new Dictionary<string, Color>();
        var order = new List<string>();
        var path = new List<string>(); // the current DFS path, for a readable error

        void Visit(string pkg)
        {
            var state = color.GetValueOrDefault(pkg, Color.White);
            if (state == Color.Black) return; // 1. already placed (shared dependency)
            if (state == Color.Grey) // 2. back to a package still on the path: a cycle
            {
                var cycle = path.Skip(path.IndexOf(pkg)).Append(pkg);
                throw new InvalidOperationException("cycle: " + string.Join(" -> ", cycle));
            }
            color[pkg] = Color.Grey;
            path.Add(pkg);
            foreach (var d in deps.GetValueOrDefault(pkg, [])) Visit(d); // 3. deps go first
            path.RemoveAt(path.Count - 1);
            color[pkg] = Color.Black;
            order.Add(pkg); // 4. post-order: placed after all of its deps
        }

        Visit(target);
        return order;
    }
}

Which direction do the edges point?

Pick one and say it out loud. “A depends on B” drawn as A → B gives a DFS post-order that is already dependencies-first. Kahn wants the reverse (B → A) so that finishing B can decrement A. Mixing the two gives you an order that is exactly backwards.

Choosing versions

Real package managers resolve ranges, not names. The building block is “given the published versions, which is the newest one inside this range?”. Two details trip people up: versions compare numerically part by part (1.10.0 is newer than 1.9.9, though not as a string), and the caret ^ means “compatible”, which for 0.x versions pins the minor number.

Python

pick_version.py

# Pick the newest published version that satisfies a range like ">=1.2.0 <2.0.0" or "^1.4.0".
import operator

Version = tuple[int, int, int]
OPS = {">=": operator.ge, "<=": operator.le, ">": operator.gt, "<": operator.lt, "=": operator.eq}


def parse(v: str) -> Version:
    major, minor, patch = (int(p) for p in v.split("."))
    return (major, minor, patch)  # 1. tuples compare part by part: (1,10,0) > (1,9,9)


def caret(v: Version) -> list[tuple[str, Version]]:
    # 2. ^ means "compatible": same left-most non-zero part. ^1.4.0 -> <2.0.0, ^0.3.1 -> <0.4.0
    upper = (v[0] + 1, 0, 0) if v[0] > 0 else (0, v[1] + 1, 0)
    return [(">=", v), ("<", upper)]


def parse_range(rng: str) -> list[tuple[str, Version]]:
    out: list[tuple[str, Version]] = []
    for part in rng.split():  # 3. space-separated comparators are ANDed
        if part.startswith("^"):
            out += caret(parse(part[1:]))
            continue
        op = next(o for o in (">=", "<=", ">", "<", "=") if part.startswith(o))
        out.append((op, parse(part[len(op):])))
    return out


def pick(available: list[str], rng: str) -> str | None:
    rules = parse_range(rng)
    ok = [v for v in available if all(OPS[op](parse(v), bound) for op, bound in rules)]
    return max(ok, key=parse, default=None)  # 4. newest match wins; None = unsatisfiable


if __name__ == "__main__":
    published = ["1.2.0", "1.9.9", "1.10.0", "2.0.0", "0.3.1", "0.3.7", "0.4.0"]
    assert pick(published, "^1.2.0") == "1.10.0"  # numeric, not string, comparison
    assert pick(published, ">=1.2.0 <1.10.0") == "1.9.9"
    assert pick(published, "^0.3.1") == "0.3.7"  # 0.x: the minor is the breaking part
    assert pick(published, ">2.0.0") is None
    print("ok")

TypeScript

pick_version.ts

import assert from "node:assert/strict";

// Pick the newest published version that satisfies a range like ">=1.2.0 <2.0.0" or "^1.4.0".
type Version = [number, number, number];
type Rule = [op: string, bound: Version];

const parse = (v: string): Version => {
  const [a, b, c] = v.split(".").map(Number);
  return [a, b, c];
};
// 1. compare part by part, numerically: 1.10.0 > 1.9.9 (as strings it would not be)
const cmp = (x: Version, y: Version): number => x[0] - y[0] || x[1] - y[1] || x[2] - y[2];

const OPS: Record<string, (c: number) => boolean> = {
  ">=": (c) => c >= 0, "<=": (c) => c <= 0, ">": (c) => c > 0, "<": (c) => c < 0, "=": (c) => c === 0,
};

function parseRange(range: string): Rule[] {
  const out: Rule[] = [];
  for (const part of range.split(/\s+/)) { // 3. space-separated comparators are ANDed
    if (part.startsWith("^")) { // 2. compatible: keep the left-most non-zero part
      const v = parse(part.slice(1));
      const upper: Version = v[0] > 0 ? [v[0] + 1, 0, 0] : [0, v[1] + 1, 0];
      out.push([">=", v], ["<", upper]);
      continue;
    }
    const op = [">=", "<=", ">", "<", "="].find((o) => part.startsWith(o))!;
    out.push([op, parse(part.slice(op.length))]);
  }
  return out;
}

export function pick(available: string[], range: string): string | null {
  const rules = parseRange(range);
  const ok = available.filter((v) => rules.every(([op, b]) => OPS[op](cmp(parse(v), b))));
  return ok.sort((x, y) => cmp(parse(y), parse(x)))[0] ?? null; // 4. newest match wins
}

const published = ["1.2.0", "1.9.9", "1.10.0", "2.0.0", "0.3.1", "0.3.7", "0.4.0"];
assert.equal(pick(published, "^1.2.0"), "1.10.0");
assert.equal(pick(published, ">=1.2.0 <1.10.0"), "1.9.9");
assert.equal(pick(published, "^0.3.1"), "0.3.7"); // 0.x: the minor is the breaking part
assert.equal(pick(published, ">2.0.0"), null);
console.log("ok");

C#

pick_version.cs

// Pick the newest published version that satisfies a range like ">=1.2.0 <2.0.0" or "^1.4.0".
string[] published = ["1.2.0", "1.9.9", "1.10.0", "2.0.0", "0.3.1", "0.3.7", "0.4.0"];
Check(Semver.Pick(published, "^1.2.0"), "1.10.0");
Check(Semver.Pick(published, ">=1.2.0 <1.10.0"), "1.9.9");
Check(Semver.Pick(published, "^0.3.1"), "0.3.7"); // 0.x: the minor is the breaking part
Check(Semver.Pick(published, ">2.0.0"), null);
Console.WriteLine("ok");

static void Check(string? got, string? want)
{
    if (got != want) throw new Exception($"got {got}, want {want}");
}

static class Semver
{
    // 1. System.Version compares Major, Minor, Build numerically: 1.10.0 > 1.9.9
    static Version Parse(string v) => Version.Parse(v);

    static IEnumerable<(string Op, Version Bound)> ParseRange(string range)
    {
        foreach (var part in range.Split(' ', StringSplitOptions.RemoveEmptyEntries)) // 3. ANDed
        {
            if (part.StartsWith('^')) // 2. compatible: keep the left-most non-zero part
            {
                var v = Parse(part[1..]);
                var upper = v.Major > 0 ? new Version(v.Major + 1, 0, 0) : new Version(0, v.Minor + 1, 0);
                yield return (">=", v);
                yield return ("<", upper);
                continue;
            }
            var op = new[] { ">=", "<=", ">", "<", "=" }.First(part.StartsWith);
            yield return (op, Parse(part[op.Length..]));
        }
    }

    static bool Holds(string op, int c) => op switch
    {
        ">=" => c >= 0, "<=" => c <= 0, ">" => c > 0, "<" => c < 0, _ => c == 0,
    };

    public static string? Pick(IEnumerable<string> available, string range)
    {
        var rules = ParseRange(range).ToList();
        return available
            .Where(v => rules.All(r => Holds(r.Op, Parse(v).CompareTo(r.Bound))))
            .OrderByDescending(Parse) // 4. newest match wins; null = unsatisfiable
            .FirstOrDefault();
    }
}

When two packages need the same library in ranges that don’t overlap, there is no single answer. Ecosystems take different exits: npm installs both copies in nested folders; pip and Cargo (for the same major version) must find one version for everybody and backtrack over choices. The general problem is NP-complete (it encodes SAT), which is why modern resolvers such as Dart’s PubGrub, uv and Poetry use SAT-style conflict learning.

What it costs

Task	Time	Space	Why
Topological order (Kahn or DFS)	O(V + E)	O(V + E)	Each node enters the queue once; each edge is decremented once.
Lexicographically smallest order	O((V + E) log V)	O(V + E)	A heap replaces the FIFO queue.
Parallel waves / longest path	O(V + E)	O(V)	One pass in topological order, carrying the longest chain seen so far.
Install closure of one target	O(reachable V + E)	O(reachable V)	DFS never touches packages the target doesn’t need.
What changes when X changes	O(downstream V + E)	O(V)	Walk forward from X only.
Version resolution with conflicts	exponential worst case		Equivalent to SAT; practical resolvers prune with learned conflicts.

The DFS recursion depth equals the longest dependency chain. With tens of thousands of nodes in a chain, Python’s default recursion limit (1000) will fail first; use an explicit stack.

Variations you’ll meet

• Build systems (Make, Bazel): nodes are targets, and a node is rebuilt only when an input changed. The DAG plus timestamps or content hashes gives incremental builds.
• Spreadsheets and reactive UIs: cells depend on cells. On a write, recompute only the downstream cells, in topological order, so each is computed exactly once.
• Task runners with workers: Kahn where the ready queue is a priority queue and a fixed number of workers pull from it. Finishing a task is the event that decrements its dependents.
• Failure propagation: when a node fails, everything downstream is blocked. That is a forward walk from the failed node.
• Project planning (PERT/CPM): tasks have durations; the critical path and each task’s slack come from forward and backward passes over the DAG.

Pitfalls

• Reporting “no cycle” because you visited every node. With Kahn, check len(order) == len(nodes). With DFS you need three colours; a plain visited set can’t tell a diamond (fine) from a cycle (fatal).
• Self-loops and duplicate edges. a: a is a cycle of length one. Duplicate edges are harmless only if you count them consistently on both sides.
• Unknown dependencies. A name that appears only on the right-hand side: is it an error, or a leaf? Ask.
• Nondeterministic order. Iterating a hash set gives a different valid order each run. If output is compared in tests, define a tie-break (name ascending, insertion order, priority).
• Edge direction confusion (see the note above): the most common reason a correct-looking sort returns reversed output.

In the interview

• Ask: can there be cycles? What should happen if there are (reject, report the cycle, partial result)? Are dependencies on unknown names allowed? Is there a required tie-break?
• Say the invariant: “A node enters the ready queue exactly when its count of unmet dependencies hits zero.”
• Mention both algorithms and why you chose one: Kahn when you need the whole order or levels, DFS when you need the closure of one target or the cycle path.
• Expected follow-ups: add priorities among ready items; add durations and N workers; add failures that block dependents; make it incremental (add an edge later and re-check for a cycle in less than O(V + E) if you can).

Check yourself

Check yourself

pick one

Kahn's algorithm finishes with 7 of 10 nodes in the order. What do you know about the other 3?

AAll three form a single cycleBEach is on a cycle or depends (directly or not) on a node that isCThey have no dependencies and were skipped

Check yourself

pick one

A build has 50 tasks and the longest dependency chain is 8 tasks of 1 minute each. With unlimited workers, what is the fastest build?

A50 minutesB8 minutesClog₂ 50 ≈ 6 minutesDIt depends on the number of edges

Check yourself

pick one

Packages A and B both depend on C, and A and B are both needed by D. A DFS with a plain visited set reaches C a second time. What is it?

AA cycle; abortBA diamond; C is already placed, skip itCA bug in the graph

Practice on your own

These are classic exercises, not gym questions:

• Given a list of build rules, print a valid build order or the cycle that prevents one.
• Given tasks with durations and dependencies, compute the critical path and each task’s slack.
• Given a dictionary of words sorted in an unknown alphabet, recover a possible letter order.
• Detect whether adding one new edge to a DAG creates a cycle, without re-sorting the whole graph.

Go deeper

• CLRS, Introduction to Algorithms, ch. 22.4 “Topological sort” (DFS finishing times) and 22.3 for the white/grey/black colouring.
• Kahn, A. B. (1962), “Topological sorting of large networks”, Communications of the ACM 5(11).
• Natalie Weizenbaum, PubGrub: next-generation version solving (2018): why version resolution is hard and how conflict learning helps.
• Semantic Versioning 2.0.0 and npm’s semver range docs for the exact meaning of ^ and ~.

Related

Topological sortThe algorithm on its own, with proofs and variants.

Scheduling and task queuesWhat to do once tasks are ready: queues, priorities, workers.

Depth-first searchColours, back edges and post-order.

HeapsSwap the ready queue for a heap to get ordered or prioritised output.