D3.js. Візуалізація графів

D3.js — це бібліотека JavaScript для управління документами, в основі яких лежать дані. D3 допомагає втілити дані в життя, використовуючи HTML, SVG і CSS. D3 дозволяє прив'язувати довільні дані до DOM, і потім застосовувати результати маніпуляцій з ними до документа.
Для розуміння статті стане в нагоді знання основ D3, і в ній ми розглянемо реалізацію алгоритмів візуалізації графа на основі сил (Force-directed graph drawing algorithms), яка D3 (version 3) має назву Force Layout. Це клас алгоритмів візуалізації графів, які обчислюють позицію кожного вузла, моделюючи силу тяжіння між кожною парою пов'язаних вузлів, а також відразливу силу між вузлами.

image

На картинці вище ви бачите, як відоме видання «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, n/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 між вузлами зв'язку, використовуючи функцію доступу.

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.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.