Da die Klasse d_array genauso wie die Klasse dictionary über Suchbäume implementiert ist, muss der Schlüsselparameter ein geordneter Typ sein.

Das Makro

forall_defined(k, D)

iteriert über alle Schlüssel k, die gerade in D enthalten sind. Dagegen iteriert das Makro

forall(v, D)

über alle Werte v, die in D enthalten sind. Es belegt die Variable v mit einer Kopie des Wertes. Die eigentlichen Werte können damit also nicht abgeändert werden; dies ist nur mit dem Operator [] und dem zugehörigen Schlüssel möglich.

Wie bei der Klasse dictionary iterieren die forall-Makros über die Schlüssel bzw. Werte in der gemäß der linearen Ordnung gegebenen Reihenfolge.

Wie kommt man von MANN zu FRAU? Für Informatiker ein Problem, das leichter zu lösen ist, als es in Wirklichkeit aussieht. Und leichter aussieht, als es in Wirklichkeit zu lösen ist. Für Informatiker, wie gesagt. In Wirklichkeit. Aber wir wollen nicht abschweifen: Eine bekannte Knobelaufgabe besteht darin, das Wort MANN in das Wort FRAU abzuleiten, und zwar so, dass in jedem Zwischenschritt ein Buchstabe durch einen anderen ersetzt werden muss, man aber immer nur zu Worten der deutschen Sprache gelangen darf. Der Start einer Ableitung könnte also so aussehen: MANN -> BANN -> BANK -> BANG -> GANG -> GANZ -> ...und da verließen sie ihn! Der Leser möge selbst versuchen, eine Lösung von Hand zu finden. Dem Autor ist es jedenfalls nicht gelungen - er hat sich nach einer geschlagenen Dreiviertelstunde daran erinnert, dass er ja Informatiker ist. Und zwar in Wirklichkeit.

Wie also lösen wir dieses Problem mit einem Algorithmus? Zunächst einmal besorgen wir uns eine möglichst lange Liste von 4-buchstabigen Worten der deutschen Sprache. Der Autor hat dazu die deutschen Wortlisten, die dem Rechschreibprüfungs-Programm International Ispell beiliegen, durch ein kleines Perl-Skript gefiltert.^[31] Das Ergebnis war eine Liste mit 1506 Worten. Diese Liste kann für eigene Experimente vom Downloadbereich des Tutoriums bezogen werden.

Wenn wir uns diese Worte alle auf ein Blatt Papier malen und Verbindungslinien zwischen je zwei Worten einzeichnen, die sich nur um einen Buchstaben unterscheiden, entsteht ein Gebilde wie in Abbildung 3.2. (Dort sind nur 35 der 1506 Worte eingezeichnet und auch nur die Verbindungen zwischen diesen.)

Abbildung 3.2. Ein Graph

Ein solches Gebilde, das aus Knoten (nodes) besteht, die durch Kanten (edges) verbunden sind, heißt Graph. Diese Struktur taucht in der Informatik häufig auf, nämlich überall dort, wo es um die Modellierung von Beziehungen zwischen einzelnen Objekten geht. Die Objekte entsprechen dabei den Knoten, die Beziehungen den Kanten eines Graphen.

Die Frage ist nun, ob es in dem Graphen von Abbildung 3.2 einen Weg vom Knoten MANN zum Knoten FRAU gibt. Wie können wir einen solchen Weg finden, bei einer so unüberschaubaren Menge von 1506 Knoten, die selbst auf einem großen Zeichenblatt nur schwer Platz findet, von der unüberschaubaren Verknäuelung der Kanten ganz zu schweigen? Vielleicht gibt es gar keinen Weg? Und wenn doch, was ist der kürzeste Weg, d. h., wie gelangen wir möglichst schnell von MANN zu FRAU, also mit möglichst wenig Zwischenschritten?

