Алгоритм DCSC поиска компонент сильной связности

Алгоритм DCSC поиска компонент сильной связности
Последовательный алгоритм
Последовательная сложность	[math]O(|V| \ln(|V|))[/math]
Объём входных данных	[math]O(|V| + |E|)[/math]
Объём выходных данных	[math]O(|V|)[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]C * O(ln(u))[/math]
Ширина ярусно-параллельной формы	[math]O(|E|)[/math]

Основные авторы описания: И.В.Афанасьев

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм DCSC (англ. Divide and Conquer Strong Components – компоненты сильной связности по принципу «Разделяй и властвуй») находит компоненты сильной связности ориентированного графа с ожидаемой работой [math]O(|V| \ln |V|)[/math] (при условии ограниченной константой степени вершин).

Также алгоритм носит другое название - Forward-Backward (сокр. FB-algorithm), в основном в литературе, связанной с его GPU-реализациями.

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

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

Для увеличения эффективности работы алгоритма на графах с большим числом тривиальных сильно-связанных компонент (размера 1 или 2), предложена модификация алгоритма: перед началом работы классического алгоритма производится шаг Trim, описанный в следующих разделах, позволяющий выделять все тривиальные сильно-связанные компоненты. В результате, к примеру в RMAT графах, после шага Trim в графе остается всего лишь несколько компонент сильной связанности большого размера, на которых алгоритм будет иметь небольшую алгоритмическую сложность.

1.2 Математическое описание алгоритма

Пусть [math]v[/math] – некоторая вершина графа. Определим следующие множества вершин:

⎯ [math]Fwd(v)[/math] – вершины, достижимые из [math]v[/math] .

⎯ [math]Pred(v)[/math] – вершины, из которых достижима [math]v[/math] (эквивалентно – вершины, достижимые из [math]v[/math] в графе, полученном из [math]G[/math] обращением всех рёбер).

Используя эти множества, разобьём все вершины графа на четыре области:

⎯ [math]V_1 = Fwd(v) \cap Pred(v) [/math]

⎯ [math]V_2 = Fwd(v) \setminus Pred(v) [/math]

⎯ [math]V_3 = Pred(v) \setminus Fwd(v)[/math]

⎯ [math]V_4 = V \setminus Pred(v) \setminus Fwd(v)[/math]

Тогда можно утверждать следующее:

1. Область [math]V_1[/math] является компонентой сильной связности.

2. Любая другая компонента сильной связности полностью содержится в одной из областей [math]V_2[/math], [math]V_3[/math], или [math]V_4[/math].

1.3 Вычислительное ядро алгоритма

Основными вычислительными операциями алгоритма являются поиск вершин, достижимых из выбранной вершины [math]v[/math], а также поиск вершин, из которых достижима выбранная вершина [math]v[/math]. Обе данные операции могут быть реализованы через поиски в ширину, устроенные следующим образом:

1. Вершина [math]v_0[/math] помещается в начало очереди и помечается как посещенная.

2. Верхняя вершина [math]v[/math] извлекается из очереди. Для всех ребер [math](v, u)[/math], исходящих из вершины [math]v[/math], проверяется, является ли посещенной вершина [math]u[/math]. В случае, если является, вершина [math]u[/math] помещается в начало очереди.

3. Происходит переход на шаг 2 до тех пор, пока в очереди есть вершины.

1.4 Макроструктура алгоритма

Алгоритм DCSC состоит в следующем:

1. Поместить в очередь множество [math]V[/math].

2. Параллельно обрабатывать очередь. Для каждого элемента очереди [math]V[/math]:

а) Выбрать произвольную ведущую вершину [math]v \in V[/math].

б) Вычислить множества [math]Fwd(v)[/math], [math]Pred(v)[/math] (эти два вычисления можно производить параллельно, кроме того, как указано выше, сами эти вычисления хорошо параллелизуются).

в) Добавить множество [math] V_1[/math] в список компонент сильной связности.

г) Добавить множества [math] V_2[/math], [math]V_3[/math] и [math]V_4[/math] в очередь.

3. Алгоритм завершает работу, когда очередь пуста и не осталось активных процессов-обработчиков.

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

Важной модификацией алгоритма является шаг Trim, производимый перед основными вычислениями алгоритма DCSC, который может быть описан следующим образом:

