Как красиво разложить граф на экране: разбираем метод Сугиямы по шагам

О чём статья

Есть задача, которая выглядит простой ровно до того момента, пока не сядешь её решать: как автоматически расположить узлы графа на плоскости, чтобы получившаяся картинка была читаемой — без свалки пересекающихся стрелок, с понятным направлением потока.

Почему не «сетка» и не «пружинки»

Первое, что приходит в голову — расставить узлы в сетку: слева направо, с переносом на новую строку. Это делается за пять минут и разваливается на первом же реальном графе: стрелки идут во всех направлениях, пересекаются, и по картинке невозможно понять, что от чего зависит. Сетка не учитывает связи — а именно они несут смысл.

Второй вариант — force-directed раскладка (Fruchterman–Reingold, stress majorization). Идея: рёбра работают как пружины (притягивают связанные узлы), узлы отталкиваются друг от друга, система итеративно приходит в равновесие. Это отлично смотрится на ненаправленных графах-«облаках» (социальные связи, кластеры), но у неё два минуса для нашего случая:

• она не минимизирует пересечения рёбер напрямую — они просто «как получится»;

• она не выстраивает направление потока: если рёбра означают «А блокирует Б», хочется видеть А слева, Б справа, а force-directed про это ничего не знает.

Когда у графа есть направление и иерархия (зависимости задач, сборочные пайплайны, диаграммы состояний), нужен слоистый подход — метод Сугиямы. Он раскладывает узлы по «слоям» (колонкам или строкам) так, что все стрелки текут в одну сторону, и целенаправленно уменьшает число пересечений.

«Так возьми готовое»: dagre, ELK, Graphviz

Метод Сугиямы давно реализован в зрелых библиотеках, и в большинстве случаев брать их — правильный выбор. Кратко, что есть на рынке:

Почему в моём случае я всё же написал свой конвейер:

• Специфичные правила. Раскладка должна была подчиняться доменным требованиям (blocks задаёт колонки, contains/relates — «мягкие» связи, порядок статусов в канбан-режиме). Проще выразить это, владея фазами ranking и ordering, чем подгонять чужой чёрный ящик параметрами.

• Два режима на одной машине. flow и waterfall у меня отличаются ровно одной фазой (ranking). С готовой библиотекой это два разных вызова с разными обвязками; со своим кодом — одна подменяемая функция.

• Никаких рантайм-зависимостей. Backend на Python: тянуть Graphviz-бинарник или Java/WASM-порт в контейнер ради раскладки — неоправданно. Чистая Python-реализация каркаса разворачивается без внешних процессов.

• Контроль формы рёбер и доводка. Такие вещи, как выпрямление цепочек, snap проходных вершин, маршрутизация «вдоль плотной колонки», — это точечные эвристики поверх каркаса. В своём коде они добавляются в нужную фазу; в чужом — упираешься в то, что заложил автор.

• Детерминизм и тестируемость. Мне важно, чтобы одинаковый вход давал побайтово одинаковый выход (иначе прыгает картинка и не пишутся тесты). Полный контроль над tie-breaker’ами это гарантирует.

Честный вывод: если вам не нужны свои правила на уровне фаз и вы миритесь с рантайм-зависимостью — берите dagre (фронт) или Graphviz/ELK (сервер). Свой велосипед оправдан, когда раскладка — часть продукта со специфичной семантикой, а не разовая визуализация. Ну и, конечно, разобраться в методе изнутри — само по себе полезно, ради чего эта статья и написана.

Метод Сугиямы: конвейер из пяти фаз

Ключевая идея: разбить сложную задачу «нарисуй граф красиво» на пять последовательных, каждая из которых решается отдельным понятным алгоритмом. Выход одной фазы — вход следующей.

1. Убрать циклы (cycle removal) — получить DAG.

2. Разложить по слоям (ranking) — назначить каждому узлу номер слоя.

3. Упорядочить внутри слоёв (crossing minimization) — подобрать порядок узлов.

4. Назначить координаты (coordinate assignment) — точная позиция каждого узла.

