Sortowanie topologiczne grafu
Jedną z nowości wprowadzonych w Pythonie 3.9 jest moduł graphlib oferujący możliwość sortowania topologicznego wierzchołków w acyklicznym grafie skierowanym.
|
|
Klasa TopologicalSorter (z konstruktorem opcjonalnie przyjmującym graf) pozwala sprawdzić, czy graf jest w istocie acykliczny (prepare() zwróci CycleError w przypadku wykrycia cyklu), a następnie iterować po posortowanych wierzchołkach, bądź też iterować po wierzchołkach do momentu, gdy zostanie znaleziony cykl (get_ready()). Klasa ta została zaprojektowana w taki sposób, aby ułatwić równoległe przetwarzanie wierzchołków, gdy staną się one dostępne.
Co to jest sortowanie topologiczne?
W grafie skierowanym (czyli takim, w którym krawędzie mają zwrot, a więc prowadzą od pewnego wierzchołka do innego wierzchołka) można znaleźć takie uporządkowanie wierzchołków, że dla każdej pary wierzchołków u oraz v połączonych krawędzią od u do v (u -> v), wierzchołek u znajdzie się przed wierzchołkiem v.
Graf można pososrtować topologicznie tylko wtedy, gdy w grafie nie ma cykli (czyli nie można się po wierzchołkach kręcić w kółko).
Co to jest graf?
Graf w module graphllib jest reprezentowany przez słownik (dict). Kluczami w słowniku są wierzchołki grafu, a wartościami są sekwencje wierzchołków będących poprzednikami wierzchołka będącego kluczem, czyli wskazującymi na wierzchołek w kluczu.
Jak posortować topologicznie graf?
Użyć nowego modułu graphlib. Chyba, że mamy w systemie starszą wersję Pythona - a wtedy trzeba sobie przypomnieć przechodzenie grafu wgłąb, a przy przechodzeniu pamiętać o dodaniu każdego odwiedzonego wierzchołka na początek listy.
Początkowo użyłam zwykłej pythonowej listy, ale wstawianie na początek, ze względu na konieczność przesuwania wszystkich elementów listy w prawo, ma złożoność O(n), dlatego użyłam klasy collections.deque (double ended queue), mającą złożoność wstawiania na początek i koniec listy O(1).
|
|
Wywołanie topo_sort(graph)
zwróci listę (deque) z wierzchołkami grafu
graph
posortowanymi w kolejności topologicznej.
Aktualizacja 2020-12-11:
Graf wejściowy w ogólnym przypadku nie zawiera kluczy, które nie mają
zależności (i występują jedynie jako elementy sekwencji będącej
wartością klucza). Dlatego, aby móc iterować po wszystkich
wierzchołkach, generuję listę wierzchołków przy użyciu
_all_verts(graph)
. Dodatkowo topo_sort()
zwraca listę we właściwej
kolejności, a nie deque.
Zastosowania
Jednym i chyba najważniejszym zastosowaniem jest znajdowanie kolejności wykonywania pewnej liczby zadań, jeśli znane są ograniczenia: jakieś zadanie może być wykonane dopiero po wykonaniu wcześniej innych zadań. Zadania są wówczas reprezentowane jako wierzchołki, a krawędzie reprezentują ograniczenia (wierzchołki prowadzą od zadań wcześniejszych do późniejszych).
W systemach *niksowych stosuje się je do ustalenia kolejności instalacji pakietów w systemach zarządzania pakietami.
Systemy budowania, które ściągają z sieci i instalują zależne moduły/biblioteki wraz z zależnościami prawdopodobnie również stosują jakąś wersję sortowania topologicznego.
Sortowanie topologiczne stanowi też podstawę dla innych algorytmów - na przykład przy szukaniu najkrótszych ścieżek w ważonym grafie skierowanym (patrz: Application to shortest path finding)