Python implementation of the C3 algorithm used in Python for MRO

c3.py

from collections.abc import Mapping, Sequence
from typing import TypeVar

T = TypeVar("T")

def linearize(node: T, dep_tree: Mapping[T, Sequence[T]]) -> tuple[T, ...]:

    @cache
    def helper(node: T) -> tuple[T, ...]:
        return (
            node,
            *merge(*(helper(dep) for dep in dep_tree[node])),
        )

    def merge(*seqs: Sequence[T]) -> list[T]:
        merge: list[T] = []
        merge_remaining = [list(seq) for seq in seqs if seq]
        while merge_remaining:
            for seq in merge_remaining:
                candidate = seq[0]
                if not any(candidate in seq[1:] for seq in merge_remaining):
                    break
            else:
                raise ValueError("Cyclic dependencies detected")
            merge.append(candidate)
            merge_remaining = [
                r
                for seq in merge_remaining
                if (r := (seq[1:] if seq[0] == candidate else seq))
            ]
        return merge

    return helper(node)