Я ищу параллельный алгоритм, который поможет мне в определении циклов в ориентированном графе.
Я знаю, что последовательный алгоритм использует dfs с раскраской, однако я думаю, что он потерпит неудачу в многопоточной среде. Один пример ориентированного графика для иллюстрации:
A → (B, C), B- > (D), D- > (E), C- > (E), E- > (F)
A
/ \
B C
| |
D |
\ /
E
|
F
(Надеюсь, что вышеизложенное дает понять это. Края на графике находятся сверху до botton)
Для вышеописанного графика во время параллельного выполнения возможно выполнение следующего действия.
(схема раскраски, которую я предположила, белая - невидимая, серая - исполнение dfs не завершено и завершено черно-белое исполнение и посещение)
Dfs (B) по потоку 1, который в конечном итоге окрашивает E как серый и делает dfs (E) (что приводит к F). Прежде чем это будет закончено, поток 2 выполняет dfs (C). Он понимает, что E серое и сообщает цикл, который, очевидно, не тот.
Я проверил, что Tarjan algo можно также использовать для обнаружения циклов, но опять же я не думаю, что его выполнение будет правильным в многопоточной среде.
Может кто-нибудь, пожалуйста, помогите мне в этом?
Спасибо.
Как утверждает Айра, каждый поток использует свой собственный цвет.
Но, если у вас есть фиксированное количество потоков, используйте бит-карту для каждого из цветов. Поскольку процессор, поддерживающий атомный бит и настроенный (т.е. BTST на x86), не требует блокировки событий, поскольку каждый поток будет тестировать и устанавливать другой бит.
Если бит установлен, элемент окрашен в серый цвет.
PS: Если вам нужно больше цветов, вы можете использовать больше бит.
Вы должны легко найти распределенные алгоритмы обнаружения блокировки, которые адресуют проблему обнаружения цикла.
Я понимаю, что распределенная не совсем многопоточная, но вы все равно должны находить там намеки.
Изменить: добавлено ограниченное решение.
Для обнаружения многопоточного цикла лучше использовать вариант алгоритма Кана (для топологической сортировки) вместо DFS. Это использует факты, которые:
1) Если ориентированный граф ацикличен, то он имеет по крайней мере одну вершину без внутренних ребер и по крайней мере одну вершину без внешних ребер;
2) Вершина, не имеющая краев или без ребер, не может участвовать в цикле; так
3) Если вы удаляете вершину без краев или нет ребер, вы остаетесь с меньшим ориентированным графом с теми же циклами, что и оригинал.
Итак, для обнаружения параллельного цикла вы можете:
1) Сначала используйте параллельную BFS для построения структуры данных, которая отслеживает степень и степень каждой вершины.
2) Затем параллельно удаляем вершины с степенью или степенью 0. Обратите внимание, что удаление вершины приведет к уменьшению глубины или внешних степеней смежных узлов.
3) Когда вы не можете удалить вершины, вы останетесь со всеми вершинами, которые задействованы в циклах. Если их нет, то исходный граф был ацикличен.
Как параллельное BFS (шаг 1), так и параллельное удаление вершин (шаг 2) легко выполняются с параллельными рабочими очередями. На шаге 1, когда вы видите вершину в первый раз, добавьте задачу в очередь, обрабатывающую смежные вершины. На шаге 2, когда вы уменьшаете вершину in-degree или out-degree до 0, добавьте задачу, чтобы удалить ее из графика.
Обратите внимание, что этот алгоритм работает так же хорошо, если вы удаляете только узлы с степенью 0 или узлами с не-степенью 0, но возможности для parallelism несколько уменьшены.