Воронка (force-directed graph)

Force-directed графы в Vega представляют собой визуализацию сетевых структур, в которых расположение узлов определяется моделью физических сил. Такой подход позволяет естественным образом отображать сложные взаимосвязи: узлы отталкиваются друг от друга, рёбра действуют как пружины, а вся система стремится к состоянию минимальной энергии.

Основой служит система имитации физических взаимодействий:

  • Отталкивание (charge force) между всеми узлами
  • Притяжение (link force) вдоль рёбер графа
  • Центрирование (center force) для удержания графа в области отображения
  • Дополнительные силы: столкновения, фиксация координат, гравитация

Формально положение узла обновляется итеративно:

  • вычисляется результирующая сила
  • применяется численное интегрирование (обычно метод Эйлера)
  • координаты корректируются на каждом шаге симуляции

В Vega используется адаптация алгоритма D3-force, интегрированная в декларативную модель визуализации.

Структура данных графа

Force-directed граф в Vega строится на двух массивах:

  • nodes — вершины графа
  • links — рёбра между вершинами

Пример структуры данных:

{
  "nodes": [
    { "id": "A", "group": 1 },
    { "id": "B", "group": 1 },
    { "id": "C", "group": 2 }
  ],
  "links": [
    { "source": "A", "target": "B" },
    { "source": "A", "target": "C" }
  ]
}

Ключевой момент заключается в том, что Vega требует согласованности идентификаторов: source и target должны ссылаться на id узлов.

Общая структура спецификации Vega

Force-directed граф реализуется через комбинацию:

  • данных (data)
  • преобразований (transform)
  • сигналов (signals)
  • сцены (marks)
  • силовой симуляции (forces через transforms или signal-driven simulation)

Минимальная конфигурация:

{
  "$schema": "https://vega.github.io/schema/vega/v5.json",
  "width": 600,
  "height": 400,

  "data": [
    {
      "name": "nodes",
      "values": [
        { "id": "A" },
        { "id": "B" },
        { "id": "C" }
      ]
    },
    {
      "name": "links",
      "values": [
        { "source": "A", "target": "B" },
        { "source": "A", "target": "C" }
      ]
    }
  ]
}

Далее добавляется force-система через трансформации и сигналы.

Силовая симуляция в Vega

Force-directed layout в Vega реализуется через набор сил:

Charge force (отталкивание)

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

  • предотвращает наложение узлов
  • расширяет граф
  • регулирует плотность

Конфигурационно:

"forces": [
  {
    "force": "charge",
    "strength": -120
  }
]

Отрицательное значение усиливает отталкивание.

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

{
  "force": "link",
  "links": "links",
  "id": "id",
  "distance": 50,
  "strength": 1
}

Параметры:

  • distance — целевая длина ребра
  • strength — жёсткость связи
  • id — ключ сопоставления узлов

Center force (центрирование)

Система удерживается в пределах области визуализации:

{
  "force": "center",
  "x": 300,
  "y": 200
}

Без этой силы граф может “уплывать” за границы холста.

Collision force (столкновения)

Используется для предотвращения перекрытия узлов:

{
  "force": "collide",
  "radius": 10
}

Эта сила особенно важна при плотных графах.

Привязка симуляции к данным Vega

В Vega данные обновляются реактивно через трансформации:

"transform": [
  {
    "type": "force",
    "iterations": 300,
    "static": false,
    "forces": [
      {
        "force": "charge",
        "strength": -80
      },
      {
        "force": "link",
        "links": "links",
        "id": "id",
        "distance": 60
      },
      {
        "force": "center",
        "x": 300,
        "y": 200
      }
    ]
  }
]

Параметр iterations определяет количество шагов симуляции при инициализации.

Отображение узлов и рёбер

Узлы

Узлы обычно отображаются как символы (symbol mark):

"marks": [
  {
    "type": "symbol",
    "from": { "data": "nodes" },
    "encode": {
      "enter": {
        "size": { "value": 100 },
        "fill": { "value": "#4c78a8" }
      },
      "update": {
        "x": { "field": "x" },
        "y": { "field": "y" }
      }
    }
  }
]

Ключевой момент: координаты x и y автоматически вычисляются force-системой.

Рёбра

Рёбра отображаются через линии:

{
  "type": "line",
  "from": { "data": "links" },
  "encode": {
    "update": {
      "x": { "field": "source.x" },
      "y": { "field": "source.y" },
      "x2": { "field": "target.x" },
      "y2": { "field": "target.y" },
      "stroke": { "value": "#999" }
    }
  }
}