5. Проложить рёбра (edge routing) — нарисовать связи в обход узлов.

Дальше — каждая фаза подробно.

Фаза 1. Убрать циклы (получить DAG)

Задача. Метод работает только с направленным ациклическим графом — DAG (directed acyclic graph): граф со стрелками, в котором, идя по стрелкам, нельзя вернуться в исходную вершину. Но реальные данные могут содержать циклы (задача А ждёт Б, Б ждёт В, В ждёт А). Пока цикл есть, «разложить по слоям слева направо» невозможно: какой из зациклённых узлов левее?

Решение. Найти рёбра, замыкающие циклы, и временно их убрать (или развернуть). Это классическая задача feedback arc set — «найти минимальный набор рёбер, удаление которых делает граф ациклическим». Точное решение NP-трудно, но на практике достаточно жадной эвристики на основе обхода в глубину (DFS).

Алгоритм: идём в глубину, каждой вершине присваиваем один из трёх цветов — белый (не посещали), серый (в текущем стеке обхода), чёрный (полностью обработана). Когда встречаем ребро в серую вершину — это «обратное ребро» (back edge), оно замыкает цикл. Такое ребро отбрасываем.

Тонкость: важно именно отбрасывать обратные рёбра, а не разворачивать. Разворот может случайно создать новый цикл в другом месте; отбрасывание гарантированно даёт DAG. Отброшенных рёбер немного (только те, что реально замыкают петли), и они всё равно продолжают влиять на раскладку — просто на более поздних фазах, через оставшиеся связи.

Ещё одна практическая деталь: DFS лучше писать итеративно, на явном стеке, а не рекурсивно. На большом графе рекурсия упрётся в лимит глубины стека и уронит процесс. Явный стек из пар (вершина, индекс_в_списке_соседей) решает это.

_WHITE, _GRAY, _BLACK = 0, 1, 2def break_cycles(    node_ids: list[str], edges: list[tuple[str, str]]) -> list[tuple[str, str]]:    adjacency: dict[str, list[str]] = defaultdict(list)    for source, target in edges:        if source != target:            adjacency[source].append(target)    color: dict[str, int] = dict.fromkeys(node_ids, _WHITE)    acyclic: list[tuple[str, str]] = []    for start in node_ids:        if color[start] != _WHITE:            continue        stack: list[tuple[str, int]] = [(start, 0)]        color[start] = _GRAY        while stack:            node, index = stack[-1]            neighbors = adjacency[node]            if index == len(neighbors):                color[node] = _BLACK                stack.pop()                continue            stack[-1] = (node, index + 1)            target = neighbors[index]            if color[target] == _GRAY:                continue          # back edge -> drop            acyclic.append((node, target))            if color[target] == _WHITE:                color[target] = _GRAY                stack.append((target, 0))    return acyclic

Результат фазы: подмножество рёбер, гарантированно образующее DAG. Порядок обхода детерминирован (следует порядку входных данных), поэтому и результат воспроизводим — важное свойство, к которому вернёмся.

Фаза 2. Разложить по слоям (ranking)

Задача. Присвоить каждому узлу номер слоя (rank) — целое число, задающее колонку (при горизонтальной раскладке) или строку (при вертикальной). Все рёбра должны идти из меньшего слоя в больший — тогда поток визуально однонаправлен.

Решение зависит от того, что мы хотим показать. Здесь удобно иметь несколько стратегий на одной и той же машине. Я сделал две.

Стратегия A — по критическому пути (longest path). Слой узла = длина самой длинной цепочки зависимостей, ведущей к нему. Это в точности критический путь из управления проектами: чем глубже задача сидит в цепочке блокировок, тем правее её колонка. Считается за линейное время топологической сортировкой (алгоритм Кана): идём по вершинам в топологическом порядке, и для каждой вершины её ранг = максимум из (ранг предшественника + 1).