Eine möglicher Algorithmus ist der folgende: Die Grundidee ist es, vom Knoten MANN aus zunächst alle unmittelbar benachbarten Knoten zu besuchen. Dann besuchen wir von diesen aus wieder alle Nachbarn, dann deren Nachbarn usw. Hierzu arbeiten wir mit einer Schlange: Am Anfang enthält die Schlange nur den Knoten MANN. Diesen ziehen wir aus der Schlange und hängen dafür alle Nachbarn von MANN an die Schlange an. Dann nehmen wir den nächsten Knoten aus der Schlange (ein Nachbar von MANN, etwa BANN) und hängen wiederum dessen Nachbarn an die Schlange an. Doch Vorsicht! Da MANN auch ein Nachbar von BANN ist, würden wir jetzt MANN wieder an die Schlange anhängen, dann wieder herausnehmen, dann wieder anhängen usw. Wir kämen in eine Endlosschleife!

Um dies zu vermeiden, müssen wir uns merken, ob ein Knoten schon einmal in der Schlange war; wir dürfen ihn nicht ein zweites Mal anhängen. Auf dem Papier etwa könnten wir ihn bunt einfärben.

Dieser Algorithmus besucht vom Startknoten aus nacheinander alle erreichbaren Knoten. Er besucht diese in Schichten (layers): Zuerst werden die Knoten mit Abstand 1 besucht, dann die mit Abstand 2, dann die mit Abstand 3 usw. Der Abstand (distance) eines Knotens von einem anderen ist die Länge eines kürzesten Weges (shortest path), d. h. einer kleinstmöglichen Folge von Kanten, die von dem einen Knoten zum anderen führt. Der Algorithmus sucht also in die Breite, genau so, wie sich Wellen um einen ins Wasser geworfenen Stein (den Startknoten) ausbreiten. Er wird daher Breitensuche (breadth first search) genannt. Abbildung 3.3 veranschaulicht dies.

Abbildung 3.3. Breitensuche

Die einzelnen Knoten werden von MANN aus schichtweise besucht. Dadurch ergibt sich ihr Abstand zu MANN und ein Pfad zu MANN zurück.

Wenn wir nun auf diese Weise alle von MANN aus erreichbaren Knoten besucht haben, ist FRAU entweder in der Menge der besuchten Knoten, oder nicht. Falls FRAU es ist, woher kennen wir dann den Weg zu MANN zurück (oder umgekehrt)? Dazu müssen wir uns nur in dem Moment, in dem wir einen Knoten an die Schlange anhängen, merken, woher wir gekommen sind; wir müssen uns also den Vorgänger (predecessor) auf dem Weg von MANN aus merken. Auf dem Papier lässt sich das durch kleine Pfeile markieren, die zum Vorgängerknoten rückwärts gerichtet sind, s. Abbildung 3.3. Entlang dieser Pfeile können wir von jedem besuchten Knoten zurück zu MANN laufen; der sich dadurch ergebende Pfad ist ein kürzester Pfad!

Wie können wir diesen Algorithmus nun mit Hilfe von LEDA implementieren? Selbstverständlich enthält LEDA eine (überaus mächtige) Datenstruktur zur Implementierung von Graphen. Diese heißt - wie sollte es anders sein - graph; wir werden sie in Kapitel 5, Graphen und Graphenalgorithmen kennen lernen. Und selbstverständlich enthält LEDA auch den Breitensuchalgorithmus, dessen Benutzung wir ebenfalls dort kennen lernen werden. Darüberhinaus bietet LEDA sogar eine Klasse an, mit deren Hilfe Graphen visualisiert und editiert werden können, die Klasse GraphWin. Mit ihr wurde z. B. Abbildung 3.2 erzeugt.

