Protokół iteracyjny w Pythonie

Python jest językiem, do którego mam bardzo ambiwalentny stosunek. Z jednej strony bardzo mi się podoba to, w jaki sposób się w nim pisze, z drugiej widzę w nim pewne założenia które zupełnie mi nie odpowiadają (powiedzmy, że nie jestem największym fanem programowania obiektowego). Nie można mu jednak zarzucić tego, że jest brzydki lub mało czytelny (co często ma miejsce w przypadku Perla, w którym również zdarza mi się programować).

Jedna z rzeczy, która w Pythonie mi się bardzo podoba to możliwość zdefiniowania, w jaki sposób będziemy iterować po klasie, którą sami tworzymy.

Weźmy na przykład strukturę, która nie jest liniowa, w tym przypadku niech to będzie graf:

# Przyjmijmy, że mamy graf który w przybliżeniu wygląda tak
# 
#     A          E
#    / \        /
#   /   \      /
#  B-----C----D-----F
#
# Tłumacząc to na kod można by otrzymać taki zapis  

g = Graph()
g.add(vertex='A', neighbours=['B', 'C'])
g.add(vertex='B', neighbours=['A', 'C'])
g.add(vertex='C', neighbours=['A', 'B', 'D'])
g.add(vertex='D', neighbours=['C', 'E', F'])
g.add(vertex='E', neighbours=['D'])
g.add(vertex='F', neighbours=['D'])

Są różne sposoby przechodzenia przez wszystkie wierzchołki grafu, na przykład przeszukiwanie wszerz (Breadth-First Search) czy przeszukiwanie w głąb (Depth-First Search) oba podejścia mają swoje zady i walety, są również podstawą dla innych bardziej złożonych algorytmów (np. przy rozwiązywaniu problemu maksymalnego przepływu) dlatego wspaniale by było napisać po prostu coś takiego:

for i,v in enumerate(g.bfs(start='A')):
    print i, v

# skutkuje wypisaniem
# 0 A
# 1 B
# 2 C
# 3 D
# 4 E
# 5 F

a następnie skupić się na implementacji szczegółów innych rozwiązań

I Python nam na to pozwala!

Trzeba jedynie zdefiniować iterator, który będzie przechodzić przez wierzchołki grafu w odpowiedni sposób.

Pisanie iteratora

Po pierwsze, trzeba by zdefiniować klasę reprezentującą graf. Załóżmy, że mamy już to zrobione (możemy mieć macierz albo listy przyległości). W takim wypadku będziemy mieć zdefiniowaną (jak w przykładzie powyżej) następującą metodę zwracającą iterator, który będzie przechodzić przez graf zaczynając od konkretnego wierzchołka (start):

def bfs(self, start=None):
    # utwórz i zwróć obiekt iteratora 
    return _bfs_iterator(self, start_v=start)

Iterator musi przechowywać obecny stan iteracji (pozwala na odwołanie się do bierzącego elementu) oraz posiadać wiedzę o tym, w jaki sposób przejść do następnego elementu z kolekcji. Można powiedzieć, że jest to uogólnione pojęcie wskaźnika.

Spróbujmy to napisać zgodnie z wymaganiami Pythona, które wyglądają następujaco:

The iterator objects themselves are required to support the following two methods, which together form the iterator protocol:

iterator.__iter__()

Return the iterator object itself. This is required to allow both containers and iterators to be used with the for and in statements. This method corresponds to the tp_iter slot of the type structure for Python objects in the Python/C API.

iterator.next()

Return the next item from the container. If there are no further items, raise the StopIteration exception. This method corresponds to the tp_iternext slot of the type structure for Python objects in the Python/C API.

Zdefiniujmy klasę następująco:

class _bfs_iterator():
    def __init__(self, g, start_v):
        self.graph = g
        self.visited = {} # musimy zapisać gdzieś 
                          # odwiedzone wierzchołki
        self.fifo = collections.deque()
        self.fifo.append(start_v) # dodajemy element od
                                  # którego będziemy zaczynać

W celu zapisania, które wierzchołki odwiedziliśmy posłużę się tutaj słownikiem. W ten sposób będziemy mogli skorzystać z szybszego dostępu do elementów słownika, co przyspieszy wykonanie przy korzystaniu z pythonowego in.

Zdefiniujmy, więc pierwszą metodę potrzebną do protokołu iteracyjnego Pythona (uwaga, brak wybuchów).

    def __iter__(self):
        return self

Teraz zaimplementujemy BFS w metodzie next uwzględniając wymogi Pythona:

    def next(self):
        while len(self.fifo):
            vertex = self.fifo.popleft()
            if vertex not in self.visited:
                # Zapamiętujemy wierzchołek, który odwiedzamy
                self.visited[vertex] = True
                # dodajemy jego sąsiadów 
                # jako kolejnych do odwiedzenia
                for n in self.graph.adj_list[vertex]:
                    self.fifo.append(n)
                break
        else:
            raise StopIteration()
        return vertex

Kiedy dodajemy sąsiadów do kolejki odwołujemy się do wewnętrznej listy (dwu wymiarowej) przyległości dla wierzchołka, który teraz odwiedzamy, w tym wypadku nazwałem ją adj_list. Równie dobrze mogłaby to być metoda, która zwraca przylegające wierzchołki, gdyby implementacja grafu polegała na macierzy.

I w tym momencie skończyliśmy naszą pracę! Mamy iterator, dzięki któremu możemy przejść po grafie przy użyciu wbudowanego, pythonowego fora.

Zachęcam do napisania również DFSa w takiej formie jako ćwiczenie ;)

A także do przejrzenia mojej implementacji grafu na GitHubie, gdzie napisałem oba iteratory. Wszelkie uwagi do tekstu, jak i do samej implementacji mile widziane (jak zawsze zachęcam do skorzystania z poczty elektronicznej).