«Методы визуализации информации при помощи графов. Часть 2. Методы визуализации ориентированных и неориентированных графов»
 
Домой Лекции Список литературы Справочник


Раздел 1. Силовые алгоритмы для визуализации графов небольшого объема

Предыдущий раздел Разделы Следующий раздел

Содержание:

Модель Идеса (1984)

Алгоритм Фрюхтермана и Рейнгольда (1991)

Использование силы гравитации при размещении графа.

Использование аналога магнитного поля для размещения ориентированных графов

Размещения, основанные на поиске локального минимума энергии

Метод барицентров

Модель энергии LinLog.



Наиболее гибкие алгоритмы, позволяющие строить изображения простых
неориентированных графов, относятся к классу силовых алгоритмов, известных также
под названием алгоритмов, основанных на физических аналогиях. Методы, основанные на
физических аналогиях очень популярны по следующим причинам:
– они пригодны для построения изображения графов произвольного вида;
– они очень интуитивны;
– их легко понять и запрограммировать;
– их легко настраивать на специфические требования;
– для графов размером порядка ста пятидесяти вершин дают вполне
удовлетворительные результаты.
Изображения, создаваемые при помощи этих алгоритмов, выглядят эстетично, отражают
симметрию и содержат мало пересечений ребер. Основу любого силового алгоритма
составляют две компоненты:
1) модель, описывающая систему из физических объектов и взаимодействие между
этими объектами;
2) алгоритм, который (приблизительно) вычисляет состояние равновесия для этой
системы.

Описание модели строится на основе представлений разработчика о том, какое
изображение можно считать хорошим в каждом конкретном случае. С моделью
связывается целевая функция, описывающая конкретное понятие «хорошести», а
алгоритм служит для оптимизации целевой функции. Если система описана, и объектам
разрешено двигаться под влиянием действующих на них сил, то она постепенно придет в
состояние равновесия, в котором все силы уравновешивают друг друга.  Изображение,
соответствующее этому положению равновесия, будет приблизительно удовлетворять
указанным выше критериям. Заметим, что такая модель может быть выражена либо в
терминах сил, действующих на физические объекты, либо в терминах потенциальной
энергии. Методы, основанные на энергии, состоят из модели энергии и алгоритма,
который ищет состояние минимума этой энергии. Силовые методы состоят из модели сил
и алгоритма, который ищет положение, в котором сумма сил, действующих на каждый
объект, равна нулю. Поскольку сила является отрицательным градиентом энергии,  то
положение равновесия соответствует локальному минимуму энергии.

Предыдущий раздел Разделы Следующий раздел