Python: biblioteka treelib

Python jest bardzo użytecznym językiem, który pozwala nam na bardzo wiele. Jednak czym byłby Python, gdyby nie dziesiątki, czy raczej setki rozszerzeń, plug-in’ów oraz bibliotek. Są to elementy zarówno wewnętrzne, jak i zewnętrzne. W tej części chciałbym przedstawić interesującą moduł, jakim jest biblioteka treelib. Umożliwia ona w łatwy sposób przechowywać oraz obsługiwać strukturę drzewa bezpośrednio z Python’a. W artykule przedstawię, czym jest ta biblioteka, a także przykład jej użycia.

Abstrakcyjne typy danych – tree

Zanim poznamy, jak wygląda oraz jak się używa biblioteki treelib. należy poznać abstrakcyjną strukturę danych ADT (Abstract Data Type), jaką jest drzewo, czyli tree. Jest to hierarchiczna struktura danych, której początkiem jest tzw. root node, a do którego są połączone child node’y. Każdy z node’ów w drzewie, z wyjątkiem root node’a, posiada swojego parent node’a. Co jest istotne, jest to struktura jeden do wielu, czyli każdy node posiada jednego parent node, natomiast każdy parent node, może posiadać 0 lub więcej child node’ów.

Wprowadzenie do TreeLib

Biblioteka treelib jest to odwzorowanie w kodzie wspomnianej wyżej struktury danych — Tree. Wtyczka ta składa się głównie z dwóch podstawowych klas, czyli Tree oraz Node. Tree obrazuje nam schemat powiązań pomiędzy node’ami, natomiast Node obrazuje konkretny węzeł w drzewie. Oczywiście razem z tymi dwoma klasami dostajemy do dyspozycji cały szereg metod, dzięki czemu praca z tą strukturą jest łatwa i przyjemna. Poniżej przykładowy schemat drzewa:

Analizując powyższy schemat, można go od razu dopasować do różnych zastosowań. Jednym z nich może być reprezentacja menu w dowolnej aplikacji:

Instalacja

Treelib nie jest podstawową biblioteką języka Python, dlatego należy ją zainstalować ręcznie. Odbywa się to w standardowy sposób dla tego języka, czyli przy użyciu narzędzia pip:

qabrio@test:~$ pip install treelib

Reprezentacja w kodzie

Więc wiemy już, co możemy zrobić, a także z użyciem jakiego narzędzia, więc została nam tylko odpowiedź na pytanie jak? W pierwszym kroku należy stworzyć obiekt typu Tree, a następnie dodawać do niego kolejne node’y. Z racji, że musimy posiadać root node, nazwiemy go wstępnie jako MENU. Ponadto każdy z elementów, będzie zawierał swój typ, identyfikator, oraz informacje o node nadrzędnym, czyli parent. Ważne jest, aby każdy identyfikator był unikalny, gdyż właśnie przy ich użyciu będziemy tworzyć powiązania z node‚ami nadrzędnymi:

from treelib import Node, Tree

menuStruct = Tree()

menuStruct.create_node(tag="Menu", identifier=1)
menuStruct.create_node(tag="File", identifier=11, parent=1)
menuStruct.create_node(tag="Edit", identifier=12, parent=1)
menuStruct.create_node(tag="Help", identifier=13, parent=1)
menuStruct.create_node(tag="New", identifier=111, parent=11)
menuStruct.create_node(tag="Open", identifier=112, parent=11)
menuStruct.create_node(tag="Exit", identifier=114, parent=11)
menuStruct.create_node(tag="Copy", identifier=121, parent=12)
menuStruct.create_node(tag="Cut", identifier=122, parent=12)
menuStruct.create_node(tag="Paste", identifier=123, parent=12)
menuStruct.create_node(tag="Index", identifier=131, parent=13)
menuStruct.create_node(tag="About", identifier=132, parent=13)
menuStruct.create_node(tag="Version", identifier=1321, parent=132)
menuStruct.create_node(tag="Credentials", identifier=1322, parent=132)

