РОЗДІЛ 2
КРИТЕРІЇ ВІДОБРАЖЕННЯ ТА МОДЕЛЮВАННЯ
ЕЛЕМЕНТІВ ЗОБРАЖЕНЬ ГРАФІВ
2.1. Критерії відображення графів, що задані матрицями суміжностей
Відомо [44, 50, 55], що матриці суміжностей, які задають структури зв’язків,
зовсім не містять інформації щодо взаємного розташування вершин графа на
площині, щодо розмірів відстаней між вершинами, щодо виду вершин та дуг, щодо
розмірів вершин тощо. Саме тому, й виникає вся трудність візуалізації графів,
що задані матрицями. Очевидно, що методи візуалізації графів повинні самі
розташовувати вершини на площині на певних відстанях одна від одної, з певним
розміром та видом вершин, з ідентифікацією кожної вершини, проводити зв’язки
між вершинами, причому виконувати все це таким чином, щоб отримане зображення
графа було наочним. Оскільки, відомі методи не забезпечують вирішення
поставленої задачі в повному обсязі, то актуальною задачею є створення нових
методів, яким присвячені наступні розділи роботи.
Для отримання наочних з точки зору сприйняття та оцінювання, зображень графів
із матриць суміжностей введено такі критерії [16, 18]:
* рівномірність розташування вершин на екрані чи на шпальті видання;
* мінімальна кількість перетинів дуг між собою;
* неприпустимість перетину вершин графа;
* мінімальна площа, яку займає зображення графа.
Рівномірність розташування вершин підвищує наочність зображення графів,
полегшує їх сприйняття та аналіз. Вона може бути реалізована шляхом
розташування сусідніх вершин на однакових відстанях. Якщо відстань між
сусідніми вершинами графа є однаковою в усіх напрямках, то тоді місця
розташування вершин графа на площині матимуть такий вигляд:
Рис. 2.1. Місця розташування вершин графа з однаковими
відстанями між сусідніми вершинами
Для певних видів графів (лінійних, циклічних, повнозв’язних) наочність
зберігається й тоді, коли відстань між сусідніми вершинами є однаковою лише по
горизонталі та вертикалі. В такому випадку місця розташування вершин матимуть
вигляд:
Рис. 2.2. Місця розташування вершин графа з однаковою відстанню між сусідніми
вершинами по горизонталі та вертикалі
Цілком зрозуміло, що останнє розташування отримується з першого за рахунок
зсуву ліворуч всіх вершин парних рядків на пів відстані між сусідніми
вершинами.
Можна зауважити, що рівномірність розташування вершин є необхідною умовою
наочності, але не достатньою, оскільки на неї також впливає кількість перетинів
дуг графа. Очевидно, що зображення графа буде більш наочним при мінімальній
кількості перетинів дуг між собою. Розглянемо приклад візуалізації графа, що
заданий такою матрицею суміжності:
При рівномірному ярусному розташуванні вершин такого графа коли в першому рядку
буде вершина за номером “1”, в другому – “2” і “3”, а в третьому – “4”, “5”,
“6”, отримаємо зображення графа:
Рис. 2.3. Відображений граф з матриці А
Як видно із рис.2.3. у відображеному графі є два перетини дуг, а саме дуга, що
з’єднує вершини графа “3” і “4” перетинає дві дуги, що з’єднують вершини “2”,
“5” та “2”, “6” відповідно.
Якщо не змінювати місця розташування вершин графа, а лише змінити порядок
розташування вершин у другому ярусі (“3” на “2”) отримаємо еквівалентний граф
(рис.2.4), у якому перетини дуг відсутні і сприйняття такого графа є кращим.
Рис. 2.4. Еквівалентний граф
Можна зауважити, що від порядку розташування вершин у ярусі залежить кількість
перетинів дуг у зображенні графа.
Неприпустимість перетину вершин графа є очевидною, проте навіть при
найвдалішому розташуванні вершин можливі випадки, коли дуга графа буде
перетинати площину однієї з вершин, що є недопустимим. У цьому випадку методи
візуалізації повинні забезпечувати обхід дугою цієї вершини, тобто змінювати
з’єднання двох вершин з прямої лінії на дугу чи ламану.
Стосовно четвертого критерію – мінімальної площі, яку займає зображення графа,
то він зводиться до отримання, по можливості, всіх дуг однакової мінімальної
довжини, що теж сприяє підвищенню наочності візуалізованих графів. Розглянемо
приклад візуалізації графа типу дерево. На рис.2.5.а наведено візуалізований
граф, що відповідає першим трьом критеріям, а на рис.2.5.б – той самий граф, у
якого довжини дуг мінімізовано. Як можна зауважити наочність останнього є
вищою, внаслідок того, що у першому випадку візуалізації графа вершини займали
місця спочатку кожного із рядків, а у другому випадку, так, щоб дуги були
однаковими й мінімальними.
Рис.2.5. Приклад застосування четвертого критерію
Далі розглянемо моделі основних елементів зображень графів, розмір і форма яких
також впливає на наочність відображення.
2.2. Загальний алгоритм візуалізації графів
Загальний алгоритм візуалізації графів наведений на рис.2.6 [9].
Рис. 2.6. Загальний алгоритм візуалізації графів
На початку роботи аналізується матриця суміжності. В результаті аналізу
отримується інформація про кількість вершин графа, його вид – орієнтований,
неорієнтований, ізольований, лінійний, тип графа – „дерево”, деревоподібний,
циклічний, повнозв’язаний. На основі інформації про вид графа вибирається яка
дуга (зі стрілкою чи без неї) буде використовуватись в процесі візуалізації, а
на основі інформації про тип графа вибирається відповідний метод розташування
вершин на площині. Алгоритм включає два етапи:
розташування вершин на площині;
проведення дуг між вершинами графа.
Розташування вершин на площині проводиться відповідно до типу графа таким
чином, щоб отримане в результаті зображення відповідало встановленим критеріям.
Крім того, на даному етапі встановлюються розміри вершин відповідно до заданого
кеглю основного шрифту видання, визначається максимальна кількість таких вершин
у ярусі на площині та кількість
- Київ+380960830922