Python implementation of selected algorithms for weighted graphs

W pracy przedstawiono implementację w języku Python wybranych algorytmów i struktur danych dla grafów z wagami. Zdefiniowano interfejs grafów ważonych i stworzono dwie klasy o odmiennych właściwościach, realizujące ten interfejs. Klasa MatrixGraph bazuje na reprezentacji macierzy sąsiedztwa, natomiast klasa DictGraph jest zbliżona do reprezentacji list sąsiedztwa. Dla krawędzi stworzono osobne klasy, mianowicie Edge oraz UdirectedEdge. Dodano także generatory dla kilku typów grafów. W pracy zaimplementowano algorytmy grafowe związane z przeszukiwaniem grafów, wyznaczaniem minimalnego drzewa rozpinającego, wyznaczaniem najkrótszych ścieżek z jednego i wielu źródeł, znajdowania maksymalnego przepływu w sieci przepływowej. Każdemu algorytmowi odpowiada osobna klasa, a w danej klasie może być zawartych kilka różnych implementacji. W pracy pojawiły się też pewne pomocnicze algorytmy i struktury danych, np. przeszukiwanie grafów wszerz i przeszukiwanie w głąb. Przeszukiwanie w głąb wykorzystano do sortowania topologicznego wierzchołków dagu. Korzystano również ze struktury danych zbiorów rozłącznych. Zaimplementowano trzy algorytmy rozwiązujące problem minimalnego drzewa rozpinaj¡cego: algorytm Boruvki, algorytm Prima (trzy implementacje), algorytm Kruskala. Zaimplementowano trzy algorytmy rozwiązujace problem najkrótszych ścieżek z jednym źródłem: najkrótsze ścieżki w dagu, algorytm Bellmana-Forda, algorytm Dijkstry (dwie implementacje). Zaimplementowano dwa algorytmy rozwiązujące problem najkrótszych ścieżek między wszystkimi parami wierzchołków: algorytm Floyda-Warshalla, algorytm Johnsona. Wkońcu zaimplementowano dwa algorytmy rozwiązujące problem maksymalnego przepływu w sieci przepływowej: algorytm Forda-Fulkersona, algorytm Edmondsa-Karpa. Dla wszystkich algorytmów przygotowano testy poprawności z wykorzystaniem modułu unittest, który jest standardowym narzędziem wspomagającym sprawdzanie kodu w Pythonie. Ponadto wykonano eksperymenty komputerowe sprawdzające zgodność rzeczywistej wydajności kodu z przewidywaniami teoretycznymi.

Python implementations of weighted graphs and selected graph algorithms are presented. Graphs interface is defined and two different classes are created which implement this interface. The MatrixGraph class is based on the adjacency-matrix representation of graphs. The DictGraph class is based on the adjacency-list representation, but with fast lookup of nodes and neighbours (dict-of-dict structure). There are also classes for graph edges: Edge and UdirectedEdge. Some graph generators are also included. In this work, many graph algorithms are implemented using a unified approach. There are separate classes devoted to different algorithms, but sometimes several algorithm versions are included in the same class. Some auxilliary algorithms and data structures are used. Two graphs searching or traversing algorithms are implemented: breadth-first search (BFS) and depth-first search (DFS). Topological sorting algorithm is based on DFS. A disjoint-set data structure is also included. Three algorithms for finding a minimum spanning tree are implemented: the Boruvka's algorithm, the Prim's algorithm (three implementations), and the Kruskal's algorithm. Three algorithms for solving the single-source shortest path problem are implemented: the dag shortest path algorithm, the Bellman-Ford algorithm, and the Dijkstra's algorithm (two implementations). Two algorithms for solving all-pairs shortest path problem are implemented: the Floyd-Warshall algorithm and the Johnson's algorithm. Two algorithms for computing the maximum show in a flow network are implemented: the Ford-Fulkerson algorithm and the Edmonds-Karp algorithm. All algorithms were tested by means of the unittest module, the Python unit testing framework. Additional computer experiments were done in order to compare real and theoretical computational complexity.