Модель данных для графов: узлы и рёбра

Графовые структуры в D3.js обычно строятся вокруг двух базовых сущностей: узлов и рёбер. Такая модель данных отражает математическое представление графа, где множество вершин соединяется множеством связей, каждая из которых может нести дополнительную семантику. В контексте визуализации это преобразуется в систему объектов, пригодных для симуляции, раскладки и интерактивного отображения.

Наиболее распространённое представление графа в D3.js включает два массива:

  • nodes — список узлов (вершин графа)
  • links — список рёбер (связей между узлами)

Каждый элемент массива nodes представляет отдельную сущность графа:

const nodes = [
  { id: "A", group: 1 },
  { id: "B", group: 1 },
  { id: "C", group: 2 }
];

Каждый объект может содержать произвольные поля. На практике часто используются:

  • id — уникальный идентификатор узла
  • group — категория для раскраски или кластеризации
  • value — вес или размер узла
  • дополнительные атрибуты предметной области

Рёбра задаются отдельным массивом:

const links = [
  { source: "A", target: "B", weight: 1 },
  { source: "B", target: "C", weight: 2 }
];

Каждое ребро описывает направленную или ненаправленную связь между двумя узлами.

Принцип связывания узлов и рёбер

В D3.js поля source и target могут хранить либо строки-идентификаторы, либо ссылки на объекты узлов. При использовании симуляции d3.forceSimulation библиотека автоматически преобразует идентификаторы в ссылки на соответствующие объекты nodes.

После обработки структура рёбер фактически меняется:

{
  source: { id: "A", group: 1, x: 120, y: 80 },
  target: { id: "B", group: 1, x: 200, y: 150 },
  weight: 1
}

Это преобразование является ключевым механизмом, обеспечивающим динамическое поведение графа.

Нормализация данных перед визуализацией

Перед передачей данных в D3 часто выполняется нормализация:

  • устранение дубликатов узлов
  • проверка уникальности id
  • приведение типов идентификаторов к единому виду
  • фильтрация невалидных связей

Пример нормализации:

const nodeMap = new Map(nodes.map(n => [n.id, n]));

const normalizedLinks = links
  .filter(l => nodeMap.has(l.source) && nodeMap.has(l.target))
  .map(l => ({
    source: nodeMap.get(l.source),
    target: nodeMap.get(l.target),
    weight: l.weight
  }));

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

Граф как объект состояния симуляции

В d3-force граф рассматривается как динамическая система. Узлы получают дополнительные параметры во время расчёта:

  • x, y — текущие координаты
  • vx, vy — скорость по осям
  • index — внутренний индекс симуляции

Изначально эти поля отсутствуют в данных и добавляются библиотекой автоматически.

const simulation = d3.forceSimulation(nodes)
  .force("link", d3.forceLink(links).id(d => d.id))
  .force("charge", d3.forceManyBody())
  .force("center", d3.forceCenter(width / 2, height / 2));

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

Роль идентификаторов в модели графа

Поле id выполняет критическую функцию: оно связывает логическую модель данных с физической моделью симуляции.

Основные требования к идентификаторам:

  • уникальность в пределах массива nodes
  • стабильность при обновлениях данных
  • предсказуемость для корректного diff-обновления

При использовании обновляемых данных D3 опирается на ключи для сопоставления старых и новых узлов:

const node = svg.selectAll("circle")
  .data(nodes, d => d.id);

Стабильность ключей обеспечивает корректную работу enter/update/exit механизма.

Связь графовой модели с DOM-структурой

Графовые данные в D3 обычно отображаются через SVG или Canvas. Каждый узел становится визуальным примитивом:

  • circle для узлов
  • line или path для рёбер

Связь между данными и DOM устанавливается декларативно:

const link = svg.selectAll("line")
  .data(links)
  .join("line");

const node = svg.selectAll("circle")
  .data(nodes)
  .join("circle");

DOM-элементы синхронизируются с массивами данных, а изменения структуры графа автоматически отражаются в визуализации.

Направленные и ненаправленные графы

Модель данных позволяет описывать оба типа графов.

Ненаправленные графы

Связь интерпретируется симметрично:

{ source: "A", target: "B" }

Направленные графы

Направление имеет значение и может использоваться для стрелок или потоков:

{ source: "A", target: "B", directed: true }

Визуально направление часто отображается через маркеры SVG:

svg.append("defs")
  .append("marker")
  .attr("id", "arrow")

Взвешенные рёбра и метрики связей

Дополнительные поля в links позволяют вводить количественные характеристики:

  • weight — сила связи
  • distance — желаемая длина ребра
  • capacity — пропускная способность
  • cost — вес в алгоритмах поиска пути

Эти значения могут напрямую влиять на силу физических моделей:

d3.forceLink(links)
  .distance(d => 100 / d.weight);

Таким образом структура данных становится входом для математической модели симуляции.

Соседство и представление связности

Хотя D3 работает с массивами, часто возникает необходимость построения структуры смежности.

Преобразование links в adjacency list:

const adjacency = new Map();

links.forEach(({ source, target }) => {
  if (!adjacency.has(source)) adjacency.set(source, []);
  adjacency.get(source).push(target);
});

Такая структура ускоряет алгоритмы поиска соседей, подсветки и анализа кластеров.

Иерархии и псевдографовые расширения

Хотя базовая модель ориентирована на произвольные графы, данные могут расширяться до иерархических структур:

const nodes = [
  { id: "root", parent: null },
  { id: "child1", parent: "root" }
];

Такие данные могут быть преобразованы в деревья для использования с d3-hierarchy, но сохраняют графовую природу на уровне хранения.

Динамические изменения графа

Модель данных в D3 предполагает изменяемость. Узлы и рёбра могут добавляться или удаляться без пересоздания всей структуры.

Добавление узла:

nodes.push({ id: "D" });

Добавление связи:

links.push({ source: "C", target: "D" });

После изменения данных симуляция может быть перезапущена или “разогнана” повторным вызовом:

simulation.nodes(nodes);
simulation.force("link").links(links);
simulation.alpha(1).restart();

Типизация и расширяемость модели

Модель графа в D3 не фиксирована и допускает произвольные расширения:

  • географические координаты
  • временные метки
  • категории и метки
  • пользовательские веса
  • метаданные взаимодействий

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

Оглавление