5.2.5. Erzeugen und Speichern von Graphen und der Editor GraphWin

Lernziele

Die Klasse GraphWin benutzen
Die Standarddarstellung zum Abspeichern von Graphen
Das Edit-and-Run-Schema
Ergebnisse von Graphenalgorithmen visualisieren
DFS-Nummerierung mit DFS_NUM()
Die Graph-Generatoren complete_graph() und random_graph()

Bisher haben wir die Graphen innerhalb unserer Programme selbst aufgebaut. Oftmals ist es aber wünschenswert oder notwendig, die Graphen, die wir bearbeiten wollen, „von außen“ in ein Programm zu füttern oder sie automatisch erzeugen zu lassen. Es stellt sich also die Frage, wie man Graphen erzeugen, editieren und abspeichern kann. Dazu lernen wir in diesem Abschnitt einige Möglichkeiten kennen.

Interaktive Eingabe mit dem Editor GraphWin

LEDA bietet die Klasse window an, die eine plattformübergreifende Schnittstelle für graphische Ein- und Ausgabe grundlegender geometrischer Objekte darstellt. Mit ihr lassen sich Algorithmen visualisieren und animieren. Auf diese sehr mächtige Klasse gehen wir hier nicht ein; vielmehr beschreiben wir kurz den Gebrauch der von ihr abgeleiteten Klasse GraphWin, die die Möglichkeiten der Klassen graph und window vereinigt.

Ein Objekt vom Typ GraphWin ist gleichzeitig ein Fenster, ein Graph und eine (zweidimensionale) Visualisierung dieses Graphen in diesem Fenster. Diese Klasse kann u. a. dazu benutzt werden, Graphen von Hand mit der Maus zu konstruieren und darzustellen, so konstruierte Graphen abzuspeichern und wieder einzulesen, oder das Ergebnis eines Graphenalgorithmus zu visualisieren. Abbildung 5.7 zeigt ein GraphWin.

Abbildung 5.7. Graphen editieren mit GraphWin

Graphen editieren mit GraphWin

Ein solches GraphWin wird durch das folgende Programm geöffnet. Für den Rest des Abschnittes ist es sinnvoll, dieses Programm zu übersetzen und zu starten, und dann die Benutzungshinweise am Bildschirm nachzuvollziehen. Es lohnt sich, ein wenig mit der Benutzeroberfläche zu experimentieren!

Filename: GraphDrawer.C
#include <LEDA/graph.h>
#include <LEDA/graphwin.h>

using leda::graph;
using leda::GraphWin;
using leda::window;
using std::cout;


int main()
{
  graph G;

  GraphWin gw(G, 500, 500, "Graph Drawer");
  gw.display(window::center,window::center);
  while(gw.edit()) { 
    // here we will fill in code for algorithms on G later
  }
}

Die Schnittstelle der Klasse GraphWin werden wir später in diesem Abschnitt besprechen. Zunächst einmal machen wir uns mit der graphischen Oberfläche vertraut.

Der linke Maus-Button wird beim Editieren in einem GraphWin am häufigsten verwendet: Ein einzelner Klick auf den Hintergrund erzeugt einen neuen Knoten. Ein einzelner Klick auf einen Knoten selektiert diesen Knoten als die Quelle einer neu einzufügenden Kante. Der nächste Klick legt dann den Zielknoten der neuen Kante fest; das ist entweder ein schon existierender Knoten oder ein neuer Knoten (wenn auf den Hintergrund geklickt wird). Bevor der Zielknoten definiert wird, können durch den mittleren Maus-Button Knicke in die Kante eingefügt werden. (Auf Systemen mit nur zwei Maus-Buttons muss dazu gleichzeitig die Taste ALT gedrückt und auf den linken Maus-Button geklickt werden.) Die Erzeugung einer neuen Kante kann durch einen Klick auf den rechten Maus-Button abgebrochen werden.

