Proponowane tematy prac magisterskich

Poniższe propozycje mają za zadanie wytworzenie bibliotek, które będą mogły być wykorzystane przez kolejne roczniki magistrantów. Co za tym idzie, oprócz kodu wymagana będzie również przyzwoita dokumentacja; oczekuję również, że wyniki pracy zostaną udostępnione na jednej z wolnych licencji (np. LGPLv3).

Boost Graph Library: backtracking

BGL zawiera standardowe implementacje grafów (lista sąsiedztwa, macierz sąsiedztwa) z możliwością zapamiętywania w wierzchołkach i krawędziach dodatkowych danych. Implementacje te należy rozszerzyć o możliwość zapamiętywania aktualnego stanu grafu, i późniejszego powrotu do niego. Innymi słowy, należy zaimplementować funkcjonalność SQL-owych transakcji (START TRANSACTION, ROLLBACK, COMMIT).

Następnie w oparciu o powyższy mechanizm zaimplementować proces generowania kolejnych słów języka zdefiniowanego przez gramatykę grafową.

Wymagania: umiejętność opracowywania nowych struktur danych i algorytmów, dobra znajomość technik programowania uogólnionego w C++.

Boost Graph Library: hipergrafy, grafy hierarchiczne

BGL obsługuje tylko zwykłe grafy. O ile mi wiadomo, podejmowano próby zaimplementowania obsługi hipergrafów, ale nie doprowadzono ich do końca. Magistrant będzie musiał zapoznać się z tymi poprzednimi pracami, a następnie w oparciu o wyciągnięte z nich wnioski opracować swój projekt dodania hipergrafów do BGL. A na koniec go zaimplementować, ale to chyba oczywiste.

W naszym zakładzie często wykorzystujemy też grafy hierarchiczne. Należy je zaimplementować jako szablon-nakładkę na zwykłe grafy, wykorzystującą jeden z atrybutów do pamiętania które wierzchołki i krawędzie są w czym zagnieżdżone. W kodzie powinny znaleźć się testy zapewniające poprawność hierarchii (brak pętli).

Wymagania: umiejętność opracowywania nowych struktur danych i algorytmów, dobra znajomość technik programowania uogólnionego w C++.

Algorytm rysowania hipergrafów hierarchicznych

W literaturze znaleźć można bardzo wiele algorytmów rysowania grafów na płaszczyźnie. Zadaniem magistranta będzie wykonanie kwerendy w poszukiwaniu algorytmu potrafiącego poradzić sobie z przypadkiem hipergrafów, których wierzchołki i krawędzie mogą być zagnieżdżone wewnątrz innych wierzchołków i krawędzi, a następnie zaimplementowanie go. Jeśli odpowiedniego algorytmu nie da się znaleźć w literaturze, trzeba go będzie samodzielnie wymyślić.

Stworzona aplikacja powinna pobierać na wejściu definicję grafu, i produkować na wyjściu jak najładniej narysowany graf. Mile widziana będzie obsługa wielu formatów wyjściowych: PNG, EPS, LaTeX, plik tekstowy z listą współrzędnych. Dane wejściowe mogą zawierać informacje o wymiarach poszczególnych wierzchołków.