График (абстрактный тип данных) - Graph (abstract data type)

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

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

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

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

Операции

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

• соседний(грамм, Икс, у): проверяет, есть ли ребро из вершины Икс к вершине у;
• соседи(грамм, Икс): перечисляет все вершины у такое, что есть ребро из вершины Икс к вершине у;
• add_vertex(грамм, Икс): добавляет вершину Икс, если его там нет;
• remove_vertex(грамм, Икс): удаляет вершину Икс, если он есть;
• add_edge(грамм, Икс, у): добавляет ребро из вершины Икс к вершине у, если его там нет;
• remove_edge(грамм, Икс, у): удаляет ребро из вершины Икс к вершине у, если он есть;
• get_vertex_value(грамм, Икс): возвращает значение, связанное с вершиной Икс;
• set_vertex_value(грамм, Икс, v): устанавливает значение, связанное с вершиной Икс к v.

Структуры, которые связывают значения с краями, обычно также обеспечивают:^[1]

• get_edge_value(грамм, Икс, у): возвращает значение, связанное с ребром (Икс, у);
• set_edge_value(грамм, Икс, у, v): устанавливает значение, связанное с ребром (Икс, у) к v.

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

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

Список смежности^[2]

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

Матрица смежности^[3]

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

Матрица заболеваемости^[4]

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

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

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

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

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

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

Общая память

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

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

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

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

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

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

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

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

Рекомендации

внешняя ссылка

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