topo_lex.py

from collections import defaultdict
from graphlib import TopologicalSorter
from heapq import heappush, heappop, heapify


def topo_lex(pairs):
    deps = defaultdict(set)  # node -> set(dependencies)
    for a, b in pairs:
        deps.setdefault(a, set())
        deps[b].add(a)

    ts = TopologicalSorter(deps)
    ts.prepare()

    pq = list(ts.get_ready())
    heapify(pq)
    out = []
    while pq:
        n = heappop(pq)  # smallest ready node
        out.append(n)
        ts.done(n)
        for r in ts.get_ready():
            heappush(pq, r)

    if len(out) != len(deps):
        raise ValueError("cycle")
    return "".join(out)


pairs = [
    ("C", "A"),
    ("C", "F"),
    ("A", "B"),
    ("A", "D"),
    ("B", "E"),
    ("D", "E"),
    ("F", "E"),
]
assert topo_lex(pairs) == "CABDFE"

Thanks for sharing, @bbelderbos ! I will read it together with the challenge of day 5 of Advent of Code, 2024 and try to understand. Although my needs are not the same as this for ordering, it shines a light on practical uses of graphs (I know, I know, there are many, but I didn't have a first-hand experience yet and your code will help me get my hands dirty).

Nice, thanks. This was for 2018 - day 07 actually.