D3.js — это библиотека JavaScript для управления документами, в основе которых лежат данные. D3 помогает претворить данные в жизнь, используя HTML, SVG и CSS. D3 позволяет привязывать произвольные данные к DOM, и затем применять результаты манипуляций с ними к документу.

Для понимания статьи пригодится знание основ D3, и в ней мы рассмотрим реализацию алгоритмов визуализации графа на основе сил (Force-directed graph drawing algorithms), которая в D3 (version 3) имеет название Force Layout. Это класс алгоритмов визуализации графов, которые вычисляют позицию каждого узла, моделируя силу притяжения между каждой парой связанных узлов, а также отталкивающую силу между узлами.



На картинке выше вы видите, как небезызвестное издание «New Yourk Times» визуализировало связи между претендентами на очередной «Оскар». Окончательный лейаут статичен, но позиции узлов графа были вычислены как раз при помощи Force Layout. Для графа был построен внутренний редактор, позволяющий сохранять координаты узлов для использования их в статическом варианте.

N.B.! Буквально вчера вышла новая версия (version 4) D3.js, поэтому начатая мною статья уже может считаться устаревшей. Тем не менее, надеюсь, что она будет полезна для понимания возможностей новой версии. Об изменениях, внесенных в новой версии в API визуализации графов можно прочитать здесь.

Немного о Layouts

D3.js API содержит несколько сотен функций, и для удобства они разделены на логические блоки, одним из которых является блок Layouts. Он заключает в себе функционал визуального отображения связанных с данными элементов друг относительно друга. Layouts получают ряд входных данных, применят к ним алгоритм или эвристику, и выводят результат в виде графического представления данных.

Layouts мало чем отличаются от d3.svg path generators в том, что они помогают преобразовывать данные для их визуального представления. Однако Layouts, как правило, работают с набором данных в целом, а не по отдельности. Кроме того, результаты работы Layout не ограничены одним SVG. Некоторые Layouts динамичны во времени: например, Force Layout, где после исполнения метода .start() экземпляра d3.layout.force() можно отслеживать события 'tick' обновления лейаута.

В D3 встроены более десятка Layouts. Их экземплярами зачастую являются функции (хотя не обязательно), которые могут быть сконфигурированы и затем применены к набору данных. В иных случаях, для ввода данных и представления результата используются отдельные методы или обработчики событий. Для использования нужно смотреть документацию каждого конкретного Layout.

Force Layout

Визуализация гибкого force-directed графа осуществляется с использованием метода численного интегрирования Верле для накладывания ограничений на перемещения элементов графа относительно друг друга. Подробнее о физическом моделировании вы можете прочитать здесь. Данная реализация использует модуль quadtree (дерево квадрантов) для ускорения взаимодействия узлов графа между собою, с помощью аппроксимации Барнса-Хата. Кроме отталкивающей силы charge узла, псевдо-гравитационная сила gravity удерживает узлы в видимой области и избегает выталкивания несвязанных подграфов за область видимости, в то время как связи графа имеют фиксированную длину linkDistance и выполняют роль геометрических ограничений. Дополнительные пользовательские воздействия и ограничения могут быть применены в событии 'tick', путем обновления атрибутов x и y узлов.



Для всестороннего обзора возможностей с примерами, смотрите видеодоклад одного из ключевых разработчиков D3 Майка Бостока и презентацию из этого доклада.

Несколько забавных примеров: divergent forces, multiple foci, graph constructor, force-directed tree, force-directed symbols, force-directed images and labels, force-directed states, sticky force layout.

Как и другие классы в D3, Layouts следуют приему method chaining, когда методы сеттеров возвращают свой Layout, позволяя выстраивать множество сеттеров в одну цепочку вызовов. В отличие от некоторых других реализаций Layouts, Force Layout сохраняет ссылку на узлы и связи графа внутри себя; таким образом, каждый экземпляр Force Layout может быть использован только с одним набором данных.

d3.layout.force()

