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

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

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

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

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

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

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

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

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

Обозначения операций на информационном графе: [1] - инициализация шага trim, [2][3] - подсчет входящих и исходящих степеней вершин, [4] - удаление вершин, относящихся к связанным компонентам единичного размера, [5] - проверка необходимости еще одного шага trim, [next trim steps] - аналогичные шаги trim, если они необходимы. [6] - выбор вершины-pivot, [7] - инициализация данных для поиска в ширину, [8][9][10] выполнение поиска в ширину в исходного графе, [8`] [9`] [10`] - выполнение поиска в ширину в транспонированном графе, [11] - обновление данных о сильно связанных компонентах, [12] - сохранение итоговых результатов.

Верхний уровень параллелизма соответсвует параллельному выполнению операций recursive FB step. Нижний уровень параллелизма соответствует параллелизму между операциями под номерами [1]-[4], [7]-[12], однако характер параллелизма зависит от конкретной реализации поиска в ширину и шага trim.

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

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

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

Кроме того, поиск данных подмножеств может так же производиться параллельно, основываясь на параллельных поисках в ширину.

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

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

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

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

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

2 Программная реализация алгоритма

2.7 Существующие реализации алгоритма

• C++, MPI: Parallel Boost Graph Library (функция strong_components), распределённый алгоритм DCSC сочетается с локальным поиском компонент сильной связности алгоритмом Тарьяна.