Wer schon einmal eine Sitzordnung für eine Hochzeit oder Familienfeier erstellen musste weiß: nichts modeliert das komplizierte Beziehungsgeflecht der Verwandschaft und Freundeskreise so gut wie ein gewichteter Hypergraph. Bei der Zuweisung der Tische möchte man die vorhanden Freundeskreise natürlich nicht trennen, damit jeder ihm/ihr angenehme Tischgenossen hat. Hierzu drängt sich Hypergraph-Partitionierung gerade zu auf.

 

Ein Hypergraph ist eine Menge an Knoten und Kanten, bei der jede Kante, im Gegensatz zu normalen Graphen, mehr als zwei Knoten verbinden kann. Eine Hypergraph-Partitionierung zerteilt die Knotenmenge in disjunkte Teilmengen, so dass die Summe der geschnittenen Kanten entlang der Partitionsgrenzen minimal ist und jede Teilmenge ungefähr die gleiche Größe besitzt.

 

Oder anders ausdrückt: sodass alle Studienfreunde bei der Hochzeit an einem Tisch sitzen und sich nicht die eine Hälfte den Tisch mit den Tanten zweiten Grades der Braut teilt und die andere Hälfte zusammen mit dem Kegelclub des Bräutigam Vaters sitzt.

 

Mit KaHyPar haben wir das momentan weltweit führende Hypergraph-Partitionierungstool an unserem Lehrstuhl entwickelt und es hat sich in der Praxis bereits bei der Lagerplanung, Schaltkreisoptimierung und eben Hochzeitssitzplanung bewährt. Um diese Kernkomponente soll eine Anwendung entstehen, die es für Hochzeiten oder Partys ermöglicht, komplexe Beziehungsgeflechte einfach und schnell zu modellieren und die Aufgabe einer optimalen Sitzplatzzuweisung der Gäste übernimmt.

 

 

 

 

Im Rahmen des PSE soll eine Webapplikation zur Hochzeitssitzplanung entwickelt werden. Dies umfasst:

 

• Model: Entwurf eines relationalen Datenbankmodels (SQL) zur Pflege von:

1.   Tischformen und Tischanordnungen
2.   Beziehungsgeflechten zwischen Gästen
3.   Hochzeit/Party Gästen

• View: Entwicklung einer responsive HTML5 Webapplikation die es dem Benutzer erlaubt:

1.   Die berechnete Sitzplatzzuweisung in einer verständlichen Form präsentiert
2.   Die Tischformen und Tischanordnungen zu verwalten und zu repräsentieren
3.   Auf intuitive Weise seine Hochzeits-/Partygäste und die Beziehungen untereinander zu modellieren und zu pflegen.

• Controlling: 

1. Finden einer geeigneten Parameterisierung unseres Hypergraph-Partitionierungstool, um KaHyPar für den Anwendungsfall zu optimieren.
2. Implementierung einer Python-Serverapplikation zur Transformation des Modells in einen Hypergraphen und zur Berechnung der optimalen Sitzplatzzuweisung mit Hilfe des Python-Interface von KaHyPar.

 

Mögliche Erweiterungen der Kernfunktionalität umfassen:

 

• Modelierung von negativ Beziehungen der Gäste, sodass zerstrittene Expartner nicht an einem Tisch landen.
• Einbeziehung der räumlichen Anordnung der Tische. Freunde die an verschiedenen Tischen Rücken an Rücken sitzen können sich besser unterhalten als wenn sie durch den ganzen Saal schreien müssen.
• Einbeziehung besonderer Tischformen wie Tafel oder U-Form.

 

• Frontend: HTML5, CSS, JavaScript
• Backend: Python, SQL