Knoten können durch Ziehen verschoben werden. Dazu muss der Knoten mit dem linken Maus-Button selektiert werden und der Button muss gedrückt bleiben.

Ein Doppelklick auf einen Knoten oder eine Kante öffnet eine Dialog-Box zum Verändern der Attribute dieses Knotens oder dieser Kante. Diese Attribute legen im Wesentlichen Form und Beschriftung fest; wir werden sie später kurz besprechen.

Ein Klick mit dem rechten Maus-Button auf einen Knoten oder eine Kante öffnet ein Kontext-Menü. Damit kann u. a. dieser Knoten bzw. diese Kante wieder gelöscht werden.

Im Default-Menü eines GraphWin finden wir die Einträge File, Edit, Graph, Layout, Window, Options, Help, Undo, Redo, und done. Hinter dem Menü-Eintrag Help verbirgt sich ein Hilfetext, der den interaktiven Gebrauch von GraphWin detailliert erklärt.

Wichtig für uns ist zunächst nur das Menü File. Dieses bietet Operationen an, um Graphen einzulesen und abzuspeichern. Über den sich darin befindenden Eintrag Exit kann das GraphWin beendet werden.

Geben wir nun einmal den in Abbildung 5.7 dargestellten Graphen ein und speichern ihn über File → Save → gw_graph ab. Dieser Menü-Eintrag wählt als Darstellung das Standardformat aus. Als Dateinamen wählen wir graph.gw.

Das Standardformat

Dadurch wird eine Datei im so genannten Standardformat erzeugt. Diese Dateien haben die Endung .gw. Die soeben erzeugte Datei beginnt mit den folgenden Zeilen:

LEDA.GRAPH
void
void
-1
3
|{}|
|{}|
|{}|
5
1 2 0 |{}|
1 2 0 |{}|
1 3 0 |{}|
2 3 0 |{}|
3 3 0 |{}|
# version string
GraphWin 1.400000
# scaling  wxmin  wymin  wxmax  wymax
0.9807129 -10 -3.6875 499.7656 460.1992
# node label font and size
0 13.25391
# edge label font and size
0 18.35156
# node index format
%d
# edge index format
%d
# multi-edge distance
4.078125
# 
...
(the remaining lines are left out; they contain further 
information about position, shape etc. of nodes and edges)

Ohne dieses Format in aller Ausführlichkeit erklären zu wollen, schauen wir uns kurz die einzelnen Abschnitte dieser Datei an. Die ersten vier davon können leicht mit Hilfe eines gewöhnlichen Texteditors erstellt und bearbeitet werden; auf diese Weise kann ein Graph auch ohne ein GraphWin von Hand oder als Ausgabe eines Programms spezifiziert werden. Die Abfolge der Abschnitte ist wie folgt:

  1. Der Header-Abschnitt: Er beginnt mit dem String LEDA.GRAPH. Darauf folgen die Datentypen der Knoten- und Kanteninformationen (falls der darunter liegende Graph vom Typ GRAPH ist, ansonsten void.)

  2. Ab Version 4.5 von LEDA: Eine optionale Zeile mit der Information darüber, ob der Graph gerichtet oder ungerichtet ist. Eine -1 steht für einen gerichteten Graphen, eine -2 für einen ungerichteten. Fehlt die Zeile, wird der Graph als gerichtet angesehen. In Versionen < 4.5 von LEDA fehlt die Zeile immer, und der Graph wird immer als gerichtet angesehen.

  3. Der Knoten-Abschnitt: Er beginnt mit der Anzahl n der Knoten. Die Knoten sind nach ihrer Position in der Knotenliste V durchnummeriert. Die folgenden n Zeilen enthalten, eingeschlossen in |{...}|, die Information, die zu diesem Knoten assoziiert ist.

  4. Der Kanten-Abschnitt: Er beginnt mit der Anzahl m der Kanten. Es folgen m Zeilen, eine für jede Kante im Graphen. Jede dieser Zeilen besteht aus 4 Einträgen in der folgenden Reihenfolge: die Nummer des Startknotens, die Nummer des Zielknotens, die Nummer der Gegenkante (0, falls keine existiert) und die mit der Kante assoziierte Information (eingeschlossen in |{...}|). (Das Konzept der Gegenkante werden wir in Abschnitt 5.2.6 kennen lernen.) Die m Zeilen für die m Kanten sind nach zwei Kriterien geordnet: zuerst nach der Nummer des Startknotens s, dann nach der Position der Kante in der Liste adj_edges(s).

  5. Der Layout-Abschnitt: Er beginnt mit dem Kommentar version string. (Vorher darf kein Kommentar auftreten!) Dieser Abschnitt enthält Informationen über das Layout des Graphen in einem GraphWin. Ist er leer, so ist kein Layout bekannt.

