Cykliczne zależności oznaczają, że poprawna kolejność zadań nie istnieje
Sortowanie topologiczne układa wierzchołki skierowanego grafu tak, aby każda zależność A→B umieszczała A przed B. Nadaje się więc do planowania zadań, kompilowania modułów czy ustalania kolejności elementów zależnych od innych. Najciekawsza jest druga strona twierdzenia: taki porządek istnieje wtedy i tylko wtedy, gdy graf nie ma skierowanego cyklu. Jeśli A wymaga B, B wymaga C, a C ponownie wymaga A, problemu nie naprawi lepsze tasowanie listy — żadna liniowa kolejność nie może spełnić wszystkich trzech warunków. Algorytm może więc jednocześnie tworzyć poprawny harmonogram i ujawniać, że wymagania są logicznie sprzeczne.
Kolejność wynika z zależności, a nie z priorytetu
Załóżmy, że moduł B może zostać zbudowany dopiero po A. Reprezentujemy to krawędzią A→B. Jeśli podobnych zależności są tysiące, potrzebujemy kolejności wszystkich modułów, w której każda krawędź wskazuje do przodu. Taki liniowy układ wierzchołków nazywa się porządkiem topologicznym.
Nie chodzi tu o sortowanie według liczby, nazwy ani „ważności”. Graf definiuje tylko częściowy porządek: A musi być przed B, ale jeśli C nie ma związku z żadnym z nich, może znaleźć się w wielu różnych miejscach. Dlatego jeden graf może mieć wiele poprawnych porządków topologicznych. Algorytm ma znaleźć dowolny, który spełnia wszystkie wymagania.
Skierowany cykl tworzy logiczną sprzeczność
Rozważmy trzy zależności: A przed B, B przed C i C przed A. Gdyby istniał porządek topologiczny, z pierwszych dwóch wynikałoby, że A jest przed C. Trzecia zależność wymaga jednak, aby C było przed A. Nie da się spełnić obu warunków jednocześnie.
To nie problem konkretnego algorytmu ani niefortunny wybór pierwszego elementu. Princeton Algorithms podaje podstawowe twierdzenie: skierowany graf ma porządek topologiczny wtedy i tylko wtedy, gdy jest DAG-iem, czyli skierowanym grafem acyklicznym. Wykrycie cyklu jest więc certyfikatem, że oczekiwany harmonogram w ogóle nie istnieje przy zadanych zależnościach.
DFS może znaleźć porządek „od końca”
Jedna klasyczna metoda wykorzystuje depth-first search. Gdy DFS wchodzi do wierzchołka, najpierw odwiedza wszystkie osiągalne zależności, a wierzchołek zapisuje dopiero po zakończeniu jego przetwarzania. Odwrócenie kolejności takich zakończeń — reverse postorder — daje porządek topologiczny dla DAG-u.
Intuicja jest taka, że wierzchołek kończy się dopiero po przetworzeniu wszystkiego, do czego prowadzą jego krawędzie. Odwracając kolejność zakończeń, umieszczamy poprzedników przed następcami. Inny popularny algorytm, metoda Kahna, wielokrotnie wybiera wierzchołki bez nieprzetworzonych poprzedników. Oba podejścia wykorzystują tę samą strukturalną cechę grafu: gdzieś musi istnieć legalny punkt startu, jeśli nie ma cyklu blokującego zależności.
Można to zrobić w czasie proporcjonalnym do rozmiaru opisu problemu
Dla grafu zapisanego jako listy sąsiedztwa zarówno przejście DFS, jak i klasyczne sortowanie topologiczne wymagają czasu O(V+E): trzeba zasadniczo odwiedzić każdy wierzchołek i każdą krawędź stałą liczbę razy. To bardzo dobra granica, ponieważ sam odczyt kompletnego grafu kosztuje podobny rząd czasu.
Warto porównać to z naiwną wizją wielokrotnego skanowania całej listy zadań w poszukiwaniu czegoś, co „da się teraz zrobić”. Odpowiednia reprezentacja grafowa i algorytm pozwalają przetworzyć zależności systematycznie, bez wielokrotnego sprawdzania tych samych warunków od początku.
Cykl jest często ważniejszą odpowiedzią niż sama kolejność
W praktycznym systemie zależności wynik „nie da się posortować” nie jest porażką algorytmu. Jest informacją diagnostyczną. Jeśli pakiet A wymaga B, B wymaga C, a C wymaga A, menedżer zależności może wskazać cykl zamiast próbować arbitralnie ustawić kolejność. Podobnie system budowania projektu może wykryć zapętlone wymagania między modułami.
To ciekawy przykład algorytmu, który rozwiązuje dwa blisko związane problemy. Gdy ograniczenia są spójne, daje harmonogram. Gdy nie są, struktura matematyczna wyjaśnia dlaczego. Lepsze sortowanie nie naprawi sprzecznych zależności — trzeba zmienić sam graf, czyli wymagania problemu.
Metoda stopni wejściowych daje bardzo namacalny test cyklu
Alternatywny sposób konstruowania porządku topologicznego zaczyna od policzenia stopnia wejściowego każdego wierzchołka, czyli liczby niespełnionych poprzedników. Wszystkie wierzchołki o stopniu zero można wykonać od razu. Po usunięciu jednego z nich zmniejszamy stopnie jego następców; nowe zera trafiają do kolejki. Jeśli uda się usunąć wszystkie V wierzchołków, kolejność ich zdejmowania jest poprawnym porządkiem topologicznym. Jeśli kolejka stanie się pusta, choć część grafu nadal pozostała, każdy pozostały wierzchołek ma poprzednika wewnątrz tej części. W skończonym grafie prowadzi to do cyklu. Algorytm nie musi więc osobno „zgadywać”, gdzie znajduje się sprzeczność: sam brak jakiegokolwiek legalnego następnego kroku ujawnia, że reszta zależności zamknęła się w pętli.