University of Konstanz
Algorithmik
Prof. Dr. Ulrik Brandes

Einführung in die Programmierumgebung zur Vorlesung "Zeichnen von Graphen"

Informationen zur Programmierung

Die Programmbibliothek yFiles stellt für die Implementierung von Algorithmen auf Graphen 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.

GraphEditor yEd

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

    java -classpath /net/algo/software/yfiles/yfiles-2.5-complete/src/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.5-complete/src/demo/yed/yed.jar":.:$CLASSPATH
    alias yed="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.5-complete/lib/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.5-complete/lib/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 z.B. mymodule erzeugen, welche von y.module.YModule ableitet. (Geben Sie mymodule 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 mymodule;
	
	import y.base.Node;
	import y.base.Edge;
	import y.view.Graph2D;
	import y.module.YModule;
	
	public class SimpleModule extends YModule
	{
		public SimpleModule()
		{
			super("Simple module", "Juris Ozols", "Creates a graph with two nodes");
		}
		
		protected void mainrun()
		{
			Graph2D graph=this.getGraph2D();
	
			// Remove existing nodes and edges.
			graph.clear();
	
			// Create two nodes and an edge between them.
	
			Node node1 = graph.createNode();
			Node node2 = graph.createNode();
			Edge edge = graph.createEdge(node1, node2);
	
			// Draw the graph.
			
			graph.setCenter(node1, 0, 0);
			graph.setCenter(node2, 100, 100);
	
			// Center the graph in the view.
			
			graph.updateViews();
			this.fitGraph2DView();
		}
	}
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. Diese wird jedoch nicht automatisch erzeugt. Erzeugen Sie somit eine Datei entsprechenden Namens und kopieren Sie folgendstehenden Abschnitt in die Datei tools.pkg: 

	<PACKAGE name="PACKAGE_TOOLS">
		<!-- yEd built-in modules -->
		<PACKAGE name="PACKAGE_CREATE_GRAPHS">
			<MODULE name="GRID" class="yext.generator.GridGenerator"></MODULE>
			<MODULE name="TREE" class="yext.generator.TreeGenerator"></MODULE>
			<MODULE name="PLANAR" class="yext.generator.PlanarGenerator"></MODULE>
			<MODULE name="RANDOM" class="yext.generator.RandomGenerator"></MODULE>
		</PACKAGE>
		<PACKAGE name="PACKAGE_CONSTRAINTS">
			<MODULE name="PORTS" class="y.module.PortConstraintModule"></MODULE>
			<MODULE name="EDGE_GROUPS" class="y.module.EdgeGroupConstraintModule"></MODULE>
		</PACKAGE>
		<MODULE name="SELECT_ELEMENTS" class="yext.tool.GraphSelector"></MODULE>
		<MODULE name="AUTOGROUPING" class="yext.tool.AutoGrouping"></MODULE>
		<MODULE name="BROWSE_GRAPH_FILES" class="yext.tool.GraphBrowser"></MODULE>
		<MODULE name="ANALYZE_GRAPH" class="yext.tool.GraphAnalyzer"></MODULE>
		<MODULE name="CENTRALITY" class="yext.tool.CentralityTool"></MODULE>
		<MODULE name="COLORIZE_GRAPH" class="yext.tool.ColorTool"></MODULE>
		<MODULE name="REVERSE_SELECTED_EDGES" class="yext.tool.ReverseSelectedEdges"></MODULE>
		<MODULE name="LAYOUT_PARALLEL_EDGES" class="y.module.ParallelEdgeLayoutModule"></MODULE>
		<MODULE name="TRANSFORM_GRAPH" class="y.module.GraphTransformerModule"></MODULE>
		<MODULE name="ALIGN_NODES" class="yext.tool.AlignmentTool"></MODULE>
		<MODULE name="SNAP_TO_GRID" class="yext.tool.GridSnapper"></MODULE>
		<MODULE name="FIT_NODE_TO_LABEL" class="yext.tool.NodeSizeAdapter"></MODULE>
		<MODULE name="FIT_LABEL_TO_NODE" class="yext.tool.NodeLabelSizeAdapter"></MODULE>

		<!-- My modules -->
		<MODULE name="Simple" class="mymodule.SimpleModule"/>
	</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.