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

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

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

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

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

Операции [ править ]

Основные операции, обеспечиваемые структурой данных графа 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 | количество ребер. ^{[ необходима цитата ]} В матричных представлениях записи кодируют стоимость следования за ребром. Стоимость отсутствующих ребер предполагается равной ∞.

	Список смежности	Матрица смежности	Матрица заболеваемости
График магазина	${\ 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 |)}$
Смежны ли вершины x и y (при условии, что их позиции хранения известны)?	${\ Displaystyle O (| V |)}$	${\ displaystyle O (1)}$	${\ Displaystyle O (| E |)}$
Замечания	Медленно удаляет вершины и ребра, потому что нужно найти все вершины или ребра	Медленно добавлять или удалять вершины, потому что матрица должна быть изменена / скопирована	Медленное добавление или удаление вершин и ребер, потому что матрица должна быть изменена / скопирована

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

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

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

Общая память [ править ]

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

Распределенная память [ править ]

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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

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