Einleitung

Für die Adjazenzlisten (Listen von Knoten!) verwendet Ihr natürlich Eure Listenklasse. Dabei werden für jeden Knoten die Knoten gespeichert, zu denen er eine Kante besitzt. Das bedeutet, daß jede Kante durch insgesamt zwei Einträge in Adjazenzlisten repräsentiert wird: der eine Endknoten in der Liste des anderen und umgekehrt. Beachtet das insbesondere bei der Implementation von insertEdge.

Die Methode computePath laßt Ihr zunächst (in der ersten Woche) leer:

  public Path computePath(Node n1, Node n2) { return null; }

Die Knoten beinhalten außerdem noch die Information, welche Sorte Fliese denn (gerade) ihnen jeweils entspricht. Die dazu notwendige Klasse Tile ist netterweise von uns für Euch schon geschrieben worden.

Der Zwei-Phasen-Graph

• Während des Einlesens werden zunächst nur Knoten mit Fliesentyp gespeichert, dann werden aus den Fliesentypen die Kanten berechnet und eingefügt (oder bei Datenfehler eine Meldung ausgegeben). Das bedeutet, hier darf insertEdge den Fliesentyp nicht verändern.
• Nach erfolgter Initialisierung jedoch soll der Fliesentyp immer die gerade von einem Knoten ausgehenden Kanten widerspiegeln, daher müssen jetzt insertEdge und deleteEdge den Fliesentyp immer anpassen.

Einlesen der Graphen

tile Spalte Zeile Fliesentyp [s|d]

Spalte und Zeile sind ganze Zahlen (auch negative), der Fliesentyp ist eine ganze Zahl von 1 bis 15. An jeweils genau einer Fliese der Datei steht als fünftes Token s bzw. d, was anzeigt, daß diese Fliese der Anfang (s) bzw. das Ende (d) des zu berechnenden Weges sein soll. Beispiel:

tile 50 50 9 tile 51 51 6 d tile 50 51 3 tile 51 50 12 s

Anmerkung: Da der Graph ungerichtet ist, ist es egal, ob ein Weg von s zu d oder umgekehrt berechnet wird.

Weitere Labyrinthe sind auch verfügbar.

Zulässige Labyrinthe

Beispiele:

erlaubt	verboten

Wohl erlaubt ist, daß das Labyrinth nicht zusammenhängend ist, solange keine offenen Wegstücke vorhanden sind:

Die Fliesentypen

Die Zuordnung der Fliesen läßt sich aus folgender Tabelle entnehmen:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

Ihr müßt (und sollt!) die Zuordnung von Fliesentyp zu verfügbaren Richtungen nicht selbst vornehmen, dafür gibt es in Tile schon vorgefertigt die Methoden getDirection, getDirections, setDirection und setDirections, mit denen Ihr abfragen/setzen könnt, ob es einen "Ausgang" in einer bestimmten Richtung gibt.

Die Benutzung von "leeren" Knoten für "leere" Felder ist verboten.

Einfügen der Kanten

Beim Einlesen fügt Ihr zunächst nur die Knoten in den Graphen ein (mit Koordinaten und Fliesentyp). Erst in einem weiteren Schritt werden in der Methode addEdgesAndCheckTiles, die am Ende von readFromFile aufgerufen werden soll, die Kanten erstellt.

Um zu entscheiden, ob an einem Knoten in einer bestimmten Richtung (die die Fliese angibt), eine Kante eingefügt werden soll -- oder ob gar eine unzulässige Datei vorliegt  muß man den direkt in dieser Richtung benachbarten Knoten anschauen und prüfen, ob seine Fliese eine entgegenkommende Richtung vorsieht.

