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

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

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

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

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

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

Операции

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

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

• смежный( G , x , y ) : проверяет, есть ли ребро от вершины x до вершины y ;
• соседи( 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]

Двумерная матрица, в которой строки представляют вершины, а столбцы — ребра. Записи указывают отношение инцидентности между вершиной в строке и ребром в столбце.

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

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

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

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

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

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

Общая память

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

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

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

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

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

2D-разделение: каждый процессор получает подматрицу матрицы смежности. Предположим, что процессоры выровнены в прямоугольнике , где и — количество обрабатывающих элементов в каждой строке и столбце соответственно. Затем каждый процессор получает подматрицу матрицы смежности размерности . Это можно представить в виде шахматной доски в матрице. ^[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: Операции над графиками, стр. 13.1.2. 360. Более подробный набор операций см. Mehlhorn, K .; Нэхер, С. (1999). «Глава 6: Графы и их структуры данных». LEDA: Платформа для комбинаторных и геометрических вычислений (PDF) . Издательство Кембриджского университета. стр. 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: Терминология и представления графов». Разработка алгоритмов и их применение . Уайли. стр. 355–364. ISBN 978-1-118-33591-8.
7. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009). Введение в алгоритмы (3-е изд.). Массачусетский Институт Технологий. стр. 253–280. ISBN  978-0-262-03384-8.
8. Бадер, Дэвид; Мейерхенке, Хеннинг; Сандерс, Питер; Вагнер, Доротея (январь 2013 г.). Разбиение графов и кластеризация графов. Современная математика. Том. 588. Американское математическое общество. дои : 10.1090/conm/588/11709. ISBN 978-0-8218-9038-7.
9. Ламсдейн, Эндрю; Грегор, Дуглас; Хендриксон, Брюс; Берри, Джонатан (март 2007 г.). «Проблемы параллельной обработки графов». Параллельная обработка писем . 17 (1): 5–20. дои : 10.1142/s0129626407002843. ISSN  0129-6264.
10. Сандерс, Питер; Мельхорн, Курт; Дитцфельбингер, Мартин; Дементьев, Роман (2019). Последовательные и параллельные алгоритмы и структуры данных: базовый набор инструментов. Международное издательство Спрингер. ISBN 978-3-030-25208-3.
11. «Параллельная обработка графиков» (PDF) .
12. Булуч, А.; Маддури, Камеш (2011). "Приложения". Параллельный поиск в ширину в системах с распределенной памятью . 2011 Международная конференция по высокопроизводительным вычислениям, сетям, хранению и анализу. CiteSeerX 10.1.1.767.5248 . дои : 10.1145/2063384.2063471. ISBN  978-1-4503-0771-0. S2CID  6540738.
13. Беста, Мацей; Хефлер, Торстен (27 апреля 2019 г.). «Обзор и таксономия сжатия графов без потерь и компактных представлений графов». arXiv : 1806.01799 [cs.DS].
14. Пурти (июль – сентябрь 2018 г.). «Обход графа и его приложения» (PDF) . Международный журнал исследований и аналитических обзоров . 5 (3): 2.

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

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