Theta-Graphen – Ausarbeitung und Java Implementierung

Im Rahmen des Informatik-Proseminars Graphen und Netzwerke an der Technischen Universität Dortmund habe ich mich mit Theta-Graphen beschäftigt. Dabei sind eine Seminarausarbeitung und ein Java-Programm zum Thema entstanden, die im Folgenden zum Download bereitstehen.

Grundidee

Der Grundgedanke von Theta-Graphen basiert auf einem trivialen Ansatz zur Wegfindung. Wenn sich jemand, z. B. im Autobahnnetz von Deutschland, von einem Startpunkt zu einem Zielpunkt bewegen möchte, ohne den Weg zu kennen, könnte er folgendermaßen vorgehen:

  • Ausgehend von seinem aktuellen Aufenthaltsort ermitteln, welche Autobahn in Richtung seines Zieles führt.
  • Diese soweit fahren, bis die Möglichkeit besteht, die Autobahn zu wechseln.

Er könnte dieses Vorgehen solange wiederholen, bis er an seinem Ziel angekommen ist.

Ausarbeitung

In diesem Aufsatz werden die theoretischen Grundlagen und die Algorithmen zur Konstruktion von Theta-Graphen vorgestellt. Die theoretischen Überlegungen in diesem Aufsatz basieren zu großen Teilen auf dem vierten Kapitel von “Giri Narasimhan und Michiel Smid: Geometric Spanner Networks. Cambridge University Press, 2007″.

Download: Seminarausarbeitung – Konstruktion von t-Spannern mithilfe von Theta-Graphen

Java-Programm – “TGT – Theta-Graph Toolkit”

Um die theoretischen Überlegungen zu veranschaulichen und die Laufzeitbetrachtungen zu verifizieren, ist das “Theta-Graph Toolkit” entstanden. Dabei handelt es sich um ein Java-Programm, mit dem es möglich ist, Graphen visuell darzustellen, zu bearbeiten und als Bild zu exportieren. Darüber hinaus fasst das Programm statistische Informationen des Graphen zusammen. Die Hauptfunktion des Programms liegt in der Konstruktion von Theta-Graphen. Es ist möglich, die in der Seminarausarbeitung beschriebenen Algorithmen MinAbove und BuildGraph auf beliebige Graphen anzuwenden. Dabei besteht unter anderem die Möglichkeit, die Algorithmen schrittweise ablaufen zu lassen, um so die einzelnen Operationen besser nachvollziehen zu können. Des Weiteren können die Laufzeit von BuildGraph automatisiert gemessen und die Ergebnisse exportiert werden. Das “Theta-Graph Toolkit” darf nach den Bedingungen der “GNU General Public License” verwendet werden.

Download: TGT – Theta-Graph Toolkit 1.0 Jar-Datei

Download: TGT – Theta-Graph Toolkit 1.0 Sourcecode

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>