Topological order with DFS

A depth-first search produces a topological order as a side effect of how it ends each node: it finishes a node only after it has finished everything that node leads to. Follow arrows from each package to the packages it requires, write a package down at the moment it finishes, and the list is an install order in which every package comes after all it requires. Follow arrows the other way, from what comes first to what comes after, and the same list runs backwards, so it is reversed at the end. Three states per node, not reached, on the current path and finished, catch a loop on the way: an arrow back to a node that is still on the path means no order exists. Kept on a stack of its own instead of in nested calls, the search handles a chain of 100,000 packages as easily as six.

The problem: an install order for packages

Four examples:

1. The site in the diagram, {"site": ["theme", "markdown"], "theme": ["fonts", "icons"], "icons": ["fonts"], "markdown": ["parser"]}, gives fonts, icons, theme, parser, markdown, site. Nine other orders are valid too, such as parser, fonts, icons, markdown, theme, site.
2. {"auth": ["session"], "session": ["crypto", "auth"]} gives []: auth and session wait for each other.
3. {"x": ["x"]} gives []: x waits for itself.
4. pkg0 requires pkg1, which requires pkg2, and so on to pkg99999: the only order starts at pkg99999.

The brute force: install what each package requires, every time

The direct code installs a package by first installing each package it requires, the same way, then the package itself unless it is installed already. It is right when there is no loop, but it remembers nothing it has explored:

"""The brute force: install what a package requires, recursively, with no memory of what was already explored."""


def naive_order(requires):
    """An install order and the number of calls it took (it never stops on a loop)."""
    order, installed = [], set()
    calls = 0

    def install(p):
        nonlocal calls
        calls += 1
        for r in requires.get(p, ()):
            install(r)                  # explored again, however often it was explored before
        if p not in installed:
            installed.add(p)
            order.append(p)

    for p in requires:
        install(p)
    return order, calls


def diamonds(k):
    """top requires a1 and b1, both require m1, m1 requires a2 and b2, ..., down to mk."""
    requires = {"top": ["a1", "b1"]}
    for i in range(1, k + 1):
        requires[f"a{i}"] = [f"m{i}"]
        requires[f"b{i}"] = [f"m{i}"]
        requires[f"m{i}"] = [f"a{i + 1}", f"b{i + 1}"] if i < k else []
    return requires


site = {
    "site": ["theme", "markdown"],
    "theme": ["fonts", "icons"],
    "icons": ["fonts"],
    "markdown": ["parser"],
}
order, calls = naive_order(site)
print("site:", " ".join(order), f"({calls} calls for {len(order)} packages)")

print("\nA chain of diamonds: every level doubles the calls")
for k in (1, 2, 4, 8, 12, 16):
    order, calls = naive_order(diamonds(k))
    assert calls == 2 ** (k + 4) - 7 * k - 15     # the exact count, so it can be worked out for larger k
    print(f"{k:2} diamonds: {len(order):2} packages, {calls:>9,} calls")

loop = {"auth": ["session"], "session": ["crypto", "auth"]}
try:
    naive_order(loop)
except RecursionError:
    print("\nauth and session require each other: the calls never end, and Python stops them with RecursionError")

site: fonts icons theme parser markdown site (15 calls for 6 packages)

A chain of diamonds: every level doubles the calls
 1 diamonds:  4 packages,        10 calls
 2 diamonds:  7 packages,        35 calls
 4 diamonds: 13 packages,       213 calls
 8 diamonds: 25 packages,     4,025 calls
12 diamonds: 37 packages,    65,437 calls
16 diamonds: 49 packages, 1,048,449 calls

auth and session require each other: the calls never end, and Python stops them with RecursionError

It makes 15 calls for the site’s 6 packages. In a chain of diamonds, where two packages of each level require the same package below them, every level doubles the calls, and the run checks each count against 2^k+4 − 7k − 15. Thirty diamonds, 91 packages, would need about 1.7 × 10¹⁰ calls, roughly 30 minutes at the CPython rate assumed in the lesson on constraints. On a loop the calls never end: auth calls session, which calls auth, until Python raises RecursionError.

What to notice

• A package’s place depends only on what it requires, so once it is done, exploring it again changes nothing: remember it.
• Arriving at a package that is entered but not finished means a loop, and a single “seen” mark cannot tell that from arriving at a finished one.