Lesen aus einer Datei und Schreiben in eine Datei

Wir wollen diese Datei ein wenig von Hand modifizieren und vorführen, wie ein so „auf Platte gebannter“ Graph wieder eingelesen und visualisiert werden kann.

Wir ändern die Datei von Hand in einem Texteditor folgendermaßen ab:

LEDA.GRAPH
string
int
-1
4
|{Anja}|
|{Sabine}|
|{Bettina}|
|{Sibylle}|
6
1 2 0 |{42}|
1 2 0 |{666}|
1 3 0 |{32168}|
2 3 0 |{4711}|
3 3 0 |{1001}|
4 1 0 |{31415927}|

Wir haben also den Layout-Abschnitt vollständig entfernt, einen GRAPH<string,int> spezifiziert, einen Knoten und eine Kante hinzugefügt, die Knoten mit den Namen netter weiblicher Wesen versehen (etwa derjenigen, die uns tagein tagaus durch ihre Arbeit in unserer Bibliothek unterstützen) und an die Kanten einige bedeutungslose ganze Zahlen geschrieben.

Den so spezifizierten Graphen lesen wir durch einen Aufruf von

G.read(filename);

aus der Datei filename wieder ein. Umgekehrt kann ein Graph durch einen Aufruf von

G.write(filename);

in die Datei filename geschrieben werden. Wird der Dateiname ausgelassen, liest read() von der Standardeingabe und write() schreibt darauf.

Nun wollen wir diesen Graphen wieder mit Hilfe eines GraphWin visualisieren. Dazu erklären wir ein GraphWin auf G und sagen ihm, dass es in den Knoten und an den Kanten die so genannten Data-Labels darstellen soll. Zusätzlich sagen wir ihm, dass die Knoten rechteckig statt kreisförmig sein sollen, und stellen auch noch die Größe dieser Rechtecke ein.

Filename: GraphVisualizer.C
#include <LEDA/graph.h>
#include <LEDA/graphwin.h>
#include <LEDA/string.h>

using leda::GRAPH;
using leda::GraphWin;
using leda::window;
using leda::string;
using std::cout;


int main()
{
  GRAPH<string, int> G;

  int err;
  if((err = G.read("GraphData/graph_modif.gw"))) {
    cout << "Error " << err << " occured while reading .gw file.\n";
    exit(1);
  }

  GraphWin gw(G, 500, 500, "Graph Visualizer");

  gw.set_node_label_type(leda::data_label);
  gw.set_edge_label_type(leda::data_label);
  gw.set_node_shape(leda::rectangle_node);
  gw.set_node_width(100);
  gw.set_node_height(30);

  gw.display(window::center,window::center);
  while(gw.edit()) {}
}

Es öffnet sich ein Fenster. Da wir jegliche Layout-Information entfernt haben, müssen wir das GraphWin anweisen, ein neues Layout zu berechnen. Das geht z. B. durch den Menüpunkt Layout → Simple Layouts → Circular Layout. GraphWin erzeugt dann das Layout von Abbildung 5.8. Eventuell müssen wir dieses von Hand noch ein wenig „zurecht rücken“.