def longest_path_ranks(    node_ids: list[str], acyclic_edges: list[tuple[str, str]]) -> dict[str, int]:    successors: dict[str, list[str]] = defaultdict(list)    indegree: dict[str, int] = dict.fromkeys(node_ids, 0)    for source, target in acyclic_edges:        successors[source].append(target)        indegree[target] += 1    rank: dict[str, int] = dict.fromkeys(node_ids, 0)    queue: list[str] = [n for n in node_ids if indegree[n] == 0]    while queue:        node = queue.pop(0)        for target in successors[node]:            rank[target] = max(rank[target], rank[node] + 1)            indegree[target] -= 1            if indegree[target] == 0:                queue.append(target)    return rank

Стратегия B — по фиксированному признаку. Слой = какая-то заранее известная категория узла, независимо от рёбер. В моём случае это статус задачи (open → in_progress → done), что даёт канбан-колонки. Рёбра при этом на слой не влияют — они пригодятся на следующей фазе для упорядочивания внутри колонок.

Важное наблюдение: обе стратегии — это одна и та же машина, отличается только фаза 2. Фазы 3–5 не знают, откуда взялись слои. Это делает метод Сугиямы очень гибким: захотите новый режим раскладки — часто достаточно написать новую функцию ranking.

Длинные рёбра и dummy-узлы. Ребро может перепрыгивать через несколько слоёв (из слоя 1 сразу в слой 4). Если оставить его как есть, следующие фазы не смогут учесть его при подсчёте пересечений, и линия пойдёт поверх узлов промежуточных слоёв. Классическое решение: разбить длинное ребро на цепочку коротких, вставив в каждый промежуточный слой фиктивную вершину (dummy node). Теперь ребро «видно» на каждом слое, участвует в упорядочивании как обычный узел, и под него резервируется коридор.

Результат фазы: словарь узел → номер слоя плюс фиктивные вершины для длинных рёбер.

Фаза 3. Упорядочить внутри слоёв (минимизация пересечений)

Задача. Слои заданы, но порядок узлов внутри каждого слоя — нет. От него напрямую зависит число пересечений рёбер. Цель — подобрать порядок, минимизирующий пересечения.

Почему это сложно. Даже для двух соседних слоёв задача «расставь узлы так, чтобы рёбер пересекалось минимум» — NP-трудна. Точное решение для реального графа искать бессмысленно долго. Поэтому применяют эвристики с хорошим соотношением «качество/время».

Барицентр / медиана + послойные проходы (sweep). Базовая идея, предложенная ещё Сугиямой: узел стоит тем удачнее, чем ближе он к «центру тяжести» своих соседей в соседнем слое. Алгоритм:

1. Фиксируем порядок в слое N.

2. Для каждого узла слоя N+1 считаем медиану позиций его соседей в слое N.

3. Сортируем слой N+1 по этой медиане.

4. Идём так по всем слоям сверху вниз, потом снизу вверх, несколько итераций.

Медиана здесь предпочтительнее среднего (барицентра): она устойчивее к «выбросам», когда у узла есть один далёкий сосед.

Transpose — добивка перестановками. После sweep остаются локальные пересечения, которые эвристика «пропустила». Их убирают жадно: проходим по соседним парам узлов в слое, пробуем поменять их местами; если пересечений стало меньше — оставляем перестановку, иначе откатываем. Повторяем, пока есть улучшения.

Точный подсчёт пересечений. Чтобы сравнивать варианты, нужно уметь считать пересечения между двумя слоями. Это делается элегантно: для рёбер, выходящих из верхнего слоя по порядку, выписываем позиции их концов в нижнем слое, и число пересечений = число инверсий в получившейся последовательности (пар, идущих «не по возрастанию»).

