Как найти компоненты связности в графе в распределенной памяти?

Question

[Вадим Мамонов]

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

Для организации вычислений на распределенной памяти полный граф был "разрезан" (связи при этом не теряются) на параграфы, каждый параграф хранится на отдельном процессе. Чтобы волновой алгоритм работал, в каждый параграф добавляются призрачные ребра вместе с призрачным узлом в тех местах,где был "разрезан" полный граф на параграфы. И написана функция синхронизации данный в призрачных узлах (все остальные функции mpi также доступны для связи между процессами). Получается некий процесс может в своем параграфе пустить волну, дойти до призрачного ребра, далее вызвать метод синхронизации данных, и снежный процесс увидет, что в призрачном узле пришла волна, и он сможет пустить еë дальше.

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

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

Comments

[mayton2019]

А где исходный код, который можно обсудить? И хорошо-бы картинку глянуть. Вот с этими призрачными ребрами. Оно то понятно что каждый себе в голове можен нафантазировать. Но авторское видение тоже надо посмотреть.

[Вадим Мамонов]

mayton2019, вы правы) Но кода нет, я его еще не написал. В моей голове вот такая картинка

[mayton2019]

Ааа.... Вот я себе это по другому представлял.

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

Answer 1

[Wataru]

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

Лидер опрашивает остальные сервера по очереди (включая себя), и справшивает их, есть ли у них еще непокрашенные вершины. Если есть, инструктирует их запустить волну. Когда волна закончится, справшивает опять. Когда сервер говорит, что больше непокрашенных вершин нет - лидер переходит к следующему серверу.

Когда сервер запускает волну - он обходит все вершины у себя, если встречает призрачное ребро, то посылает сообщение другому серверу запустить обход у себя с присоеденненной вершины.
Чтобы отследить конец волны, перед запуском обхода в другом сервере, каждый сервер отслывает лидеру сообщение, что вот тот сервер теперь будет работать. Когда волна в каком-то сервере заканчивается, он присылает лидеру сообщение, что все закончилось. Лидер поддерживает счетчик - сколько еще серверов работает. Когда счетчик достигает 0, надо еще подождать немного (скажем, пол секунды), на случай реордеринга сообщений. Если в течении этой пол секунды никаких сообщений не пришло, можно запускать новую волну.

Более сложный вариант - когда у вас сразу запускаются все волны. Опять же, без лидера совсем сложно будет.
Тут, наверно стоит сначала в каждом отдельном параграфе найти все компоненты связности отдельно. Это будут промежуточные варианты.

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

Когда сервер получает сообщение о номере по призначному ребру, если этот номер меньше текущего у компоненты, она перекрашивается. И сообщение рассылается по всем остальным призрачным ребрам, торчащим из этой компоненты. Рано или поздно, все вершины одной компоненты по всем серверам будут помечены минимальным номером.

Чтобы определить, что все закончилось, можно разбить процесс на фазы. В первой фазе все рассылают свои номера. Во второй фазе только те, у кого номера обновились. И т.д. Фаза на сервере начинается после сообщения от лидера. Каждый сервер отправляет на лидер сообщение, когда он закончил рассылать свои номера и были ли там вообще обновления. Сообщения надо делать по tcp с подтверждением. Когда лидер заметит, что никто никаких сообщений больше не рассылал в предыдущей фазе - все сошлось.

Comments

[Вадим Мамонов]

Лёгкий вариант это а-ля стандарт алгоритм, но медленный. А вот трудный норм, в качестве ид связной компоненты я возьму минимальный глобальный номер узла в полном графе. После как вы и написали найду итеративно самый минимальный ид. А затем я на каждом процессе соберу информацию сколько у кого компонент и ид компонент, отсортирую, увижу совпадение ид ии ввиду локальную нумерацию компонент.
Спасибо вам!