Python implementation of selected algorithms for multigraphs

W pracy przedstawiono implementację w języku Python wybranych algorytmów wykorzystujących multigrafy. Multigrafy są instancjami klasy MultiGraph, ale interfejs jest zgodny z klasą Graph, opisującą grafy proste. Dzięki temu klasy odpowiadające algorytmom mogą działać na obu typach grafów. Przygotowano dwie różne implementacje multigrafów, z wagami i bez wag.Zaimplementowano trzy algorytmy do znajdowania cykli Eulera: algorytm Flory'ego, algorytm z wykorzystaniem stosu, oraz algorytm Hierholzera. Ponadto dołączono algorytmy rozwiązujące problem chińskiego listonosza.Stworzono szereg heurystycznych algorytmów do znajdowania maksymalnego zbioru niezależnego: algorytm trywialny (zachłanny), algorytmy z dołączaniem wierzchołków, algorytmy z usuwaniem wierzchołków. Najwięcej algorytmów dotyczy kolorowania wierzchołków grafu. Jest to algorytm dokładny, sześć algorytmów sekwencyjnych i trzy algorytmy sekwencyjne z wymianą kolorów. Dołączono również algorytm kolorowania krawędzi, wykorzystujący graf krawędziowy.Algorytmy zbiorów niezależnych i algorytmy kolorowania grafów zostały przetestowane. Sprawdzono ich jakość i realną złożoność obliczeniową.Python implementations of selected graph algorithms using multigraphs are presented. Multigraphs are instances of the MultiGraph class,but interface is compatible with the Graph class describing simple graphs. This is why algorithm classes can be used with both types of graphs.Two different implementations of the MultiGraph class are available, for weighted and unweighted graphs.The algorithms for finding an Eulerian cycle are presented: the Fleury's algorithm, the algorithm using a stack, andthe Hierholzer's algorithm. The algorithms solving the chineese postman problem are also included.Several heuristic algorithms for finding a maximum independent set are shown: the trivial/greedy algorithm,the smallest first algorithm, the largest last algorithm, and their modified versions. Many algorithms for node coloring are prepared: the exact algorithm, six sequential algorithms, and three sequential algorithms with color interchange. Edge coloring algorithm using a line graphs is also included.Independet set algorithms and graph coloring algoriths were tested and their quality and complexity was checked