Force-directed граф у Canvas 2D з нуля

1. Модель даних графа

Всьому рушію укладання потрібні лише два масиви: список вузлів (кожен із позицією та швидкістю) та список ребер (пари індексів вузлів). Матриця суміжності не потрібна — списку ребер достатньо і для пружинних сил, і для відмальовки.

class GraphLayout {
  constructor(nodeCount, edgeList, width, height) {
    this.width = width;
    this.height = height;
    // Розташовуємо вузли випадково біля центру
    this.nodes = Array.from({ length: nodeCount }, () => ({
      x: width / 2 + (Math.random() - 0.5) * 100,
      y: height / 2 + (Math.random() - 0.5) * 100,
      vx: 0, vy: 0,
      fixed: false  // true, доки користувач перетягує цей вузол
    }));
    this.edges = edgeList; // [[i, j], [i, k], ...]
  }
}

// Приклад: невеликий граф, 6 вузлів, 7 ребер
const layout = new GraphLayout(6, [
  [0,1],[0,2],[1,2],[1,3],
  [2,4],[3,4],[3,5]
], 800, 600);

2. Пружинні сили на ребрах (закон Гука)

Кожне ребро трактується як пружина з природною довжиною спокою L₀. Якщо два з'єднані вузли розташовані далі, ніж L₀, пружина притягує їх; якщо ближче — відштовхує, точно за законом Гука: F = −k·(d − L₀):

function applySpringForces(nodes, edges, restLength = 80, k = 0.05) {
  for (const [i, j] of edges) {
    const a = nodes[i], b = nodes[j];
    const dx = b.x - a.x, dy = b.y - a.y;
    const dist = Math.max(Math.hypot(dx, dy), 0.01);
    const force = k * (dist - restLength);   // закон Гука: F = -k(d - L0)
    const fx = (dx / dist) * force, fy = (dy / dist) * force;
    a.vx += fx; a.vy += fy;   // тягнемо a до b
    b.vx -= fx; b.vy -= fy;   // тягнемо b до a (3-й закон Ньютона)
  }
}

3. Відштовхування між усіма вузлами (закон Кулона)

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

function applyRepulsion(nodes, strength = 4000) {
  for (let i = 0; i < nodes.length; i++) {
    for (let j = i + 1; j < nodes.length; j++) {
      const a = nodes[i], b = nodes[j];
      const dx = b.x - a.x, dy = b.y - a.y;
      const distSq = Math.max(dx*dx + dy*dy, 25);  // обмеження мінімальної відстані
      const dist = Math.sqrt(distSq);
      const force = strength / distSq;   // закон Кулона: F = k / r²
      const fx = (dx / dist) * force, fy = (dy / dist) * force;
      a.vx -= fx; a.vy -= fy;   // відштовхуємо a від b
      b.vx += fx; b.vy += fy;   // відштовхуємо b від a
    }
  }
}

4. Центрувальна сила та демпфування

Без центрувальної сили взаємно відштовхувані вузли дрейфували б назовні назавжди без жодної причини десь зупинитись. Слабка сила до центру канви утримує весь макет закріпленим, а демпфування швидкості (тертя) — це те, що насправді дозволяє симуляції встановитись у стабільний стійкий макет замість нескінченних коливань:

function applyCenteringAndDamping(nodes, cx, cy, centerStrength = 0.01, damping = 0.85) {
  for (const n of nodes) {
    if (n.fixed) continue;  // не боремося з перетягуванням мишею
    n.vx += (cx - n.x) * centerStrength;
    n.vy += (cy - n.y) * centerStrength;
    n.vx *= damping;   // тертя: розсіює кінетичну енергію щокадру
    n.vy *= damping;
  }
}

Коефіцієнт демпфування, близький до 1.0 (напр., 0.95), дозволяє макету плавно й повільно розгойдуватись і встановлюватись; менше значення (напр., 0.7) збігається швидше, але може виглядати різко. Більшість реалізацій також поступово збільшують демпфування з часом ("симульований відпал"), щоб зафіксувати остаточний макет.

5. Цикл інтегрування

Кожен кадр анімації застосовуйте всі сили послідовно, а потім інтегруйте швидкість у позицію простим напівнеявним методом Ейлера — тим самим інтегратором, що використовується в кожній симуляції частинок:

function step(layout) {
  applySpringForces(layout.nodes, layout.edges);
  applyRepulsion(layout.nodes);
  applyCenteringAndDamping(layout.nodes, layout.width / 2, layout.height / 2);

  for (const n of layout.nodes) {
    if (n.fixed) continue;
    n.x += n.vx;
    n.y += n.vy;
  }
}

6. Відмальовка ребер і вузлів

Відмальовка — найпростіша частина: очистіть канву, намалюйте кожне ребро як лінію, потім намалюйте кожен вузол як заповнене коло зверху:

function render(ctx, layout) {
  ctx.clearRect(0, 0, layout.width, layout.height);

  // Спочатку ребра, щоб вузли малювались поверх них
  ctx.strokeStyle = 'rgba(148,163,184,0.5)';
  ctx.lineWidth = 1.5;
  for (const [i, j] of layout.edges) {
    const a = layout.nodes[i], b = layout.nodes[j];
    ctx.beginPath();
    ctx.moveTo(a.x, a.y);
    ctx.lineTo(b.x, b.y);
    ctx.stroke();
  }

  // Вузли зверху
  ctx.fillStyle = '#38bdf8';
  for (const n of layout.nodes) {
    ctx.beginPath();
    ctx.arc(n.x, n.y, 8, 0, Math.PI * 2);
    ctx.fill();
  }
}

// Головний цикл
function animate() {
  step(layout);
  render(ctx, layout);
  requestAnimationFrame(animate);
}
animate();

7. Інтерактивне перетягування

Перетягування вузла робить макет "живим" і є необхідним для дослідження щільних графів. На mousedown знайдіть найближчий вузол під курсором і позначте його fixed, щоб фізичний цикл пропускав його; на mousemove прив'яжіть позицію цього вузла безпосередньо до миші; на mouseup відпустіть його назад у симуляцію:

let draggedNode = null;

canvas.addEventListener('mousedown', (e) => {
  const { x, y } = getCanvasCoords(e);
  let closest = null, closestDist = 15;  // радіус влучання 15px
  for (const n of layout.nodes) {
    const d = Math.hypot(n.x - x, n.y - y);
    if (d < closestDist) { closest = n; closestDist = d; }
  }
  if (closest) { closest.fixed = true; draggedNode = closest; }
});

canvas.addEventListener('mousemove', (e) => {
  if (!draggedNode) return;
  const { x, y } = getCanvasCoords(e);
  draggedNode.x = x; draggedNode.y = y;
  draggedNode.vx = draggedNode.vy = 0;
});

addEventListener('mouseup', () => {
  if (draggedNode) draggedNode.fixed = false;
  draggedNode = null;
});

Відпускання перетягнутого вузла назад у вже встановлений макет дає йому свіжі умови нульової швидкості, тому він плавно повторно врівноважується із сусідами, а не смикається чи відлітає геть — невелика, але важлива деталь для макета, що відчувається фізично обґрунтованим.

8. Масштабування: Barnes-Hut для O(N log N) відштовхування

Наївний цикл відштовхування з розділу 3 — O(N²) за кадр: цілком прийнятно для кількох сотень вузлів, але швидко стопориться задовго до кількох тисяч. Точно як у гравітаційному N-тіловому симуляторі, апроксимація Barnes-Hut на основі квадродерева групує віддалені скупчення вузлів в один "віртуальний заряд" у їхньому спільному центрі мас, знижуючи вартість до O(N log N):

// Схема: побудуйте квадродерево щокадру, потім для кожного
// вузла обходьте дерево й трактуйте достатньо віддалений/малий
// квадрант як одну точкову масу в його центрі мас замість
// відвідування кожного вузла в ньому окремо.
function applyRepulsionBarnesHut(nodes, quadtree, theta = 0.8) {
  for (const n of nodes) {
    quadtree.visit((quad, x0, y0, x1, y1) => {
      const size = x1 - x0;
      const dx = quad.comX - n.x, dy = quad.comY - n.y;
      const dist = Math.hypot(dx, dy);
      if (size / dist < theta) {
        applyForceFrom(n, quad.comX, quad.comY, quad.mass);
        return true;  // зупиняємо спуск — трактуємо як одну масу
      }
      return false; // занадто близько/велике — спускаємось у дочірні
    });
  }
}