Abbildung 5.8. Graphen visualisieren mit GraphWin

Graphen visualisieren mit GraphWin

Die Methode read() liefert 1 zurück, wenn die angegebene Datei nicht existiert, 2, wenn der Knoten- oder Kantentyp des GRAPH nicht mit dem in der Datei spezifizierten übereinstimmen, 3, wenn die Datei keinen Graphen kodiert, und 0, wenn alles in Ordnung ist.

Attribute von GraphWin

Die Knoten- und Kantenattribute eines GraphWin legen fest, wie Knoten und Kanten gezeichnet werden. Diese können entweder von Hand eingestellt werden (z. B. nach einem Doppelklick auf einen Knoten) oder durch die jeweiligen set-Methoden der Programmierschnittstelle. Letzteres haben wir in obigem Programm angewendet, um die Knoten rechteckig darzustellen und die Knoten- und Kanteninformation sichtbar zu machen.

Wir listen hier kurz die wichtigsten Knoten- und Kantenattribute auf. (Es gibt noch mehr.) Für nähere Erläuterungen, insbesondere was das so genannte Benutzer-Koordinatensystem und die Spezifikation von Farbwerten angeht, sei auf die Manualseiten der Klassen GraphWin, window, color und point verwiesen. Auf das Benutzer-Koordinatensystem werden wir auch in Abschnitt 5.3.8 noch näher eingehen.

Die wichtigsten Knotenattribute sind die folgenden:

  • position: Ein Attribut vom Typ point, das die Position des Mittelpunktes des Knotens im Benutzer-Koordinatensystem festlegt.

  • shape: Ein Attribut vom Typ gw_node_shape, das die Form des Knotens bestimmt. Mögliche Werte sind circle_node, ellipse_node, square_node und rectangle_node.

  • width: Ein Attribut vom Typ int, das die Breite des Knotens in Pixel bestimmt.

  • height: Ein Attribut vom Typ int, das die Höhe des Knotens in Pixel bestimmt.

  • color: Ein Attribut vom Typ color, das die Farbe angibt, mit dem das Innere des Knotens ausgefüllt wird.

  • border_color: Ein Attribut vom Typ color, das die Farbe der Umrandung des Knotens bestimmt.

  • border_width: Ein Attribut vom Typ int, das die Breite des Rahmens des Knotens in Pixel bestimmt.

  • label_type: Ein Attribut vom Typ gw_label_type, das festlegt, welches der drei möglichen Labels des Knotens dargestellt wird. Mögliche Werte sind no_label, user_label, data_label und index_label. Jeder Knoten eines GraphWin hat drei assoziierte Labels: ein Index-Label, das der internen Nummerierung der Knoten in der Knotenliste V entspricht, ein Benutzer-Label vom Typ string und ein Daten-Label, das der zu einem Knoten assoziierten Information entspricht, wenn der darunter liegende Graph vom Typ GRAPH ist.

  • user_label: Ein Attribut vom Typ string, das das Benutzer-Label des Knotens bestimmt.

  • label_color: Ein Attribut vom Typ color, das die Farbe des darzustellenden Labels bestimmt. Farben können u. a. durch Rot-Grün-Blau-Werte angegeben werden; so kodiert etwa color(255,0,0) das reinste Rot. Die einzubindende Header-Datei heißt color.h. Eine andere Möglichkeit der Farbspezifikation bietet eine in dieser Datei definierte Aufzählung von 16 vordefinierten Farbwerten mit den Namen leda::black, leda::white usw.

  • label_pos: Ein Attribut vom Typ gw_position, das die Position des darzustellenden Labels relativ zum Mittelpunkt des entsprechenden Knoten festlegt. Mögliche Werte sind central_pos, northwest_pos, north_pos, northeast_pos, east_pos, southeast_pos, south_pos und west_pos.