def _median_index(neighbor_positions: list[int], fallback: float) -> float:    # Медиана позиций соседей в соседнем слое (fallback - если соседей нет,    # узел остаётся на месте). В проекте используется взвешенный вариант    # медианы (bias к более плотной стороне), здесь для ясности - обычная.    if not neighbor_positions:        return fallback    neighbor_positions.sort()    middle = len(neighbor_positions) // 2    if len(neighbor_positions) % 2 == 1:        return float(neighbor_positions[middle])    return (neighbor_positions[middle - 1] + neighbor_positions[middle]) / 2.0def _sorted_by_median(    layer: list[str],    fixed_positions: dict[str, int],   # позиции узлов в уже зафиксированном слое    adjacency: dict[str, list[str]],) -> list[str]:    measures: dict[str, float] = {}    for current_index, node in enumerate(layer):        neighbor_positions = [            fixed_positions[n] for n in adjacency.get(node, ()) if n in fixed_positions        ]        measures[node] = _median_index(neighbor_positions, float(current_index))    # Сортируем по медиане; при равенстве сохраняем прежний порядок (детерминизм).    return sorted(layer, key=lambda node: (measures[node], layer.index(node)))def _pair_crossings(    upper: list[str], lower: list[str], down_adj: dict[str, list[str]]) -> int:    lower_index = {node: i for i, node in enumerate(lower)}    # Позиции концов рёбер в нижнем слое, в порядке выхода из верхнего слоя.    sequence: list[int] = []    for node in upper:        targets = sorted(            lower_index[t] for t in down_adj.get(node, ()) if t in lower_index        )        sequence.extend(targets)    # Число пересечений = число инверсий в этой последовательности.    crossings = 0    for i in range(len(sequence)):        for j in range(i + 1, len(sequence)):            if sequence[i] > sequence[j]:                crossings += 1    return crossings

Что оставляем на память. Sweep не монотонен — он может как улучшить, так и слегка ухудшить картинку на конкретной итерации. Поэтому запоминаем лучший встреченный порядок (по числу пересечений) и в конце возвращаем именно его, а не результат последней итерации.

Практическая деталь из моей задачи: помимо «жёстких» рёбер, задающих слои, есть «мягкие» связи, которые на слой не влияют, но по которым логично держать узлы рядом (например, связанные задачи одного ранга). Их удобно учитывать как дополнительный, более слабый сигнал при упорядочивании — и как вторичный критерий (при равном числе пересечений предпочесть вариант, где такие узлы стоят компактнее).

Результат фазы: порядок узлов внутри каждого слоя, дающий мало пересечений.

Фаза 4. Назначить координаты (coordinate assignment)

Задача. Слои и порядок внутри них известны. Теперь — точная координата каждого узла вдоль слоя (высота, если колонки идут слева направо). Цели конфликтуют: хочется, чтобы рёбра были прямыми (концы на одной линии), но при этом узлы не наезжали друг на друга.

Это самая тонкая фаза, и именно здесь пришлось повозиться. Разберу по частям.

Наивный подход и почему он плох. Простейший вариант: поставить каждый узел напротив медианы его соседей, а если два узла в слое налезают — сдвинуть правый. Проблема: односторонний сдвиг вносит систематический перекос (всё «уезжает» в одну сторону), а ещё оставляет лишние дыры — узел, притянутый к своей медиане, может оставить над собой пустоту, которую никто не заполнит. На практике это выглядит как «одна задача висит слишком высоко, а под ней пусто».

Правильная упаковка слоя: изотоническая регрессия (PAVA). Задачу «расставить узлы в слое как можно ближе к желаемым позициям, но с соблюдением минимальных зазоров и без наезжания» можно сформулировать строго: минимизировать суммарное отклонение от желаемых позиций при ограничении «каждый следующий узел не ближе к предыдущему, чем на минимальный зазор». Если сделать замену переменных (вычесть из позиции каждого узла накопленную сумму минимальных зазоров), ограничение превращается в «последовательность должна быть неубывающей» — а это в точности изотоническая регрессия, которая решается алгоритмом PAVA (Pool Adjacent Violators) за линейное время.

Что делает PAVA по сути: идёт по узлам слева направо; если очередной узел «хочет» встать левее предыдущего блока (нарушает монотонность) — сливает их в один блок и ставит на общее среднее; повторяет, пока последовательность не станет монотонной. Результат — оптимальная упаковка: никаких лишних дыр (плотнее минимальных зазоров не сожмёшь, шире — нет смысла) и никакого перекоса (блоки центрируются на среднем своих желаний, а не сдвигаются в одну сторону).

