Диссертация (1090614), страница 16
Текст из файла (страница 16)
Такой подход позволяет пересекать графы с количествомвершин порядка нескольких миллионов и количеством связей порядканескольких миллиардов в каждом.Алгоритм способен обрабатывать объемы данных, не помещающиеся воперативную память, за счет последовательного считывания данных сжесткого диска при выполнении фильтрации дублированных связей.Операция объединения двух графов аналогична пересечению всеголишь с одним отличием: множества вершин исходных графов объединяются,при этом отождествление вершин по набору атрибутов гарантирует отсутствиеповторяющихся вершин в новом графе.126При работе с небольшими графами (несколько десятков вершин) ещевозможно выполнить размещение элементов сети вручную.
При увеличенииразмеров исследуемого графа начиная с нескольких сотен вершин задачаручного размещения становится невыполнимой.В связи с большим разнообразием видов графов, существует множестворазличныхспособовавтоматическогоотображенияграфов.Модульавтоматического размещения предназначен для автоматического размещенияобъектов и реализует графические схемы [18, 38] типа павлиний хвост, линиятемы, круговое размещение, покомпонентное круговое размещение, а такжеразмещение, основанное на алгоритме выделения сообществ в сети.Всеразработанныеалгоритмыавтоматическогоразмещениянаправленны на работу с большими графами, достигающими сотен тысячвершин. Визуальное представление сетей может выступать в качествемощного метода отображения скрытой информации, хранящейся в данных осистеме взаимосвязанных объектов.Модуль визуализации отвечает за способы отображения объектов сети иза скорость их отображения.
В программном комплексе предусмотренонесколько изобразительных соглашений для вершин: иконки, линии темы,таблицы. Отдельно стоит отметить способ представления вершин в виделинии темы.Линиятемы–это вершина,котораяпредставляетсяв видегоризонтального отрезка с иконкой, причем все смежные вершины соединеныс линией темы перпендикулярно (если они находятся над или под ней) или сближайшим ее концом. Положение концов линии темы и ее длина можетменяться.Использованиеданногоспособапредставленияпозволяетэффективно решать задачу визуализации для некоторых графов.
Доступнавизуализация множественных связей с изломами между вершинами, с127возможностью задания ширины, цвета и типа линии. Для атрибутов такжепредусмотрено множество способов и настроек отображения.Для эффективного отображения графов используются специальноразработанные структуры данных, позволяющие получать быстрый доступ кданным, и алгоритмы машинной графики, заточенные под одновременноеотображение большого количества объектов.Всевершиныисвязиграфахранятсявсоответствующихсбалансированных бинарных деревьях поиска, где ключами выступаютуказатели на объекты.Структура связей графа хранится в сбалансированном бинарном деревепоиска, где в качестве ключей выступают указатели на вершины, а в качествезначений хранятся множества инцидентных ребер соответствующей вершины,которые в свою очередь также реализованы на сбалансированных бинарныхдеревьях поиска.
Выбор данной структуры обусловлен тем, что доступ кслучайной вершине или связи, доступ к инцидентным связям вершины иудаление или добавление объектов будет осуществляться за логарифмическоевремя.При визуализации используются координаты вершин, хранящихся вструктуре вершины. В то время как координаты связей вычисляются впроцессе визуализации. Для этого предусмотрена отдельная структураданных, отвечающая за хранение направляющей линии между парой вершин.Все связи между заданной парой вершин будут строго параллельнынаправляющей линии и содержать такое же количество изломов.
Тем самымдостигается эффективное расходование оперативной памяти без ущербапроизводительности.Процесс визуализации распараллелен на несколько уровней. Процессотрисовки связей, вершин и атрибутов происходит параллельно, и толькопосле полного выполнения всех потоков граф отображается на экране.128Отдельно стоит отметить, что при перемещении или изменении одного илинескольких объектов схемы, перерисовывается не вся схема целиком, а толькоее небольшая часть. Это достигается за счет применения описанной вышеметодики независимо для объектов двух типов: объектов, которые могутменять свое состояние в процессе выполнения операции, и объектов,остающихся неизменными в процессе выполнения операции.Практически большую часть времени объектов второго типа на порядкименьше, чем объектов первого типа, тем самым в процессе работы с графомчасто выполняется перерисовка объектов второго типа, в то время какзатратная операция перерисовки большого количества объектов первого типавыполняется заметно реже.
За счет этого достигается высокая скоростьвизуализации графа и манипулирования данными.Описанный программный комплекс реализован на языке C++.Реализациявизуализациивыполненасиспользованиемграфическойбиблиотеки OpenGL. Интерфейс реализован с использованием библиотеки Qt.Все используемые средства реализации являются кроссплатформенными. Темсамым программный комплекс способен функционировать в различныхоперационных системах.Описанный программный комплекс позволяет обрабатывать 6 млн вершин исвязей при визуализации в режиме реального времени.4.2.Хранение данныхХранилище графов [78] ориентировано главным образом на поддержкуопераций пополнения, объединения и пересечения графов, и поискакратчайших путей между двумя группами вершин.Используемые структуры данных рассчитаны на работу с графами,содержащими до 100 миллионов вершин и нескольких миллиардов связей,129поэтому хранение графа в виде матрицы смежности не представляетсявозможным.
За основу взят способ хранения графа в виде списков смежности.Вкачествебазовойструктурыхранилищаиспользуетсяспециализированная файловая система. Данная система реализуется внутринекоторого файла стандартной файловой системы компьютера, поэтому подлогическимфайломбудемпониматьфайл,принадлежащийданнойспециализированной системе. Предполагается, что каждый логический файлсостоит из некоторых записей переменной длины.
Главные преимущества отиспользования собственной файловой системы состоят в следующем:• отсутствие системных вызовов при работе с собственной файловойсистемой;• втрадиционныхфайловыхсистемахимеетсясущественноеограничение на количество одновременно открытых файлов, котороеотсутствует при использовании собственной файловой системы;• управление буферизацией и хранением данных прозрачно и независит от особенностей операционной системы;• отсутствие сложной системы адресации (структуры каталогов) илишних механизмов (права доступа) приводит к отсутствиюдополнительных накладных расходов на организацию храненияданных.Все добавляемые в граф вершины идентифицируются возрастающиминатуральными числами, начиная с 1.
Атрибуты вершин складываются внекоторый файл по порядку.Если атрибуты очередной вершины требуют для своего хранения S байт,то для них резервируется 1.2 ∗ + байт, где -параметр алгоритма,который выбирается в зависимости от параметров атрибутов того графа,который планируется хранить. Наличие дополнительного места позволяет вдальнейшем изменять атрибуты некоторой вершины, в том числе путем130добавленияновых.Еслисвободногоместанедостаточно,длямодифицируемой вершины будет выделена еще одна запись, и обе записибудут объединены в двунаправленный список. В дальнейшем возможновыделение дополнительных записей.При этом возникает некоторая фрагментация, которая может бытьустранена путем перестроения файла атрибутов вершин, что потребует полнойостановки работы хранилища.Каждой вершине сопоставлен один логический файл (), в которомхранятся записи, описывающие связи этой вершины.
При этом одинлогический файл может быть сопоставлен нескольким вершинам.Каждая связь , добавляемая в хранилище, формирует некоторую запись,которая содержит идентификаторы двух соединяемых вершин, два битахарактеризующие ее направленность (связь может быть ненаправленной), атакже все атрибуты связи. Кроме того, каждой связи присваивается некоторыйуникальный идентификатор, который также добавляется в виде отдельногополя к добавляемой записи.При работе с хранилищем может возникнуть необходимость в полномудалении или изменении содержащихся в вершине или связи атрибутов.Соответствующие операции реализованы в хранилище.Для более быстрого выполнения операций поиска вершин поконкретнымзначенияматрибутоввхранилищеприсутствуетспециализированный индекс по атрибутам вершин. Данный индекс такжеиспользует собственную копию специализированной файловой системы.Также реализована операция поиска кратчайших путей между паройобъектов.Рассматриваемыйобъемданныхделаетневозможнымиспользование стандартного алгоритма поиска в ширину для нахождениякратчайшего пути.
Для реализации операций поиска пути и нахождениякомпонент связности используется сбалансированное дерево кортежей (a, b,131N), состоящих из идентификаторов двух вершин и числа, равного количествусвязей в графе между ними.Данная структура за логарифм от числа уникальных ребер операцийпозволяет получить все вершины смежные с данной с условием, что кратностьсвязи должна быть выше заданного порога. С помощью этой структуры ипоиска в ширину происходит поиск путей и обнаружение компонентсвязности.Более сложные алгоритмы предполагают создание и поддержаниедополнительных структур данных, размер которых потенциально можетпревосходить размер самого графа в несколько раз.Используемая схема кластеризации списков смежности при построенииграфа не использует дополнительных структур данных, позволяя при этомзначительно сократить количество дисковых операций, требуемых длянахождения какого-либо пути между двумя группами вершин, по сравнениюс тривиальным алгоритмом поиска в ширину.Используемые структуры данных позволяют проводит эффективныеобъединение и пересечение графов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
