Die Klassen node_array und edge_array und deren Benutzung haben wir schon in Abschnitt 5.2.1 kurz vorgestellt. Diese Klassen erlauben es, zu den Knoten bzw. Kanten eines Graphen zusätzliche Informationen zu assoziieren. Wir werden im Folgenden nur von Knoten-Arrays reden; alles Gesagte gilt entsprechend für Kanten-Arrays.

Die Definitionen

node_array<I> A(G);
node_array<I> B(G,x)

erzeugen zwei Knoten-Arrays A und B, die zu jedem Knoten des schon fertig aufgebauten Graphen G einen Wert vom Typ I assoziieren. Im ersten Fall wird jedem Knoten der Default-Wert des Typs I zugewiesen, im zweiten Fall der explizit angegebene Wert x.

Der Zugriff auf einen zu einem Knoten v assoziierten Wert geschieht über den Subskript-Operator, der wie immer eine Referenz auf den entsprechenden Wert liefert:

A[v] = y;

Knoten- und Kanten-Arrays bieten eine sehr flexible Möglichkeit, zu den Knoten und Kanten eines Graphen eine Information zu assoziieren: Es können auf einem vorgegebenen Graphen beliebig viele solcher Arrays zu einem beliebigen Zeitpunkt der Ausführung definiert werden. Allerdings muss der Graph G zum Zeitpunkt der Definition feststehen. Nur für die zu diesem Zeitpunkt in G enthaltenen Knoten ist das Knoten-Array gültig:

Warnung

Werden nochmals Knoten bzw. Kanten zu einem Graphen hinzugefügt, auf dem schon ein Knoten- bzw. Kanten-Array definiert ist, so erweitert sich die Indexmenge dieses Arrays nicht um diese Knoten bzw. Kanten! Eine Anweisungsfolge wie die folgende erzeugt daher eine Fehlermeldung: node_array<int> dist(G); node v = G.new_node(); dist[v] = 42; Hier ist eher die Verwendung eines GRAPH oder einer node_map sinnvoll.

In manchen Fällen weiß man, dass der Graph G niemals mehr als n Knoten enthalten wird, und dass dieses n nicht sehr groß ist. Dann lohnt sich möglicherweise folgender Konstruktor von node_array:

node_array<I> A(G, n, x);

Hier wird im Knoten-Array a priori Platz für insgesamt n Knoten geschaffen, und der zu jedem Knoten assoziierte Wert auf x gesetzt. Ist m die aktuelle Anzahl von Knoten in G zum Zeitpunkt dieser Definition, so muss dabei natürlich n >= m gelten, und insgesamt dürfen nur noch n-m neue Knoten zu G hinzugefügt werden, ohne dass das Knoten-Array ungültig wird.

Wie schon gesagt, können auf einem Graphen G beliebig viele Knoten- und Kanten-Arrays definiert werden. Anstatt nun viele verschiedene Knoten- und Kanten-Arrays zu definieren, erweist sich oft die folgende Alternative als effizienter, die anwendbar ist, wenn die Anzahl der zu definierenden Arrays a priori bekannt ist: Angenommen, es werden insgesamt n_slots viele Knoten-Arrays und e_slots viele Kanten-Arrays benötigt. Dann erzeugt der Konstruktor

graph G(n_slots, e_slots);

der Klasse graph einen Graphen, bei dem die internen Strukturen zur Darstellung eines Knotens bzw. einer Kante Platz für zusätzliche Einträge (so genannte „Slots“) aus n_slots vielen Knoten-Arrays bzw. e_slots vielen Kanten-Arrays enthalten. (Die genaue interne Darstellung und die Art der Indirektion beim Zugriff soll hier nicht weiter von Interesse sein.) Um diese zusätzlichen Einträge für ein bestimmtes Knoten-Array A nutzen zu können, muss dieses wie folgt angelegt werden:

node_array<I> A;
A.use_node_data(G, x);

Dies reserviert einen der Slots für A und initialisiert alle Einträge des Arrays mit x. Ist kein Slot mehr verfügbar, wird A als gewöhnliches Knoten-Array angelegt.

Diese nächste Möglichkeit, um eine Information zu Knoten und Kanten zu assoziieren, eignet sich vor allem für dynamische Graphen, d. h. für Graphen, in denen oft und zu nicht vorhersehbaren Zeitpunkten Knoten und Kanten hinzugefügt oder gelöscht werden.