Создает новый force-directed layout со следующими настройками по умолчанию: size 1?1, link strength 1, friction 0.9, distance 20, charge strength -30, gravity strength 0.1, theta parameter 0.8 (перечисленные параметры будут описаны ниже). По умолчанию узлы и связи графа — пустые массивы, и когда Layout запускается, внутренний параметр «охлаждения» alpha устанавливается в 0.1. Общий шаблон для построения force-directed layouts — это установка всех конфигурационных свойств, и затем вызов метода .start():

var force = d3.layout.force()
    .nodes(nodes)
    .links(links)
    .size([w, h])
    .linkStrength(0.1)
    .friction(0.9)
    .linkDistance(20)
    .charge(-30)
    .gravity(0.1)
    .theta(0.8)
    .alpha(0.1)
    .start();

Обратите внимание, что, в отличие от других D3 Layouts, force-directed layout не связан с определенным визуальным представлением. Обычно узлы отображаются как SVG элементы circle, а связи отображаются как SVG элементы line. Но вы также можете отобразить узлы как символы или изображения.

force.size([width, height])

Если параметр size передан, устанавливает доступный размер лейаута (ширину и высоту). В противном случае возвращает текущий размер, который по умолчанию равен [1, 1]. В force-directed layout размер влияет на две вещи: гравитационный центр и начальную случайную позицию добавляемых узлов (их координаты x и y). Центр гравитации рассчитывается просто [x/2, y/2]. При добавлении узлов в Force Layout, если они не имеют уже установленных атрибутов x и y, тогда эти атрибуты инициализируются с использованием равномерного случайного распределения в диапазоне [0, x] и [0, y], соответственно.

force.linkDistance([distance])

Если параметр distance передан, устанавливает указанное в нем расстояние между связанными узлами (длину связей). В противном случае, возвращает текущую длину связей, которая по умолчанию равна 20. Если distance константа, то все связи будут иметь одинаковую длину. Иначе, если distance — функция, тогда эта функция вычисляется для каждой связи (по порядку). Функция принимает два аргумента — связь и ее индекс; контекст this функции имеет значение текущего Force Layout. Возвращаемое функцией значение используется для установки длины каждой связи. Функция вычисляется при запуске (метод .start()) лейаута.

Связи реализованы не как «силы упругости», что распространено в иных force-directed лейаутах, но как слабые геометрические ограничения. На каждое событие 'tick' лейаута, расстояние между каждой парой связанных узлов вычисляется и сравнивается с целевым расстоянием; затем связи перемещаются ближе или дальше друг от друга, пока не сойдутся на нужном расстоянии. Такой подход вкупе с методом численного интегрирования Верле значительно более стабилен, нежели подходы, использующие силы упругости, а также допускает гибкую реализацию других ограничений в обработчике события 'tick', таких как иерархическое представление.

force.linkStrength([strength])

Если параметр strength передан, устанавливает указанную жесткость связей в диапазоне [0,1]. В противном случае, возвращает текущую жесткость, которая по умолчанию равна 1. Если strength константа, то все связи будут иметь одинаковую жесткость. Иначе, если strength — функция, тогда эта функция вычисляется для каждой связи (по порядку). Функция принимает два аргумента — связь и ее индекс; контекст this функции имеет значение текущего Force Layout. Возвращаемое функцией значение используется для установки жесткости каждой связи. Функция вычисляется при запуске (метод .start()) лейаута.

force.friction([friction])

Если параметр friction передан, устанавливает указанный коэффициент трения. В противном случае, возвращает текущий коэффициент, который по умолчанию равен 0.9. Наименование этого параметра, возможно, вводит в заблуждение; он не соответствует стандартному коэффициенту трения (из физики). Скорее он больше похож на затухание скорости: на каждое событие 'tick' процесса моделирования скорость узлов вычисляется на основе параметра friction. Так, значение 1 соответствует лишенной трения среде, а значение 0 замораживает все узлы на месте. Значения вне диапазона [0,1] не рекомендуются и могут иметь дестабилизирующие эффекты.

force.charge([charge])

