Алгоритмы или теория для объединения частей двух структур графов?

Question

У меня есть ориентированный ациклический граф, пример которого может выглядеть так:

                     | 
                    (1)
                   / | \
                  /  |  \
                (3) (2) (4)
                /  / | \  \
               /  /  |  \  \
              /  /   |   \  \
            (6)(7)  (5)  (8)(9)
             |  |    |    |  |
           (10)(11) (12)(13)(14)
             \   \   |    /  /
              \   \ (15)_/  /
               \   \ |     /
                \___(16)__/
                     |  
                     |  

• Выполнение каждого узла происходит вниз.
• Если узел имеет более одной исходящей ветви, создается копия графа, и выбранная ветвь выполняется в другом процессе.
• Если узел имеет более одной входящей ветви, копии графа направляются обратно в главный процесс, чтобы их можно было объединить, чтобы в основной копии были все изменения, внесенные в ветви (в отдельных процессах).
• Процессы долго выполняются и являются переходными, поэтому я не могу / не хочу направлять каждый узел обратно к мастеру после того, как он был выполнен - ​​я хочу объединяться с мастером только тогда, когда большая часть работы ( филиал) был завершен удаленно.

Так, например, на узле (1) есть три ветви, которые должны синхронизироваться на узле (16). Само по себе это относительно просто - пометить узел (16) как synch для узла (1) и объединить от узла (1) до (16) вниз по ветви, синхронизируемой, когда выполнение достигает (16).

Однако узел (2) имеет две ветви, которые также должны синхронизироваться в узле (16) (у него также есть две ветви, которые должны синхронизироваться в узле (15)).

В этом примере проблема заключается в том, что когда выполнение достигает узла (16), он не знает, с какой глубины выполняется резервное копирование дерева для начала синхронизации (т. Е. Узла (1) или (2)).

Мне нужно что-то вроде схемы раскраски графа, в которой разные пути выполнения предоставляют свои собственные указатели на узел, из которого они произошли, поэтому, когда активирован путь (11) -> (16), выполнение знает, что часть графа должна быть объединена начинается в узле (2).

Есть ли какая-то теория или алгоритм, который может здесь помочь? Или я неправильно подхожу к проблеме?

Answer 1

Топологическая сортировка - это то, что вы ищете. Вы можете использовать алгоритм для разделения узлов графа на три класса узлов для каждого фиксированного узла X - предшествующие узлы X, последующие узлы X и независимые от X узлы.

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

АЛГОРИТМ

1. Взять набор прямых предшественников узлов DP узла X.
2. Для каждого прямого узла-предшественника Ni в DP найти набор узлов-предшественников Pi.
3. Найдите множество общих узлов-предшественников CP, пересекая все Pi.
4. Найдите уникальный бесполезный узел в CP (если CP не пусто).

Пример

Давайте посмотрим на узел 15. Теперь есть два прямых предшественника 12 и 13. Теперь найдите все предшественники этого обоих узлов - для 12 они равны 5, 2 и 1. Для 13 они равны 8, 2 и 1. пересечение этих наборов равно 2 и 1, поэтому эти два узла являются общими предшественниками, а узел 2 является общим предшественником без преемника (хотя узел 1 является общим предшественником, но имеет узел 2 в качестве преемника). Поэтому в узле 15 объединяются две ветви, исходящие из узла 2.