The key idea: a package is done when its requirements are

Give each package one of three states: new, open (entered and not finished, so it is on the current path) and done. Start a search at every package that is still new. The search opens a package and reads its requirements one by one:

• a new requirement is opened and searched first;
• a done requirement is in the order already, so there is nothing to do;
• an open requirement is on the current path, so it requires the package being read, directly or through others: that is a loop, and the answer is [].

When its last requirement has been read, the package is done and goes to the end of the order, after everything it requires. The arrows here point from a package to what must come before it. With arrows from what comes first to what comes after, as in the lesson on Kahn’s algorithm, a node finishes after everything that must follow it, and that list must be reversed. Reversing a list that is already right gives one that is exactly backwards.

A recursive function is the shortest way to write the search, but a chain of 100,000 packages would need 100,000 nested calls. Keep the path in a list instead, and beside each package on it the position of the next requirement to read: the package on top decides the next step, and popping it returns to the one below where it stopped. Each name is opened once and each requirement read once, so the search costs O(n + m) time for n names and m requirements, and O(n) memory beside the input.

A dry run on the site

"""Every step of the depth-first search on two small sets of packages: what it reads, the path, and the order so far."""

NEW, OPEN, DONE = "new", "open", "done"


def trace(requires):
    state, order = {}, []
    for root in requires:
        if state.get(root, NEW) != NEW:
            continue
        state[root] = OPEN
        stack = [[root, 0]]                      # [package, position of the next requirement to read]
        print(f"  start at {root:<22} path: {root}")
        while stack:
            top = stack[-1]
            p, i = top
            needs = requires.get(p, [])
            if i == len(needs):
                stack.pop()
                state[p] = DONE
                order.append(p)
                print(f"  {p + ' is done':<31} order: {' '.join(order)}")
                continue
            top[1] += 1
            r = needs[i]
            s = state.get(r, NEW)
            step = f"{p} needs {r}"
            if s == DONE:
                print(f"  {step:<31} {r} is done already: nothing to do")
            elif s == OPEN:
                loop = [q for q, _ in stack[[q for q, _ in stack].index(r):]] + [r]
                print(f"  {step:<31} {r} is open, on the path: a loop, {' > '.join(loop)}")
                return []
            else:
                state[r] = OPEN
                stack.append([r, 0])
                print(f"  {step:<31} path: {' > '.join(q for q, _ in stack)}")
    return order


site = {
    "site": ["theme", "markdown"],
    "theme": ["fonts", "icons"],
    "icons": ["fonts"],
    "markdown": ["parser"],
}
print("The site:")
print("Install order:", trace(site))

print("\nauth and session:")
print("Install order:", trace({"auth": ["session"], "session": ["crypto", "auth"]}))

The site:
  start at site                   path: site
  site needs theme                path: site > theme
  theme needs fonts               path: site > theme > fonts
  fonts is done                   order: fonts
  theme needs icons               path: site > theme > icons
  icons needs fonts               fonts is done already: nothing to do
  icons is done                   order: fonts icons
  theme is done                   order: fonts icons theme
  site needs markdown             path: site > markdown
  markdown needs parser           path: site > markdown > parser
  parser is done                  order: fonts icons theme parser
  markdown is done                order: fonts icons theme parser markdown
  site is done                    order: fonts icons theme parser markdown site
Install order: ['fonts', 'icons', 'theme', 'parser', 'markdown', 'site']

auth and session:
  start at auth                   path: auth
  auth needs session              path: auth > session
  session needs crypto            path: auth > session > crypto
  crypto is done                  order: crypto
  session needs auth              auth is open, on the path: a loop, auth > session > auth
Install order: []

fonts is finished first, so it is installed first. When icons reads fonts again, fonts is done: a package reached twice is not a loop. On the second input, session reads auth while auth is still open below it on the path: a loop.

Exercise: an install order for any input

install_order({"app": ["lib", "util"], "util": ["lib"]})   # ['lib', 'util', 'app']
install_order({"auth": ["session"], "session": ["auth"]})  # []: a loop
install_order({"x": [], "y": []})                          # ['x', 'y'], or ['y', 'x']