Если параметр charge передан, устанавливает указанную силу заряда узла. В противном случае, возвращает текущую силу заряда, которая по умолчанию равна -30. Если charge константа, то все узлы будут иметь одинаковую силу заряда. Иначе, если charge — функция, тогда эта функция вычисляется для каждого узла (по порядку). Функция принимает два аргумента — узел и его индекс; контекст this функции имеет значение текущего Force Layout. Возвращаемое функцией значение используется для установки силы заряда каждого узла. Функция вычисляется при запуске (метод .start()) лейаута.

Отрицательное значение силы заряда приводит к отталкиванию узлов, а положительное значение приводит к притяжению узлов. Для представления графа должны использоваться отрицательные величины; для симуляции задачи N тел могут быть использованы положительные величины. Как предполагается, все узлы являются бесконечно малыми точками с равным зарядом и массой. Силы зарядов эффективно реализованы с помощью алгоритма Барнса-Хата путем вычисления дерева квадрантов при каждом событии 'tick'. Установка силы заряда равной 0 отключает вычисление дерева квадрантов, что может заметно улучшить производительность, если вам такая функциональность не требуется.

force.chargeDistance([distance])

Если параметр distance передан, устанавливает максимальное расстояние, на котором действуют силы заряда узла. В противном случае, возвращает текущее максимальное расстояние, которое по умолчанию равно бесконечности. Определение конечного расстояния улучшает производительность Force Layout и дает на выходе более локализованный лейаут; это особенно полезно в сочетании с пользовательской гравитацией gravity.

force.theta([theta])

Если параметр theta передан, устанавливает критерий аппроксимации Барнса-Хата. В противном случае, возвращает текущее значение, которое по умолчанию равно 0.8. В отличие от связей, которые влияют только на два связанных узла, сила заряда имеет всеобщее значение: каждый узел оказывает влияние на все остальные узлы, даже если они находятся на несвязанных подграфах.

Чтобы избежать задержки, связанной с квадратичной временной сложностью, Force Layout использует алгоритм Барнса-Хата, который имеет временную сложность O(n log n) за один 'tick'. На каждое событие 'tick' создается дерево квадрантов для сохранения текущей позиции узла; затем для каждого узла вычисляется сумма сил зарядов всех остальных узлов. Для групп узлов, которые находятся далеко, сила заряда аппроксимируется обработкой отдаленной группы узлов как одного большого узла. Theta определяет точность вычисления: если отношение площади квадранта в дереве квадрантов к расстоянию между узлом и центром масс квадранта меньше чем theta, все узлы в данном квадранте обрабатываются как один большой узел, а не вычисляются по отдельности.

force.gravity([gravity])

Если параметр gravity передан, устанавливает силу гравитационного притяжения. В противном случае, возвращает текущую гравитационную силу, которая по умолчанию равна 0.1. Наименование этого параметра, возможно, вводит в заблуждение; он не соответствует физической гравитации (которая может быть имитирована присваиванием параметру charge положительного значения). Вместо этого параметр gravity реализован как небольшое геометрическое ограничение, подобное виртуальной пружине, соединяющей каждый узел с центром лейаута. Такой подход обладает замечательными свойствами: возле центра лейаута сила гравитационного притяжения практически равна нулю, что предотвращает любое локальное искажение лейаута; поскольку узлы выдвинуты дальше от центра, сила гравитационного притяжения усиливается в линейной пропорции к расстоянию. Таким образом, сила гравитационного притяжения всегда будет преодолевать отталкивающие силы заряда на определенном пороге, препятствуя выходу несвязных узлов за границы лейаута.

Гравитация может быть отключена путем установки силы гравитационного притяжения равной нулю. При отключении гравитации рекомендуется реализовать какое-нибудь другое геометрическое ограничение для предотвращения выхода узлов за границы лейаута.

force.nodes([nodes])

Если параметр nodes передан, устанавливает указанные в массиве узлы графа. В противном случае возвращает текущий массив узлов, который по умолчанию пуст. Каждый узел имеет следующие атрибуты:

• index — индекс (отсчет индекса с 0) узла в массиве nodes.
• x — координата x текущей позиции узла.
• y — координата y текущей позиции узла.
• px — координата x предыдущей позиции узла.
• py — координата y предыдущей позиции узла.
• fixed — булевское значение, отражающее, зафиксирована ли позиция узла.
• weight — число связанных с узлом ребер.

