Алгоритми чи теорія для об'єднання частин двох структур графів? - алгоритм, структури даних

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

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

• Виконання кожного вузла відбувається вниз.
• Якщо вузол має більше ніж одну вихідну гілку, створюється копія графіка, а обрана гілка виконується в іншому процесі.
• Де вузол має більше ніж одну вхідну гілкукопії графа відводяться назад до основного процесу, тому їх можна об'єднати, так що основна копія містить всі зміни, внесені до гілок (в окремих процесах).
• Процеси довго біжать і минущі, тому яможе "t / do" не бажати маршрутизувати кожен вузол назад майстром після його виконання - я хочу лише злитися з майстром, коли велика частина роботи (гілка) була завершена віддалено.

Так, наприклад, у вузлі (1) Є три гілки, які повинні синхронізуватися на вузлі (16). Сама по собі це відносно просто - позначити вузол (16) як synch для вузла (1) і злиття з вузла (1) до (16) під час синхронізації гілки під час виконання ударів (16).

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

Проблема в цьому прикладі, коли виконання виконує вузли (16) він не знає, наскільки дерево сильно підтримує синхронізацію (наприклад, вузол (1) або (2))

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

Чи існує трохи теорії чи алгоритму, який може тут допомогти? Чи я наближаюсь до проблеми у неправильному напрямку?

Відповіді:

Топологічне сортування це те, що ви шукаєте. Ви можете використовувати алгоритм для розбиття вузлів графа на три класу вузлів для кожного фіксованого вузла 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.