def _place_layer(layer, desired, positions, cross_size, gap):    # prefix[i] - накопленные минимальные зазоры до i-го узла;    # после замены targets[i] = desired[i] - prefix[i] ограничение    # превращается в "targets должны быть неубывающими".    prefix = [0.0] * len(layer)    for i in range(1, len(layer)):        prefix[i] = prefix[i-1] + separation(layer[i-1], layer[i], cross_size, gap)    targets = [desired[layer[i]] - prefix[i] for i in range(len(layer))]    # PAVA: сливаем соседние блоки, пока последовательность не станет монотонной.    values, counts = [], []    for t in targets:        value, size = t, 1        while values and values[-1] > value:            pv, ps = values.pop(), counts.pop()            value = (value * size + pv * ps) / (size + ps)            size += ps        values.append(value); counts.append(size)    i = 0    for value, size in zip(values, counts):        for _ in range(size):            positions[layer[i]] = value + prefix[i]   # возвращаем сдвиг обратно            i += 1

Этот приём — в духе известного алгоритма Brandes–Köpf для назначения координат в слоистых графах (он выравнивает узлы в прямые вертикальные «ленты»). Полный Brandes–Köpf сложнее; здесь взята его идея — «тянуть к прямизне, но без наложений» — в более простой и предсказуемой форме.

Выпрямление цепочек. Медианное притяжение с чередующимися проходами (вниз/вверх) оставляет длинные цепочки-«паровозики» слегка зигзагообразными: на каждом проходе узел выравнивается только по одной стороне. Помогает несколько двусторонних сглаживающих проходов в конце: узел тянется к медиане соседей сразу слева и справа. Это выпрямляет то, что односторонние проходы оставляли волнистым.

Финальная доводка — snap проходных вершин. Даже после сглаживания у звена цепочки остаётся «дрожание» в несколько пикселей относительно линии соседей. На отрисовке это превращается в противный излом «горизонталь — короткий наклон — горизонталь». Лечится точечно: если узел является проходной вершиной (ровно один вход и не более одного выхода — то есть звено цепочки), его координату «прищёлкиваем» точно к координате доминирующего соседа — но только если он и так уже почти на месте (в пределах небольшого порога). Проходы повторяем до сходимости, чтобы выравнивание распространилось вдоль всей цепочки; после каждого прохода снова прогоняем PAVA, чтобы snap не создал наложений. Развилки и слияния (вершина с несколькими соседями с одной стороны — «ромб», веер) намеренно не трогаем: там наклон рёбер геометрически неизбежен, если не давать узлам налезать.

Важный принцип всей фазы: любая операция, двигающая узлы, тут же прогоняется через упаковку, гарантирующую минимальные зазоры. Так мы получаем «красивее», ни разу не заплатив «наезжающими карточками».

Результат фазы: финальная координата каждого узла. Рёбра максимально прямые, узлы не пересекаются.

Фаза 5. Проложить рёбра (edge routing)

Задача. Узлы стоят. Осталось нарисовать сами связи — и так, чтобы линии не проходили сквозь узлы (и по возможности не путались между собой).

Здесь есть развилка ответственности. Первые четыре фазы уже расставили узлы по слоям с коридорами и гарантируют, что провести связи без пересечений геометрически возможно. Но конкретную пиксельную форму линии удобно считать отдельно — тем более что она должна пересчитываться на лету, когда пользователь таскает узлы мышью.

Подход — генерация кандидатов + проверка на столкновения. Для каждого ребра генерируем несколько вариантов пути и берём первый, который ни с чем не сталкивается, предпочитая варианты с меньшим числом изломов:

• прямой отрезок — если концы уже почти на одной линии;

• пологая скошенная прямая — для обычных связей вдоль потока (небольшой наклон), она читается мягче, чем прямоугольные изломы;

