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.

1
2
3
4

   graph = {"A": {"B", "C"}, "B": {"D"}, "C": {"D"}}
   ts = TopologicalSorter(graph)
   tuple(ts.static_order())
   # ('D', 'B', 'C', 'A')

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).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

  import collections

  def topo_sort(graph):
      """
      Sorts graph topologically.
      ``graph`` is a dictionary with keys being vertices
      and values being iterables of vetex's predecessors.
      """

      def _all_verts(graph):
          """
          Returns all vertices in the ``graph``: 
          those being keys and those included in values
          """
          keyvalslist = map(lambda p: list(p[1]) + [p[0]], graph.items()) 
          return set([v for keyvals in keyvalslist for v in keyvals])

      def _topo(v, visited, ts):
          """
          
          """
          visited[v] = True
          for p in graph.get(v, []):
              if not visited[p]:
                  _topo(p, visited, ts)
          ts.appendleft(v)

      verts = _all_verts(graph)

      print("verts" ,verts)
      ts = collections.deque()
      visited = dict((v, False) for v in verts)
      for v in verts:
          if not visited[v]:
              _topo(v, visited, ts)

      return [v for v in ts]

  graph = {"A": {"B", "C"}, "B": {"D"}, "C": {"D"}}
  print(topo_sort(graph))

  # ('D', 'C', 'B', 'A')

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)