Visualization of graphs with Python

W pracy zbadano problem rysowania grafów w języku Python. Zebrano szereg bibliotek i pakietów, które współpracują z Pythonem. Stworzono kilka implementacji nowych algorytmów, oraz pokazano struktury danych dla prostych grafów geometrycznych.Zaimplementowano algorytm rekurencyjny do rysowania drzew radialnych, gdzie centrum drzewa jest w środku rysunku, a inne wierzchołki leżą na koncentrycznych kręgach. Stworzono też pomocniczy algorytm do wyznaczania centrum i promienia drzewa. Dla grafów skierowanych acyklicznych (dagów) przedstawiono zmodyfikowany algorytm sortowania topologicznego. Umożliwia on rysowanie dagów z krawędziami skierowanym z lewa na prawo. Stworzono galerię grafów z wieloma grafami nazwanymi, zawierającą grafy pełne, grafy 3-regularne i 4-regularne, oraz grafy ze ścianami kwadratowymi. Zaimplementowano szereg skryptów do rysowania grafów. Jeden ze skryptów rysuje wierzchołki grafu na okręgu, co jest wygodne dla grafówHamiltona, skierowanych i nieskierowanych. Wszystkie skrypty do rysowania używają Gnuplota 4, ze względu na jego elastyczność i interfejs wiersza poleceń. Główne algorytmy przetestowano pod kątem wydajności.

The problem of graph drawing with Python is considered. A range of libraries and packages is collected. Some new algorithms are created and implemented. Data structures for simple geometric graphs are shown.The recursive algorithm for drawing radial trees is created, where the tree center is in the middle of the picture and other nodes are placed on concetric circles. The auxiliary algorithm for finding the tree center and the tree radius is used. For the case of directed acyclic graphs (dags), the modifiedtopological sorting algorithm is created. It is used to draw dags with edges directed from left to right.Gallery of graphs is created with several named graphs, including complete graphs, cubic graphs, quartic graphs, and graphs with square faces. A family of scripts for graph drawing is provided. There is a script for drawing graph nodes on the circle, which is very suitable for Hamiltonian graphs (directed or undirected). All scripts use Gnuplot 4 as a plotting engine, because it is a very fexible program with a command line interface. Main algorithms were tested in order to confirm the complexity.