Von der Klasse graph im Sinne von C++ abgeleitet ist die Klasse GRAPH zur Realisierung so genannter parametrisierter Graphen. Parametrisiert bedeutet hier, dass zu jedem Knoten und zu jeder Kante ein Wert eines bestimmten Informationstyps I1 bzw. I2 assoziiert ist.

Beispielsweise legt eine Definition

GRAPH<string,int> G;

G als einen parametrisierten Graphen fest, bei dem zu jedem Knoten ein Wert des Typs string und zu jeder Kante ein Wert des Typs int assoziiert ist.

Eine neuer Knoten in G wird durch

G.new_node(s);

erzeugt, wobei die Information (hier: der String) s mit dem neuen Knoten assoziiert wird. Dem entsprechend kann auch der Methode new_edge() eine zusätzliche Information i übergeben werden, die dann mit der neu erzeugten Kante assoziiert wird:

G.new_edge(v1, v2, i);

Auf die entsprechenden Werte kann über ein geeignetes Knoten-Item v oder Kanten-Item e mit dem Subskript-Operator zugegriffen werden:

node v;
edge e;
//... v and e erhalten ihre Werte...
G[v] = "MANN";
G[e] = 42;

Diese Datenstruktur ist voll dynamisch, d. h. zu den Knoten und Kanten kann eine Information ohne Einschränkungen assoziiert werden, auch wenn der Graph sehr stark wächst oder schrumpft. Zudem ist der Zugriff auf die Information über ein Knoten- oder ein Kanten-Item ein wenig effizienter als bei einem Knoten- oder Kanten-Array. Allerdings kann in einem GRAPH immer nur eine Information pro Knoten und Kante gespeichert werden:

	Anmerkung
	Will man mehrere Variablen zu einem Knoten oder einer Kante assoziieren, so kann man einen Verbundtyp als selbstdefinierten Typparameter verwenden. Eine andere Möglichkeit besteht darin, ein oder mehrere zusätzliche node_arrays bzw. edge_arrays oder die noch zu besprechenden node_maps bzw. edge_maps zu benutzen.

Als Anwendungsbeispiel wollen wir nochmals unsere Suche „Von MANN zu FRAU“ aus Abschnitt “Ein Anwendungsbeispiel: Breitensuche in einem Graphen” implementieren. Dieses Mal aber wollen wir den Algorithmus zur Breitensuche selbstverständlich nicht selbst schreiben: Wie jeden anderen grundlegenden Graphenalgorithmus hat LEDA auch diesen eingebaut. Er steht über die Funktion BFS() zur Verfügung.

Was müssen wir tun, um die eingebaute Funktion BFS() für unser Problem geeignet einzusetzen? Zunächst einmal müssen wir hier explizit den Graphen aufbauen, auf dem diese Funktion suchen soll. Das haben wir in Abschnitt “Ein Anwendungsbeispiel: Breitensuche in einem Graphen” nicht getan. Dort hatten wir noch keine Datenstruktur für Graphen und haben den Graphen nur implizit während des Programmlaufes erzeugt, indem wir ihn mittels Breitensuche durchwandert haben.

Wir lesen also wieder aus einer Datei unsere Liste der vierbuchstabigen Wörter ein und erzeugen für jedes gelesene Wort einen Knoten. Dieser Knoten muss wissen, welches Wort er trägt. Um diese Information zu assoziieren, benutzen wir einen GRAPH<string,int>. Der Typ int der Kanteninformationen ist dabei unwichtig - wir assoziieren keine spezielle Information zu den Kanten, müssen aber trotzdem eine angeben. Daher setzen wir alle Kantenwerte auf 0.