Die wichtigsten Kantenattribute sind die folgenden:

  • direction: Ein Attribut vom Typ gw_edge_dir, das festlegt, ob die Kante gerichtet oder ungerichtet gezeichnet wird. Mögliche Werte sind undirected_edge, directed_edge, redirected_edge (die Kante wird von Ziel zu Quelle gerichtet gezeichnet) und bidirected_edge (die Kante wird bidirektional gezeichnet).

  • width: Ein Attribut vom Typ int, das die Breite der Kante in Pixel festlegt.

  • color: Ein Attribut vom Typ color, das die Farbe der Kante festlegt.

  • style: Ein Attribut vom Typ gw_edge_style, das den Linienstil der Kante festlegt. Mögliche Werte sind solid, dashed, dotted und dashed_dotted.

  • label_type: (Siehe das gleichnamige Knotenattribut.)

  • user_label: (Siehe das gleichnamige Knotenattribut.)

  • label_color: (Siehe das gleichnamige Knotenattribut.)

  • label_pos: Ein Attribut vom Typ gw_position, das die Position des darzustellenden Labels relativ zur entsprechenden Kante festlegt. Mögliche Werte sind central_pos, east_pos und west_pos.

Die Programmierschnittstelle der Klasse GraphWin

Die Klasse GraphWin besitzt eine sehr mächtige Schnittstelle mit vielen Operationen. Wir besprechen davon hier nur die wichtigsten; sie sollen uns in die Lage versetzen, die Ergebnisse von Graphenalgorithmen zu visualisieren.

Zu einem GraphWin ist immer ein graph G und ein window W assoziiert. Beide können im Konstruktor von GraphWin angegeben oder ausgelassen werden. Werden G oder W nicht angegeben, benutzt GraphWin eine eigene (private) Instanz.

Der von uns typischerweise benutzte Konstruktor ist

GraphWin gw(G, width, height, label);

Wir legen also zusätzlich Breite und Höhe fest und geben dem Fensterrahmen ein Label.

G darf dabei durchaus auch ein GRAPH sein. In diesem Fall hat jeder Knoten und jede Kante ein assoziiertes Daten-Label, das vom GraphWin dargestellt werden kann; dieses Daten-Label entspricht dem im GRAPH zu einem Knoten bzw. zu einer Kante assoziierten Wert.

Ein GraphWin wird geöffnet und dargestellt durch einen Aufruf

gw.display(x, y);

Dabei erscheint das Fenster mit der linken oberen Ecke an der Pixel-Position (x,y) auf dem Bildschirm. Ein Aufruf

gw.display(window::center, window::center);

zentriert das Fenster auf dem Bildschirm.

Die interaktive Schnittstelle wird durch

gw.edit();

gestartet. Jetzt kann der zu gw assoziierte Graph editiert werden. Der Editiervorgang wird beendet, sobald done gedrückt oder File → Exit ausgewählt wird. Im ersten Fall liefert die Methode edit() den Wert true zurück, im zweiten den Wert false.

Dadurch lässt sich mit einer einfachen while-Schleife das so genannte Edit-and-Run-Schema zum interaktiven Austesten von Graphenalgorithmen verwirklichen: In einem iterativen Prozess wird zunächst ein Graph in einem GraphWin erstellt, dann wird done gedrückt, es läuft ein Algorithmus auf dem soeben eingegebenen Graphen, das Ergebnis des Algorithmus wird visualisiert, der Graph wird wieder im GraphWin editiert usw. Dieses Schema hat immer die folgende Grundform:

while(G.edit()) {
  // lasse einen Graphenalgorithmus auf G laufen
  ...
  // visualisiere die Ergebnisse des Algorithmus
  ...
}

Die Schleife wird verlassen, sobald der Benutzer File → Exit auswählt.