1. Пометить все вершины из [math]v \in V[/math] активными.

2. Для каждой вершины [math]v[/math]вычислить число входящих ([math]in(v)[/math]) и исходящих ([math]out(v)[/math]) дуг [math](v, u) \in E[/math], таких, что вершина [math]u[/math] - активная.

3. Все вершины [math]v \in V[/math] , для которых [math]in(v)[/math] или [math]out(v)[/math] равно нулю, пометить как неактивные.

4. Переходить на шаг 2, до тех пор, пока число активных вершин не перестанет изменяться.

Кроме того, в зависимости от схемы хранения графа может потребоваться предварительное нахождение транспонированного к нему для более эффективной реализации как шага trim, так и поиска вершин, из которых достижима заданная вершина [math]v[/math] в вычислительном ядре алгоритма.

1.5 Схема реализации последовательного алгоритма

Последовательный алгоритм реализуется следующим псевдокодом:

Входные данные:
  граф с вершинами V, рёбрами E;
Выходные данные: номера компонент сильной связанности c(v) для каждой вершины v ∈ V.

compute_scc_with_trim(G)
{
	G’ = transpose(G)
	G = trim(G)
	compute_scc()
}

compute_scc(V, G, G’)
{
	p = pivot(V)

	fwd = bfs(G, p);
	pred = bfs(G’, p);

	compute_scc(fwd / pred, G, G’)
	compute_scc(pred / fwd, G, G’)
	compute_scc(V / pred / fwd, G, G’)
}

pivot(V)
{
	return random v in V
}

trim(G)
{
	for each v in V(G)
		active[v] = true

	changes = false
	do
	{
		for each v in V
			in_deg(v) = compute_in_degree(v)
			out_deg(v) = compute_out_degree(v)
		
		for each v in V
			if (in_deg[v] == 0 || out_deg[v] == 0)
				active[v] = false
				changes = true
	} while (!changes)
	return active
}

bfs здесь стандартный поиск в ширину, описанный в соответствующем разделе, результатом которого являются все узлы, достижимые из вершины [math] p [/math] в графе [math] G [/math]

1.6 Последовательная сложность алгоритма

Ожидаемая последовательная сложность алгоритма составляет [math]O(|V| \ln(|V|))[/math] при условии, что степень вершин ограничена сверху константой.

1.7 Информационный граф

На рисунке 1 представлен информационный граф алгоритма DCSC, демонстрирующий связь между его основными частями.

Рисунок 1. Информационный граф алгоритма DCSC(Forward-Backward-Trim).

Итак, алгоритм состоит из первоначального шага Trim, выбора pivot-вершины [1], поиска в ширину в прямом и транспонированном графах (forward и backward BFS), обработки результатов поиска [2], проверки необходимости проведения последующих рекурсивных шагов [3], а также рекурсивных вызовов FB-шага. Далее будут приведены более подробные информационные графы для каждой из частей, а также дана подробная расшифровка соответствующих операций, а в следующем разделе мы оценим ресурс параллелизма для каждой части алгоритма.

На рисунке 2 представлен информационный граф шага Trim.

Рисунок 2. Информационный граф шага Trim алгоритма DCSC.

[1] - выделение памяти под массивы данных числа входящих и исходящих дуг, а также активных вершин

[2] - инциализация переменной наличия изменений

[3] - инициализация массива сильно связанных компонент, а также массива активных вершин.

[4] - установка переменной наличия изменений в позицию "нет изменений"

[5] - обнуление массивов числа входящих и исходящих дуг

[6] - проверка, активны ли вершины на концах каждого ребра, увеличение числа входящих/исходящих дуг для соответствующих вершин, изменение переменной наличия изменений

[7] - проверка активности всех вершин графа

[8] - присваивание номеров сильно связанных компонентам с нулевой степенью входящих или исходящих вершин

[9] - проверка, происходили ли изменения на шаге 6, переход к следующей итерации

Информационный граф этапа поиска в ширину (Forward и Backward BFS) приведен в соответствующем разделе (Поиск_в_ширину_(BFS)).

1.8 Ресурс параллелизма алгоритма

Алгоритм изначально предназначен для параллельной реализации и имеет несколько уровней параллелизма.

