===== BWInf 2012 - Graphenzeichnen =====

Hier gibt's reichlich Material zum Projekt //Graphenzeichnen// beim [[http://ls2-www.cs.tu-dortmund.de/bwinf/|BWInf 2012 Workshop]].

==== Projektleiter ====

  * [[staff:gutwenger|Dr. Carsten Gutwenger]]
  * [[staff:klein|Dr. Karsten Klein]]


==== Sugiyama-Verfahren ====

In diesem Workshop beschäftigen wir uns mit dem Zeichenverfahren von Sugiyama, dem Klassiker zum Zeichnen von hierarchischen Graphen.
Eine gute Einführung dazu findet sich in der Vorlesung //[[http://ls11-www.cs.tu-dortmund.de/people/wong/lehre2007/gd2007.jsp|Automatisches Zeichnen von Graphen]]// von Prof. Mutzel.
Insbesondere ist hier folgendes Material dieser Vorlesung interessant:

  * Vorlesung **[[http://ls11-www.cs.tu-dortmund.de/people/wong/lehre2007/SugiyamaLayerWeb.pdf|Sugiyama]]**\\ Eine allgemeine Einführung zum Sugiyama-Verfahren, sowie Methoden zur Schichtung des Graphen.

  * Vorlesung **Kreuzungsminimierung** [[http://ls11-www.cs.tu-dortmund.de/people/wong/lehre2007/CrossMinGDWeb_Teil1.pdf|Teil 1]] und [[http://ls11-www.cs.tu-dortmund.de/people/wong/lehre2007/CrossMinGDWeb_Teil2.pdf|Teil 2]]\\ Heuristiken zur 2-Schichten Kreuzungsminimierung.
 
  * **[[http://ls11-www.cs.tu-dortmund.de/people/wong/lehre2007/schichten.pdf|Skript]]** zum Sugiyama-Verfahren\\ Hier wird das gesamte Verfahren nochmal kurz zusammengefasst.


==== OGDF ====

Wir verwenden in diesem Workshop die OGDF-Bibliothek, also das //Open Graph Drawing Framework//. Infos zu OGDF findet ihr hier:

  * [[http://www.ogdf.net|Homepage]] von OGDF.
  * [[http://www.ogdf.net/doku.php/tech:overviews|Überblick der wichtigsten Datenstrukturen]]
  * Beispiele zur Anwendung des Sugiyama-Layouts: [[http://www.ogdf.net/doku.php/tech:howto:hierl|Beispiel 1]], [[http://www.ogdf.net/doku.php/tech:howto:hierlr|Beispiel 2]]
  * [[http://www.ogdf.net/doku.php/tech:devres|Infos für Entwickler]], insbesondere die Referenz-Dokumentation der OGDF-Entwicklerversion.


=== Erstellen von neuen Projekten ===

  * C++ / Allgemein / Zusätzliche Includeverzeichnisse: ''C:\Users\BWInf\Documents\OGDF''
  * C++ / Präprozessor / Präprozessordefinitionen: ''OGDF_OWN_LPSOLVER'' (bei Debug zusätzlich ''OGDF_DEBUG'')
  * Linker / Eingabe / Zusätzliche Abhängigkeiten: ''ogdf.lib; Psapi.lib''
  * Linker / Allgemein / Zusätzliche Bibliotheksverzeichnis: ''C:\Users\BWInf\Documents\OGDF\Win32\Debug'' bzw. ''C:\Users\BWInf\Documents\OGDF\Win32\Release''
==== Benchmark-Set ====

Zum Testen eurer Implementierungen könnt ihr die folgende Benchmark-Set benutzen. Sie enthält 1214 Graphen im GML-Format mit 20 bis 100 Knoten.

  * [[http://ls11-www.cs.tu-dortmund.de/people/gutweng/BWInf-Bench.zip|BWInf-Bench.zip]]


==== Visualisierung ====

  * [[http://ls11-www.cs.tu-dortmund.de/people/gutweng/gde-win.exe|GDE Graph-Editor]] (erfordert Admin-Rechte zur Installation)