Граф (абстрактный тип данных)

Абстрактный тип данных в информатике

Направленный граф с тремя вершинами (синие кружки) и тремя ребрами (черные стрелки).

В информатике граф — это абстрактный тип данных , предназначенный для реализации концепций неориентированного графа и ориентированного графа из области теории графов в математике .

Структура данных графа состоит из конечного (и, возможно, изменяемого) набора вершин ( также называемых узлами или точками ), вместе с набором неупорядоченных пар этих вершин для неориентированного графа или набором упорядоченных пар для ориентированного графа. Эти пары известны как ребра (также называемые связями или линиями ), а для ориентированного графа также известны как ребра , но также иногда как стрелки или дуги . Вершины могут быть частью структуры графа или могут быть внешними сущностями, представленными целочисленными индексами или ссылками .

Структура данных графа может также связывать с каждым ребром некоторое значение ребра , например, символическую метку или числовой атрибут (стоимость, емкость, длина и т. д.).

Операции

Диаграмма классов UML для графа (абстрактный тип данных)

Основные операции, предоставляемые структурой данных графа G , обычно включают: ^[1]

• neighbor( 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 , z ) : добавляет ребро z из вершины x в вершину y , если его там нет;
• remove_edge( G , x , y ) : удаляет ребро из вершины x в вершину y , если оно там есть;
• get_vertex_value( G , x ) : возвращает значение, связанное с вершиной x ;
• set_vertex_value( G , x , v ) : устанавливает значение, связанное с вершиной x, равным 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 | — число ребер. ^{[ необходима цитата ]} В матричных представлениях записи кодируют затраты на прохождение ребра. Затраты на отсутствующие ребра предполагаются равными ∞.

Списки смежности обычно предпочтительны для представления разреженных графов , в то время как матрица смежности предпочтительна, если граф плотный; то есть число ребер близко к числу вершин в квадрате, или если необходимо иметь возможность быстро найти, есть ли ребро, соединяющее две вершины. ^{[5] [6]} ${\displaystyle |E|}$ ${\displaystyle |V|^{2}}$

Более эффективное представление множеств смежности

Временную сложность операций в представлении списка смежности можно улучшить, сохраняя наборы смежных вершин в более эффективных структурах данных, таких как хэш-таблицы или сбалансированные двоичные деревья поиска (последнее представление требует, чтобы вершины были идентифицированы элементами линейно упорядоченного набора, такими как целые числа или строки символов). Представление смежных вершин с помощью хэш-таблиц приводит к амортизированной средней временной сложности для проверки смежности двух заданных вершин и удаления ребра и амортизированной средней временной сложности ^[7] для удаления заданной вершины x степени . Временная сложность других операций и асимптотические требования к пространству не изменяются. ${\displaystyle O(1)}$ ${\displaystyle O(\deg(x))}$ ${\displaystyle \deg(x)}$

Параллельные представления

Распараллеливание графовых задач сталкивается со значительными трудностями: вычисления, управляемые данными, неструктурированные проблемы, плохая локальность и высокий коэффициент доступа к данным для вычислений. ^{[8] [9]} Представление графа, используемое для параллельных архитектур, играет важную роль в решении этих проблем. Плохо выбранные представления могут неоправданно увеличить стоимость связи алгоритма, что снизит его масштабируемость . Далее рассматриваются архитектуры с общей и распределенной памятью.

Общая память

В случае модели общей памяти представления графов, используемые для параллельной обработки, такие же, как и в последовательном случае, ^[10], поскольку параллельный доступ только для чтения к представлению графа (например, список смежности ) эффективен в общей памяти.

Распределенная память

В модели распределенной памяти обычный подход заключается в разбиении набора вершин графа на множества . Здесь — количество доступных элементов обработки (PE). Разделы набора вершин затем распределяются по PE с соответствующим индексом, в дополнение к соответствующим ребрам. Каждый PE имеет свое собственное представление подграфа , где ребра с конечной точкой в ​​другом разделе требуют особого внимания. Для стандартных интерфейсов связи, таких как MPI , идентификатор PE, владеющего другой конечной точкой, должен быть идентифицируемым. Во время вычислений в алгоритмах распределенного графа передача информации по этим ребрам подразумевает связь. ^[10] ${\displaystyle V}$ ${\displaystyle p}$ ${\displaystyle V_{0},\dots ,V_{p-1}}$ ${\displaystyle p}$

Разделение графа должно быть выполнено аккуратно - есть компромисс между низкой коммуникацией и равномерным размером раздела ^[11] Но разделение графа является NP-трудной задачей, поэтому вычислить их не представляется возможным. Вместо этого используются следующие эвристики.

1D разбиение: Каждый процессор получает вершины и соответствующие исходящие ребра. Это можно понимать как разложение матрицы смежности по строкам или столбцам. Для алгоритмов, работающих с этим представлением, это требует шага связи All-to-All, а также размеров буфера сообщений, поскольку каждый PE потенциально имеет исходящие ребра к каждому другому PE. ^[12] ${\displaystyle n/p}$ ${\displaystyle {\mathcal {O}}(m)}$

