В информатике , А график представляет собой абстрактный тип данных , который предназначен для осуществления неориентированного графа и ориентированный граф понятий из области теории графов в математике .
Структура данных графа состоит из конечного (и , возможно , изменяемого) набор из вершин (также называемых узлами или точками ), вместе с набором неупорядоченных пар этих вершин для неориентированного графа или набором упорядоченных пар для ориентированного графа. Эти пары называются ребрами (также называемыми связями или линиями ), а для ориентированного графа также называются ребрами, но также иногда стрелками или дугами . Вершины могут быть частью структуры графа или могут быть внешними объектами, представленными целочисленными индексами или ссылками .
Структура данных графа может также связывать с каждым ребром некоторое значение ребра , например символическую метку или числовой атрибут (стоимость, емкость, длина и т. Д.).
Операции
Основные операции, обеспечиваемые структурой данных графа G, обычно включают: [1]
adjacent
( G , x , y ): проверяет, есть ли ребро из вершины x в вершину y ;neighbors
( G , x ): перечисляет все вершины y такие, что есть ребро от вершины x до вершины y ;add_vertex
( G , x ): добавляет вершину x , если ее нет;remove_vertex
( G , x ): удаляет вершину x , если она есть;add_edge
( G , x , y ): добавляет ребро из вершины x в вершину y , если его там нет;remove_edge
( G , x , y ): удаляет ребро из вершины x в вершину y , если оно есть;get_vertex_value
( G , x ): возвращает значение, связанное с вершиной x ;set_vertex_value
( G , х , v ): задает значение , связанное с вершиной х к v .
Структуры, которые связывают значения с краями, обычно также предоставляют: [1]
get_edge_value
( G , x , y ): возвращает значение, связанное с ребром ( x , y );set_edge_value
( G , x , y , v ): устанавливает значение, связанное с ребром ( x , y ), равным v .
Общие структуры данных для графического представления
- Список смежности [2]
- Вершины хранятся в виде записей или объектов, и каждая вершина хранит список смежных вершин. Эта структура данных позволяет хранить дополнительные данные о вершинах. Дополнительные данные могут быть сохранены, если ребра также хранятся как объекты, и в этом случае каждая вершина хранит свои инцидентные ребра, а каждое ребро хранит свои инцидентные вершины.
- Матрица смежности [3]
- Двумерная матрица, в которой строки представляют исходные вершины, а столбцы - конечные вершины. Данные о ребрах и вершинах должны храниться извне. Между каждой парой вершин может храниться только стоимость одного ребра.
- Матрица заболеваемости [4]
- Двумерная матрица, в которой строки представляют вершины, а столбцы - края. Записи указывают отношение инцидентности между вершиной в строке и ребром в столбце.
Следующая таблица дает временную сложность стоимость выполнения различных операций на графиках, для каждого из этих представлений, с | V | количество вершин и | E | количество ребер. [ необходима цитата ] В матричных представлениях записи кодируют стоимость следования за ребром. Стоимость отсутствующих ребер предполагается равной ∞.
Список смежности | Матрица смежности | Матрица заболеваемости | |
---|---|---|---|
График магазина | |||
Добавить вершину | |||
Добавить край | |||
Удалить вершину | |||
Удалить край | |||
Смежны ли вершины x и y (при условии, что их позиции хранения известны)? | |||
Замечания | Медленно удаляет вершины и ребра, потому что нужно найти все вершины или ребра | Медленно добавлять или удалять вершины, потому что матрица должна быть изменена / скопирована | Медленное добавление или удаление вершин и ребер, потому что матрица должна быть изменена / скопирована |
Списки смежности обычно предпочтительны, потому что они эффективно представляют разреженные графы . Матрица смежности предпочтительна, если граф плотный, то есть число ребер | E | близко к квадрату числа вершин, | V | 2 , или если нужно иметь возможность быстро найти, есть ли ребро, соединяющее две вершины. [5] [6]
Параллельные представления
Распараллеливание графов сталкивается со значительными проблемами: вычислениями, управляемыми данными, неструктурированными проблемами, плохой локальностью и высоким соотношением доступа к данным и вычислений. [7] [8] Графическое представление, используемое для параллельных архитектур, играет важную роль в решении этих проблем. Плохо выбранные представления могут излишне увеличить стоимость связи алгоритма, что снизит его масштабируемость . Далее рассматриваются архитектуры с разделяемой и распределенной памятью.
В случае модели с разделяемой памятью представления графа, используемые для параллельной обработки, такие же, как и в последовательном случае [9], поскольку параллельный доступ только для чтения к представлению графа (например, списку смежности ) эффективен в разделяемой памяти.
Распределенная память
В модели с распределенной памятью обычным подходом является разбиение множества вершин графика в наборы . Здесь,- количество доступных обрабатывающих элементов (ПЭ). Разделы набора вершин затем распределяются между PE с совпадающим индексом, в дополнение к соответствующим ребрам. Каждый PE имеет свое собственное представление подграфа , где ребра с конечной точкой в другом разделе требуют особого внимания. Для стандартных интерфейсов связи, таких как MPI , идентификатор PE, владеющего другой конечной точкой, должен быть идентифицируемым. Во время вычислений в алгоритмах распределенного графа передача информации по этим ребрам подразумевает обмен данными. [9]
Разбиение графа должно выполняться осторожно - существует компромисс между низкой связью и разделением по размеру [10]. Но разделение графа - это NP-трудная задача, поэтому вычислить их невозможно. Вместо этого используются следующие эвристики.
1D-разбиение: каждый процессор получает вершины и соответствующие исходящие ребра. Это можно понимать как разложение матрицы смежности по строкам или столбцам. Для алгоритмов, работающих с этим представлением, это требует шага связи «Все ко всем», а такжеразмеры буфера сообщений, поскольку каждый PE потенциально имеет выходящие края для каждого другого PE. [11]
2D-разбиение: каждый процессор получает подматрицу матрицы смежности. Предположим, что процессоры выровнены по прямоугольнику., где а также - количество обрабатываемых элементов в каждой строке и столбце соответственно. Затем каждый процессор получает подматрицу матрицы смежности размерности. Это можно представить в виде шахматной доски в матрице. [11] Следовательно, каждый блок обработки может иметь выходящие ребра к PE только в одной строке и столбце. Это ограничивает количество коммуникационных партнеров для каждого PE до снаружи возможные.
Сжатые представления
Графы с триллионами ребер встречаются в машинном обучении , анализе социальных сетей и других областях. Представления сжатых графов были разработаны для уменьшения требований к вводу-выводу и памяти. Применимы общие методы, такие как кодирование Хаффмана , но список смежности или матрица смежности можно обрабатывать определенными способами для повышения эффективности. [12]
Смотрите также
- Обход графа для стратегий обхода графа
- База данных графов для устойчивости графа (структуры данных)
- Переписывание графов для преобразований графов на основе правил (структур данных графов)
- Программное обеспечение для рисования графиков для программного обеспечения, систем и поставщиков систем для рисования графиков
Рекомендации
- ^ a b См., например, Goodrich & Tamassia (2015) , раздел 13.1.2: Операции над графами, стр. 360. Более подробный набор операций см. В Mehlhorn, K .; Нахер, С. (1999), «Глава 6: Графы и их структуры данных», LEDA: платформа для комбинаторных и геометрических вычислений , Cambridge University Press, стр. 240–282..
- ^ Кормен и др. (2001) , стр. 528–529; Гудрич и Тамассия (2015) , стр. 361-362.
- ^ Кормен и др. (2001) , стр. 529–530; Гудрич и Тамассия (2015) , стр. 363.
- ^ Кормен и др. (2001) , упражнение 22.1-7, стр. 531.
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), «Раздел 22.1: Представления графов», Введение в алгоритмы (второе издание), MIT Press и McGraw-Hill, стр. 527–531, ISBN 0-262-03293-7.
- ^ Гудрич, Майкл Т .; Тамассия, Роберто (2015), «Раздел 13.1: Терминология и представления графов», Разработка алгоритмов и приложения , Wiley, стр. 355–364..
- ^ Бадер, Дэвид; Мейерхенке, Хеннинг; Сандерс, Питер; Вагнер, Доротея (январь 2013 г.). Разбиение графов и кластеризация графов . Современная математика. 588 . Американское математическое общество. DOI : 10.1090 / conm / 588/11709 . ISBN 978-0-8218-9038-7.
- ^ ЛУМСДЕЙН, ЭНДРЮ; ГРЕГОР, ДУГЛАС; ХЕНДРИКСОН, БРЮС; БЕРРИ, ДЖОНАТАН (март 2007 г.). «Проблемы параллельной обработки графов». Письма параллельной обработки . 17 (1): 5–20. DOI : 10.1142 / s0129626407002843 . ISSN 0129-6264 .
- ^ а б Сандерс, Питер; Мельхорн, Курт; Дицфельбингер, Мартин; Дементьев, Роман (2019). Последовательные и параллельные алгоритмы и структуры данных: базовый набор инструментов . Издательство Springer International. ISBN 978-3-030-25208-3.
- ^ «Параллельная обработка графиков» (PDF) .
- ^ а б «Параллельный поиск в ширину в системах с распределенной памятью | Труды Международной конференции 2011 года по высокопроизводительным вычислениям, сетевым технологиям, хранению данных и анализу». DOI : 10.1145 / 2063384.2063471 . S2CID 6540738 . Цитировать журнал требует
|journal=
( помощь ) - ^ Беста, Мацей; Хефлер, Торстен (27 апреля 2019 г.). "Обзор и систематика сжатия графов без потерь и пространственно-эффективных графических представлений". arXiv : 1806.01799 . Цитировать журнал требует
|journal=
( помощь )
Внешние ссылки
- Библиотека графов Boost: мощная библиотека графов C ++ sa Boost (библиотеки C ++)
- Networkx: библиотека графов Python
- GraphMatcher - программа на Java для выравнивания ориентированных / неориентированных графов.
- GraphBLAS Спецификация интерфейса библиотеки для операций с графами с особым вниманием к разреженным графам.