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"

Shorter + nicer, before:

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


class Graph:
    def __init__(self, n):
        self.n = n
        self.graph = defaultdict(list)
        self.in_degree = [0] * n

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.in_degree[v] += 1


def kahn_topological_sort(graph):
    pq = [i for i in range(graph.n) if graph.in_degree[i] == 0]
    heapify(pq)  # pick smallest index first
    order = []

    while pq:
        node = heappop(pq)
        order.append(node)
        for nei in graph.graph[node]:
            graph.in_degree[nei] -= 1
            if graph.in_degree[nei] == 0:
                heappush(pq, nei)

    if len(order) != graph.n:
        raise ValueError("Graph has at least one cycle, topological sort not possible")
    return order


nodes = {"C", "B", "A", "D", "E", "F"}
pairs = [
    ("C", "A"),
    ("C", "F"),
    ("A", "B"),
    ("A", "D"),
    ("B", "E"),
    ("D", "E"),
    ("F", "E"),
]
letters = sorted(nodes)  # ensures lexicographic order by index
idx = {ch: i for i, ch in enumerate(letters)}
rev = letters  # index -> letter
graph = Graph(len(letters))

for u, v in pairs:
    graph.add_edge(idx[u], idx[v])

order_idx = kahn_topological_sort(graph)
assert "".join(rev[i] for i in order_idx) == "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.