О чём статья

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

Я делаю визуальный трекер задач. В какой-то момент импортировал в него проект на сотню задач с зависимостями — и получил то, что на скриншоте выше. С этим надо было что-то делать.

Я полез разбираться и выяснил, что это отдельная дисциплина — Graph Drawing — и ей не один десяток лет. Для направленных графов один из основных подходов — слоистая раскладка Сугиямы (Sugiyama layered layout), описанная ещё в 1981 году. На похожих идеях работают dot из Graphviz, Dagre и ELK (Eclipse Layout Kernel).

В статье разбираю метод по шагам: из каких фаз он состоит, какой алгоритм работает на каждой и какие грабли я собрал по дороге. Весь код — из рабочего проекта: раскладка узлов на Python (около 950 строк вместе с типами и упаковкой компонент), маршрутизация рёбер на TypeScript (ещё около 300).

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

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

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

Для зависимостей задач, пайплайнов и диаграмм состояний лучше подходит слоистый подход: узлы раскладываются по слоям-колонкам, стрелки текут в одну сторону, а число пересечений целенаправлено уменьшается. Это и есть метод Сугиямы.

Готовые инструменты

Метод давно реализован в зрелых библиотеках. В большинстве случаев проще взять готовую:

• Graphviz (dot; в браузере — @viz-js/viz через WASM) — зрелая реализация с кластерами, портами и роутингом. В моём Python-контейнере это означало бы отдельную системную зависимость и внешний процесс. Внутрь фаз конвейера через публичный API не влезть — остаётся настраивать атрибуты.

• @dagrejs/dagre — чистый JS с простым API. Он возвращает координаты узлов и точки рёбер; в UI их можно отрисовать как есть или заменить своим роутером. Фазы конвейера через публичный API не подменяются.

• d3-dag — один из JS-вариантов с настраиваемым конвейером: можно подменить layering, decross, coord. Работает с DAG, поэтому циклы надо обработать заранее; рендеринг и роутинг остаются на вас.

• ELK (elkjs) — самый навороченный: compound-узлы, явные порты, роутинг, Web Worker. Опций много, но вставить свою JS-реализацию отдельной фазы через elkjs нельзя.

• Grandalf (Python) — маленькая библиотека с читаемыми исходниками, но проект скорее экспериментальный, и лицензию GPLv2/EPLv1 стоит примерить к своему продукту заранее.

• fast-sugiyama (Python + Rust) — быстро, без Graphviz-процесса, результат близок к dot. Пока beta.

• yFiles for HTML — коммерческий SDK, умеет почти всё, включая инкрементальную раскладку. Стоит соответственно.

Почему я всё-таки написал свою реализацию.

Главная причина — доменные правила. В трекере три вида связей, и раскладка обязана их различать: blocks задаёт ранги, а contains и relates растягивать граф не должны — подзадача должна стоять рядом с родителем, а не уезжать на другой конец холста. Мне нужно было, чтобы тип связи влиял и на назначение ранга, и на порядок внутри слоя.

Вторая — два режима на одном конвейере. Flow (колонки по зависимостям) и Waterfall (колонки по статусам) различаются только назначением слоёв. В коде это одна сменная функция.

Ну и мелочи, которые в сумме перевесили: не хотелось тащить в Python-контейнер Graphviz-бинарник ради одной функции, а точечные эвристики формы рёбер (выпрямление цепочек, прижатие линий к плотной колонке) проще докрутить в своём коде, чем выпрашивать у чужого параметрами.

Если своих правил группировки нет и лишняя зависимость не пугает — берите dagre на фронте или Graphviz/ELK на сервере. Свой велосипед оправдан, когда раскладка — часть продукта со своей семантикой, а не разовая картинка.

---

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

В этой реализации расплывчатое «нарисуй граф красиво» разбито на пять последовательных задач:

1. Разорвать циклы (cycle removal).

2. Назначить слои (ranking).

3. Упорядочить узлы внутри слоёв (ordering).

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

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

Фаза 1. Разорвать циклы

Пока в графе есть цикл А → Б → В → А, «раньше/позже» не определено — раскладке нужен DAG.

Обход в глубину красит вершины в три цвета; ребро в «серую» вершину (ещё лежащую в стеке DFS) замыкает цикл — я убираю его из временного графа раскладки. Из модели связь не исчезает: в Flow это касается только blocks, потому что именно они задают слои. На доске связь остаётся и может участвовать в следующих фазах.

Точное решение задачи feedback arc set NP-трудно, но на реальных досках циклы — редкость, и жадной эвристики хватает за глаза.

Два практических нюанса. Стек DFS явный, а не рекурсивный: на длинной цепочке задач рекурсия упрётся в лимит глубины Python. И при фиксированном входном порядке результат детерминирован — это ещё пригодится.

_WHITE, _GRAY, _BLACK = 0, 1, 2

def 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

Фаза 2. Назначить слои (ranking)

Слой — это пока только номер колонки: что левее, что правее. Точное место внутри колонки появится позже.

• Flow: ранг узла — число blocks в самой длинной направленной цепочке до него. Чем глубже задача в цепочке блокеров, тем правее колонка. Это не календарный critical path: длительности задач алгоритм не учитывает.

• Waterfall: ранг — просто статус, open → in_progress → blocked → done. Получаются канбан-колонки, а связи влияют только на порядок внутри них. Это порядок колонок, а не обязательная последовательность жизненного цикла задачи.

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

Ещё одна доменная деталь. Ранги считаются только по blocks, и узел, у которого вся семантика в contains (типичный эпик), остался бы в колонке 0 — далеко от своих подзадач. Поэтому после ranking ранг «заякоренных» узлов распространятся по contains-рёбрам, пока есть что распространять, — и поддерево оказывается в одной колонке, стопкой.

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