Zum Visualisieren der Ergebnisse ist es oft notwendig, die Knoten- oder Kantenattribute bestimmter Knoten und Kanten zu verändern. So könnten z. B. nach einem Aufruf von BFS() die Kanten, die zu jedem erreichten Knoten den Vorgänger auf einem kürzesten Weg zurück zum Startknoten angeben, rot eingefärbt und rückwärts gerichtet gezeichnet werden.

Die Attribute eines bestimmten Knotens bzw. einer bestimmten Kante können durch Paare von get-set-Methoden ausgelesen und geändert werden. So wird z. B. die Rahmendicke eines bestimmten Knotens v durch folgenden Aufruf auf den Wert 5 gesetzt:

gw.set_border_width(v, 5);

Die Namensgebung der set-Methoden folgt immer dem Schema set_(Name_des_Attributs). Diese Methoden erwarten als Argument einen Knoten bzw. eine Kante, gefolgt von einem Wert, dessen Typ dem des zu setzenden Attributwerts entspricht. Für die get-Methoden gilt das Entsprechende. Diese liefern einen Wert, dessen Typ dem auszulesenden Attributtyp entspricht.

Jedes Attribut hat einen Default-Wert, der beim Erzeugen eines neuen Knotens bzw. einer neuen Kante verwendet wird. Oft ist es nützlich, diesen abzuändern. So wird z. B. die Default-Rahmendicke der Knoten durch folgenden Aufruf auf den Wert 5 gesetzt:

gw.set_node_border_width(5);

Die Namensgebung der set-Methoden für das Setzen des Default-Wertes eines Knotenattributes folgt dem Schema set_node_(Name_des_Attributs). Für die Kantenattribute gilt Entsprechendes mit set_edge_(Name_des_Attributs). Diese Methoden haben ein implizites zweites Argument, das den Wert true hat; das bedeutet, dass von der Änderung des Default-Wertes alle existierenden Knoten bzw. Kanten betroffen sind, dass also deren Attributwert nachträglich abgeändert wird. Soll dies vermieden werden, muss als zweites Argument false angegeben werden.

Der Graphenalgorithmus kann den Graphen G verändern, z. B. durch Einfügen oder Löschen von Knoten und Kanten. Dann ist unbedingt Folgendes zu beachten:

[Warning] Warnung

Wenn der Graphenalgorithmus den darunter liegenden Graphen G verändert, so muss zwingenderweise vor dem nächsten edit() ein

gw.update_graph();

ausgeführt werden, damit das GraphWin über diese Modifikationen informiert wird und seine internen Datenstrukturen anpassen kann. Ohne diese Anweisung kann das Programm abstürzen!

Ein

gw.redraw();

veranlasst das GraphWin, den Graphen gemäß aller spezifizierten Attribute neu zu zeichnen. Ein edit() ruft zunächst redraw() von selbst auf.

Einige Methoden von GraphWin lösen automatisch ein Neuzeichnen des Graphen aus. Manchmal möchte man jedoch mehrere Änderungen am Graphen oder an seinen Attributen hintereinander vornehmen und das unmittelbare Neuzeichnen (etwa aus Performanzgründen) verhindern. Dazu dient

gw.set_flush(false);

Danach wird ein Neuzeichnen nur durch ein explizites redraw() ausgelöst. Ein gw.set_flush(true) stellt das ursprüngliche Verhalten wieder her.

Mit

gw.message(msg);

kann ein String als kurze Nachricht am oberen Ende der Zeichenfläche ausgegeben werden. Durch

gw.del_message();

verschwindet diese wieder. Um dazwischen secs Sekunden mit dem Programmablauf innezuhalten, kann

gw.wait(secs);

aufgerufen werden. Das Argument ist dabei vom Typ float; fehlt es, wird gewartet, bis der Benutzer auf done drückt.

Ein Beispiel: Visualisierung von DFS_NUM()

Als Beispiel für das Edit-and-Run-Schema wollen wir die Funktion DFS_NUM() interaktiv nutzbar machen und deren Ergebnis visualisieren.

