Алгоритм визуализации графа — это алгоритм, позволяющий расположить узлы графа в двумерном или трехмерном пространстве так, чтобы все его ребра имели бы более-менее одинаковую длину.
Общие сведения о графах и графовых моделях
Под графом следует понимать пару множеств, первое из которых является непустым конечным множеством элементов произвольной природы или множеством вершин, а второе выступает как подмножество декартового произведения множества вершин и именуется множеством дуг. Дуги бывают ориентированные и неориентированные.
Графы и графовые модели широко используются в самых разных областях, поскольку позволяют осуществить наглядное представление сложной информации. Графовыми моделями считаются расширения графов, к примеру, графы, имеющие атрибуты для элементов. Формирование визуальных образов используется для наглядного отображения графов и графовых моделей.
Визуализация графов связана с графическим отображением компонентов графа, представляющим связи между вершинами и удовлетворяющим эстетическим критериям. Примером эстетического критерия может служить минимальное количество пересечений дуг или отсутствие пересечений дуг и вершин.
Известно достаточно много методик визуализации графов, на базе которых сформированы системы визуализации графовых моделей. Среди последних имеются как узкоспециализированные, так и системы общего предназначения. Однако только лишь визуализация графовых моделей может дать представление лишь о структуре отображаемой информации.
Понимание того, как можно работать с информацией, которая представлена графами, способно повысить уровень понимания самой информации. Алгоритмы на графах призваны отображать операции над информацией, которая может быть представлена при помощи графов. Визуализация графовых алгоритмов может дать представление о методах работы с графовой информацией.
Иными словами, визуализация преобразования графовой модели при помощи реализации некоторого алгоритма может дать более полное представление об изображенной информации и, помимо этого, способна описать алгоритм преобразования графа. К примеру, если графовая модель отображена при помощи сети Петри в исходном состоянии, то примером визуализации алгоритма может быть демонстрация работы сети. Сегодня получило развитие направление визуализации алгоритмов, и в том числе, алгоритмов на графах.
Алгоритм визуализации графа
Под визуализацией графа следует понимать графическое отображение компонентов графа и связей между ними при помощи набора графических примитивов, удовлетворяющего определенному набору эстетических критериев. К примеру, треугольники для вершин графа, и ломаные линии для дуг. Известно достаточно много методик визуализации графов.
Данные методики условно могут быть поделены на классы, которые соответствуют классам графов. К примеру, известно всего одно семейство алгоритмов, отображающих ориентированные ациклические графы. Это так называемая по уровневая методика. Но для отображения неориентированных графов создано существенно больше семейств алгоритмов. Это, отображение, когда весь набор вершин расположен на концентрических окружностях или силовой метод, когда дуги считаются пружинами и для укладки применяется физическая модель шаров, которые соединены пружинами.
Визуализация облегчает понимание отображенной информации и, следовательно, упрощает ее анализ и последующую обработку. Проблема визуализации графов исследуется давно, и уже имеется значительное количество накопленных результатов в данной области. Но следует заметить, что визуализация алгоритмов на графах считается более сложной задачей. Поскольку алгоритм способен отображать определенные преобразования над графом или графовой моделью, то его визуализация может быть представлена в виде последовательной смены состояний графовой модели при использовании шагов или правил алгоритма.
Если пытаться визуализировать какие-либо данные просто выполнив их загрузку в программу, предназначенную для построения графов, то результат скорее всего будет отрицательный. Это означает, что необходимо вначале сформулировать, что требуется определить при помощи графов, и придумать жизнеспособную гипотезу. Для этого следует разобраться, какие данные уже имеются, а также что из них может быть представлено как объекты, а что как связи между ними. Как правило, объектов бывает существенно меньшее количество, чем связей между ними.
Рассмотрим простой пример, сделаем предположение, что люди, которые посещали одно и то же мероприятие, имеют определенные связи друг с другом. При этом, чем чаще они совместно участвовали в мероприятиях, тем более сильные образовывались связи. Предположим, что имеются данные об участниках 650 мероприятий. Эти данные могут быть представлены в виде 650 таблиц программы Excel, имеющих примерно 23000 записей в них, которые содержат поля «Leader ID», «Должность», «Организация».
Для того чтобы построить граф хватит одного уникального идентификатора, например, в нашем случае это может быть Leader ID, и признака, который привязывает всех участников к одной из следующих возможных областей:
- К органам власти.
- К области бизнеса.
- К области образования (к университету).
Данная информация пока отсутствует, а для того, чтобы ее получить, можно пойти простым путем, а именно, в каждом из 650-ти файлов следует удалить лишние столбцы и прибавить новое поле, заполнив его значениями для каждой строки. К примеру, это может быть:
- Один для сферы власти.
- Два для сферы бизнеса.
- Три для сферы образования и науки.
Для того чтобы загрузить данные практически в любую из программ визуализации необходимо создать следующие файлы:
- Перечень вершин.
- Список ребер.
После того как таблицы с данными сформированы, следует выбрать средство, позволяющее их представить в виде графа. Например, это может быть программа Gephi, которая является мощным инструментом, способным обработать графы с сотнями тысяч вершин и связей.
В итоге можно получить граф примерно в следующем виде:
Рисунок 1. Граф. Автор24 — интернет-биржа студенческих работ