Wenn wir für das Wort A einen neuen Knoten a erzeugt haben, schauen wir nach, ob es in dem bisher konstruierten Graphen schon Knoten gibt, die zu a benachbart sein müssen. Diese Knoten finden wir mit derselben Methode wie in Abschnitt “Ein Anwendungsbeispiel: Breitensuche in einem Graphen”: Wir erzeugen durch Ersetzen der Buchstaben von A alle möglicherweise benachbarten Worte B und schauen nach, ob B schon im Graph vorkommt. Haben wir einen solchen Knoten gefunden, müssen wir die entsprechenden Kanten einfügen, um die Nachbarschaftsbeziehung herzustellen. Für jede Kante ist dabei auch die Rückwärtskante einzufügen, da die Ableitungsbeziehung des Buchstabenspiels symmetrisch ist: Lässt sich das Wort A in das Wort B ableiten, so auch umgekehrt. Um aber zu B den entsprechenden Knoten b im schon konstruierten Graphen zu finden, müssen wir uns zu jedem Wort den entsprechenden Knoten merken; das erledigen wir lässig mit einem d_array<string,node>. Dieses d_array dient auch zum vorausgehenden Test, ob ein bestimmtes Wort B überhaupt als Knoten im Graphen vorkommt.

Ist der Graph G fertig aufgebaut, lassen wir den Benutzer zwei Worte from und to eingeben, zu denen eine Ableitung gesucht werden soll. Ein geeigneter Aufruf

BFS(G, start, dist, pred);

führt dann in G eine Breitensuche aus, beginnend im Knoten start. Die dabei für jeden besuchten Knoten v berechnete Abstandsinformation wird in das Knoten-Array dist eingetragen; die Kante, über die v bei der Suche erreicht wurde und die daher auf einem kürzesten Weg von start zu v liegt, wird im Knoten-Array pred eingetragen. Dieses Knoten-Array pred benutzen wir am Schluss, um entlang eines kürzesten Weges vom Knoten to zurück zum Startknoten from zu laufen.

#include <LEDA/graph.h>
#include <LEDA/d_array.h>
#include <LEDA/list.h>
#include <LEDA/basic_graph_alg.h>

#include <fstream>
#include <iostream>

using leda::GRAPH;
using leda::node;
using leda::edge;
using leda::node_array;
using leda::d_array;
using leda::string;
using leda::list;
using std::cout;
using std::cin;

int main()
{
  std::ifstream is("Data/4LetterWords.txt");

  
  GRAPH<string,int> G;
  d_array <string,node> D;
  string s;

  // Read all words. Each word becomes a node of G
  while (is >> s) {
    node v = G.new_node(s);
    D[s] = v; // Which node belongs to which word?

    // Find all adjacent words and record adjacency in G
    // Step through all 4 letters of s
    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;
        // Candidate adjacent word: replace letter i
        s_adjacent[i] = c;
        if(D.defined(s_adjacent)) {
          // Adjacent word found; record adjacency by edges
          G.new_edge(D[s], D[s_adjacent], 0);
          G.new_edge(D[s_adjacent], D[s], 0); // backward edge
        }       
      }
    }
  }

  // Let user input search words
  string from, to;
  
  cout << "Start with word: ";
  cin >> from;
  cout << "End with word: ";
  cin >> to;
  
  if(!D.defined(from) || !D.defined(to)) {
    cout << "At least one of the words is not a part of the word list!\n";
    exit(1);
  }

  // Call Breadth First Search on G
  node_array<int> dist(G,-1);
  node_array<edge> pred(G);
  BFS(G, D[from], dist, pred);

  // Output distance and path from <from> to <to>
  int distance = dist[D[to]];
  cout << "The distance from " << from << " to " << to;
  cout << " is " << distance << "\n";

  if(distance == -1) {
    cout << "There is no way from " << from << " to " << to << ".\n";
  } 
  else {
    cout << "Here is a way to reach it:\n";
    node v = D[to];
    node start = D[from];
    list<node> L;
    L.push(v); // Output nodes in reverse order later
    while(v != start) {
      v = G.opposite(v, pred[v]);
      // v = G.source(pred[v]); is also possible here
      L.push(v);
    }
    
    int dcount = 0; 
    forall(v, L)
      cout << dcount++ << " " << G.inf(v) << "\n";
  }  

}

Der kürzeste Weg von ANJA zu IRIS lautet wie folgt:

Start with word: ANJA
End with word: IRIS
The distance from ANJA to IRIS is 15
Here is a way to reach it:
0 ANJA
1 ANNA
2 ANNE
3 AHNE
4 AHLE
5 AALE
6 AALS
7 HALS
8 HAIS
9 HAIN
10 MAIN
11 MEIN
12 DEIN
13 DRIN
14 IRIN
15 IRIS

