Knowledge base: Warsaw University of Technology

Settings and your account

Back

Graph algorithms visualization

Kamil Marcin Sienkiewicz, Filip Turkot, Piotr Marek Wcisło

Abstract

This document is a bachelor's thesis on topic "Graph Algorithms Visualization". It also contains user's manual of the program and documentation on creating own visualizations. The process of development has also been described, as well as conclusions drawn from it. Graph algorithm visualization is to clearly present the graph as a set of vertices and edges, as well as calculations performed on algorithm’s data structures. One of the main goals of visualizing application is to provide a convenient way to create own visualisations. In order to do so, the program has been equipped with tools for creating graphs and storing their data in XML files. The issue of the best positioning of graph vertices has been covered in the thesis. The algorithm visualization can be performed either in a continuous way, or it can step-by-step show the operations carried out by the algorithm. Considering this feature, it can be confidently said, that prepared program can serve as a tool helpful in teaching graph algorithms. The application provides a lot of flexibility in creating own visualizations. The problem of storing arbitrary vertices’ and edges’ attributes, such as the weight and capacity, has been solved. Besides operating on graph itself, the program allows to display custom data that may help in understanding algorithm's actions, for example a it allows to display a table with priority queue. Creating own visualizations in the presented application involves implementing delivered programming interface. Besides the interface, the application has many useful functions, which are helpful in operating on a graph. As a part of the thesis, visualizations of many popular graph algorithms have been implemented: graph searching, finding the shortest path between vertices or the finding the maximum flow in a graph. The application was created using the Waterfall model. A work schedule has been prepared, based on requirements. The program was developed using Windows Presentation Foundation technology, and was written in C# 6.0 programming language. Key functionalities of the application, such as compatibility with the Graph library, by PhD Jan Bródka, were covered with unit tests to ensure reliability. The application has a set of tests graphs attached, on which program was tested thoroughly.
Diploma type
Engineer's / Bachelor of Science
Diploma type
Engineer's thesis
Author
Kamil Marcin Sienkiewicz (FMIS) Kamil Marcin Sienkiewicz,, Faculty of Mathematics and Information Science (FMIS) Filip Turkot (FMIS) Filip Turkot,, Faculty of Mathematics and Information Science (FMIS) Piotr Marek Wcisło (FMIS) Piotr Marek Wcisło,, Faculty of Mathematics and Information Science (FMIS)
Title in Polish
Wizualizacja algorytmów grafowych
Supervisor
Jan Bródka (FMIS/DACSCM) Jan Bródka,, Department of Applied Computer Science and Computation Methods (FMIS/DACSCM)Faculty of Mathematics and Information Science (FMIS)
Certifying unit
Faculty of Mathematics and Information Science (FMIS)
Affiliation unit
Department of Applied Computer Science and Computation Methods (FMIS/DACSCM)
Study subject / specialization
, Informatyka (Computer Science)
Language
(pl) Polish
Status
Finished
Defense Date
15-02-2016
Issue date (year)
2016
Reviewers
Jan Bródka (FMIS/DACSCM) Jan Bródka,, Department of Applied Computer Science and Computation Methods (FMIS/DACSCM)Faculty of Mathematics and Information Science (FMIS) Paweł Kotowski (FMIS/DACSCM) Paweł Kotowski,, Department of Applied Computer Science and Computation Methods (FMIS/DACSCM)Faculty of Mathematics and Information Science (FMIS) Paweł Kotowski (FMIS/DACSCM) Paweł Kotowski,, Department of Applied Computer Science and Computation Methods (FMIS/DACSCM)Faculty of Mathematics and Information Science (FMIS) Jan Bródka (FMIS/DACSCM) Jan Bródka,, Department of Applied Computer Science and Computation Methods (FMIS/DACSCM)Faculty of Mathematics and Information Science (FMIS) Jan Bródka (FMIS/DACSCM) Jan Bródka,, Department of Applied Computer Science and Computation Methods (FMIS/DACSCM)Faculty of Mathematics and Information Science (FMIS) Paweł Kotowski (FMIS/DACSCM) Paweł Kotowski,, Department of Applied Computer Science and Computation Methods (FMIS/DACSCM)Faculty of Mathematics and Information Science (FMIS)
Keywords in Polish
graf, wizualizacja, algorytm, C#, .NET, Windows Presentation Foundation
Keywords in English
graph, visualization, algorithm, C#, .NET, Windows Presentation Foundation
Abstract in Polish
Niniejszy dokument stanowi pracę inżynierską na temat "Wizualizacja algorytmów grafowych". Zawarto w nim również instrukcję korzystania z opracowanej aplikacji oraz dokumentację tworzenia własnych wizualizacji. Opisany został także proces tworzenia aplikacji, jak i wnioski z niego płynące. Wizualizacja algorytmu grafowego polega na czytelnym zaprezentowaniu zarówno grafu jako zbioru wierzchołków i krawędzi, jak i obliczeń wykonywanych na strukturach danych algorytmu. Celem aplikacji wizualizującej jest również zapewnienie jak największej wygody tworzenia własnych wizualizacji. Dlatego opracowany program został wyposażony w narzędzia do tworzenia grafów i przechowywania ich danych w plikach XML. W pracy poruszony został także problem automatycznego rozmieszczania wierzchołków grafu. Wizualizacja algorytmu może odbywać się w trybie ciągłym, lub krok po kroku prezentować działania wykonywane przez algorytm. Z uwagi na tę cechę można śmiało stwierdzić, że opracowany program posłużyć może za narzędzie pomocnicze w nauczaniu algorytmów grafowych. Aplikacja zapewnia dużą swobodę tworzenia własnych wizualizacji. Rozwiązany został problem przechowywania dowolnych atrybutów wierzchołków i krawędzi, takich jak waga czy pojemność. Oprócz oprerowania na samym grafie, program umożliwia wyświetlenie dowolnych danych pomagających w zrozumieniu działania algorytmu, dla przykładu pozwala na wyświetlenie tabeli z kolejką priorytetową. Tworzenie własnych wizualizacji uruchamianych w przedstawianej aplikacji opiera się na implementacji dostarczonego interfejsu programistycznego. Oprócz samego interfejsu, aplikacja dostarcza wiele funkcji pomocnych w operowaniu na grafie. W ramach pracy zaimplementowane zostały wizualizacje wielu popularnych algorytmów grafowych: przeszukiwania grafu, szukania najkrótszych ścieżek łączących wierzchołki, czy znajdowania największego przepływu w grafie. Aplikację tworzono w oparciu o model iteracyjny kaskadowy. Na podstawie przyjętych wymagań został sporządzony harmonogram prac. Przy tworzeniu aplikacji wykorzystano technologię Windows Presentation Foundation, a sam program został napisany w języku C# 6.0. Kluczowe funkcjonalności aplikacji, jak m.in. zgodność z biblioteką Graph autorstwa dr Jana Bródki, jest pokryta testami jednostkowymi w celu zapewnienia niezawodności działania. Do aplikacji dołączony jest zestaw grafów przykładowych, na których program został szczegółowo przetestowany.
File
  • File: 1
    Wizualizacja algorytmów grafowych - teskt pracy.pdf
Request a WCAG compliant version
Local fields
Identyfikator pracy APD: 9135

Uniform Resource Identifier
https://repo.pw.edu.pl/info/bachelor/WUTe85afda73d6f43ecacc13bdc4cdc68e8/
URN
urn:pw-repo:WUTe85afda73d6f43ecacc13bdc4cdc68e8

Confirmation
Are you sure?
Report incorrect data on this page