menuStruct.show()

Na samym końcu skorzystaliśmy jeszcze z funkcji show, dzięki której możemy zobaczyć ‚graficzną’ reprezentację drzewa w linii komend:

Menu
├── Edit
│   ├── Copy
│   ├── Cut
│   └── Paste
├── File
│   ├── Exit
│   ├── New
│   └── Open
└── Help
    ├── About
    │   ├── Credentials
    │   └── Version
    └── Index

Ścieżka do node

Mając już przygotowane drzewo, poznajmy jak się po nim poruszać. Jedną z częściej wykonywanych czynności jest poszukiwanie ścieżki do danego node’u. Biblioteka nie udostępnia metody, która zwróci nam to bezpośrednio, lecz nic nie stoi na przeszkodzie, aby taką funkcję napisać. W tym celu posłużymy się dwoma wbudowanymi metodami, czyli contains, która zwraca true, jeśli node id istnieje w drzewie, oraz path_to_leaves, który zwraca nam listę ścieżek, które prowadzą do ‚wyjścia’ z drzewa. Za ścieżkę prowadzącą do wyjścia z drzewa rozumiemy ścieżki, które łączą root node z node’ami nieposiadającymi żadnych child nod’ów. W przykładzie stworzonym w tym artykule istnieje 9 ścieżek wyjścia od root node’a.

def show_path(nid, menu):
    if not menu.contains(nid):
        return None
    for path in menu.paths_to_leaves():
        if nid in path:
            return path[:path.index(nid) + 1]

Przeanalizujmy stworzoną funkcję. Przyjmuje ona dwa argumenty, gdzie pierwszy to node id, natomiast kolejny to obiekt, w którym będziemy szukać. Na początku sprawdzamy, czy dany node w ogóle istnieje w podanym obiekcie. Jeśli warunek zostanie spełniony, to szukamy pierwszej ścieżki, która go zawiera. Na koniec musimy jeszcze ograniczyć zwracaną listę, aby kończyła się na poszukiwanym node. Działanie tej funkcji będzie następujące:

show_path(132, menu=menuStruct)  # result: [1, 13, 132]
show_path(11, menu=menuStruct)  # result: [1, 11]
show_path(113, menu=menuStruct)  # result: None

Interfejs klasy Tree

Oprócz dwóch wykorzystanych metod interfejs klasy Tree posiada jeszcze wiele interesujących elementów. Do najpopularniejszych możemy zaliczyć takie jak parent, children oraz get_node, które odpowiednio zwracają nam obiekt parent node, listę child node’ów oraz o konkretnego node. Poniżej przykłady ich użycia:

menuStruct.parent(12)  # Node(tag=Menu, identifier=1, data=None)
menuStruct.children(12)  # [Node(tag=Copy, identifier=121, data=None), Node(tag=Cut, identifier=122, data=None), Node(tag=Paste, identifier=123, data=None)]
menuStruct.get_node(12)  # Node(tag=Edit, identifier=12, data=None)

Idąc dalej, mamy możliwość stworzenia listy wszystkich node’ów z drzewa:

menuStruct.all_nodes()   # result: list of all nodes

Dla konkretnego node‚a, możemy sprawdzić na przykład, na którym poziomie się on znajduje:

manuStruct.depth(12) # result 1

Ciekawymi rozwiązaniem jest również możliwość eksportu całego drzewa do postaci słownika lub do pliku json. Możemy to uczynić za pomocą metod:

menuStruct.to_dict() # result dictionary
menuStruct.to_json() # result json

Po więcej ciekawych metod z interfejsu biblioteki treelib odsyłam bezpośrednio do dokumentacji. Znajduje się tam opis każdej metody, a także przykłady użycia. Polecam!

TreeLib – dokumentacja