Die Fliesen liegen jedoch im allgemeinen völlig durcheinander in der Knotenliste Eures Graphen, so daß man den Nachbar anhand seiner Koordinaten erstmal suchen müßte, was uns mit O(#Anzahl Knoten) zu lange dauert.

Deshalb sollt Ihr eine etwas fortgeschrittene Methode einsetzen, bei der zuerst alle waagerechten Kanten und dann alle senkrechten Kanten eingefügt werden:

1. Zunächst wird mit sortNodesRowThenColumn die Knotenliste des Graphen so sortiert, daß alle Knoten einer Zeile von links nach rechts hintereinander liegen. Erreicht wird dies durch Euren Mergesort, dem ein entsprechender Comparer gegeben wird, der eine lexikographische Ordnung auf den Knoten vorgibt, bei der der Zeilenindex Vorrang hat vor dem Spaltenindex.
2. Wenn Ihr jetzt die Knotenliste von vorne an durchlauf, erfolgt der Durchlauf im wesentlichen zeilenweise. Da natürlich alle Zeilen hintereinander in der Liste liegen, müßt Ihr aufpassen, wann Ihr eine neue Zeile betretet.

   In jeder Zeile ist es jetzt einfach zu überprüfen, ob zwei hintereinanderliegende Fliesen zueinander passen. Wenn ja, fügt eine Kante zwischen ihren Knoten ein, wenn nein, gebt eine Fehlermeldung aus. Beachtet, daß Ihr den ersten und letzten Knoten jeder Zeile gesondert betrachten müßt, da es ja sein könnte, daß er verbotene "in der Luft hängende" Ausgänge nach außen hat. Beachtet auch, daß bei "Löchern" in einer Zeile die Knoten links und rechts eines Loches zwar hintereinander in der Liste liegen, aber keinesfalls verbunden werden dürfen.

3. Jetzt wird das ganze mit den Spalten gemacht. Sortiert also die Knotenliste lexikographisch mit Spalte hat Vorrang vor Zeile (sortNodesColumnThenRow).
4. Nun durchlauft ganz analog zum zweiten Punkt die Liste spaltenweise und prüft hintereinanderliegende Fliesen und fügt ggf. senkrechte Kanten ein.

Beachtet: Innerhalb von addEdgesAndCheckTiles darf nicht findNode. Zum Testen schenken wir Euch ein toString für den Graphen:

  /**
   * Convert whole graph to textual representation.
   *
   * @return string.
   */
  public String toString()
  {
    StringBuffer sb = new StringBuffer();
    Node n1, n2;
    ListWithPointer nodes = getNodes(), adjacentNodes;
    
    for(nodes.reset(); !nodes.atEnd(); nodes.advance())
      {
	n1 = (Node)nodes.getCurrent();
	sb.append(n1 + " adjacent nodes: ");
	adjacentNodes = n1.getAdjacentNodes();
	for(adjacentNodes.reset(); !adjacentNodes.atEnd(); adjacentNodes.advance())
	  {
	    n2 = (Node)adjacentNodes.getCurrent();
	    sb.append(n2 + " ");
	  }
	sb.append("\n");
      }
    return sb.toString();
  }

Mit einem einfachen main läßt sich dann ein Graph einlesen, aufbauen und ausgeben:

  /**
   * This is just for debugging.
   *
   * @param argv first argument has to be a filename.
   */   
  public static void main(String[] argv)
  {
    LabyrinthGraph G = null;

    if(argv.length != 1)
      {
	System.err.println("Filename as argument expected!");
	return;
      }
    try
      {
	G = new MyGraph(argv[0]);  // Read graph. Use your class name!
      }
    catch(IOException e)
      {
	System.err.println("IOException: " + e.getMessage());
	return;
      }
    catch(LabyrinthException e)
      {
	System.err.println("LabyrinthException: " + e.getMessage());
	return;
      }
    
    System.out.println(G);  // toString() is your friend.
  }

So, das war der Teil der ersten Woche. Und nicht vergessen: Es sieht schlimmer aus als es ist.

Wege suchen

Ein Weg im Graphen zwischen den als Start und Ziel ausgezeichneten Knoten -- so einer überhaupt existiert -- läßt sich nun sehr leicht rekursiv über Tiefensuche (DFS - Depth First Search) finden. Es genügt uns, wenn computePath irgendeinen Weg zwischen diesen Knoten zurückliefert, er muß weder kurz noch schön sein.

Visualisierung des Labyrinths

Der LabyrinthViewer wird wie jede andere Component in Euer Fenster per add eingefügt. Der anzuzeigende Graph mit/ohne Weg wird dann per setLabyrinth gesetzt. Das Malen geschieht dann automatisch.

Da ein neuer mit setLabyrinth gesetzter Graph eine andere Ausdehnung als der alte haben, paßt sich der LabyrinthViewer automatisch in der Größe an. Dafür muß sich allerdings auch die Fenstergröße ändern, weshalb Ihr direkt nach dem Aufruf von setLabyrinth einmal die pack Methode Eures Frames aufrufen solltet:

    setLayout(new BorderLayout());
    add("Center", viewer = new LabyrinthViewer());
    .
    .
    .
    viewer.setLabyrinth(graph, path);
    pack();

Ihr sollt eine Menüzeile vorsehen, in deren "File"- (oder "Datei"-)Menü sich ein Punkt zum Laden eines neuen Labyrinths befindet (über einen FileDialog).

Per Maus das Labyrinth ändern

Zum Abfragen der Mausklicks könnt Ihr ganz analog zum bekannten ActionListener einen LabyrinthClickListener mit addLabyrinthClickListener beim LabyrinthViewer installieren.

    viewer.addLabyrinthClickListener(new LabyrinthClickListener() {
      public void actionPerformed(LabyrinthClickEvent e)
	{
	  handleClick(e);
	}
    });

Bei geeignetem Mausklick wird dann das actionPerformed des Listeners aufgerufen. Übergeben wird ihm dabei ein LabyrinthClickEvent-Objekt, das die Koordinaten der Fliese enthält und den Bereich der Fliese, auf den geklickt wurde (getPart).

Jetzt gilt es herauszufinden, ob sich an dieser Stelle bereits eine Kante befindet, und wenn ja, welche. Beachtet, daß Ihr ggf. neue Knoten erzeugen müßt, wenn der Benutzer eine Kante irgendwo haben möchte, wo noch nicht ein oder gar beide Endknoten existieren. Ebenso sollt Ihr einen Knoten löschen, wenn er keine zu ihm inzidende Kante mehr besitzt (also seine Adjazenzliste leer ist). Das gilt nicht für den Start- bzw. Endknoten, diese müssen immer existieren.

Das angezeigte Labyrinth soll stets im obigen Sinne zulässig sein, es darf keine "in der Luft hängende" Wegstücke geben. Spätestens hier wird Euch auffallen, wenn Eure Routinen zum Einfügen und Löschen von Kanten nicht dafür sorgen, daß die Fliesen der Knoten immer auf dem neuesten Stand sind.

Wer Lust hat, kann jetzt noch eine Speicherroutine einbauen und hat einen praktischen Labyrintheditor, um den ihn jeder beneiden wird.

Wir wünschen Euch viel Spaß und vor allem viele lehrreiche Momente mit dieser Programmieraufgabe.

Ressourcen

• Das labyrinth-Package
• Mergesort-Implementation
• Dokumentation des labyrinth-Packages
• Beispiellabyrinthe

Alexander Schwartz Olaf Jahn Last modified: Tue Apr 25 17:23:34 MET DST 2000