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

редактировать

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

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

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

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

Содержание

1 Операции
2 Представления
3 Представления параллельных графиков
- 3.1 Общая память
- 3.2 Распределенная память
4 См. Также
5 Ссылки
6 Внешние ссылки

Операции

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

смежный(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): добавляет ребро из вершины x в вершину y, если ее нет;
remove_edge(G, x, y): удаляет ребро из вершины x в вершину y, если она есть;
get_vertex_value(G, x): возвращает значение, связанное с вершиной x;
set_vertex_value(G, x, v): устанавливает значение, связанное с вершиной x, равным v.

Структуры th при значениях, связанных с краями, обычно также предоставляют:

get_edge_value(G, x, y): возвращает значение, связанное с краем (x, y);
set_edge_value(G, x, y, v): устанавливает значение, связанное с ребром (x, y), равным v.

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

На практике используются разные структуры данных для представления графов:

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

В следующей таблице даны временная сложность затраты на выполнение различных операций с графами для каждого из этих представлений с | V | количество вершин и | E | количество ребер. В матричных представлениях записи кодируют стоимость следования за ребром. Стоимость отсутствующих ребер предполагается равной ∞.

	Список смежности	Матрица смежности	Матрица инцидентности
График хранения	$O (\| V \| + \| E \|) {\ displaystyle O (\| V \| + \| E \|)}$ $O (\| V \| + \| E \|)$	$О (\| V \| 2) {\ Displaystyle O (\| V \| ^ {2})}$ $O (\| V \| ^ {2})$	$O (\| V \| ⋅ \| E \|) {\ Displaystyle O (\| V \| \ cdot \| E \|)}$ $O (\| V \| \ cdot \| E \|)$
Добавить вершину	$O (1) {\ displaystyle O (1)}$ $O (1)$	$O (\| V \| 2) {\ displaystyle O (\| V \| ^ {2})}$ $O (\| V \| ^ {2})$	$O (\| V \| ⋅ \| E \|) {\ displaystyle O (\| V \| \ cdot \| E \|)}$ $O (\| V \| \ cdot \| E \|)$
Добавить край	$O (1) {\ displaystyle O (1)}$ $O (1)$	$O (1) {\ displaystyle O (1)}$ $O (1)$	$O (\| V \| ⋅ \| E \|) {\ displaystyle O (\| V \| \ cdot \| E \|)}$ $O (\| V \| \ cdot \| E \|)$
Удалить вершину	$O ( \| E \|) {\ displaystyle O (\| E \|)}$ $O (\| E \|)$	$O (\| V \| 2) {\ displaystyle O (\| V \| ^ {2})}$ $O (\| V \| ^ {2})$	$O (\| V \| ⋅ \| E \|) {\ displaystyle O (\| V \| \ cdot \| E \|)}$ $O (\| V \| \ cdot \| E \|)$
Удалить край	$O (\| V \|) {\ displaystyle O (\| V \|)}$ $O (\| V \|)$	$O (1) {\ displaystyle O (1)}$ $O (1)$	$O (\| V \| ⋅ \| E \|) {\ displaystyle O (\| V \| \ cdot \| E \|)}$ $O (\| V \| \ cdot \| E \|)$
Смежны ли вершины x и y (при условии, что их позиции хранения известны)?	$O (\| V \|) {\ displaystyle O (\| V \|)}$ $O (\| V \|)$	$O (1) {\ displaystyle O (1)}$ $O (1)$	$O (\| E \|) {\ displaystyle O (\| E \|)}$ $O (\| E \|)$
Замечания	Медленно удаляет вершины и ребра, потому что необходимо найти все вершины или ребра	Медленно добавлять или удалять вершины, потому что матрица должна быть изменена / скопирована	Медленно добавлять или удалять вершины и ребра, потому что размер матрицы должен быть изменен / скопирован.

Списки смежности обычно предпочтительны, поскольку они эффективно представляют разреженные графы. Матрица смежности предпочтительна, если граф плотный, то есть количество ребер | E | близко к числу вершин в квадрате, | V |, или если нужно иметь возможность быстро найти, есть ли ребро, соединяющее две вершины.

Представления параллельных графов

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

Общая память

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

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

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

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

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

2D-разбиение: каждый процессор получает подматрицу матрицы смежности. Предположим, что процессоры выровнены по прямоугольнику $p = pr × pc {\ displaystyle p = p_ {r} \ times p_ {c}}$ ${\ displaystyle p = p_ {r} \ times p_ {c}}$ , где $pr {\ displaystyle p_ {r }}$ ${\ displaystyle p_ {r}}$ и $pc {\ displaystyle p_ {c}}$ ${\ displaystyle p_ {c}}$ - количество обрабатываемых элементов в каждой строке и столбце соответственно. Затем каждый процессор получает подматрицу матрицы смежности размерности $(n / pr) × (n / pc) {\ displaystyle (n / p_ {r}) \ times (n / p_ { c})}$ ${\ displaystyle (n / p_ {r}) \ times (n / p_ {c})}$ . Это можно представить в виде шаблона шахматной доски в матрице. Следовательно, каждый блок обработки может иметь выходящие ребра к PE только в одной строке и столбце. Это ограничивает количество партнеров по обмену данными для каждого PE до $pr + pc - 1 {\ displaystyle p_ {r} + p_ {c} -1}$ ${\ displaystyle p_ {r} + p_ {c} -1}$ из $p = pr × pc. {\ displaystyle p = p_ {r} \ times p_ {c}}$ ${\ displaystyle p = p_ {r} \ times p_ {c}}$ возможные.

См. Также

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

Ссылки

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

На Викискладе есть носители, связанные с Graph (абстрактный тип данных).

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