Зображення графів знаходиться на перетині математики та комп'ютерних наук, оскільки вона поєднує теорію графів з візуалізацією інформації для створення двовимірних представлень графів, що виникають у практичних задачах аналізу соціальних мереж, картографії, лінгвістики, та біоінформатики, pp. vii–viii; , Section 1.1, «Typical Application Areas»..
Зображення графа або мережевої діаграми — це графічне представлення вершин та ребер графа. Не слід плутати зображення з самим графом: зовні одному графу можуть відповідати дуже різні зображення , p. 6.. З теоретичної точки зору, важливо лише те, які пари вершин з'єднані ребрами. Однак, у певних ситуаціях розташування вершин та ребер на малюнку впливає на його чіткість, зручність використання, вартість виготовлення та естетичне сприйняття . Задача стає більш складною, якщо граф змінюється з часом, коли додаються і видаляються ребра (зображення динамічного графа), або мета полягає у збереженні мапи думок користувача.
Домовленості
Графи зазвичай зображуються як діаграми, що наголошують на зв'язках між вузлами, де вершини представлені у вигляді дисків, коробок або текстових міток, і ребер, зображених відрізками, ламаними або кривими в евклідовому просторі, p. viii.. Такі діаграми можна побачити у роботах 13-го століття Раймунда Луллія, які він використовував для зображення повних графів, з метою аналізу усіх попарних комбінацій для множини метафізичних понять..
У випадку орієнтованих графів стрілки вживаються для зазначення їх орієнтації; Проте, дослідження користувачів показали, що використання такого способу, як звуження, цю інформацію надає ефективніше; .. використовує домовленість, що кожне ребро орієнтується від нижчої до вищої вершини, що робить непотрібним зображення кінцівок стріл..
Альтернативні домовленості використовують такі уявлення суміжності, як , де вершини представлені у вигляді областей в площині, що не перетинаються, а ребра зображені як примикання між областями. Зображення перетинів, в яких вершини зображені, як геометричні об'єкти, що не перетинаються, а ребра — їх перетинами. Зображення видимості, в яких вершини представлені областями в площині, а ребра областями, що мають безперешкодну пряму видимість одне одного. Зображення зливання, на яких ребра — гладкі, криві в межах математичних . Зображення у вигляді тканини, де вершини представлені у вигляді горизонтальних ліній, а ребра у вигляді вертикальних ліній.. Зображення матриці суміжності графа.
Критерії якості Багато різних критеріїв якості були визначені для креслень графа в спробі знайти об'єктивний спосіб оцінки їх естетичності та практичності, Section 2.1.2, Aesthetics, pp. 14–16; .. Крім спрямування вибору між різними методами компонування для графа, деякі методи компонування намагаються безпосередньо оптимізувати ці заходи.
Числом схрещень креслення є число пар ребер, що перетинаються між собою. Якщо цей граф є планарним, то часто буває зручно зобразити його без будь-яких перетинів ребер; тобто, в такому випадку, графік являє собою граф вкладення. Однак неплоскі графи часто виникають у додатках, тому алгоритми малювання графа, як правило, повинні дозволяти перетин ребер, p 14.. Площина зображення — це найменша територія вікна обмеження графа, щодо найближчої відстані між будь-якими двома вершинами. Креслення з меншою площею, як правило, краще, ніж з більшою площею, бо вони дозволяють зберегти особливості малюнка, що будуть показані в більшому розмірі й, отже, більш розбірливо. Співвідношення сторін обмежувального блоку також може бути важливим. Симетрія зображення — це проблема пошуку груп симетрії у даному графі, і знаходження зображення, що є найбільш симетричним. Деякі методи розташування автоматично ведуть до симетричних зображень; з іншого боку, деякі методи зображення починаються зі знаходження симетрії отриманого графа для його зображення, p. 16.. Важливо, щоб ребра мали якомога простішу форму, щоб людському оку було легше їх відстежувати. На полілінійних кресленнях, ступінь викривлення ребра можна виміряти , і багато методів спрямоваі на створення кресленнь з невеликою кількістю загальних згинів або кількома згинами на ребро. Подібним чином для сплайн-кривих складність ребер може бути виміряна кількістю контрольних точок на ребрі. Кілька популярних критеріїв якості, пов'язаних з довжиною ребер: в загальному випадку бажано звести до мінімуму загальну довжину країв, а також максимальну довжину будь-якого краю. Крім того, для довжин ребер може бути кращим залишатися однаковими, а не різноманітними. Кутова роздільність — це міра найгострішого кута у зображенні графа. Якщо граф має вершини з великими степенями, то він обов'язково матиме не велику кутову роздільність, але кутова роздільність може бути обмежена знизу функцією степеня.. Число нахилів графа — це мінімальна кількість різних нахилів, що потрібні для зображення прямими лініями ребер сегмента (з перетином). Кубічний граф має кількість нахилів не більше чотирьох, але граф з п'ятьма кутами може мати необмежену кількість нахилів; ще залишається не зрозумілим, чи обмежена кількість нахилів 4-кутного графа.
Методи макетування Існує багато стратегій компонування графів: У системі силового компонування, програми зображення графів змінюють початкове розміщення вершин шляхом безперервного переміщення вершин відповідно до системи сил, заснованої на фізичних метафорах, пов'язаних з системами пружин або молекулярної механіки. Зазвичай, ці системи поєднують в собі сили тяжіння між сусідніми вершинами з силами відштовхування між усіма парами вершин, щоб знайти макет, в якому довжини ребер малі, в той час, як вершини добре розділені. Ці системи можуть виконувати метод найшвидшого спуску на основі мінімізації з функції енергії, або ж вони можуть перевести свої сили безпосередньо у швидкості або прискорення для рухомих вершин, Section 2.7, «The Force-Directed Approach», pp. 29–30, and Chapter 10, «Force-Directed Methods», pp. 303—326.. Метод використовує власні вектори матриці, такі як отриманого з матриці суміжності графа; .. Ортогональні методи компонування, що дозволяють ребрам графа йти горизонтально або вертикально, паралельно осям координат макета. Ці методи були спочатку розроблені для схем надвеликого рівня інтеграції, друкованих плат і проблем компонування, але вони також були пристосовані до зображення графів. Вони зазвичай включають багатофазний підхід, в якому введення графа вирівнюється шляхом заміни точок перетину вершинами, знаходиться топологічне вкладення планаризованного графа, орієнтація сторін вибирається так, щоб звести до мінімуму вигини, вершини розташовуються послідовно з цими орієнтаціями, і, нарешті, етап ущільнення макету зменшує площу малюнка, Chapter 5, «Flow and Orthogonal Drawings», pp. 137—170; .. Алгоритми макету дерев використовують для зображення деревоподібних структур з коренем, зокрема, це пасує для дерев. Зазвичай, у техніці, що називається «кульовий макет» (), нащадок кожного вузла у дереві малюється на колі, що оточує вузол, із радіусом цих кіл, що спадає на нижчих рівнях дерева так, щоб ці кола не накладалися одне на одного, Section 2.2, «Traditional Layout — An Overview».. Методи (які часто називають зображеннями у стилі Сугияма) найкраще підходять для орієнтованого ациклічного графа або графів, близьких до ациклічних, таких як графи залежностей між модулями або функціями в програмній системі. У цих методах, вузли графа розташовані на горизонтальних шарах з використанням методів, таких як , таким чином, що більшість ребер йдуть вниз від одного шару до іншого; після цього кроку вузли в кожному шарі розташовуються з метою мінімізації перетинів; ; , Chapter 9, «Layered Drawings of Digraphs», pp. 265—302..
Дугова діаграма, це стиль компонування, відомий з 1960-х років., розташуємо вершини в одну лінію; ребра можуть бути зображені як півкола вище або нижче лінії, або як плавні криві, з'єднані з декількох півкіл. У коловій схемі вершини обережно розташовані по колу, з метою зменшення перетинів та розташування сусідніх вершин якомога ближче одне до одного. Ребра можуть бути зображені як хорди кола чи його арки зсередини або зовні. Іноді можуть бути використані декілька кіл.. У вершини записуються таким чином, що кожна вершина знаходиться вище, справа, або з обох боків від іншої, тоді й тільки тоді, коли вона з цієї вершини. Таким чином, стиль макета робить відношення досяжності графа візуально очевидним, Section 4.7, «Dominance Drawings», pp. 112—127..
Графічні креслення для конкретних додатків Графи та зображення графа, що виникають в інших областях застосування, включають: , зображення соціальної мережі, що часто пропонується ; .. Діаграма Гассе, це спеціалізований тип зображення графа, спеціалізований на частково впорядковані множини, pp. 15-16, and Chapter 6, «Flow and Upward Planarity», pp. 171—214; .. (), тип графічного малювання, що використовується в алгебричній геометрії. Діаграма станів автомата, графічне зображення скінченного автомата. Схема комп'ютерної мережі, зображення вузлів і з'єднань Комп'ютерної мережі. Блок-схема, зображення, у якому вузли представляють кроки алгоритму, та сторони — Потік керування між кроками. Діаграма потоків даних, зображення в якому вузли беруться за компоненти Інформаційної системи та сторони — рух інформації з одного компонента у інший. Біоінформатика включає філогенетичне дерево, мережу білок-білкової взаємодії, та .
Крім того, та трасування — кроки автоматизації проєктування електроніки (EDA) схожі у багатьох аспектах до зображення графів, оскільки існує проблема у розподілених обчисленнях, та література з зображенням графів містить декілька результатів, позичених з літератури EDA. Однак, ці проблеми також різняться у деяких важливих аспектах: наприклад, у EDA, область мінімізації та довжина сигналу важливіші за естетичність, але проблеми зв'язку у EDA можуть мати понад два термінали на мережу у той час, як аналогічна проблема у зображенні графа зазвичай містить пари вершин для кожного ребра.
Програмне забезпечення Програмне забезпечення, системи та провайдери систем для малювання графів: , програма з відкритим вихідним кодом від для зображення великих мереж шляхом малювання вузлів у вигляді горизонтальних ліній. , програмне забезпечення з відкритим вихідним кодом для візуалізації мереж молекулярної взаємодії. Gephi, програмне забезпечення для аналізу та візуалізації мережі з відкритим кодом. graph-tool — безкоштовна бібліотека Python для аналізу графів. Graphviz, система для малювання графів з відкритим вихідним кодом від «Graphviz and Dynagraph — Static and Dynamic Graph Drawing Tools», by John Ellson, Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Gordon Woodhull, in .. , програмне забезпечення для комерційного аналізу та візуалізації мережі для графових баз даних. Mathematica, засіб обчислення загального призначення, що містить 2D і 3D візуалізації графа та інструменти аналізу графівGraphPlot Mathematica documentation. , бібліотека .NET (раніше називалася GLEE) з відкритим кодом для зображення графів.. NetworkX — це бібліотека Python для вивчення графів та мереж. «Tulip — A Huge Graph Visualization Framework», by David Auber, in . — інструмент візуалізації даних з відкритим кодом. yEd, редактор графів з функціоналом розмітки«yFiles — Visualization and Automatic Layout of Graphs», by Roland Wiese, Markus Eiglsperger, and Michael Kaufmann, in .. 3.0 з graphdrawing пакетом (необхідно мати ); see also the older GD 2012 presentation . , програмне забезпечення для візуалізації великих мереж з відкритим кодом.
Див. також Одночасне вкладення графів
Примітки Виноски
Загальні посилання
. . . . . .
Спеціалізовані підтеми
. . . . . . . . . . . . . . . . . . . . . . . .
Посилання GraphX library for .NET : WPF бібліотека з відкритим кодом для обчислення та візуалізації графів. Підтримує багато макетів та алгоритмів з'єднання сторін.