Die Funktion BFS() benötigt ein Knoten-Array node_array<int>, das auf G gültig ist, und dessen Werte alle mit -1 vorbelegt sind. Sie liefert außerdem eine Liste der bei der Suche erreichten Knoten zurück; diese wird hier nicht benötigt.

Den Weg von to zurück zu from erhalten wir, indem wir den Verweisen in pred folgen. Wie wir in Abschnitt 5.2.4 sehen werden, liefert die Methode opposite() zu einer Kante und zu einem Knoten, der Quelle bzw. Ziel dieser Kante ist, den jeweils anderen Knoten, der dann Ziel bzw. Quelle der Kante ist.

Um die Ableitungsschritte in der richtigen Reihenfolge auszugeben, sammeln wir alle Worte auf dem Weg zurück in einer Liste, und geben die Liste dann umgedreht wieder aus. (Dies geschieht hier implizit, indem wir jedes Wort vorne an die Liste anhängen und diese dann am Schluss von vorne nach hinten ausgeben.)

Die Methode inf() liefert zu einem Knoten- oder Kanten-Item eine Kopie des zu dem entsprechenden Knoten oder der entsprechenden Kante assoziierten Wertes. Im Unterschied zum Operator [] kann dadurch der Wert nicht verändert werden.

Es gibt noch eine dritte Möglichkeit, Graphen mit Informationen zu versehen: Knoten-Maps und Kanten-Maps sind eine voll dynamische Alternative zu Knoten-Arrays und Kanten-Arrays. Sie werden von LEDA in Form der Klassen node_map und edge_map angeboten.

Die Definitionen

node_map<I> A(G);
node_map<I> B(G,x);

legen zwei Knoten-Maps auf dem Graphen G an. Dabei wird in A zu jedem Knoten der Default-Wert des Typs I assoziiert, in B der explizit angegebene Wert x. Kanten-Maps werden entsprechend definiert.

Wie bei Knoten- und Kanten-Arrays geschieht der Zugriff auf die zu einem Knoten oder einer Kante assoziierte Information über den Subskript-Operator [].

Knoten- und Kanten-Maps benutzen Hashing, um zu Knoten bzw. Kanten Informationen zu assoziieren. Die Definition einer Knoten- und Kanten-Map benötigt daher konstant viel Zeit (im Gegensatz zu O(n) bzw. O(m) bei Knoten- und Kanten-Arrays, wenn der Graph n Knoten und m Kanten hat), und der Zugriff auf die zu einem Knoten oder zu einer Kante assoziierte Information hat (als Erwartungswert) konstante Kosten.

Wie bei Knoten- und Kanten-Arrays gibt es auch hier bei a priori bekannter Anzahl von zu definierenden Knoten- und Kanten-Maps die Möglichkeit, einen der im Konstruktor des Graphen

graph G(n_slots, e_slots);

erzeugten Slots für die Knotenwerte durch

node_map<I> A;
A.use_node_data(G, x);

zu nutzen. Übrigens teilen sich die Klassen node_array und node_map diese Slots und verhalten sich bei Verwendung eines solchen Slots durch use_node_data() genau gleich.

Welche der vorgestellten Möglichkeiten soll man nun wann benutzen? Tabelle 5.1 versucht, eine Hilfestellung zu geben. n ist dabei die Anzahl der Knoten in einem Graphen. Die Tabelle zeigt nur die Möglichkeiten, zu einem Knoten Informationen zu assoziieren; für die Kanten gilt Entsprechendes mit den entsprechenden Typen.

Das Hauptkriterium ist die Frage, ob der Graph dynamisch ist und sich daher nach der Definition der jeweiligen Struktur noch ändern wird, oder ob er statisch ist. Nur in letzterem Fall kommen Knoten- und Kanten-Arrays in Frage.

Ist er statisch, so spielt weiterhin die Frage eine Rolle, zu wie vielen Knoten und Kanten Informationen assoziiert werden sollen. Sind dies nur wenige, so verbraucht eine Knoten- oder Kanten-Map nur wenig Speicherplatz gegenüber den anderen Möglichkeiten und sollte daher bevorzugt werden. Sind dagegen zu mehr als der Hälfte der Knoten oder Kanten Informationen zu speichern, so lohnen sich Knoten- und Kanten-Arrays.

Die Manualseiten zu node_array, edge_array, GRAPH, node_map und edge_map enthalten weitere Informationen zu den jeweiligen Klassen.