Алгоритмы визуализации графов

Общие сведения

Визуализацией графа называется построение двухмерного (реже для специфических исходных данных — трехмерного) представления его ребер и вершин. Для визуализации графов существуют различные алгоритмы. Они отличаются друг от друга требованиями к графу (взвешенные/невзвешенные ребра, ограничение на максимальное число вершин), скоростью получения конечного результата, видом представления графа, которое будет построено по окончанию работы, а главное — целью, с которой они применяются.

Визуализация графов находит применение в различных практических отраслях: программная инженерия (диаграммы сущностей, потоков данных, маршрутов), управление проектами, представление структурированных знаний и данных, проектирование микросхем, социологические исследования и др [8, c.3].

Способы и критерии визуализации

Поскольку существует большое количество видов графов, для их отображения используются различные способы [8, c.4]:

· Произвольное:

Рисунок 1. Граф, изображенный произвольным способом.

· Полигональное — в нем для отображения ребер используются ломаные:

Рисунок 2. Граф, изображенный полигональным способом.

· Прямолинейное — ребра изображаются отрезками:

Рисунок 3. Граф, изображенный прямолинейным способом.

· Ортогональное — ребра — ломаные, состоящие из вертикальных и горизонтальных отрезков:

Рисунок 4. Граф, изображенный ортогональным способом.

· Сеточное — вершины расположены в узлах сетки:

Рисунок 5. Граф, изображенный сеточным образом.

· Восходящее и нисходящее — применяется для изображения ориентированных графов. Показывает «поток» — направлением движения по графу (например, сверху вниз). Также этот способ позволяет наглядно визуализировать иерархические отношения (например, генеалогическое древо) вершин:

Рисунок 6. Граф, изображенный восходящим / нисходящим способом Помимо выбора способа визуализации графа необходимо учесть ряд эстетических критериев [8, с.11]:

• · Минимизация числа пересечений ребер
• · Минимизация пространства занимаемого изображением графа (размеров областей графа)
• · Максимизация минимального угла между ребрами в графе
• · Универсальность длин ребер (минимизация различий между ними)
• · Минимизация числа изгибов ортогональных и наклонов полигональных отображений
• · Максимизация симметрии

Чем большее число этих критериев соблюдено в ходе построения представления графа на плоскости или в трехмерном пространстве, тем доступнее будет его дальнейший анализ.