lgorith
an.de
Ein Open Source
Graphentheorie
Framework für
C++, das ich (alleine) entwickelt habe.
Der Fokus liegt auf der Implementierung komplexer Optimierungs-Verfahren (Verzweigungs-Vektor
Minimierung, Problemkern-Reduktionen, Früherkennung von suboptimalen Kandidaten,
Früherkennung von Sackgassen, etc.)
mit denen auch für algorithmisch schwere Probleme gute Laufzeiten erreicht werden.
Es beinhaltet
Es beinhaltet
- Hoch optimierte Algorithmen für diverse NP-vollständige Probleme
Clique, Coloring, Dominating Set, Independent Set, Vertex Cover - Algorithmen für diverse polynomielle Probleme
Max-Flow, Min-Cut, Maximum Matching, Kürzeste Wege - Einen handgeschriebenen XML Parser
- Grafische Darstellung in einem handgeschriebenen (low-level) X11 Fenster, das Nicht-Blockierend arbeitet und Double-Buffering verwendet
- Solver für First Order Prädikatenlogik, Modal Logik und Computation Tree Logic
- Import- und Export Filter für alle gängigen Dateiformate für Graphen
gxl, dot, gastex, gml, graphml, rgml, tei, tgf, vrmlgraph, xgmml - Export Filter für einige Grafik-Formate
pdf, ps, svg, metapost, povray, tikz - Einen Spring-Embedder
Meine Lösung für das bekannte
Einstein-Rätsel.
(Eigentlich ist das das Zebrarätsel
und hat überhaupt nichts mit Einstein zu tun...)
So habe ich es manuell gelöst und dann dieses Javascript geschrieben, das das Problem genau so löst. Graphentheoretisch ausgedrückt, konstruiert es einen Graphen für das Problem und zerlegt diesen in 5 Cliquen der Größe 5 und nutzt dabei hauptsächlich aus, dass die Kantenrelation in Cliquen transitiv ist.
So habe ich es manuell gelöst und dann dieses Javascript geschrieben, das das Problem genau so löst. Graphentheoretisch ausgedrückt, konstruiert es einen Graphen für das Problem und zerlegt diesen in 5 Cliquen der Größe 5 und nutzt dabei hauptsächlich aus, dass die Kantenrelation in Cliquen transitiv ist.
22 KiB
Berechnet offene oder geschlossene Springerzüge
(Graphentheoretisch ausgedrückt, sucht es Hamiltonkreise
bzw. Hamiltonpfade in Springergraphen).
Mit Hilfe von Warnsdorffs Heuristik und Erreichbarkeits-Analysen (mit denen verhindert wird, dass Schnittknoten im Springergraphen zu früh verwendet werden) wird die Laufzeit deutlich verbessert.
Mit Hilfe von Warnsdorffs Heuristik und Erreichbarkeits-Analysen (mit denen verhindert wird, dass Schnittknoten im Springergraphen zu früh verwendet werden) wird die Laufzeit deutlich verbessert.
108 KiB
Es ist zwar nichts Anderes als der
Dijkstra Algorithmus,
den ich natürlich auch im Open-Graphtheory.org
Projekt implementiert habe, aber ich kann mich trotzdem nicht davon trennen... Dafür bin
ich einfach zu stolz darauf, den Algorithmus schon in der Schulzeit selbst entwickelt zu
haben.
29 KiB
Ein Programm, das (per Backtracking) Damen auf einem Schachbrett so verteilt, dass
jedes Feld bedroht ist. Graphentheoretisch ausgedrückt, sucht es
Dominanzmengen
in Queen-Graphen.
Generiert in nur O(n²) Schritten Spielpläne für Turniere.
Dazu verwendet es die 1-Faktorisierung von vollständigen Graphen
nach Kirkman und Reiß (Satz 7.14 auf Seite 129 in
Graphen
an allen Ecken und Kanten von Professor Lutz Volkmann).