Эти атрибуты не обязательно устанавливать перед передачей узла Force Layout; если они не установлены, соответствующие значения по умолчанию будут инициализированы Force Layout при вызове метода .start(). Однако, имейте в виду, что если вы храните какие-то другие данные в ваших узлах, ваши атрибуты данных не должны конфликтовать с вышеприведенными свойствами, используемыми Force Layout.

force.links([links])

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

• source — начальный узел (элемент массива nodes)
• target — конечный узел (элемент массива nodes)

Примечание: значения атрибутов source и target могут быть первоначально заданы как индексы в массиве nodes; они будут заменены ссылками после вызова метода .start(). Объекты link могут иметь дополнительные поля, задаваемые пользователем; эти данные могут быть использованы для вычисления жесткости linkStrength связи и расстояния linkDistance между узлами связи, иcпользуя функцию доступа.

force.start()

Запуск процесса моделирования; этот метод должен быть вызван при создании Force Layout, после установки узлов и связей. Кроме того, его нужно вызывать вновь, когда узлы или связи изменяются. Force Layout использует «охлаждающий» параметр alpha, который регулирует температуру Force Layout: поскольку физическое моделирование сводится к статичному лейауту, температура снижается, вследствие чего узлы замедляют движение. В конечном счете, alpha опускается ниже определенного порога, и моделирование останавливается окончательно, освобождая ресурсы. Force Layout может быть вновь «подогрет» с помощью метода .resume() или путем перезапуска; также это происходит автоматически при использовании режима drag.

При запуске Force Layout инициализирует различные атрибуты связанных с ним узлов. Индекс каждого узла вычисляется путем перебора массива, начиная с 0. Начальные координаты узла x и y, если их значение не указано, вычисляются на основе соседних узлов: если связанный узел уже имеет начальное значение x и y, соответствующие координаты применяются к новому узлу. Это увеличивает устойчивость лейаута графа при добавлении новых узлов, в отличие от использования значений по умолчанию, которые инициализируют координаты случайным образом в пределах размера лейаута. Координаты px и py предыдущей позиции узла (если не указаны) принимают значение начальных координат, что дает новым узлам начальную скорость равную нулю. Наконец, значение fixed по умолчанию равно false.

Force Layout также инициализирует атрибуты source и target связей links: эти атрибуты могут быть заданы не только прямыми ссылками на узлы nodes, но и числовыми индексами узлов (это удобно при считывании данных из файла JSON или иного статического описания). Атрибуты source и target связей заменяются соответствующими записями в nodes, только если эти атрибуты — числа; таким образом, эти атрибуты не затрагиваются на уже существующих связях при перезапуске Force Layout. Параметры linkDistance и linkStrength связей также вычисляются при запуске.

force.alpha([value])

Получает или задает «охлаждающий» параметр alpha процесса моделирования Force Layout. Если значение передано, устанавливает параметр alpha и возвращает Force Layout. Если переданное значение больше нуля, этот метод также перезапускает Force Layout, если он еще не запущен, вызывая событие 'start' и включая 'tick'-таймер. Если переданное значение не положительно, и Force Layout запущен, этот метод останавливает Force Layout на следующем событии 'tick' и вызывает событие 'end'. Если значение не задано, этот метод возвращает текущее значение «охлаждающего» параметра.

force.resume()

Эквивалентен вызову:

force.alpha(.1);

Устанавливает «охлаждающий» параметр alpha в 0.1 и затем перезапускает таймер. Как правило, вам не нужно вызывать этот метод прямо; он вызывается автоматически методом .start(). Он также вызывается автоматически методом .drag() при перетаскивании.

force.stop()

Эквивалентен вызову:

force.alpha(0);

Завершает процесс моделирования, устанавливая охлаждающий параметр alpha в 0. Этот метод может использоваться для явной остановки процесса моделирования. Если вы не остановите Force Layout явно, это произойдет автоматически после того, как параметр «охлаждения» alpha опустится ниже определенного порога.

force.tick([value])

Выполняет один шаг моделирования Force Layout. Этот метод может быть использован вместе с методами .start() и .stop() для вычисления статического лейаута. Например:

