Помните XKCD #2347 про башню зависимостей, которая держится на проекте «какого-то чувака из Небраски»? Один разработчик решил реализовать эту метафору на практике и написал StackTower — инструмент, который рисует башню из зависимостей любого пакета.​

Подаём на вход пакет из PyPI, npm или crates — получаем визуализацию, где блоки реально стоят друг на друге. Чем глубже зависимость в графе, тем она ближе к основанию. Есть два стиля рендеринга: чистый и hand-drawn в духе XKCD.​

Самое интересное — под капотом оказалась NP-hard задача. Чтобы блоки не пересекались, нужно найти правильный порядок узлов в каждом слое. Автор прошёл путь от брутфорса через PQ-деревья и барицентрическую эвристику до комбинированного алгоритма с branch-and-bound. Подсчёт пересечений рёбер свёлся к подсчёту инверсий через дерево Фенвика — O(E log V) вместо O(E²).​

Бонусом идёт «Nebraska Guy Ranking» — алгоритм находит мейнтейнеров, на которых держится вся башня. Чем глубже пакет и чем меньше у него мейнтейнеров, тем выше скор.​

Быстрый старт

go install github.com/matzehuels/stacktower@latest

# Парсим зависимости fastapi, например
stacktower parse python fastapi -o fastapi.json

# Рендерим что получилось
stacktower render fastapi.json -t tower -o fastapi.svg

Написано на Go, код на гитхабе.

@prog_tools