Алгоритм обнаружения цикла Роча – Татта

Алгоритм Роча – Татта это распределенный алгоритм в теории графов для обнаружения циклов на крупномасштабных ориентированных графах, основанный на абстракции массовой синхронной передачи сообщений. Этот алгоритм обнаружения циклов путем передачи сообщений подходит для реализации в распределенном графе. процессорных системах, а также подходит для реализации в системах дисковых вычислений, таких как GraphChi, где вычисления в основном основаны на вторичной памяти. Дисковые вычисления необходимы, когда у нас есть один компьютер для обработки крупномасштабных данных. графики, а вычисления превышают объем основной памяти.

Обзор

Алгоритм Роча – Татта — это общий алгоритм обнаружения циклов в ориентированном графе. $G$ путем передачи сообщений между его вершинами на основе абстракции массовой синхронной передачи сообщений. Это вершинно-ориентированный подход, при котором вершины графа работают вместе для обнаружения циклов. Массовая синхронная параллельная модель состоит из последовательности итераций, в каждой из которых вершина может получать сообщения, отправленные другими вершинами на предыдущей итерации, и отправлять сообщения другим вершинам.

В каждом проходе каждая активная вершина $G$ отправляет набор последовательностей вершин своим внешним соседям, как описано ниже. На первом проходе каждая вершина $v$ отправляет сообщение $(v)$ всем своим дальним соседям. В последующих итерациях каждая активная вершина $v$ добавляет $v$ к каждой последовательности, полученной на предыдущей итерации. Затем он отправляет все обновленные последовательности своим внешним соседям. Если $v$ не получил ни одного сообщения на предыдущей итерации, то $v$ деактивируется сам. Алгоритм завершается, когда все вершины деактивируются.

Для последовательности $(v_{1},v_{2},\ldots ,v_{k})$ полученный вершиной $v$, добавленная последовательность не пересылается в двух случаях: (i) если $v=v_{1}$, затем $v$ обнаружил цикл, о чем сообщается; (ii) если $v=v_{i}$ для некоторых $i\in {2,3,\ldots ,k}$, затем $v$ обнаружил последовательность, содержащую цикл $(v=v_{i},v_{i+1},\ldots ,v_{k},v_{k+1}=v)$; в этом случае последовательность отбрасывается, поскольку цикл должен был быть обнаружен на более ранней итерации; если быть точным, этот цикл должно быть обнаружено в итерации $k-i+1$. Каждый цикл $(v_{1},v_{2},\ldots ,v_{k},v_{k+1}=v_{1})$ обнаруживается всеми $v_{i},i=1$ к $k$ в той же итерации; об этом сообщает вершина $\min\{v_{1},\ldots ,v_{k}\}$.

На рисунке ниже представлен пример выполнения алгоритма. В итерации $i=3$, все три вершины обнаруживают цикл $(2,3,4)$. Алгоритм гарантирует, что о цикле сообщается только один раз, выдавая обнаруженный цикл только из вершины с наименьшим значением идентификатора в упорядоченной последовательности, которой в примере является вершина 2.

Общее количество итераций алгоритма равно числу вершин в самой длинной путь в графе, плюс еще несколько шагов по деактивации последних вершин. В ходе анализа общее количество итераций, мы игнорируем несколько дополнительных итераций, необходимых для деактивации финальной вершин и обнаружения окончания вычисления, поскольку $O(1)$ итерации. На практике фактическое число количество этих последних нескольких итераций зависит от платформы, используемой для реализации алгоритма.

Экспериментальная производительность

Симуляторы показывают, что алгоритм Роча-Татта имеет меньшие накладные расходы на связь, чем распределенная версия поиска в глубину , как в отношении количества сообщений, так и в отношении общего количества отправленных битов. В частности, распределенная версия DFS может потребовать обмена сообщениями на порядок больше, чем алгоритм Роча-Татта.