Mit Breitensuche kann ein Graph systematisch durchwandert werden. Ein anderes Verfahren ist die Tiefensuche (depth first search). Hier werden von einem besuchten Knoten aus sofort alle noch nicht besuchten, adjazenten Knoten (rekursiv) besucht. Dieses Verfahren läuft zuerst vom Startknoten aus tief in den Graphen hinein, statt wie bei Breitensuche um diesen ersten Knoten herum. Durch die rekursive Suche erhält jeder Knoten v eine DFS-Nummer, das ist die Nummer des rekursiven Aufrufs, bei dem dieser Knoten v erreicht wird. Dieser rekursive Aufruf startet möglicherweise weitere rekursive Aufrufe, die irgendwann beendet sein werden. Erst dann wird auch der rekursive Aufruf für v beendet; dadurch erhält v seine Completion-Nummer, das ist der Zeitpunkt, zu dem ein Knoten völlig abgearbeitet wurde.

Die LEDA-Funktion DFS_NUM() führt auf einem gerichteten Graphen eine Tiefensuche aus und berechnet für jeden Knoten die DFS-Nummer und die Completion-Nummer. Als Argumente müssen ihr ein Graph und zwei darauf gültige Knoten-Arrays dfsnum und compnum übergeben werden. Sie liefert eine Liste der bei der Suche traversierten Kanten zurück. Diese Kanten formen in ihrer Gesamtheit einen Baum (falls der Graph zusammenhängend ist), weil Tiefensuche keine Zyklen beschreitet; ist der Graph nicht zusammenhängend, formen sie eine Ansammlung von einzelnen Bäumen, was als Wald (forrest) bezeichnet wird. Abbildung 5.9 zeigt einen solchen DFS-Wald.

Abbildung 5.9. Ein DFS-Wald, berechnet von DFS_NUM() und dargestellt mit GraphWin

Ein DFS-Wald, berechnet von DFS_NUM() und dargestellt mit GraphWin

Das folgende Programm wendet das Edit-and-Run-Schema an, um mittels DFS_NUM() auf einem Graphen interaktiv einen DFS-Wald zu berechnen und darzustellen. Drückt der Benutzer auf done, so wird der Wald berechnet. Im GraphWin wird dann jede Kante des Waldes rot eingefärbt und mit Breite 5 gezeichnet, und jeder Knoten wird so dargestellt, dass er seine DFS-Nummer und seine Completion-Nummer zeigt.

Filename: DFS_NUMDemo.C
#include <LEDA/graph.h>
#include <LEDA/basic_graph_alg.h>
#include <LEDA/node_array.h>
#include <LEDA/graphwin.h>
#include <LEDA/list.h>
#include <LEDA/string.h>


using leda::graph;
using leda::node;
using leda::node_array;
using leda::GraphWin;
using leda::window;
using leda::list;
using leda::edge;
using leda::string;
using std::cout;


int main()
{
  graph G;

  GraphWin gw(G, 500, 500, "DFS Numbering");
  gw.display(window::center,window::center);
  gw.set_node_shape(leda::ellipse_node);
  gw.set_node_width(42);
  gw.set_node_label_type(leda::user_label);

  while(gw.edit()) {
    node_array<int> dfsnum(G);
    node_array<int> compnum(G);
    list<edge>  L = DFS_NUM(G, dfsnum, compnum);
    gw.set_width(L, 5);
    gw.set_color(L, leda::red);
    node v;
    forall_nodes(v,G) {
      string label1("%d",dfsnum[v]);
      string label2("%d",compnum[v]);
      gw.set_user_label(v, label1 + "|" + label2);
    }
  }
    
}

Den set-Methoden zum Setzen von Attributwerten kann statt eines einzelnen Knotens oder einer einzelnen Kante auch eine Liste von Knoten bzw. Kanten übergeben werden, was dann sinnvoll ist, wenn - wie in obigem Beispiel - die Attribute vieler Knoten oder Kanten gleichzeitig gesetzt werden sollen.