Wir wollen an dieser Stelle aber Breitensuche einmal von Hand selbst implementieren und dabei mit den Mitteln auskommen, die wir bisher schon kennen. Das folgende Programm implementiert diesen Algorithmus mit Hilfe zweier Dictionary-Arrays und einer Schlange. Das erste d_array heißt was_in_queue und dient zwei Zielen: Wir merken uns darin, ob ein String schon einmal in der Schlange war und welche Strings es überhaupt im Graphen gibt. Das zweite heißt pred; hierin merken wir uns zu einem String den Vorgänger-String auf dem Weg zu MANN zurück. Das Programm baut den Graphen also nicht explizit als Datenstruktur auf.

Um von einem Knoten wie MANN aus alle Nachbarknoten zu finden, ersetzen wir zuerst den ersten Buchstaben (M) durch alle anderen 25 des Alphabets, dann - unter Beibehaltung des ersten M - den zweiten (A) durch alle Buchstaben, dann den dritten und zuletzt den vierten. Für jeden der so erzeugten Strings testen wir mittels der Methode defined, ob dieser String überhaupt als Knoten im Graph, sprich im Dictionary-Array was_in_queue, vorkommt. Wenn ja, so ist er ein Nachbar des ursprünglichen Strings.

Solange die Schlange nicht leer ist, ziehen wir den ersten Knoten aus der Schlange. Wenn das der gesuchte Knoten ist, hören wir auf und geben den Weg zurück zum Startknoten aus. Ansonsten hängen wir alle seine benachbarten Knoten, die noch nicht in der Schlange waren, an diese an, markieren diese als in die Schlange aufgenommen und merken uns den Weg zurück zu dem Knoten, von dem wir gekommen sind.

#include <LEDA/d_array.h>
#include <LEDA/queue.h>
#include <LEDA/string.h>
#include <istream>

using leda::d_array;
using leda::queue;
using leda::string;
using std::ifstream;
using std::cout;


int main()
{
  ifstream is("Data/German4LetterWords.txt");

  d_array<string,bool> was_in_queue;
  d_array<string,string> pred;

  string word;
  while (is >> word) 
    was_in_queue[word] = false;
  
  string from = "MANN";
  string to = "FRAU";
  
  bool found = false;

  queue<string> Q;
  Q.append(from);
  was_in_queue[from] = true;

  while( !Q.empty() && !found) {

    string s = Q.pop(); // get next node from the queue

    if(s == to) { // we have found a path
      // and output it in reverse order
      cout << "Here is a path from " << to 
           << " back to " << from << ":\n";
      string t = to;
      cout << t << "\n";
      while(t != from) {
        t = pred[t];
        cout << t << "\n";
      }
      found = true;
    }

    else // insert all not yet queued neighbours into queue
      for(int i = 0 ; i < 4 ; i++) {
        string s_adjacent = s;
        // step through all letters of the alphabet
        for(char c = 'A' ; c <= 'Z' ; c++) {
          if(c == s[i]) continue; // don't generate s itself
          // candidate adjacent word: replace letter i
          s_adjacent[i] = c;
          // is s_adjacent really adjacent and was not yet in queue?
          if(was_in_queue.defined(s_adjacent) 
             && !was_in_queue[s_adjacent]) {
            // append s_adjacent to the queue for later processing
            // mark it as queued and memorize where we came from
            Q.append(s_adjacent);
            was_in_queue[s_adjacent] = true;
            pred[s_adjacent] = s;
          }
        }      
      }
  }

  if(!found)
    cout << "No path found from " << from << " to " << to << "\n";
}

Das Programm gibt Folgendes aus:

Here is a path from FRAU back to MANN:
FRAU
TRAU
TRAN
DRAN
DRIN
DEIN
DENN
DANN
MANN

Na also! Da kann der MANN ja doch zur FRAU kommen, und der Informatiker ist sogar der schnellste, weil er den kürzesten Weg kennt!

Die Klasse d_array ist durch randomisierte Suchbäume implementiert. Sind n Schlüssel-Wert-Paare in einem d_array gespeichert, so benötigt ein Zugriff über den Operator [] Zeit O(log n). Der Platzverbrauch dabei ist O(n).

Mehr über die Klasse d_array findet sich auf der entsprechenden Manualseite.