Диссертация (1090614), страница 17
Текст из файла (страница 17)
Есть лишь два требования к хранилищам,необходимые для успешного выполнения этих операций. Во-первых, спискивершин обоих хранилищ со всеми их атрибутами должны одновременнопомещаться в оперативной памяти. Во-вторых, объединенное хранилище недолжно содержать вершины, все связи которой вместе с атрибутами непомещались бы в оперативную память.Данная структура хранилища и предусмотренные операции былипротестированы на графах, имеющих порядка 100 миллионов вершин инескольких миллиардов связей.132Используемые структуры данных4.3.Спроектированы эффективные структуры данных, которые позволилисоздатьразвитуюсистемуредактированияианализабезущербапроизводительности и с допустимым объемом занимаемой памяти.
Длябыстрого доступа к вершинам и связям используются сбалансированныебинарные деревья поиска.Для быстрого доступа к инцидентным связям вершины используетсяеще одна структура – сбалансированное бинарное дерево поиска, ключами вкотором будут указатели на вершины, а хранимым значением для каждогоключа (вершины) будет сбалансированное бинарное дерево поиска, ключамив котором будут являться указатели на связи.В данной структуре для каждой вершины хранится набор инцидентныхсвязей.
В таблице 4.1 приведен анализ эффективности базовых операций свыбранной структурой при работе с графом, полностью загруженным воперативную память. Пусть - множество вершин графа, - множество реберграфа.Таблица 4.1. Асимптотика операций при работе с графом.ОперацияАсимптотика операцийДобавление связи(2(||))Удаление связи(2(||))Добавление вершины(2(||))Удаление вершины(2(||))Поиск вершины((||))Поиск связи((||))133Объем занимаемой памяти: (с1|| + с2||), где с1 = 2, с2 = 3.Так как все вершины и связи хранятся в бинарных сбалансированныхдеревьях поиска, все оценки времени работы и объема занимаемой памятиимеют логарифмическую сложность. Для хранения всей структуры графаиспользуется 3 базовых структуры данных: множество всех вершин,множество всех связей, структура, сопоставляющая каждой вершинемножество ее инцидентных связей.
Константа с1 получена за счет двойногохранения каждой вершины в первой и третьей структуре. Константа с2получена за счет хранения каждой связи во второй структуре и двойногохранения каждой связи в третьей структуре данных.В вышеописанной структуре данных в каждой вершине хранится всянеобходимая информация для визуализации.
Со связями дело обстоитнесколько иначе: данные по изображению связи в качестве ломаной линиихранятся в отдельной структуре данных.Введем следующие структуры данных. Первая структура данных будетсодержать пару указателей на вершины c заданной операцией сравнения.Другая структура содержит в себе координаты ломаной линии, котораявыступает в качестве направляющей при отрисовке всех связей между двумяобъектами. Связь будет визуализироваться с тем же количеством сегментов,идущих параллельно направляющей линии, за исключением двух: первого ипоследнего. Кроме того, во второй структуре также будет хранитьсядополнительная информация о различных параметрах сдвигов относительнонаправляющей линии.Более того, экземпляр класса будет содержать в себе сбалансированноебинарное дерево поиска, ключами в котором будут являться указатели насвязи.
Это сделано для того, чтобы иметь быстрый доступ ко всем объектам,которыедолжныбытьвизуализированыотносительнозаданной134направляющей кривой, так как для каждой связи не подразумевается хранениекоординат ее отрисовки. Все координаты будут вычисляться во времявыполнения программы.Тогда можно создать сбалансированное бинарное дерево поиска,ключами в котором будут структуры, содержащие пары вершин, а значениембудет структура с координатами ломаной линии.Таким образом мы сможем сократить объем хранимой памяти, темсамым эффективно решать задачу хранения настроек отрисовки связей и ихбыструю визуализацию.
При работе с большими графами критичнымиявляются не только все без исключения базовые операции, но и объемтребуемойпамяти.Разработаннаяструктураданныхподходитдляпоставленной задачи.Далее приводится описание диаграммы классов, включающей в себяосновные базовые классы. Здесь и далее на диаграммах классов будутотображаться только значимые поля и методы, остальные будут опущены.135Рис.
4.2.Диаграмма классов автоматического размещений.НаРис.4.2представленадиаграммакласcов автоматическогоразмещений графа на плоскости. Все алгоритмы автоматического размещенийунаследованы от одного общего интерфейса, благодаря чему встраиваниенового алгоритма производится быстро. Класс CircularLayout реализуетгеометрическуюмодельCircularLayoutComponents–круговогокруговогоразмещенияобъектов,покомпонентногоразмещения,CenterNodeLayout – размещение «вершина в центре». Размещения на основелиний темы (SingleThemeLayout и TwoThemeLayout) унаследованы отбазового класса IThemeLayout.
Для работы этих алгоритмов необходимывершины, представленные на схеме в виде линий тем. Для алгоритмовавтоматическогоразмещениянаосновевыделенныхсообществ(FDLayoutCommunities и CircLayoutCommunities) необходимы результатыалгоритма выделения сообществ – список непересекающихся множестввершин.Рис. 4.3.Диаграмма классов алгоритмов выделения сообществ.На Рис. 4.3 представлены два класса, реализующих алгоритм выделениясообществ. Оба класса унаследованы от интерфейса ICommunityDetector,136определяющего общие методы запуска алгоритма (Apply) и получениярезультатовалгоритм(GetCommunities).Блонделя(разделКласс1.3.2),BlondelCommDetectorклассреализуетAvsCommDetector–модифицированный алгоритм на основе случайного Россваля-Бергстрома(раздел 3.1).Рис.
4.4.Диаграмма классов визуального отображения вершин и связей.На Рис. 4.4 представлены классы, отвечающие за визуальноеотображение объектов на схеме. Интерфейс IFigure определяет набор методови свойств, которые потом будут использоваться при визуализации всей схемы.Интерфейс INodeFigure определяет отображение вершины, Класс LinkFigureопределяет и реализует отображение связи на плоскости.
В разработанномпрограммном комплексе предусмотрено несколько способов отображениявершин: в виде иконки (класс IconNodeFigure), в виде таблицы (классTableNodeFigure) и в виде линии темы (класс ThemeNodeFigure).137Рис. 4.5.Диаграмма классов вершин и связей.На Рис. 4.5 представлена диаграмма классов вершин и связей. КлассAttributedItem реализует хранение и работу с атрибутами объекта. КлассSelectableItem определяет процедуру работы при выделении объекта на схеме,класс HidableItem определяет методы для скрытия объекта со схемы.Классы Node и Link наследуются от базового класса Item, тем самым ониобладают необходимыми свойствами и методами для работы с атрибутами ивизуального отображения на схеме.138Рис.
4.6.Диаграмма классов, использующихся при визуализации и работе сграфом.На Рис. 4.6 представлены классы, использующиеся для хранения ивизуализации графа. Класс Network определяет хранение графовой структурыи базовые операции над ней. Класс NetworkDrawing реализует быструювизуализацию объектов на экране. Класс Chart является промежуточнымзвеном при работе с хранилищем, графом и его отображением. Класс Viewportреализуетбазовыеметоды-обработчикидействий,поступающихотпользователя: масштабирование, навигация, выделение, редактированиеобъектов.1394.4.ДанныйпрограммныйИнструменты анализакомплекспредоставляетширокуюфункциональность при работе с графами больших размеров [74, 75].В программном комплексе предусмотрено несколько изобразительныхсоглашений длявершин: иконки,линии темы,таблицы.Доступнавизуализация множественных связей с изломами между вершинами, свозможностью задания ширины, цвета и типа линии. Для атрибутов такжепредусмотрено множество способов и настроек отображения.Помимо богатой функциональности отображения различных элементовграфа, разработанное ядро визуализации человеко-машинного интерфейсапозволяет манипулировать большими графами, размеры которых достигаютмиллиона вершин и нескольких миллионов связей, за счет специальноразработанных и оптимизированных алгоритмов машинной графики.За счет связки с графовым хранилищем удобно работать с огромнымиграфами путем выгрузки подграфов по заданным фильтрам, объединения ипересечения графов.
Стоит отметить, что, за счет наличия модуля конвертацииданных, все графы хранятся в едином специализированном форматехранилища.Аналитические инструменты позволяют проводить разнообразныеисследования графа и его структуры:• поиск и выделение вершин и связей по заданным атрибутам;• подсчет показателя центральности для всех вершин и связей.В теории графов центральность элемента (вершины или связи)определяет его значимость относительно других объектов.
В программномпродукте реализованы несколько показателей центральности: центральностьпо посредничеству, центральность по степени, центральность по близости.140Например,используетсяпоказательсвязи–центральностьпопосредничеству (betweenness centrality): количество кратчайших путей междувсеми парами вершин, проходящих через заданную связь.Центральность по степени – это отношение количества связейопределённого узла к общему количеству других узлов.Центральность по близости (4.1) выражает, насколько близко узелрасположенкостальнымузламсети.Формально,нормализованнаяцентральность по близости выражается как отношение числа других узловграфа к сумме расстояний между определённым узлом и всеми другими.
Еслизначение центральности по близости равно 1, это означает, что определённыйузел связан со всеми другими узлами. ( ) =−1∑∈ (,),(4.1)где - множество вершин графа, = || - количество всех вершин, вершина, для которой выполняется вычисление показателя центральности,(, ) - функция расстояния от вершины до вершины .Кроме того, для поиска важных объектов с точки зрения структурыграфа выполняется поиск мостов и точек сочленения. Точкой сочленения (илиточкойартикуляции)называетсятакаявершина,удалениекоторойувеличивает число компонент связности. Поиск всех точек сочленения в графевыполняется на основе поиска в глубину.Мостом называется такое ребро, удаление которого увеличивает числокомпонент связности.
Неформально эта задача ставится следующим образом:требуется найти на заданной карте дорог все "важные" дороги, т.е. такиедороги, что удаление любой из них приведёт к исчезновению пути междукакой-то парой городов. Поиск всех мостов в графе также реализуется наоснове поиска в глубину.141Программный комплекс позволяет проанализировать кратчайшие путимежду любой парой вершин в сети, для нахождения кратчайших путей междупарой вершин используется алгоритм Дейкстры.Для сравнения графов одного размера используются показателиплотности и кластеризации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