force.start();
for (var i = 0; i < n; ++i) force.tick();
force.stop();

Количество итераций зависит от размера графа и его сложности. Выбор начальных позиций также имеет важное значение. Например, здесь узлы расположены по диагонали:

var n = nodes.length;
nodes.forEach(function(d, i) {
  d.x = d.y = width / n * i;
});

Если вы не инициализируете позиции узлов вручную, Force Layout инициализирует их случайным образом, приводя к несколько непредсказуемому подведению.

force.on([type, listener])

Регистрирует определенный обработчик listener для обработки событий определенного типа type от Force Layout. В настоящее время поддерживаются только события 'start', 'tick', и 'end'.

Объекты-события, которые передаются функции-обработчику, являются пользовательскими объектами, созданными с использованием d3.dispatch(). Каждый объект-событие имеет два свойства: type (строка, 'start', 'tick', или 'end'), и alpha, являющееся текущим значением «охлаждающего» параметра alpha. Свойство event.alpha может быть использовано для мониторинга прогресса моделирования Force Layout или для внесения в этот процесс ваших собственных корректив.

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

Событие 'tick' отправляется на каждом шаге моделирования. Отслеживайте события 'tick' для обновления отображаемых позиций узлов и связей. Например, если вы изначально отображаете узлы и связи следующим образом:

var link = vis.selectAll("line")
    .data(links)
  .enter().append("line");

var node = vis.selectAll("circle")
    .data(nodes)
  .enter().append("circle")
    .attr("r", 5);

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

force.on("tick", function() {
  link.attr("x1", function(d) { return d.source.x; })
      .attr("y1", function(d) { return d.source.y; })
      .attr("x2", function(d) { return d.target.x; })
      .attr("y2", function(d) { return d.target.y; });

  node.attr("cx", function(d) { return d.x; })
      .attr("cy", function(d) { return d.y; });
});

В данном случае, мы сохранили набор узлов (node) и связей (link) на этапе инициализации, чтобы нам не было нужно повторно выбирать узлы на каждом шаге моделирования. При желании вы можете отобразить узлы и связи иным образом; например, вы можете использовать символы вместо кругов.

Событие 'end' отправляется, когда внутренний «охлаждающий» параметр alpha опускается ниже пороговой величины (0.005) и обнуляется.

force.drag()

Связывает поведение с узлами для интерактивного перетаскивания, как мышью, так и касанием. Используйте его в сочетании с методом call для узлов; например, вызовите node.call(force.drag) для инициализации. В режиме drag при наведении курсора мыши на узел его атрибут fixed устанавливается в true, тем самым останавливая его движение. Фиксация узла при наведении мыши (mouseover), в отличии от фиксации при клике по узлу (mousedown), упрощает задачу вылавливания нужного узла. Когда происходит событие 'mousedown', и на каждое последующее событие 'mousemove' вплоть до события 'mouseup', центр узла устанавливается в текущую позицию мыши. Кроме того, каждое событие 'mousemove' инициирует метод .resume() Force Layout, «подогревая» процесс моделирования. Если вы хотите, чтобы перемещенные узлы зафиксировались после перетаскивания, установите атрибут fixed в true при событии 'dragstart', как сделано в этом примере.

Примечание реализации: обработчики событий 'mousemove' и 'mouseup' зарегистрированы для текущего окна window, так что когда пользователь начинает перетаскивать узел, процесс перетаскивания не будет прекращен, даже если курсор мыши вышел за пределы лейаута. Каждый обработчик событий использует пространство имен «force», чтобы избежать конфликта с другими обработчиками событий, которые может привязать к узлам или к окну пользователь. Если узел перемещается путем перетаскивания, последующее событие 'click', которое вызовется при отпускании кнопки мыши ('mouseup'), будет отменено. Если вы регистрируете обработчик события 'click', вы можете проигнорировать события 'click', возникающие при перетаскивании, следующим образом:

selection.on("click", function(d) {
  if (d3.event.defaultPrevented) return; // ignore drag
  otherwiseDoAwesomeThing();
});

Напоследок ознакомьтесь с этими двумя примерами: collapsible force layout и divergent forces.