def install_order(requires):
    """Every package after everything it requires, or [] when some packages require each other in a loop."""
    # This search is right on small inputs without loops. It misses loops, and it recurses once per package.
    seen = set()
    order = []

    def visit(p):
        seen.add(p)
        for r in requires.get(p, []):
            if r not in seen:
                visit(r)
        order.append(p)

    for p in requires:
        if p not in seen:
            visit(p)
    return order

import copy
import random

from install import install_order


def names_of(requires):
    return list(dict.fromkeys([*requires, *(r for rs in requires.values() for r in rs)]))


def has_loop(requires):
    """Installs, again and again, any package whose requirements are all installed: slow, but hard to get wrong."""
    names = names_of(requires)
    done = set()
    while True:
        ready = [p for p in names if p not in done and all(r in done for r in requires.get(p, []))]
        if not ready:
            return len(done) < len(names)
        done.update(ready)


def check(requires):
    got = install_order(requires)
    if has_loop(requires):
        assert got == [], f"install_order({requires}) returned {got}, but some packages require each other in a loop"
        return
    names = names_of(requires)
    assert sorted(got) == sorted(names), f"install_order({requires}) returned {got}, not every package exactly once"
    at = {p: i for i, p in enumerate(got)}
    for p, rs in requires.items():
        for r in rs:
            assert at[r] < at[p], f"install_order({requires}) returned {got}, which puts {p} before {r}"


def test_the_examples():
    """the three calls of the prompt"""
    assert install_order({"app": ["lib", "util"], "util": ["lib"]}) == ["lib", "util", "app"]
    assert install_order({"auth": ["session"], "session": ["auth"]}) == []
    assert sorted(install_order({"x": [], "y": []})) == ["x", "y"]


def test_the_site():
    """the lesson's site: fonts is reached twice, which is not a loop"""
    check({"site": ["theme", "markdown"], "theme": ["fonts", "icons"], "icons": ["fonts"], "markdown": ["parser"]})


def test_loops_of_every_size():
    """a package that requires itself, a loop of two behind a package, a loop of four that the first package misses"""
    check({"x": ["x"]})
    check({"cart": ["auth"], "auth": ["session"], "session": ["crypto", "auth"]})
    check({"a": [], "b": ["c"], "c": ["d"], "d": ["e"], "e": ["b"]})


def test_repeats_and_empty_input():
    """a requirement listed twice, a package with an empty list, and no packages at all"""
    check({"app": ["lib", "lib"]})
    check({"app": [], "lib": ["app"]})
    assert install_order({}) == []


def test_the_input_is_left_unchanged():
    """the function reads the dictionary and changes nothing in it"""
    requires = {"a": ["b"], "b": ["c"]}
    before = copy.deepcopy(requires)
    install_order(requires)
    assert requires == before


def test_random_sets_of_packages():
    """400 random sets of up to 8 packages, half of them made without a loop"""
    rng = random.Random(11)
    for t in range(400):
        names = [f"p{i}" for i in range(rng.randint(1, 8))]
        requires = {}
        for i, p in enumerate(names):
            pool = names[:i] if t % 2 == 0 else names
            if pool:
                requires[p] = [rng.choice(pool) for _ in range(rng.randint(0, 3))]
            elif rng.random() < 0.5:
                requires[p] = []
        keys = list(requires)
        rng.shuffle(keys)
        check({p: requires[p] for p in keys})


def test_a_chain_of_100000():
    """pkg0 requires pkg1, which requires pkg2, ... down to pkg99999; then the same chain closed into a loop"""
    n = 100_000
    chain = {f"pkg{i}": [f"pkg{i + 1}"] for i in range(n - 1)}
    got = install_order(chain)
    assert len(got) == n and got[0] == "pkg99999" and got[-1] == "pkg0", "the chain must be installed from its end"
    chain["pkg99999"] = ["pkg0"]
    assert install_order(chain) == [], "the chain closed into a loop has no install order"

Why the finishing order is valid, with the code in five languages Pro: opens with a Pro, Premium or Ultimate pass

Deep chains measured in five languages, and six bugs found Pro: opens with a Pro, Premium or Ultimate pass

Kahn or DFS, reporting the loop, and a practice set Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Following arrows to requirements, the order in which a depth-first search finishes packages is an install order; with arrows from what comes first to what comes after, reverse it.
• Three states, new, open and done, tell a loop, an arrow to an open package, from a package reached twice.
• Keep the path and each package’s next position on a stack of your own: O(n + m) time, and no recursion limit to hit.