Связь координат узлов и рёбер критична: Vega автоматически связывает объекты через ссылки.

Сигналы и интерактивность

Signals позволяют управлять параметрами симуляции в реальном времени.

Перетаскивание узлов

Добавляется сигнал drag:

"signals": [
  {
    "name": "dragged",
    "value": null,
    "on": [
      {
        "events": "@node:mousedown",
        "update": "datum"
      },
      {
        "events": "mouseup",
        "update": "null"
      }
    ]
  }
]

При закреплении узла его координаты фиксируются:

"fx": { "signal": "dragged.id ? dragged.x : null" },
"fy": { "signal": "dragged.id ? dragged.y : null" }

Масштабирование и панорамирование

Для больших графов добавляется zoom:

{
  "name": "view",
  "value": { "x": 0, "y": 0, "scale": 1 },
  "on": [
    {
      "events": "wheel",
      "update": "clamp(scale * pow(1.001, event.deltaY), 0.5, 5)"
    }
  ]
}

Marks затем трансформируются через x, y, scale.

Фиксация узлов

Некоторые узлы необходимо закрепить:

  • корневые элементы
  • центральные сущности
  • пользовательские выбранные узлы

В Vega это достигается через fx и fy:

{
  "type": "symbol",
  "encode": {
    "update": {
      "fx": { "signal": "datum.fixed ? datum.x : null" },
      "fy": { "signal": "datum.fixed ? datum.y : null" }
    }
  }
}

Настройка параметров стабильности

Стабильность графа зависит от:

  • силы отталкивания
  • длины рёбер
  • числа итераций
  • демпфирования (alpha decay)

Пример настройки:

{
  "force": "charge",
  "strength": -60,
  "theta": 0.9
}

Параметр theta влияет на аппроксимацию расчёта дальних сил.

Производительность и оптимизация

Force-directed графы чувствительны к числу узлов.

Основные оптимизации:

Ограничение числа итераций

Слишком большое значение iterations приводит к:

  • замедлению рендеринга
  • блокировке UI при инициализации

Упрощение силы отталкивания

Сильное отталкивание между всеми парами узлов даёт O(n²). Vega использует оптимизации, но при больших графах нагрузка остаётся значительной.

Кластеризация

Группировка узлов до симуляции уменьшает сложность:

  • предварительное объединение
  • иерархическое разбиение
  • multi-level force layout

Lazy update

Обновление координат только при изменениях данных или взаимодействии пользователя.

Типичные проблемы построения графа

Распад структуры

При слишком слабых link-силах граф теряет форму и превращается в облако.

Перенасыщение центра

При сильной центровке узлы слипаются в середине.

Коллизии без collide force

При отсутствии collision force узлы перекрывают друг друга, делая визуализацию нечитаемой.

Нестабильная симуляция

При несбалансированных силах граф не достигает устойчивого состояния и постоянно “дрожит”.

Пример полной конфигурации Vega force-directed графа

{
  "$schema": "https://vega.github.io/schema/vega/v5.json",
  "width": 600,
  "height": 400,

  "data": [
    {
      "name": "nodes",
      "values": [
        { "id": "A" },
        { "id": "B" },
        { "id": "C" },
        { "id": "D" }
      ]
    },
    {
      "name": "links",
      "values": [
        { "source": "A", "target": "B" },
        { "source": "A", "target": "C" },
        { "source": "B", "target": "D" }
      ]
    }
  ],

  "transform": [
    {
      "type": "force",
      "iterations": 200,
      "static": false,
      "forces": [
        {
          "force": "charge",
          "strength": -90
        },
        {
          "force": "link",
          "links": "links",
          "id": "id",
          "distance": 70
        },
        {
          "force": "center",
          "x": 300,
          "y": 200
        },
        {
          "force": "collide",
          "radius": 12
        }
      ]
    }
  ],

  "marks": [
    {
      "type": "line",
      "from": { "data": "links" },
      "encode": {
        "update": {
          "x": { "field": "source.x" },
          "y": { "field": "source.y" },
          "x2": { "field": "target.x" },
          "y2": { "field": "target.y" },
          "stroke": { "value": "#bbb" }
        }
      }
    },
    {
      "type": "symbol",
      "from": { "data": "nodes" },
      "encode": {
        "update": {
          "x": { "field": "x" },
          "y": { "field": "y" },
          "size": { "value": 120 },
          "fill": { "value": "#4c78a8" }
        }
      }
    }
  ]
}
Оглавление