На верхнем уровне алгоритм DCSC может параллельно выполнять FB-шаги, продемонстрированные на рисунке 1. Таким образом, на каждом рекурсивном шаге алгоритма могут рекурсивно порождаться до 3 новых параллельных процессов, общее число которых равно числу сильно связанных компонент графа. Кроме того, поиски в ширину в исходном и транспонированном графах независимы и также могут выполняться параллельно друг с другом. Таким образом, на верхнем уровне может выполняться до [math] 2*u/log|u|[/math] параллельных потоков, где [math] u [/math] - это число сильно связанных компонент графа. Важно заметить, что вычисления FB-шагов одного уровня (а также всех последующих рекурсивных) абсолютно независимы по данным, так как производятся в непересекающихся множествах вершин графа, поэтому могут производиться в том числе и на различных узлах. Кроме того, составные шаги алгоритма (поиск в ширину и шаг Trim) также имеют значительный потенциал параллелизма, описанный далее.

Этап Trim алгоритма, информационный граф которого приведен на рисунке 2, обладает значительным ресурсом параллелизма: единственной последовательной частью является инициализация массивов и переменных (1)(2), а также проверка условия выхода из цикла (9). Операции (3),(5),(7) и (8) абсолютно независимы и могут производиться параллельно, их число составляет [math]O(|V|)[/math]. Проверки и обновления данных в операции (6) также могут производиться параллельно, однако обновления данных должны производиться атомарно. Число операций (6) равно [math]O(E)[/math]. Таким образом, почти все операции шага Trim могут выполняться параллельно, при этом число параллельно выполняемых операций составляет [math]|V|[/math] или [math]|E|[/math]. Учитывая, что величины [math]|V|[/math] и [math]|E|[/math] для графов большого размера крайне велики, потенциал параллелизма данной части алгоритма очень значителен и достаточен для полной загрузки современных вычислительных узлов/сопроцессоров. Кроме того, операции (3),(5),(7),(8) могут быть успешно векторизованы.

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

В случае линейного подхода на каждом шаге алгоритма поиска в ширину может выполняться [math]O(n)[/math] параллельных операций, где [math]n[/math] - это число вершин, добавленных для просмотра на предыдущем шаге. Перед началом работы алгоритма для просмотра добавляется вершина-источник, на первом шаге - все еще не посещенные смежные с ней, на втором - все еще не посещенные смежные с вершинами на первом шаге, и т.д. Максимальное (или даже среднее) число вершин на каждом шаге оценить проблематично, так как число шагов алгоритма, число достижимых вершин, а также структура связей между ними определены лишь структурой конкретного входного графа. В случае, если все вершины достижимы, а число шагов поиска в ширину составляет [math] r [/math], то среднее число параллельно обрабатываемых вершин на каждом шаге составляет [math] O(|V|)/r [/math]. Важно заметить, что наибольший уровень параллелизма достигается на средних шагах алгоритма, в то время как число вершин для обработки на начальных и конечных шагах может быть небольшим.

В случае квадратической параллелизации алгоритм поиска в ширину на каждом шаге обходит все ребра графа, таким образом выполняя [math]O(|E|)[/math] параллельных операций, что совпадает с аналогичной оценкой для шага trim. Кроме того, поиск в ширину при реализации с использованием формата списка ребер графа может быть векторизован.

Таким образом, на начальном этапе алгоритма может выполняться [math]O(|V|)[/math] или [math]O(|E|)[/math] параллельных операций. Далее следует [math]O(log(u))[/math] шагов, в каждом из которых в среднем присутствует [math]2*u/O(log(u))[/math] поисков в ширину, которые так же обладают внутренним ресурсом параллелизма: каждый поиск в ширину имеет [math]O(|E|)[/math] параллельных операций на каждом шаге при квадратическом подходе к параллелизации.

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

1.9 Входные и выходные данные алгоритма

Входные данные: граф [math]G(V, E)[/math], [math]|V|[/math] вершин [math]v_i[/math] и [math]|E|[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math].

Объём входных данных: [math]O(|V| + |E|)[/math].

Выходные данные: для каждой вершины [math]v[/math] исходного графа – номер компоненты сильной связанности, в которую входит данная вершина [math] c(v) [/math], вершины, принадлежащие одной компоненте сильно связанности имеют одинаковые номера

Объём выходных данных: [math]O(|V|)[/math].

1.10 Свойства алгоритма

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