Диссертация (1090614), страница 9
Текст из файла (страница 9)
Каждая вершина перемещается на подсчитанный вектор в случае, если егодлина больше или равна . Переход к шагу 4.4. Если ни одна вершина не была смещена (т.е. длины всех векторовсмещений оказались меньше ), то переход к шагу 5, иначе – переход кшагу 6.5. Если текущее количество итераций превысило заданный порог k, товыполняется переход к шагу 6, иначе – переход к шагу 2.6.
Конец алгоритма.Результат: построено размещение вершин графа на плоскости.Рассматриваемая динамическая система начинает итерационно переходитьиз одного состояния в другое, меняя расположение вершин таким образом, чтобысистема стремилась к состоянию равновесия (Алгоритм 2.6 шаги 3-5).Следовательно, алгоритм закончит свою работу либо в случае, когда былодостигнуто максимальное количество итераций, либо когда динамическая системаперешла в состояние равновесия.62Визуализацииграфов,полученныеданнымметодом,какправило,получаются эстетичными, обладают симметрией и со значительно уменьшеннымколичеством пересечений связей (Рис.
2.5, Рис. 2.7).Рис. 2.5. Результат применения автоматического размещения «павлиний хвост».Базовый метод физических аналогий ограничен размером исследуемогографа: хорошие результаты на небольших графах, плохие результаты на графах,состоящих более чем из сотни вершин. Плохая применимость классическогоподхода на больших графах обусловлена несколькими причинами. Одной изосновных причин является тот факт, что используемая физическая модель обычноимеет большое множество локальных минимумов.Даже использование сложных механизмов получения локального минимумане дают базовому методу хороших результатов при работе на больших графах.Однако, существуют оптимизации, позволяющие получать приемлемыерезультаты на графах, размеры которых достигают десятки и даже сотни тысячвершин.
Ключевая идея оптимизации заключается в технике многоуровневогоразмещения, которая состоит в том, чтобы представить граф в более простой форме(сгруппировать вершины в иерархически вложенный набор кластеров), применитьклассический алгоритм размещения к данному упрощенному представлению иповторить аналогичные операции для каждого из выделенных кластеров. Темсамым базовый метод размещения на основе физических аналогий будетиерархически углубляться от более простых структур к сложным.632.2.2.Геометрическая модель автоматического размещения «быстрыйпавлиний хвост»Вданномразделепредлагаетсягеометрическаямодельалгоритмаавтоматического размещения [14], базирующегося на основе метода физическиханалогий под названием «быстрый павлиний хвост».Алгоритм 2.7.
Размещение «быстрый павлиний хвост» для всего графа.Вход: (, )-граф, где -множество вершин, - множество ребер, = ||, =||.Последовательность шагов:1. Множество вершин графа разбивается на компоненты связности(Алгоритм 2.3). Переход к шагу 2.2. Выполняется размещение каждой компоненты связности независимо другот друга с использованием построения минимального остовного дерева(Алгоритм 2.8). Переход к шагу 3.3. Совмещение размещенных компонент в одно размещение. Размещениядлякаждойкомпонентысвязностирасполагаютсявдольоднойгоризонтальной прямой, гарантируя отсутствие пересечений соседнихкомпонент связности. Переход к шагу 4.4.
Конец алгоритма.Результат: построено размещение вершин графа на плоскости.Алгоритм 2.8. Размещение «быстрый павлиний хвост» для одной компонентысвязности.Вход: множество вершин, входящих в одну компоненту связности.Последовательность шагов:1. Выполняется построение минимального остовного дерева. Переход кшагу 2.2. Выполняется поиск корневой вершины. Переход к шагу 3.3. Корневая вершина располагается на плоскости.
Переход к шагу 4.644. Выполняетсяразмещениедетейпоследнихдобавленныхвершин(определяются из остовного дерева) на плоскости с использованием (2.4).Переход к шагу 5.5. Добавление новых связей из исходного графа между присутствующимивершинами на схеме. Переход к шагу 6.6. Перемещение вершин с использованием (2.5). Переход к шагу 7.7. Если все вершины добавлены на плоскость, то переход к шагу 8. Иначе –переход к шагу 4.8. Конец алгоритма.Результат: построено размещение вершин графа из одной компоненты связностина плоскости.Асимптотическая сложность алгоритма «быстрый павлиний хвост» равна( ∗ с ∗ (|| + ||)), где – диаметр визуализируемого графа, – множествовершин, – множество ребер, с – константа (по умолчанию равна 25), задающаяколичество итераций при размещении очередного слоя (Алгоритм 2.9.
шаг 6).Благодаря использованию метода физических аналогий вершины обладаютсилой притяжения за счет связей-пружин и отталкивающей силой за счет зарядавершинивсетехжесвязей-пружин.Нижеприведенынесколькоосновополагающих идей, на которых базируется данный алгоритм. Такжеприводится более подробное описание каждого шага.Размещение графа основывается на выделении минимального остовногодерева (Алгоритм 2.8 шаг 1). Построение минимального остовного деревавыполняется с помощью алгоритма Крускала [10].Минимальное остовное дерево строится для того, чтобы построитьпоследовательность добавления вершин на плоскость, начиная с корневой .Корневая вершина будет первой, которая получит координаты на плоскости.Выбор корневой вершины (Алгоритм 2.8 шаг 2) может осуществлятьсяразными способами в зависимости от свойств исследуемых графов.
Чаще всего она65выбирается на основе одного из показателя центральности вершины в графе. Впрограммном комплексе используется 2 способа выбора. Первый (метод поумолчанию) - степень вершины, то есть выбираются та вершина, чья степеньявляется максимальной в исходном графе. Второй – корневая вершинаопределяется как вершина, при которой совокупная длина путей до всех остальныхвершин в минимальном остовном дереве будет минимальной. В реализациииспользуется первый метод за счет скоростных характеристик.После того, как построено минимальное остовное дерево и выбрана корневаявершина, всем остальным вершинам в дереве выставляется метка (уровеньглубины) – длина пути до корневой вершины.
Например, корневая вершина будетиметь уровень 0, инцидентные ей вершины – уровень 1. Данные уровнипроставляются на основе алгоритма обхода в ширину.Начиная с корневой вершины, вершины каждого уровня последовательнодобавляются на плоскость (Алгоритм 2.8 шаг 3). Каждый следующий уровеньвершин из минимального остовного дерева добавляется на заранее заданную сетку̅на плоскости по новой окружности (Алгоритм 2.8 шаг 4) на позицию ℎ(рассчитывается для каждой вершины уровня), которая является линейнойкомбинацией двух других векторов. Первый вектор – текущий центр масс̅ .
другой вектор - ̅ , соединяющий родительскую вершину текущейразмещения с прародительской (родительской вершиной родительской вершины для текущейдобавляемой вершины).̅̅̅ℎ= с ( ̅ + ̅ ) + ̅|| | |̅=1| |∑̅ ′ ′ ∈̅ = ̅ − ̅(2.4)66̅ | – длина вектора ̅ , |̅| – длина вектора ̅ , –Где с – константа, |представляет множество всех вершин, присутствующих на схеме, | | мощность множества (количество всех вершин, присутствующих на схеме).И так, вслед за добавлением вершин новые ребра добавляются только междутеми вершинами, которые присутствуют на схеме (Алгоритм 2.8 шаг 5).Затем происходит перемещение вершин (Алгоритм 2.8 шаг 6) за счетподсчета вектора смещения, определяющегося действием влияющих на вершинусил рассматриваемой физической модели.
Процедура заканчивается, когдадостигается заранее заданное количество итераций, или когда смещение вершиныстановится меньше заданного порога (в таком случае перемещение вершинысчитается незначительным).Для эффективного вычисления отталкивающей силы (Алгоритм 2.8 шаг 6),вершины на плоскости располагаются на сетку с заданным значением размераячейки. Таким образом для подсчета отталкивающих сил между вершинами втерминах пружин необходимо только знание о соседних связанных вершинах, сточки зрения заряженных частиц – знание о ближайших вершинах в пространстве.Вычислительная сложность зависит от размера сетки и может быть доведена до() .
Оптимизация достигается за счет анализа только соседних вершин,попадающих в локальную область на плоскости вокруг рассматриваемой вершиныграфа.Вектора сил притяжения и отталкивания считаются для каждой вершины изатем суммируются. Таким образом подсчитывается вектор смещения вершины наплоскости (Алгоритм 2.8 шаг 6). В процессе размещения вершин используетсядерево (Рис. 2.6), благодаря которому определяется порядок, по которому вершиныучаствуют в вычислении сил взаимодействия пружин. Вершины располагаются,начиная с корня минимального остовного дерева. Минимальное остовное деревоопределяется как минимальный набор ребер, необходимый для того, чтобы графостался связным, и сумма весов ребер была минимальной. Использование67минимального остовного дерева позволяется в итеративном процессе переходадинамической системы к состоянию равновесия сохранить структуру исходногографа, базирующуюся на центральности вершин.Рис.
2.6. Процедура размещения вершин на плоскости с учетом минимальногоостовного дерева, начиная с корня дерева.Суммарная сила, действующая на вершину на каждом шаге алгоритма засчет взаимодействия (притяжения и отталкивания) с другими вершинамирассчитывается по следующей формуле:⃗, = ⃗, + ⃗, == − ∑(|⃗ | − ) ∙ ⃗ − ∑(|⃗ | − ) ∙ ⃗ ,=1(2.5)=0где:• = 0 для всех |⃗ | > • и – константы, определяющие степень влияния притяжения иотталкивания от вершины;• - рекомендуемая длина связи с инцидентной вершиной ;• ⃗ – вектор между вершиной u и i;• |⃗ | – евклидово расстояние между двумя вершинами одного ребра, т.ерасстояние между текущей вершиной и соседней вершиной ;• – количество связей, одним концом из которых является вершина ;68• –количествовершинвлокальнойобластинаплоскости,удовлетворяющих неравенству |⃗ | < ;• ⃗ – вектор между вершиной u и вершиной j, вершины u и j не связаны,вершина j находится от вершины u на расстоянии меньше r;• отталкивание между вершинами применимо только в случае, когда ониближе друг другу на расстояние, меньшее чем .На Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
