dc.contributor.advisor |
Kapanowski, Andrzej [SAP11015142] |
pl |
dc.contributor.author |
Malinowski, Łukasz |
pl |
dc.date.accessioned |
2020-07-25T05:52:10Z |
|
dc.date.available |
2020-07-25T05:52:10Z |
|
dc.date.submitted |
2014-10-24 |
pl |
dc.identifier.uri |
https://ruj.uj.edu.pl/xmlui/handle/item/200349 |
|
dc.language |
pol |
pl |
dc.title |
Implementacja wybranych algorytmów dla grafów bez wag w języku Python |
pl |
dc.title.alternative |
Python implementations of selected graph algorithms for unweighted graphs |
pl |
dc.type |
master |
pl |
dc.abstract.pl |
W pracy przedstawiono implementację w języku Python wybranychalgorytmów i struktur danych dla algorytmów bez wag.Zdefiniowano wspólny interfejs dla grafów prostych i multigrafów,oparty na trzech klasach: Edge (dla krawędzi skierowanych),Graphs i MultiGraph. Stworzono sześć różnych implementacjirealizujących interfejs grafów, łącznie z generatorami pewnychtypów grafów.W pracy zaimplementowano dwa najważniejsze algorytmy przeszukiwaniagrafów: przeszukiwanie wszerz i przeszukiwanie w głąb.Zaimplementowano dwa różne algorytmy sortowania topologicznegografów acyklicznych skierowanych.Pokazano algorytmy wyznaczania składowych spójnych grafunieskierowanego i silnie spójnych składowych grafu skierowanego.Zaimplementowano dwa sposoby wyznaczania domknięcia przechodniego,oraz kilka algorytmów do kolorowania wierzchołków i krawędzi grafu.Dla grafów dwudzielnych stworzono implementację algorytmusprawdzającego dwudzielność grafu, oraz implementacje trzechalgorytmów wyznaczania maksymalnego skojarzenia w grafach dwudzielnych:algorytm ścieżek powiększających, algorytm Hopcrofta-Karpa,a także algorytm oparty o metodę Forda-Fulkersona.Każdemu algorytmowi odpowiada osobna klasa, oraz odpowiedni zestawtestów jednostkowych, przygotowanych z wykorzystaniem standardowychnarzędzi wspomagających sprawdzanie kodu w Pythonie.Ponadto dla wybranych implementacji wykonano eksperymenty komputerowesprawdzające zgodność rzeczywistej wydajności kodu z przewidywaniamiteoretycznymi. |
pl |
dc.abstract.en |
Python implementations of selected graph algorithms anddata structures for unweighted graphs are presented.Graphs interface is defined which is suitable for simple graphsand for multigraphs. The interface is based on three classes:the Edge class (for directed edges), the Graph class,and the MultiGraph class.Some graph generators are also included.The algorithms are implemented using a unified approach.There are separate classes devoted to different algorithms.All algorithms were tested by means of the standard Pythonunit testing framework. Additional computer experimentswere done in order to compare real and theoreticalcomputational complexity.Two algorithms for traversing of a graph are presented:breadth-first search and depth-first search.Two algorithms for finding a topological ordering of a dagare shown.Algorithms to compute the connected components of an undirectedgraph and to compute the strongly connected componentsof a directed graph are presented.There are two algorithms for computing the transitive closureof a graph, several algorithms for a vertex coloringand for an edge coloring.There are also algorithms connected with Eulerian graphs andHamiltonian graphs.For the case of bipartite graphs, there are algorithmsfor bipartiteness testing and for finding a maximum bipartitematching: the augmenting path algorithm, the Hopcroft-Karp algorithm,and the algorithm based on the Ford-Fulkerson method. |
pl |
dc.subject.pl |
grafy, multigrafy, przeszukiwanie wszerz,przeszukiwanie w głąb, sortowanie topologiczne,składowe spójne, silnie spójne składowe,grafy dwudzielne, maksymalne skojarzenie,domknięcie przechodnie, kolorowanie grafu,grafy eulerowskie, grafy hamiltonowskie |
pl |
dc.subject.en |
graphs, multigraphs,\nbreadth-first search, depth-first search, topological sorting,\nconnected components, strongly connected components,\nbipartite graphs, maximum bipartite matching,\ntransitive closure, graph coloring,\nEulerian graphs, Hamiltonian graphs |
pl |
dc.contributor.reviewer |
Kapanowski, Andrzej [SAP11015142] |
pl |
dc.contributor.reviewer |
Marcinek, Roman [SAP11011562] |
pl |
dc.affiliation |
Wydział Fizyki, Astronomii i Informatyki Stosowanej |
pl |
dc.identifier.project |
APD / O |
pl |
dc.identifier.apd |
diploma-92185-112822 |
pl |
dc.contributor.departmentbycode |
UJK/WFAIS |
pl |
dc.area |
obszar nauk ścisłych |
pl |
dc.fieldofstudy |
informatyka stosowana |
pl |