• ортогональные Г- и Z-образные пути — для «крутых» связей (веер, где перепад поперёк потока большой): линия идёт вдоль свободных коридоров между узлами.

Столкновение проверяется просто: путь — это набор отрезков, для каждого проверяем пересечение с прямоугольником каждого узла (расширенным на небольшой зазор). Так как все сегменты осевые (горизонтальные или вертикальные), проверка сводится к пересечению двух прямоугольников:

type Pt = { x: number; y: number };// Пересекает ли осевой отрезок a->b прямоугольник rect (расширенный на pad)?function segmentHitsRect(a: Pt, b: Pt, rect: RouteRect, pad: number): boolean {  const [rx0, ry0, rx1, ry1] = rectBounds(rect);  const x0 = rx0 - pad, y0 = ry0 - pad, x1 = rx1 + pad, y1 = ry1 + pad;  // Bounding box отрезка (у осевого отрезка он вырожден в линию) против рамки.  const loX = Math.min(a.x, b.x), hiX = Math.max(a.x, b.x);  const loY = Math.min(a.y, b.y), hiY = Math.max(a.y, b.y);  return loX <= x1 && hiX >= x0 && loY <= y1 && hiY >= y0;}function pathHitsObstacles(points: Pt[], obstacles: RouteRect[]): boolean {  for (let i = 0; i < points.length - 1; i += 1) {    for (const rect of obstacles) {      if (segmentHitsRect(points[i], points[i + 1], rect, CLEARANCE)) {        return true;      }    }  }  return false;}

Сама генерация кандидатов и выбор первого «чистого» пути:

function routeEdge(  source: RouteRect,  target: RouteRect,  obstacles: RouteRect[],): Pt[] {  const s = /* точка выхода из source + короткий «ус» (stub) */;  const t = /* точка входа в target + короткий «ус» */;  const dxAbs = Math.abs(t.x - s.x);  const dyAbs = Math.abs(t.y - s.y);  // Пологая связь вдоль потока -> скошенная прямая; крутая (веер) -> ортогонали.  const gentle = dyAbs <= dxAbs;  // Кандидаты, от дешёвых (мало изломов) к дорогим.  const candidates: Pt[][] = [];  if (gentle) candidates.push([s, t]);                       // скошенная прямая  candidates.push([s, { x: s.x, y: t.y }, t]);               // Г-путь у источника  candidates.push([s, { x: t.x, y: s.y }, t]);               // Г-путь у цели  for (const mx of verticalChannels(s, t, obstacles)) {      // Z-пути по коридорам    candidates.push([s, { x: mx, y: s.y }, { x: mx, y: t.y }, t]);  }  let fallback: Pt[] | null = null;  for (const path of candidates) {    fallback ??= path;    if (!pathHitsObstacles(path, obstacles)) return path;    // первый чистый  }  return fallback ?? [s, t];   // если всё перекрыто - хоть что-то нарисуем}

Полезная эвристика для веера. Когда в один узел сходится много связей от узлов, растянутых по вертикали, «наивные» пути веером расходятся и выглядят неряшливо. Приём: длинный вертикальный участок пути вести вдоль более плотной колонки узлов — тогда связь от крайнего узла прижимается к общей массе параллельных линий, а не улетает в сторону одинокого узла. Получаются аккуратные пучки параллельных дорожек, как в разводке печатных плат.

Отдельно стоит отметить, почему routing вынесен из «расстановки узлов»: измерения показали, что наложения линий на узлы почти невозможно убрать раздвиганием узлов (нужен кратный рост зазоров, и всё равно остаются перекрытия) — потому что проблема в форме линии, а не в тесноте. Правильнее гарантировать геометрическую возможность обхода на фазах 1–4, а саму форму считать отдельным маршрутизатором.

Результат фазы: для каждого ребра — ломаная (или скошенная прямая), огибающая узлы.

Связные компоненты: собираем несколько графов вместе

Реальная доска — это часто не один граф, а несколько независимых: группы задач без связей между собой. Раскладывать их в общей системе слоёв бессмысленно — одна большая цепочка растянет весь холст, а остальное будет болтаться.

Решение в два шага:

1. Выделить связные компоненты. Классический union-find (система непересекающихся множеств): объединяем узлы, соединённые ребром; в конце каждая группа — отдельная компонента. С оптимизациями (сжатие путей, объединение по рангу) работает практически за линейное время.

2. Разложить каждую компоненту отдельно и затем упаковать их прямоугольники рядом. Упаковку удобно делать «полками» (shelf packing): раскладываем боксы слева направо, перенос на новую «полку» при переполнении ширины; целевую ширину берём так, чтобы итог был примерно квадратным, а не вытянутой лентой.

Сквозные свойства, о которых легко забыть

Несколько вещей, которые важны не меньше самих алгоритмов.

Детерминизм. При одинаковом входе результат должен быть идентичным — иначе раскладку невозможно нормально тестировать, а пользователь при повторном нажатии кнопки получает «прыгающую» картинку. Достигается тем, что каждый шаг зависит только от входных данных и порядка их обхода: везде, где есть неоднозначность (порядок соседей, сортировка при равных ключах), фиксируем порядок входных данных как tie-breaker.

Отказоустойчивость. Раскладка не должна ронять запрос. Если на вход пришёл «неправильный» граф (например, из-за отброшенных рёбер что-то осталось без ранга) — лучше поставить узел в слой 0, чем бросить исключение.

Гарантия «без наложений» как инвариант. Самое ценное решение по архитектуре фазы 4: не «сначала подвигаем, потом починим наложения», а «любое движение сразу проходит через упаковку, которая наложения исключает». Инвариант, который держится на каждом шаге, избавляет от целого класса багов.

Что осталось за кадром

Метод Сугиямы — это каркас, который можно улучшать почти бесконечно. Что напрашивается дальше:

• Полный Brandes–Köpf для фазы координат: он умеет ещё аккуратнее выравнивать узлы, в том числе «плавающие» вершины без межслойных связей, которые в упрощённой версии могут держаться с краю колонки.

• Минимизация пересечений рёбер между собой (не только с узлами): сейчас каждое ребро маршрутизируется независимо, а можно раскладывать пучки параллельных линий согласованно.

• Режим force-directed как альтернатива — для сильно связанных кластеров без явной иерархии, где слоистая раскладка не даёт выигрыша.

• Схлопывание поддеревьев при отдалении (level of detail): на большом графе показывать группы свёрнутыми, разворачивая по мере приближения.

---

Итог

Метод Сугиямы ценен тем, что раскладывает неподъёмную задачу «нарисуй граф красиво» на пять обозримых фаз, у каждой — свой понятный алгоритм с известными свойствами:

1. Убрать циклы — DFS, отбрасывание обратных рёбер (feedback arc set).

2. Слои — longest path (критический путь) или фиксированный признак; dummy-узлы для длинных рёбер.

3. Порядок в слоях — медианная эвристика + послойные проходы + transpose; пересечения считаем через инверсии.

4. Координаты — притяжение к медиане + упаковка изотонической регрессией (PAVA) в духе Brandes–Köpf; сглаживание и snap цепочек.

5. Рёбра — генерация кандидатов-путей с обходом узлов, эвристики для веера.

Плюс union-find для компонент и упаковка их боксов. Всё это реализуемо с нуля, без внешних библиотек, детерминированно и с гарантией отсутствия наложений — и работает на графах в сотни узлов.

Если будете делать похожее — рекомендую собирать конвейер именно так, по фазам: каждую можно отлаживать и заменять независимо, а неочевидные сложности (лишние дыры, зигзаги цепочек, наложение линий) оказываются локализованы в конкретной фазе, а не размазаны по всему коду.

---

Часть работы — особенно доводка фазы координат (PAVA, выпрямление цепочек, snap проходных вершин) — велась в паре с AI-ассистентом: гипотезы проверялись на синтетических графах измерительными скриптами, а решения фиксировались, когда метрики (число наложений, суммарный «излом» рёбер) подтверждали улучшение.