Graph-Generatoren

LEDA bietet noch eine ganz andere Möglichkeit zum Erzeugen von Graphen an: Oftmals ist es vor allem beim Testen von eigenen Graphenalgorithmen sinnvoll, Graphen automatisch erzeugen zu lassen, anstatt sie mühsam von Hand zu spezifizieren. Zu diesem Zweck gibt es in LEDA Graph-Generatoren; das sind Funktionen, die Graphen erzeugen. Um diese Funktionen benutzen zu können, muss die Header-Datei graph_gen.h eingebunden werden.

Die Funktion

void complete_graph(graph& G, int n);

erzeugt einen vollständigen Graphen mit n Knoten. Das ist ein Graph, bei dem es für jedes Paar (v,w) von Knoten eine Kante (v,w) im Graphen gibt. Der Graph hat also n·(n-1) viele Kanten.

Die Funktion

void random_graph(graph& G, int n, int m, bool no_anti_parallel_edges,
                  bool loopfree, bool no_parallel_edges);

erzeugt einen zufälligen Graphen mit n Knoten und m Kanten. Ist no_anti_parallel_edges gesetzt, so werden keine Rückwärtskanten erzeugt, ist loopfree gesetzt, so werden keine Selbstschleifen erzeugt, und ist no_parallel_edges gesetzt, so werden keine Multikanten erzeugt.

Diese Funktionen lassen sich auch schön in einem GraphWin beobachten. Der entsprechende Menüpunkt ist Graph → Create.

Weitere Informationen

Mehr zur überaus mächtigen Schnittstelle der Klasse GraphWin findet sich auf der entsprechenden Manualseite. Wichtig für das Gesamtverständnis ist auch die Elternklasse window, der ebenfalls eine Manualseite gewidmet ist.

Das Standardformat ist detailliert auf einer entsprechenden Seite im LEDA-Guide beschrieben.

Mehr zu den Graph-Generatoren von LEDA kann auf deren Manualseite gefunden werden.

Übungen

Übung 55.

in Abbildung 5.7 erscheint eine Multikante als Halbkreis gezeichnet. Spielen Sie so lange mit einem GraphWin herum, bis Sie herausgefunden haben, wie man das bewerkstelligt.

Übung 56.

Wenden Sie das Edit-and-Run-Schema zum Visualisieren von Breitensuche an: Nach jedem Aufruf von BFS() sollen die Kanten, die zu jedem erreichten Knoten den Vorgänger auf einem kürzesten Weg zurück zum Startknoten angeben, rot eingefärbt gezeichnet werden. Zusätzlich soll in jedem Knoten der berechnete Abstand zum Startknoten erscheinen. Der Startknoten soll der erste Knoten sein, der vom Benutzer eingegeben wurde. Das ist der erste Knoten in der Knotenliste V des zum GraphWin assoziierten Graphen G; diesen erhält man durch G.first_node(). Er soll zusätzlich mit einem dicken, grünen Rand kenntlich gemacht werden.

Übung 57.

Führen Sie folgendes Experiment durch, um die Effizienz von node_array, node_map und GRAPH hinsichtlich des Zugriffs auf assoziierte Werte zu vergleichen: Erzeugen Sie einen zufälligen Graphen mit einer Million Knoten und 0 Kanten und assoziieren Sie zu jedem Knoten den Wert 0. Iterieren Sie 20 Mal über alle Knoten des Graphen und erhöhen Sie dabei den assoziierten Wert um 1. Iterieren Sie über die Knoten erst in ihrer natürlichen Reihenfolge in V, dann in einer zufälligen Reihenfolge. (Dafür können Sie z. B. ein array<node> permutieren und dann indirekt über dieses Array auf die Knoten zugreifen.) Messen und vergleichen Sie die Laufzeiten.




Imprint-Dataprotection