Visualisierung von Graphalgorithmen

  • Typ: Praxis der Softwareentwicklung
  • Zielgruppe: Bachelor
  • Semester: WS 22/23
  • Ort:

    nach Vereinbarung

  • Zeit:

    nach Vereinbarung

  • Beginn: 08.11.2022
  • Dozent:

    Matthias Schimek, Daniel Seemaier, Niklas Uhl

  • Hinweis:

    Erstes Treffen: 08.11. 14:00, Raum 211

Beschreibung

Viele Echtwelt-Probleme (z.B. kürzeste Wege oder Cluster finden) lassen sich als Graphen modellieren und mithilfe von Graphalgorithmen lösen. Diese Algorithmen lassen sich in der Regel auf kleinen Beispielinstanzen gut animieren, was aber oft mit viel Aufwand verbunden ist. Ziel dieses PSE ist es daher, ein Visualisierungsframework für Graphalgorithmen (auf Graphen mit gegebener Einbettung) zu entwickeln. Das entwickelte Framework soll schließlich Graphalgorithmen im Backend ausführen und die einzelnen Schritte in einem Web-Interface animiert darstellen. Der Fokus soll dabei auf einer möglichst hohe Generalität liegen, damit eine Vielzahl unterschiedlicher Algorithmen eingebunden werden kann (könnte). Zusätzlich soll es möglich sein, einzelne Frames der Animationen als Tikz-Bilder für LaTeX Dokumente zu exportieren.

 

Ziele:

  • Entwurf des Frameworks
  • Implementierung einiger Basic-Toolbox Algorithmen (z.B. BFS, Dijkstra, Flussalgorithmen, Graphfärbungsalgorithmen, Clustering Algorithmen, ...)
  • Web-Oberfläche als Frontend, Visualisierung der Graphen (muss: 2D, kann: 3D) und Algorithmenschritte
  • Tikz-Export

 

Anforderungen:

  • Interesse an Basic-Toolbox Algorithmen
  • Java, Interesse an Javascript (oder Typescript) und React


Fragen? Schreibt uns gerne eine Mail: {schimek, daniel.seemaier, uhl}@kit.edu