При автоматической генерации графов из динамических источников — планов выполнения SQL-запросов (Query Execution Plans), деревьев синтаксического анализа (AST), инфраструктурных схем Terraform или конвейеров CI/CD — узлы изначально не имеют координат $x$ и $y$. Попытка отрендерить граф с координатами $(0, 0)$ приводит к наложению всех элементов в одну точку.
Задача автоматической раскладки (Graph Auto-Layout) заключается в детерминированном вычислении двумерных координат вершин и траекторий ребер с минимизацией пересечений линий и сохранением визуального порядка потока данных.
Сложность графовой раскладки относится к классу NP-трудных задач. Вычисление оптимальной позиции для графа из 300 узлов и 500 ребер требует от $O(|V| + |E|)$ до $O(|V|^3)$ операций в зависимости от алгоритма. Выполнение подобных расчетов в главном потоке JavaScript (Main Thread) гарантированно блокирует Event Loop на время от 150 до 2 000 мс, вызывая просадку FPS до 0 и резкую деградацию ключевой метрики INP.
Для обеспечения стабильных 60 кадров в секунду архитектура графового приложения разделяется на два независимых слоя:
transition: transform 300ms ease) без единого фриза пользовательского ввода.АРХИТЕКТУРА ВЫНОСА РАСКЛАДКИ В WEB WORKER:
┌────────────────────────────────────────────────────────────────────────┐
│ ГЛАВНЫЙ ПОТОК (REACT MAIN THREAD) │
│ ├─ UI State (React Flow / Canvas) │
│ ├─ User Interactions (Zoom, Pan, Click) ──► INP = 0 мс (без фризов) │
│ │ │
│ │ postMessage({ nodes, edges, algorithm: 'elk' }) │
│ ▼ │
├────────────────────────────────────────────────────────────────────────┤
│ ФОНОВЫЙ ПОТОК (WEB WORKER THREAD) │
│ │ │
│ ├─ Парсинг топологии: Dagre / ELK Graph Representation │
│ ├─ Фаза 1: Устранение циклов (Cycle Breaking) │
│ ├─ Фаза 2: Назначение слоев/рангов (Layering / Ranking) │
│ ├─ Фаза 3: Минимизация пересечений ребер (Cross Reduction) │
│ ├─ Фаза 4: Расчет точных координат узлов и изгибов ребер │
│ │ │
│ │ postMessage({ layoutedNodes, layoutedEdges }) │
│ ▼ │
└────────────────────────────────────────────────────────────────────────┘В зависимости от топологии и семантики данных применяются три фундаментальных семейства алгоритмов:
Используется для направленных ациклических графов (DAG). Алгоритм Сугиямы разбивает процесс на четыре строгие фазы:
Библиотека elkjs является трансляцией ядра Eclipse Layout Kernel на JavaScript/WebAssembly. В отличие от легковесного Dagre, ELK поддерживает:
Применяются для ненаправленных сетевых топологий, графов знаний и социальных связей. Граф моделируется как физическая система:
forceManyBody).forceLink).forceCenter притягивает систему к центру вьюпорта, предотвращая разлет вершин в бесконечность.alphaDecay) до достижения термодинамического равновесия.МАТЕМАТИЧЕСКАЯ МОДЕЛЬ FORCE-DIRECTED СИМУЛЯЦИИ:
┌─────────────────────────────────────────────────────────────┐
│ F_total(i) = F_repulsion(i) + F_spring(i) + F_center(i) │
│ │
│ 1. Отталкивание: F_rep = - (k_rep / distance^2) * normal_vec│
│ 2. Притяжение: F_spr = k_spr * (distance - rest_length) │
│ 3. Интегрирование Верле: │
│ pos(t + dt) = pos(t) + velocity(t) * dt + F_total * dt^2 │
│ alpha(t + 1) = alpha(t) * (1 - alphaDecay) │
│ │
│ Симуляция останавливается, когда alpha < alphaMin (0.001) │
└─────────────────────────────────────────────────────────────┘Главный поток извлекает структуры узлов и связей, удаляет React-функции и отправляет плоский JSON через Worker.postMessage().
Web Worker инициализирует внутренний граф Dagre или ELK-дерево с учетом физических габаритов (width, height) каждого узла.
Выполняются фазы ранжирования, минимизации пересечений и назначения координат без блокировки рендер-потока браузера.
Главный поток получает обновленный массив позиций и плавно интерполирует перемещение нод к целевым координатам.
Команда проектирует редактор архитектурных микросервисных диаграмм, в котором сервисы сгруппированы по VPC-сетям (вложенные подграфы), а ребра должны соединять строго определенные порты интерфейсов под прямыми углами. Какую библиотеку раскладки необходимо выбрать и почему?
В СУБД (PostgreSQL, ClickHouse, Snowflake) аналитический запрос парсится в ориентированное дерево реляционных операторов (Seq Scan, Hash Join, Aggregate). Алгоритм Dagre с направлением сверху вниз (TB — Top to Bottom) строит иерархическую диаграмму, где ширина ребер пропорциональна объему переданных строк данных.
Облачные дашборды генерируют топологию инфраструктуры: кластеры содержат неймспейсы, неймспейсы содержат поды, а поды — контейнеры. Иерархический алгоритм elkjs раскладывает вложенные прямоугольники с сохранением отступов (padding) и маршрутизирует связи между Service Mesh портами.
В системах информационной безопасности (SOC / SIEM) необходимо визуализировать сотни взаимосвязанных хостов, IP-адресов и CVE-уязвимостей. Силовой алгоритм Force-Directed группирует скомпрометированные сегменты сети в органические кластеры на основе плотности сетевых соединений.
Платформы совместной разработки отображают историю версий. Алгоритм раскладки распределяет коммиты по строго параллельным дорожкам веток (swimlanes) с детерминированным порядком слияний (merge commits).
Реализуем production-ready архитектуру: вынесем вычисления раскладки в Web Worker с поддержкой двух алгоритмов — легковесного Dagre для плоских DAG и мощного Elkjs для сложных иерархий.
import type { Node, Edge } from '@xyflow/react';
export type LayoutAlgorithm = 'dagre' | 'elk' | 'd3-force';
export interface LayoutOptions {
direction: 'TB' | 'LR' | 'BT' | 'RL'; // Направление потока
nodeSpacing: number; // Расстояние между соседними узлами
rankSpacing: number; // Расстояние между слоями иерархии
}
// Запрос от главного потока к воркеру
export interface LayoutRequestMessage {
id: string; // ID задачи для отслеживания гонки запросов
algorithm: LayoutAlgorithm;
nodes: Array<Pick<Node, 'id' | 'parentId' | 'width' | 'height'> & { data?: unknown }>;
edges: Array<Pick<Edge, 'id' | 'source' | 'target' | 'sourceHandle' | 'targetHandle'>>;
options: LayoutOptions;
}
// Ответ воркера главному потоку
export interface LayoutResponseMessage {
id: string;
nodes: Array<{ id: string; x: number; y: number }>;
durationMs: number;
error?: string;
}import dagre from '@dagrejs/dagre';
import ELK from 'elkjs/lib/elk.bundled.js';
import type {
LayoutRequestMessage,
LayoutResponseMessage,
} from './layout-worker-types';
const elkInstance = new ELK();
// 1. Алгоритм Dagre для плоских DAG-графов
function runDagreLayout(
nodes: LayoutRequestMessage['nodes'],
edges: LayoutRequestMessage['edges'],
options: LayoutRequestMessage['options']
) {
const dagreGraph = new dagre.graphlib.Graph();
dagreGraph.setDefaultEdgeLabel(() => ({}));
dagreGraph.setGraph({
rankdir: options.direction,
nodesep: options.nodeSpacing,
ranksep: options.rankSpacing,
});
// Регистрация узлов с их размерами
for (const node of nodes) {
dagreGraph.setNode(node.id, {
width: node.width ?? 180,
height: node.height ?? 60,
});
}
// Регистрация ребер
for (const edge of edges) {
dagreGraph.setEdge(edge.source, edge.target);
}
// Запуск вычислений
dagre.layout(dagreGraph);
// Извлечение координат (Dagre возвращает центр узла, переводим в левый верхний угол)
return nodes.map((node) => {
const nodeWithPos = dagreGraph.node(node.id);
const width = node.width ?? 180;
const height = node.height ?? 60;
return {
id: node.id,
x: nodeWithPos.x - width / 2,
y: nodeWithPos.y - height / 2,
};
});
}
// 2. Алгоритм Elkjs для сложных многоуровневых графов
async function runElkLayout(
nodes: LayoutRequestMessage['nodes'],
edges: LayoutRequestMessage['edges'],
options: LayoutRequestMessage['options']
) {
const directionMap = {
TB: 'DOWN',
BT: 'UP',
LR: 'RIGHT',
RL: 'LEFT',
};
// Построение иерархического графа ELK
const elkGraph = {
id: 'root',
layoutOptions: {
'elk.algorithm': 'layered',
'elk.direction': directionMap[options.direction],
'elk.spacing.nodeNode': String(options.nodeSpacing),
'elk.layered.spacing.nodeNodeBetweenLayers': String(options.rankSpacing),
'elk.layered.nodePlacement.strategy': 'BRANDES_KOEPF',
},
children: nodes.map((node) => ({
id: node.id,
width: node.width ?? 180,
height: node.height ?? 60,
})),
edges: edges.map((edge) => ({
id: edge.id,
sources: [edge.source],
targets: [edge.target],
})),
};
const layoutedGraph = await elkInstance.layout(elkGraph);
return (layoutedGraph.children ?? []).map((child) => ({
id: child.id,
x: child.x ?? 0,
y: child.y ?? 0,
}));
}
// Слушатель входящих сообщений в потоке воркера
self.onmessage = async (event: MessageEvent<LayoutRequestMessage>) => {
const { id, algorithm, nodes, edges, options } = event.data;
const startTime = performance.now();
try {
let resultPositions: Array<{ id: string; x: number; y: number }> = [];
if (algorithm === 'dagre') {
resultPositions = runDagreLayout(nodes, edges, options);
} else if (algorithm === 'elk') {
resultPositions = await runElkLayout(nodes, edges, options);
}
const response: LayoutResponseMessage = {
id,
nodes: resultPositions,
durationMs: performance.now() - startTime,
};
self.postMessage(response);
} catch (err) {
self.postMessage({
id,
nodes: [],
durationMs: performance.now() - startTime,
error: err instanceof Error ? err.message : 'Unknown layout error',
} satisfies LayoutResponseMessage);
}
};import { useEffect, useRef, useCallback, useState } from 'react';
import type { Node, Edge } from '@xyflow/react';
import type {
LayoutAlgorithm,
LayoutOptions,
LayoutRequestMessage,
LayoutResponseMessage,
} from '@/workers/layout-worker-types';
export function useGraphLayoutWorker() {
const workerRef = useRef<Worker | null>(null);
const activeRequestId = useRef<string | null>(null);
const [isComputing, setIsComputing] = useState(false);
useEffect(() => {
// Инициализация Web Worker через Webpack/Vite URL синтаксис
workerRef.current = new Worker(
new URL('../workers/layout.worker.ts', import.meta.url),
{ type: 'module' }
);
return () => {
workerRef.current?.terminate();
};
}, []);
const computeLayout = useCallback(
(
nodes: Node[],
edges: Edge[],
algorithm: LayoutAlgorithm = 'dagre',
options: LayoutOptions = { direction: 'TB', nodeSpacing: 50, rankSpacing: 80 }
): Promise<Node[]> => {
return new Promise((resolve, reject) => {
if (!workerRef.current) {
reject(new Error('Web Worker не инициализирован'));
return;
}
const requestId = crypto.randomUUID();
activeRequestId.current = requestId;
setIsComputing(true);
const handleMessage = (event: MessageEvent<LayoutResponseMessage>) => {
// Игнорируем устаревшие ответы при быстрых повторных вызовах
if (event.data.id !== activeRequestId.current) return;
workerRef.current?.removeEventListener('message', handleMessage);
setIsComputing(false);
if (event.data.error) {
reject(new Error(event.data.error));
return;
}
const positionMap = new Map(
event.data.nodes.map((n) => [n.id, { x: n.x, y: n.y }])
);
// Обновляем узлы с новыми координатами
const updatedNodes = nodes.map((node) => {
const pos = positionMap.get(node.id);
return pos ? { ...node, position: pos } : node;
});
resolve(updatedNodes);
};
workerRef.current.addEventListener('message', handleMessage);
const request: LayoutRequestMessage = {
id: requestId,
algorithm,
nodes: nodes.map((n) => ({
id: n.id,
parentId: n.parentId,
width: n.measured?.width ?? 200,
height: n.measured?.height ?? 80,
})),
edges: edges.map((e) => ({
id: e.id,
source: e.source,
target: e.target,
sourceHandle: e.sourceHandle,
targetHandle: e.targetHandle,
})),
options,
};
workerRef.current.postMessage(request);
});
},
[]
);
return { computeLayout, isComputing };
}import React, { useCallback } from 'react';
import {
ReactFlow,
useNodesState,
useEdgesState,
useReactFlow,
Panel,
type Node,
type Edge,
} from '@xyflow/react';
import { useGraphLayoutWorker } from '@/hooks/useGraphLayoutWorker';
interface AutoLayoutGraphProps {
initialNodes: Node[];
initialEdges: Edge[];
}
export function AutoLayoutGraph({ initialNodes, initialEdges }: AutoLayoutGraphProps) {
const [nodes, setNodes, onNodesChange] = useNodesState(initialNodes);
const [edges, , onEdgesChange] = useEdgesState(initialEdges);
const { fitView } = useReactFlow();
const { computeLayout, isComputing } = useGraphLayoutWorker();
const handleApplyLayout = useCallback(
async (algorithm: 'dagre' | 'elk') => {
try {
const layoutedNodes = await computeLayout(nodes, edges, algorithm, {
direction: 'LR',
nodeSpacing: 40,
rankSpacing: 100,
});
// Применяем новые позиции; CSS-анимация сгладит движение
setNodes(layoutedNodes);
// Центрируем камеру после завершения пересчета
window.requestAnimationFrame(() => {
fitView({ duration: 500, padding: 0.2 });
});
} catch (err) {
console.error('Ошибка вычисления раскладки:', err);
}
},
[nodes, edges, computeLayout, setNodes, fitView]
);
return (
<div className="relative h-screen w-full">
<ReactFlow
nodes={nodes}
edges={edges}
onNodesChange={onNodesChange}
onEdgesChange={onEdgesChange}
fitView
>
<Panel position="top-right" className="flex gap-2">
<button
type="button"
disabled={isComputing}
onClick={() => handleApplyLayout('dagre')}
className="rounded bg-accent-blue px-3 py-1.5 text-xs font-medium text-white shadow hover:bg-accent-blue/80 disabled:opacity-50"
>
{isComputing ? 'Расчет...' : 'Dagre Layout (Быстрый)'}
</button>
<button
type="button"
disabled={isComputing}
onClick={() => handleApplyLayout('elk')}
className="rounded bg-accent-purple px-3 py-1.5 text-xs font-medium text-white shadow hover:bg-accent-purple/80 disabled:opacity-50"
>
{isComputing ? 'Расчет...' : 'ELK Layered (Продвинутый)'}
</button>
</Panel>
</ReactFlow>
</div>
);
}React Flow собирает физические ширину и высоту нод (node.measured) из DOM перед отправкой топологии на расчет.
Топология передается в Web Worker с уникальным requestId, полностью освобождая Main Thread для взаимодействия пользователя.
Worker выполняет детекцию циклов, оптимизацию барицентров и послойную упаковку без фризов пользовательского интерфейса.
Полученные мировые координаты передаются в Zustand-стор, активируя CSS transform с плавным масштабированием камеры через fitView.
Пользователь быстро переключает фильтр данных дважды за 100 мс, отправляя два запроса на раскладку (Req 1 и Req 2). Из-за различия в объеме графа Req 2 завершился в воркере быстрее (за 40 мс), чем Req 1 (за 180 мс). Что произойдет, если в хуке не реализована проверка активного идентификатора запроса?
Попытка вызвать elkInstance.layout(graph) прямо внутри обработчика нажатия кнопки onClick в React-компоненте:
// ❌ КАТЕГОРИЧЕСКИЙ АНТИПАТТЕРН: блокирует UI на 500+ мс
const handleLayout = async () => {
const result = await elk.layout(graphData); // Главный поток замирает!
setNodes(result);
};Во время работы алгоритма пользователь не может панорамировать холст, курсор мыши замирает, анимации прерываются, а метрика INP взлетает до сотен миллисекунд.
Решение: Всегда изолируйте алгоритмы раскладки в выделенном Web Worker, как показано в примере выше.
Если передать в Dagre или Elk фиксированные дефолтные размеры (width: 150, height: 50), в то время как кастомный React-узел содержит динамический текст или формы высотой 200 пикселей, алгоритм рассчитает координаты вслепую. После рендеринга узлы перекроют друг друга (Node Overlapping).
Решение: Читайте фактические габариты из свойства node.measured?.width и node.measured?.height, которые React Flow вычисляет через внутренний ResizeObserver перед запуском авто-раскладки.
Если отправить объект узла node, содержащий в поле data React-элементы (icon: <Icon />), колбэки (onClick: () => {}) или символы, метод postMessage выбросит DOMException: DataCloneError, так как структурированное клонирование (Structured Clone Algorithm) не поддерживает функции и JSX.
Решение: Очищайте структуры данных перед отправкой в Worker, передавая только плоские поля: id, parentId, width, height.
Dagre по умолчанию вычисляет координаты центра симметрии узла (x_center, y_center). React Flow ожидает в свойстве position координаты левого верхнего угла (x_top_left, y_top_left). Забыв вычесть половину ширины и высоты (x - width / 2), разработчик получает визуальный сдвиг узлов относительно их ребер.