Сучасні інформаційні технології / Обчислювальна техніка та програмування

Ткаченко Р.В.

Київський національний університет України «Київський політехнічний інститут»

Візуалізація графів за допомогою використання методу фізичних аналогій.

На даний час представлення інформації все більше і більше використовується в різних областях точних та природних наук. В програмуванні графові моделі застосовуються при створенні програмного забезпечення (управляючі графи, ієрархії класів, діаграми потоків даних), дизайні бази даних (діаграми сутність-зв’язок), розробка інформаційних систем і систем реального часу (моделювання комп’ютерних мереж, графи станів, мережі Петрі), а також в системному програмуванні – при створенні теорії компіляції і перетворювання програм. Питання візуалізації подібних графових структур являється наріжним каменем в процесі адекватного відображення інформації.

Автоматичне розташування графів – це задача конструювання геометричного представлення графа, яке задовольняє набору естетичних критеріїв.

В залежності від застосування елементи графа можуть зображуватись різноманітними способами. Наприклад, вершини можуть бути нарисовані, наприклад, у вигляді точок, кіл, прямокутників або інших геометричних фігур, або представлені неявно – через імена, якими помічені вершини. Аналогічно має більшу різноманітність рисування ребер: наприклад, у вигляді відрізків прямих, ломаних ліній або кривих. Інформація, зіставлена елементам графа, може візуалізуватися з використанням текстових міток, розташованих всередині або поряд з об’єктом графу, різноманітними кольорами або іншими візуальними елементами, такими як, наприклад, товщина ліній або розмір прямокутників.

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

Одним з найпопулярніших методів рисування графів являється зображення графу з використанням фізичних аналогій. Така увага до них пояснюється тим, що, оскільки фізичні аналогії, з одної сторони, роблять алгоритм рисування достатньо прозорим для розуміння і простими для реалізації, а з іншої, приводять до алгоритмів, які дають досить оптимальні розташування графів.

При пошуку зображення графа його можна розглядати як систему тіл з силами, взаємодіючими між тілами, наприклад, приймаючи вершини графу тілами, а ребра пружинами. В цьому випадку алгоритм знаходить конфігурацію рівноваги тіл з локально мінімальною енергією – так званою конфігурацією рівноваги сил, в якій кожне тіло займає таку позицію, що сума всіх сил, прикладених до тіла, дорівнює нулю.

Початкова конфігурація графу:

Кінцева конфігурація графу:

Більш точно, сила, прикладена до вершини p, визначається за формулою

де – сила натягу, діюча на вершину p із-за пружини (p,q), а – сила відштовхування існуюча між частками p і q. За законом Фуко пропорційна різниці між відстанню від p до q і довжиною пружини з мінімальною енергією; а сила слідує оберненому квадратному закону.

Нехай означає відстань на площині між p і q. Тоді для x-ї координати сили F(p) можна використовувати формулу

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

- – це натуральна (з нульовою енергією) довжина пружини між p і q. Якщо пружина має довжину (тобто )), то не виникає сил натягу між p і q;

- – коефіцієнт жорсткості пружини між p і q. Чим більше він, тим сильніше пружина намагається встановити відстань між p і q, рівною ;

- – коефіцієнт сили відштовхування між p і q.

Дана модель націлена на задоволення двом естетичним вимогам:

- сили пружини між сусідніми вершинами націлені на те, щоб відстань між ними приблизно була рівною ;

- електронні сили мають гарантувати, щоб вершини не наближались близько одна до одної.

Досліди показали, що в багатьох випадках алгоритм рисування будує симетричне зображення графу.

Для отримання більш якісних зображень можна використовувати не закон Фуко, а логарифмічний закон, коли

Однак досліди показали, що не завжди зростання якості результуючих зображень в цьому випадку компенсують збільшення обчислювальної складності.

В конкретних додатках за рахунок змін значень параметрів , , можна управляти наочністю представлення і вираження в рисунку семантики графа.

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

Найпростіший з них – це алгоритм, який діє в два етапи.

На першому етапі вершини розташовуються на площині випадковим чином.

Другий етап – це послідовність ітерацій до стабілізації, на кожній з яких обчислюються для всіх вершин p сили F(p) і для тих із них, для яких відбувається переміщення вершини в напрямку цієї сили на відстань, пропорційне модулю сили. Пропорція зсуву одна для всіх вершин являється ще одним параметром алгоритму.

Алгоритм достатньо простий, разом з цим він дозволяє здійснити інтуїтивно зрозумілий плавний перехід від випадкового розташування до конфігурації рівноваги сил.

Література:

1. Касьянов В.Н. Графы в программировании: обработка, визуализация и применение /  В.Н. Касьянов, В.А Евстигнеев – СПб. БХВ-Петербург, 2003 – 1104 с. ил.

2. Isabel F. Cruz. Graph Drawing Tutorial [Електронний ресурс]. – Режим доступу: http://www.cs.brown.edu/~rt/papers/gd-tutorial/gd-constraints.pdf (18.05.2011). – Назва з екрану.

3. Ivan Herman, Member, IEEE CS Society, Guy Melançon, M. Scott Marshall. Graph Visualization and Navigation in Information Visualization: a Survey [Електронний ресурс]. – Режим доступу: http://staff.science.uva.nl/~marshall/publications/StarGraphVisuInInfoVis.pdf (18.05.2011). – Назва з екрану.