Как обрабатывать узлы сильно связанных компонент в ориентированном графе?

Question

Я новичок в области программирования алгоритмов графа. Я борюсь с интересной проблемой в отношении сильно связанных компонентов, и любая помощь в этом отношении высоко ценится.

В моем приложении целью является выполнение задач по нескольким потокам, насколько это возможно. Эти задачи обозначаются как узлы в ориентированном графе, а задачи могут иметь циклические зависимости. Циклические зависимости разбиваются путем нахождения сильно связанных компонентов, а затем принудительного применения предопределенного правила для удаления ребра. Таким образом, все задачи в сильно подключенном компоненте будут выполняться последовательно.

Теперь рассмотрим пример, когда задачи 1,2, ... 8 имеют следующий шаблон зависимости. {1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4, 4 -> 5, 5 -> 6, 6 -> 4, 7 -> 8}. Используя сильно связанные компоненты и предопределенное правило для разрыва циклических зависимостей, мы получаем три набора узлов, т.е. A = {1 -> 2 -> 3}, B = {4 -> 5 -> 6} и C = {7 - > 8}, но поскольку A и B связаны ребрами, они не могут выполняться параллельно.

Я хотел бы знать, есть ли какой-либо алгоритм или набор алгоритмов, которые я могу использовать для получения наборов узлов, чтобы я мог поместить A и B в последовательное выполнение, тогда как C может выполняться параллельно с A или B. По моему пониманию топографическая сортировка может быть полезна, но она используется только для ациклических графов. Любое предложение или помощь приветствуются. Спасибо.

Answer 1

Фактор-граф, который вы описываете с узлами A, B, C и т. Д., Всегда ацикличен: если он имел цикл, например, с участием A и B, все задачи в A достижимы из всех задач в B и наоборот , поэтому A и B являются одним и тем же SCC. Итак, да, вы можете переносить этот график.