Многопоточный алгоритм для определения цикла в ориентированном графе

Я ищу параллельный алгоритм, который поможет мне в определении циклов в ориентированном графе.

Я знаю, что последовательный алгоритм использует dfs с раскраской, однако я думаю, что он потерпит неудачу в многопоточной среде. Один пример ориентированного графика для иллюстрации:

A → (B, C), B- > (D), D- > (E), C- > (E), E- > (F)

(Надеюсь, что вышеизложенное дает понять это. Края на графике находятся сверху до botton)

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

(схема раскраски, которую я предположила, белая - невидимая, серая - исполнение dfs не завершено и завершено черно-белое исполнение и посещение)

Dfs (B) по потоку 1, который в конечном итоге окрашивает E как серый и делает dfs (E) (что приводит к F). Прежде чем это будет закончено, поток 2 выполняет dfs (C). Он понимает, что E серое и сообщает цикл, который, очевидно, не тот.

Я проверил, что Tarjan algo можно также использовать для обнаружения циклов, но опять же я не думаю, что его выполнение будет правильным в многопоточной среде.

Может кто-нибудь, пожалуйста, помогите мне в этом?

Спасибо.

Ответ 1

Как утверждает Айра, каждый поток использует свой собственный цвет.

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

Если бит установлен, элемент окрашен в серый цвет.

PS: Если вам нужно больше цветов, вы можете использовать больше бит.

Ответ 2

Вы должны легко найти распределенные алгоритмы обнаружения блокировки, которые адресуют проблему обнаружения цикла.

Я понимаю, что распределенная не совсем многопоточная, но вы все равно должны находить там намеки.

Изменить: добавлено ограниченное решение.

Ответ 3

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

1) Если ориентированный граф ацикличен, то он имеет по крайней мере одну вершину без внутренних ребер и по крайней мере одну вершину без внешних ребер;

2) Вершина, не имеющая краев или без ребер, не может участвовать в цикле; так

3) Если вы удаляете вершину без краев или нет ребер, вы остаетесь с меньшим ориентированным графом с теми же циклами, что и оригинал.

Итак, для обнаружения параллельного цикла вы можете:

1) Сначала используйте параллельную BFS для построения структуры данных, которая отслеживает степень и степень каждой вершины.

2) Затем параллельно удаляем вершины с степенью или степенью 0. Обратите внимание, что удаление вершины приведет к уменьшению глубины или внешних степеней смежных узлов.

3) Когда вы не можете удалить вершины, вы останетесь со всеми вершинами, которые задействованы в циклах. Если их нет, то исходный граф был ацикличен.

Как параллельное BFS (шаг 1), так и параллельное удаление вершин (шаг 2) легко выполняются с параллельными рабочими очередями. На шаге 1, когда вы видите вершину в первый раз, добавьте задачу в очередь, обрабатывающую смежные вершины. На шаге 2, когда вы уменьшаете вершину in-degree или out-degree до 0, добавьте задачу, чтобы удалить ее из графика.

Обратите внимание, что этот алгоритм работает так же хорошо, если вы удаляете только узлы с степенью 0 или узлами с не-степенью 0, но возможности для parallelism несколько уменьшены.