Фаза 3. Упорядочить узлы внутри слоёв (ordering)

Теперь надо расставить узлы внутри каждого слоя так, чтобы рёбра пересекались как можно реже. Минимизация пересечений NP-трудна, поэтому здесь работает классическая связка эвристик.

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

Пересечения между парой слоёв считаются как инверсии в последовательности концов рёбер — в лоб, двойным циклом. Да, квадрат; на сотнях узлов это незаметно, а до тысяч мои доски пока не доросли. Если дорастут — заменю на подсчёт инверсий сортировкой слиянием.

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.0


def _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

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

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

Желаемая позиция узла — медиана позиций его соседей. Дальше слой «упаковывается»: минимизируем суммарное отклонение от желаемых позиций при ограничении «между соседями не меньше минимального зазора». Подстановкой это сводится к изотонической регрессии, которую решает PAVA (pool adjacent violators): конфликтующие узлы сливаются в блок и центрируются по среднему своих желаний. В отличие от наивного «сдвинь вправо, если наехал», PAVA не даёт систематического дрейфа; большие промежутки остаются только там, где их требуют желаемые позиции.

Например, две карточки хотят оказаться на координатах 0 и 20, но между их центрами нужно оставить 80. Жадный проход оставит первую на 0 и сдвинет вторую на 80. PAVA поставит их на -30 и 50: зазор соблюдён, а весь блок не уехал вправо.

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

В конце snap: «проходной» узел (один вход и не больше одного выхода) притягивается точно на координату соседа, если отклонение меньше 0.6 его размера. Появился он не от хорошей жизни: короткое ребро с разницей в три пикселя рисуется как «ступенька — склон — ступенька», и я не сразу понял, откуда эти ступеньки берутся, пока не посмотрел координаты руками. Порог подбирал экспериментально: меньше — короткие рёбра остаются кривыми, больше — настоящие ветки начинают прилипать к чужой оси. Snap повторяется до неподвижной точки (на практике 2-3 прохода, лимит 8), и после каждого движения слой снова прогоняется через PAVA. Так результат автораскладки остаётся без наложений.

Зазоры заданы долями размера карточки, а не пикселями: 0.6 ширины между колонками, 0.5 высоты между узлами в колонке. Раскладка масштабируется вместе с узлами.

def _place_layer(
    layer: list[str],
    desired: dict[str, float],
    positions: dict[str, float],
    cross_size: dict[str, float],
    gap: float,
) -> None:
    # prefix[i] - накопленные минимальные зазоры до i-го узла;
    # после замены targets[i] = desired[i] - prefix[i] ограничение
    # превращается в "targets должны быть неубывающими".
    prefix: list[float] = [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: list[float] = [desired[layer[i]] - prefix[i] for i in range(len(layer))]

    # PAVA: сливаем соседние блоки, пока последовательность не станет монотонной.
    values: list[float] = []
    counts: list[int] = []
    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

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

Осталось провести сами линии — так, чтобы маршрут не задевал чужие карточки.

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

Для каждого ребра генерируются кандидаты от дешёвых к дорогим: пологая диагональ (если смещение поперёк потока не больше, чем вдоль), два Г-пути, Z-пути через свободные коридоры между узлами — не больше десяти каналов на ось, чтобы не взорваться на плотном графе. Берётся первый маршрут, прошедший проверку; если перекрыто всё — рисуем первый кандидат, ребро в любом случае должно быть видно. Из узла линия выходит «усом» в 16 px, к чужим карточкам не приближается ближе 10 px, углы скругляются дугой радиуса 6 px. Для веера из одного узла длинный участок ведётся вдоль более плотной колонки — плотность считается просто: сколько карточек лежит примерно в той же колонке.

Для диагонального кандидата проверка консервативная: сравнивается bounding box отрезка с прямоугольником карточки. Чистую диагональ она может отвергнуть, зато не пропустит линию через карточку. Роутер избегает карточек, но не оптимизирует пересечения рёбер друг с другом.

Ниже сокращённый листинг: выбор портов и генерация каналов опущены.

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;
}

---

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

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

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

В Flow перед конвейером граф режется на слабосвязные компоненты — классический union-find со сжатием путей и объединением по рангу. Каждая компонента раскладывается отдельно, а готовые прямоугольники упаковываются «полками»: слева направо с переносом строки, целевая ширина — корень из суммарной площади с запасом ×1.4. Итог получается примерно квадратным, а не лентой на три экрана.

Что важнее алгоритмов

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

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

Отсутствие наложений как инвариант. Для результата автораскладки с фиксированными размерами карточек каждое движение проходит через упаковку, которая исключает наложения по построению. Багам вида «после сглаживания карточки наехали друг на друга» просто неоткуда взяться.

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

• Полный Brandes–Köpf для фазы координат: четыре прохода выравнивания дали бы ещё более прямые цепочки, чем мой медианный вариант с PAVA.

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

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

• Level of detail — на большом графе сворачивать поддеревья и разворачивать при приближении.

Итог

Метод Сугиямы хорош тем, что каждую фазу можно отлаживать и заменять независимо. Лишняя дыра в колонке — смотри упаковку, зигзаг цепочки — сглаживание, линия легла на карточку — роутинг. Всегда понятно, в какую фазу копать.

Весь конвейер уместился в тысячу строк Python плюс триста строк TypeScript. Сам движок раскладки не требует отдельной графовой библиотеки. Для фиксированных размеров карточек результат автораскладки не содержит наложений, а после ручного перетаскивания фронтенд обновляет маршрут. Если будете делать похожую вещь, начинайте с простого конвейера и добавляйте эвристики там, где их требует реальный граф.

Благодарю за внимание!