University of Konstanz
Algorithmik
Prof. Dr. Ulrik Brandes

Projektpraktikum Sensor- und Ad Hoc-Netzwerke

Wichtige Informationen zur Programmierung

Ziel des Praktikums ist es, Algorithmen auf Graphen zu implementieren. Die Programmbibliothek yFiles stellt dafür notwendige Grundfunktionen zur Verfügung, z.B. eine Implementierung der Graph Datenstruktur Graph2D. Sofern es möglich ist, sollten Datenstrukturen immer der yFiles-Bibliothek entnommen werden. Weitere Bibliotheken, welche je nach Thema Anwendung finden, sind z.B. or (lineare Programmierung) und mtj (lineare Algebra). Alle Implementierungen werden in der Programmiersprache JAVA durchgeführt.

Verzeichnisorganisation und CVS

Legen Sie ein Verzeichnis an, in welchem Sie alles, was zum Praktikum gehört, ablegen. Dieses Verzeichnis wird im Folgenden das Praktikumsverzeichnis genannt. In diesem Verzeichnis wird der Verzeichnisbaum angelegt, der unter der Kontrolle des CVS steht. Das geht wie folgt:

Sie müssen CVS mitteilen, wo sich das Archiv, das Sie benutzen, befindet. Fügen Sie dazu in der Datei ~/.bashrc.<username> die Zeile export CVSROOT=/net/algo/cvs ein. (<username> bezeichnet Ihren maximal 8-stelligen Usernamen.) Öffnen Sie eine neue Shell und arbeiten Sie in dieser weiter.

Wechseln Sie jetzt in das Praktikumsverzeichnis und führen dort das Kommando cvs checkout lehre/ws05/pp aus.

Wenn alles fehlerfrei ablief, wurden im Praktikumsverzeichnis einige Unterverzeichnisse und eine Datei lehre/ws05/pp/README angelegt, in der die Verzeichnisstruktur erklärt wird. Das Verzeichnis lehre/ws05/pp/ wird im Folgenden Quellverzeichnis genannt. Erzeugen Sie im Quellverzeichnis ein Unterverzeichnis mit dem Namen <username>, in dem Sie alle Ihre .java Quelldateien ablegen. Stellen Sie diese unter die Kontrolle des CVS. Wichtige Kommandos sind dabei:

Hilfe gibt es mit dem Kommando cvs --help bzw. cvs --help-commands. Ein sehr ausführliches Tutorial ist die CVS Dokumentation.

GraphEditor YEd

Der GraphEditor YEd ist eine Anwendung zum Anzeigen und Editieren von Graphen. Gestartet wird der GraphEditor mittels folgender Eingabe in der Shell: 

    /net/lin_local/java/j2sdk1.4.2/bin/java -classpath /net/algo/software/yfiles/yfiles-2.3.0.3-complete/demo/yed/yed.jar:. yed.Launcher
Um dies zu vereinfachen, fügen Sie folgende Zeilen in die Datei ~/.bashrc.<username> ein: 
    export CLASSPATH="/net/algo/software/yfiles/yfiles-2.3.0.3-complete/demo/yed/yed.jar":.:$CLASSPATH
    alias yed="/net/lin_local/java/j2sdk1.4.2/bin/java yed.Launcher&"
Öffnen Sie eine neue Shell und starten Sie YEd nun mit yed.

Generell sollten sie alle Programme mit dem Klassenpfad 

     /net/algo/software/yfiles/yfiles-2.3.0.3-complete/y.jar:.
kompilieren. Fügen Sie also am besten der Datei ~/.bashrc.<username> eine weitere Zeile hinzu: 
    export CLASSPATH="/net/algo/software/yfiles/yfiles-2.3.0.3-complete/y.jar":$CLASSPATH
Außerdem ist es vorteilhaft, das Quellverzeichnis in den Klassenpfad mit aufzunehmen, damit YEd die von Ihnen erzeugten Klassen immer findet.

Falls Sie die Bibliotheken or oder mtj benötigen, nehmen Sie die entsprechenden Dateien in den Klassenpfad mit auf. 

    /net/algo/software/or/or124.jar
    /net/algo/software/mtj/mtj.jar

YEd kennt sogenannte Module. Module sind über den Menüeintrag Tools (Werkzeuge) erreichbar. Ihre Klassen sollen von einem Modul aus aufgerufen werden.

Modul Programmierung

Die Klasse y.module.YModule ist die abstrakte Basisklasse für YEd Module. Um ein eigenes Modul zu schreiben, müssen Sie Folgendes tun:

  1. Eine Klasse im Unterverzeichnis <username> erzeugen, welche von y.module.YModule ableitet. (Geben Sie <username> als package Namen dieser Klasse an.)
  2. Einen Konstruktor in dieser Klasse definieren, welcher keine Argumente entgegennimmt.
  3. Die Methode mainrun() überschreiben.
Die Klasse sieht dann beispielsweise so aus: 
    package <username>;
    import java.io.*;
    import y.base.*;
    import y.module.YModule;
    import y.view.Graph2D;

    public class HelloWorldModule extends YModule {

      public HelloWorldModule() {
        super("","","");
      }
  
      protected void mainrun() {
        Graph2D G=getGraph2D();
        System.out.println("Hello World");
      }
    }
Jedes Modul besitzt eine Referenz auf den Graphen, der gerade im YEd dargstellt wird. Auf diesen Graphen kann über getGraph2D() zugegriffen werden.

Graphen

Die grundlegensten Eigenschaften von Graphen sind in der Klasse y.base.Graph definiert. Knoten im Graphen werden mit der Methode createNode() erzeugt, Kanten mit der Methode createEdge(Node u,Node v). Knoten werden mit der Methode removeNode(Node v) aus einem Graphen entfernt, Kanten mit der Methode removeEdge(Edge e).

Module Deklarieren

Damit YEd auf neue Module zugreifen kann, müssen diese deklariert werden. Module, die unter Tools (Werkzeuge) in YEd ansprechbar sein sollen, werden in der Datei tools.pkg im Verzeichnis ~/.yed deklariert (dies wird nach dem ersten Aufruf von YEd automatisch erzeugt). Diese Datei sieht beispielsweise folgendermaßen aus: 

    <PACKAGE name="Tools">
      <PACKAGE name="pp">
      <MODULE name="Create unit disk graph" class="<username>.CreateUDGModule"></MODULE>
      <MODULE name="Compute coordinates" class="<username>.CompCoordsModule"></MODULE>
      <MODULE name="Routing algorithm" class="<username>.RoutingModule"></MODULE>
      <MODULE name="Test suite" class="<username>.TestSuiteModule"></MODULE>
      </PACKAGE>
    </PACKAGE>

Programme Dokumentieren

Alle Klassen, die Sie schreiben, müssen dokumentiert werden. Dies soll zum Einen die Verwendbarkeit der Programme gewährleisten (Wie werden Methoden aufgerufen? Was berechnen die Methoden? Wie hängen die einzelnen Klassen zusammen?), zum Anderen soll der Programmcode verständlich und nachvollziehbar gemacht werden. Das zweite Ziel wird durch Kommentare im Quellcode (z.B. Zeilen, die mit // beginnen) erreicht. Zum ersten Punkt wird das Tool javadoc empfohlen. Wie dieses verwendet wird, wie Kommentare geschrieben werden, und vieles mehr steht auf der Javadoc Tool Home Page.