/ / Algorytmy lub teoria łączenia części dwóch struktur wykresów? - algorytm, struktury danych

Algorytmy lub teoria łączenia części dwóch struktur wykresów? - algorytm, struktury danych

Mam skierowany acykliczny wykres, którego przykład może wyglądać następująco:

                     |
(1)
/ | 
/  |  
(3) (2) (4)
/  / |   
/  /  |    
/  /   |     
(6)(7)  (5)  (8)(9)
|  |    |    |  |
(10)(11) (12)(13)(14)
      |    /  /
    (15)_/  /
    |     /
___(16)__/
|
|
  • Wykonanie każdego węzła odbywa się w dół.
  • Gdy węzeł ma więcej niż jedną gałąź wychodzącą, tworzona jest kopia wykresu, a wybrany oddział wykonuje się w innym procesie.
  • Gdzie węzeł ma więcej niż jedną gałąź przychodzącąkopie wykresu są kierowane z powrotem do głównego procesu, aby można je było scalić, tak aby kopie wzorcowe zawierały wszystkie zmiany wprowadzone w gałęziach (w oddzielnych procesach).
  • Procesy są długotrwałe i przejściowe, więc janie mogę "t / don" wytyczyć każdego węzła z powrotem do mastera po jego wykonaniu - chcę tylko scalić się z masterem, kiedy duża część pracy (gałąź) została wykonana zdalnie.

Na przykład w węźle (1) są trzy gałęzie, które muszą być synchronizowane w węźle (16). Sam w sobie jest to stosunkowo proste - zaznacz węzeł (16) jako synch dla węzła (1) i scalanie z węzła (1) do (16) w dół synchronizowana gałąź po wykonaniu trafień wykonania (16).

Jednak węzeł (2) ma dwie gałęzie, które również muszą być synchronizowane w węźle (16) (ma również dwa, które muszą zostać zsynchronizowane w węźle (15)).

W tym przykładzie problem polega na tym, że wykonanie trafia w węzeł (16) nie wie, jak daleko cofnąć drzewo, aby rozpocząć synchronizację (tj. węzeł (1) lub (2)).

Potrzebuję czegoś w rodzaju schematu kolorowania wykresów, w którym różne ścieżki wykonania dostarczają własne wskaźniki do węzła, z którego pochodzą, więc gdy ścieżka (11) -> (16) jest aktywowany, wykonanie wie, że część wykresu, który ma zostać scalony, rozpoczyna się w węźle (2).

Czy jest tu trochę teorii lub algorytmu, który może tutaj pomóc? Czy też podchodzę do problemu w niewłaściwy sposób?

Odpowiedzi:

2 dla odpowiedzi № 1

Sortowanie topologiczne jest tym, czego szukasz. Możesz użyć algorytmu do podzielenia węzłów wykresu na trzy klasy węzłów dla każdego węzła X - poprzednika X, następnych węzłów X i węzłów niezależnych od X.

Zauważ, że twój wykres musi być aliasowy dla algorytmu, podczas gdy twoje wykresy są cykliczne (ale nie widzę żadnego cyklu w twoim przykładzie).

ALGORYTM

  1. Weź zestaw bezpośrednich węzłów poprzedzających DP węzła X.
  2. Dla każdego bezpośredniego poprzednika węzła Ni w DP znajdź zestaw wcześniejszych węzłów Pi.
  3. Znajdź zestaw wspólnych poprzedników węzłów CP przecinając wszystkie Pi.
  4. Znajdź unikalny węzeł, w którym nie ma następcy CP (gdyby CP jest niepusty).

PRZYKŁAD

Spójrzmy na węzeł 15. Istnieją dwa bezpośrednie poprzedniki 12 i 13. Teraz znajdź wszystkich poprzedników tych dwóch węzłów - dla 12 to 5, 2 i 1. Dla 13 to 8, 2 i 1. Przecięcie tych zbiorów wynosi 2, a zatem 1 te dwa węzły są wspólnymi poprzednikami, a węzeł 2 jest wspólnym poprzednikiem bez następcy (podczas gdy węzeł 1 jest wspólnym poprzednikiem, ale węzeł 2 jest jego następcą). Dlatego w węźle 15 łączą się dwie gałęzie pochodzące od węzła 2.