Обход графа внешней памяти

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

Фон

Обход графа — это подпрограмма в большинстве графовых алгоритмов. Цель алгоритма обхода графа — посетить (и/или обработать) каждый узел графа. Алгоритмы обхода графа, такие как поиск в ширину и поиск в глубину , анализируются с использованием модели фон Неймана , которая предполагает равномерную стоимость доступа к памяти. Эта точка зрения игнорирует тот факт, что в огромных экземплярах часть графа находится на диске, а не во внутренней памяти. Поскольку доступ к диску происходит намного медленнее, чем доступ к внутренней памяти, существует необходимость эффективного обхода внешней памяти .

Модель внешней памяти

Для алгоритмов внешней памяти модель внешней памяти Аггарвала и Виттера используется для анализа. Машина задается тремя параметрами M , B и D. : M — размер внутренней памяти, B — размер блока диска, а D — количество параллельных дисков. Мерой производительности алгоритма внешней памяти является количество операций ввода-вывода, которые он выполняет.

Поиск в ширину внешней памяти

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

Мунагала и Ранаде

Визуализация вычисления L(t) в алгоритме поиска Мунагалы-Ранаде в ширину .

Для неориентированного графа $G$, Мунагала и Ранаде предложил следующий алгоритм внешней памяти:

Позволять $L(t)$ обозначим узлы на уровне поиска в ширину t и пусть $A(t):=N(L(t-1))$ быть мультимножеством соседей уровня t-1. Для каждого т, $L(t)$ может быть построен из $A(t)$ путем преобразования его в набор и исключения из него ранее посещенных узлов.

1. Создавать $A(t)$ путем доступа к списку смежности каждой вершины в $L(t-1)$. Этот шаг требует $O(|L(t-1)|+|A(t)|/(D\cdot B))$ Ввод/вывод.
2. Следующий $A'(t)$ создан из $A(t)$ путем удаления дубликатов. Этого можно добиться путем сортировки $A(t)$, за которым следует этап сканирования и уплотнения, требующий $O(\operatorname {sort} (|A|))$ Ввод/вывод.
3. $L(t):=A'(t)\backslash \{L(t-1)\cup L(t-2)\}$ рассчитывается путем параллельного сканирования $L(t-1)$ и $L(t-2)$ и требует $O((|A(t)|+|L(t-1)|+|L(t-2)|)/(D\cdot B))$ Ввод/вывод.

Общее количество операций ввода-вывода этого алгоритма следует с учетом того, что $\sum _{t}|A(t)|=O(m)$ и $\sum _{t}|L(t)|=O(n)$ и есть $O(n+\operatorname {sort} (n+m))$.

Визуализация трех описанных шагов, необходимых для вычисления L ( t ), изображена на рисунке справа.

Мельхорн и Мейер

Мельхорн и Мейер предложил алгоритм, основанный на алгоритме Мунагалы и Ранаде (MR) и улучшающий их результат.

Он состоит из двух этапов. На первом этапе граф предварительно обрабатывается, на втором этапе выполняется поиск в ширину с использованием информации, собранной на первом этапе.

На этапе предварительной обработки граф разбивается на несвязанные подграфы. $S_{i},\,0\leq i\leq K$ с небольшим диаметром. Далее он соответствующим образом разделяет списки смежности, создавая внешний файл $F=F_{0}F_{1}\dots F_{K-1}$, где $F_{i}$ содержит список смежности для всех узлов в $S_{i}$.

Фаза поиска в ширину аналогична алгоритму MR. алгоритм поддерживает отсортированный внешний файл H. Кроме того , Этот файл инициализируется с помощью $F_{0}$. Кроме того, узлы любого созданного уровня поиска в ширину содержат идентификаторы файлов. $F_{i}$ соответствующих подграфов $S_{i}$. Вместо использования произвольного доступа для создания $L(t)$ файл H. используется

1. Выполнить параллельное сканирование отсортированного списка $L(t-1)$ и Х. ​Извлеките списки смежности для узлов $v\in L(t-1)$, это можно найти в H .
2. списки смежности для остальных узлов, которые не удалось найти в H. Необходимо получить Сканирование закончено $L(t-1)$ возвращает идентификаторы разделов. После сортировки и удаления дубликатов соответствующие файлы $F_{i}$ могут быть объединены во временный файл F' .
3. Недостающие списки смежности можно извлечь из F' с помощью сканирования. Затем оставшиеся списки смежности объединяются в H за один проход.
4. $A(t)$ создается путем простого сканирования. Информация о разделе прикреплена к каждому узлу в $A(t)$.
5. Алгоритм аналогичен алгоритму MR.

Ребра могут сканироваться чаще в H , но количество неструктурированных операций ввода-вывода для получения списков смежности сокращается.

Общее количество операций ввода-вывода для этого алгоритма равно $O\left({\sqrt {\frac {n\cdot (n+m)}{D\cdot B}}}+\operatorname {sort} (n+m)\right)$

Поиск в глубину внешней памяти

Алгоритм поиска в глубину исследует граф вдоль каждой ветви как можно глубже перед обратным отслеживанием.

Для ориентированных графов Бухсбаума, Гольдвассера, Венкатасубраманиана и Вестбрука. предложил алгоритм с $O((V+E/B)\log _{2}(V/B)+\operatorname {sort} (E))$ Ввод/вывод.

Этот алгоритм основан на структуре данных, называемой деревом буферизованного репозитория (BRT). Он хранит множество элементов из упорядоченной вселенной. Элементы идентифицируются по ключу. БТР предлагает две операции:

• insert(T, x), который добавляет элемент x к T и требует $O(1/B\log _{2}(N/B))$ амортизированные входы/выходы. N — количество предметов, добавленных в БТР.
• extract(T, k), который сообщает и удаляет из T все элементы с ключом k . Это требует $O(\log _{2}(N/B)+S/B)$ Ввод-вывод, где S — размер набора, возвращаемого экстрактом .

Алгоритм имитирует внутренний алгоритм поиска в глубину. Стек S узлов удерживается. Во время итерации узла v поверх S поместите непосещенного соседа на S и выполните итерацию. Если непосещенных соседей нет, pop v .

Трудность состоит в том, чтобы определить, является ли узел непосещенным, не делая $\Omega (1)$ Число операций ввода-вывода на каждое ребро. Для этого для узла v входящие ребра ⁠ $(x,v)$⁠ помещаются в BRT D при v первом обнаружении . Далее, исходящие ребра ( v , x ) помещаются в приоритетную очередь P ( v ), определяемую рангом в списке смежности.

Для вершины u вершине S все ребра ( u , x ) извлекаются из D. на Такие ребра существуют только в том случае, если x был обнаружен с момента последнего нахождения u на вершине S (или с момента запуска алгоритма, если u впервые оказался на вершине S ). Для каждого ребра ( u , x ) операция удаления ( x ) выполняется над P ( u ). Наконец, операция удаления мин на ⁠ $P(u)$⁠ дает следующий непосещенный узел. Если P ( u ) пусто, u извлекается из S .

Псевдокод этого алгоритма приведен ниже.

1  procedure BGVW-depth-first-search(G, v):
2      let S be a stack, P[] a priority queue for each node and D a BRT
3      S.push(v)
4      while S is not empty:
5          v := S.top()
6          if v is not marked:
7              mark(v)
8          extract all edges (v, x) from D, ∀x: P[v].delete(x)
9          if (u := P[v].delete-min()) is not null:
10             S.push(u)
11         else:
12             S.pop()

13  procedure mark(v)
14      put all edges (x, v) into D
15      ∀ (v, x): put x into P[v]