Двумерное разбиение: Каждый процессор получает подматрицу матрицы смежности. Предположим, что процессоры выровнены в прямоугольнике , где и — количество элементов обработки в каждой строке и столбце соответственно. Тогда каждый процессор получает подматрицу матрицы смежности размерности . Это можно визуализировать как шахматный узор в матрице. ^[12] Следовательно, каждый процессорный блок может иметь исходящие ребра только к PE в той же строке и столбце. Это ограничивает количество партнеров по коммуникации для каждого PE до возможных . ${\displaystyle p=p_{r}\times p_{c}}$ ${\displaystyle p_{r}}$ ${\displaystyle p_{c}}$ ${\displaystyle (n/p_{r})\times (n/p_{c})}$ ${\displaystyle p_{r}+p_{c}-1}$ ${\displaystyle p=p_{r}\times p_{c}}$

Сжатые представления

Графы с триллионами ребер встречаются в машинном обучении , анализе социальных сетей и других областях. Сжатые представления графов были разработаны для снижения требований к вводу-выводу и памяти. Применимы общие методы, такие как кодирование Хаффмана , но список смежности или матрица смежности могут быть обработаны определенным образом для повышения эффективности. ^[13]

Обход графа

Поиск в ширину и поиск в глубину

Поиск в ширину (BFS) и поиск в глубину (DFS) — два тесно связанных подхода, которые используются для исследования всех узлов в заданном связанном компоненте . Оба начинаются с произвольного узла, « корня ». ^[14]

Смотрите также

• Обход графа для получения дополнительной информации о стратегиях обхода графа
• Графовая база данных для сохранения графа (структуры данных)
• Переписывание графов для преобразований графов на основе правил (структуры данных графов)
• Программное обеспечение для рисования графиков для программного обеспечения, систем и поставщиков систем для рисования графиков

Ссылки

1. См., например, Goodrich & Tamassia (2015), Раздел 13.1.2: Операции над графами, стр. 360. Более подробный набор операций см. в Mehlhorn, K. ; Näher, S. (1999). "Глава 6: Графы и их структуры данных". LEDA: Платформа для комбинаторных и геометрических вычислений (PDF) . Cambridge University Press. стр. 240–282.
2. Кормен и др. (2001), стр. 528–529; Гудрич и Тамассия (2015), стр. 361–362.
3. Кормен и др. (2001), стр. 529–530; Гудрич и Тамассия (2015), с. 363.
4. Кормен и др. (2001), Упражнение 22.1-7, стр. 531.
5. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л.; Стайн , Клиффорд (2001). «Раздел 22.1: Представления графов». Введение в алгоритмы (Второе изд.). MIT Press и McGraw-Hill. стр. 527–531. ISBN 0-262-03293-7.
6. Гудрич, Майкл Т .; Тамассиа, Роберто (2015). «Раздел 13.1: Терминология и представления графов». Разработка и применение алгоритмов . Wiley. С. 355–364. ISBN 978-1-118-33591-8.
7. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л.; Стайн , Клиффорд (2009). Введение в алгоритмы (3-е изд.). Массачусетский технологический институт. С. 253–280. ISBN  978-0-262-03384-8.
8. Бадер, Дэвид; Мейерхенке, Хеннинг; Сандерс, Питер; Вагнер, Доротея (январь 2013 г.). Разбиение графов и кластеризация графов. Contemporary Mathematics. Том 588. Американское математическое общество. doi :10.1090/conm/588/11709. ISBN 978-0-8218-9038-7.
9. Ламсдейн, Эндрю; Грегор, Дуглас; Хендриксон, Брюс; Берри, Джонатан (март 2007 г.). «Проблемы параллельной обработки графов». Parallel Processing Letters . 17 (1): 5–20. doi :10.1142/s0129626407002843. ISSN  0129-6264.
10. Сандерс, Питер; Мельхорн, Курт; Дицфельбингер, Мартин; Дементьев, Роман (2019). Последовательные и параллельные алгоритмы и структуры данных: базовый набор инструментов. Springer International Publishing. ISBN 978-3-030-25208-3.
11. "Параллельная обработка графов" (PDF) . Архивировано из оригинала (PDF) 2021-08-25 . Получено 2020-03-09 .
12. Buluç, A.; Madduri, Kamesh (2011). "Applications". Параллельный поиск в ширину в системах с распределенной памятью . Международная конференция по высокопроизводительным вычислениям, сетевым технологиям, хранению и анализу 2011 года. CiteSeerX 10.1.1.767.5248 . doi :10.1145/2063384.2063471. ISBN  978-1-4503-0771-0. S2CID  6540738.
13. Беста, Мачей; Хёфлер, Торстен (27 апреля 2019 г.). «Обзор и таксономия сжатия графов без потерь и представления графов с эффективным использованием пространства». arXiv : 1806.01799 [cs.DS].
14. Purti (июль–сентябрь 2018 г.). «Обходы графов и их применение» (PDF) . Международный журнал исследований и аналитических обзоров . 5 (3): 2.

Внешние ссылки

• Boost Graph Library: мощная библиотека графиков C++ на Boost (библиотеки C++)
• Networkx: библиотека графов Python
• GraphMatcher — программа на Java для выравнивания ориентированных/неориентированных графов.
• GraphBLAS Спецификация библиотечного интерфейса для операций с графами, с особым акцентом на разреженные графы.