5.2.4. Über Knoten und Kanten iterieren und in Graphen navigieren

Lernziele

Die Methoden sort_nodes(), bucket_sort_nodes(), sort_edges() und bucket_sort_edges()
Makros zum Iterieren über Kanten und Knoten
Die Methoden opposite(), source() und target() zum Navigieren
Kanten in einer bestimmten Reihenfolge um Knoten anordnen
Kanten zwischenzeitlich verbergen mit hide_edge() und restore_edge()
Graph-Iteratoren

Navigare necesse est“. Navigieren ist unausweichlich, sowohl im täglichen Leben, als auch in Graphen. Dieser Abschnitt beschreibt die verschiedenen Möglichkeiten, über die Knoten und Kanten eines Graphen zu iterieren und in einem Graphen von Knoten zu Knoten zu wandern.

Iterieren über alle Knoten und Kanten

Schon kennen gelernt haben wir die Makros

forall_nodes(v, G) { ... }
forall_edges(e, G) { ... }

mit denen über alle Knoten bzw. Kanten eines Graphen G iteriert werden kann. Die Knoten und Kanten liegen in einer Liste V bzw. E; diese und die folgenden Makros iterieren über diese Listen. Auch schon eingeführt haben wir die Möglichkeit, diese Listen zu sortieren. Dafür gibt es drei Möglichkeiten (wir besprechen hier nur die Möglichkeiten für die Knotenliste V):

Ein Aufruf

G.sort_nodes(order);

mit einem auf G gültigen Knoten-Array node_array<T> order bringt die Knoten in V in die gemäß order gegebenen Reihenfolge. T muss dabei ein numerischer Typ sein.

Ein Aufruf

G.sort_nodes(cmp);

mit einem Zeiger auf eine Vergleichsfunktion für Knoten

int (*cmp)(node, node);

sortiert die Knoten in V in der gemäß cmp gegebenen Reihenfolge.

Und schließlich führt ein Aufruf von

G.bucket_sort_nodes(f);

Bucket-Sort mit der Verteilungsfunktion f() aus. Hierfür gilt dasselbe, was wir in Abschnitt 2.3.4 über Bucket-Sort von linearen Listen gesagt haben.

Mit dem Makro

forall_rev_nodes(v, G) { ... }

kann die Liste V von hinten nach vorne durchwandert werden, dem entsprechend mit dem Makro

forall_rev_edges(e, G) { ... }

die Liste E.

Iterieren über die zu einem Knoten adjazenten Kanten und Knoten

Mit dem Makro

forall_adj_nodes(v, w) { ... }

wird über alle zum Knoten w adjazenten Knoten v iteriert. Im Falle eines gerichteten graph sind das alle v, für die es eine Kante (w,v) im Graphen gibt. Im ungerichteten Fall sind es alle v, für die es eine Kante (w,v) oder eine Kante (v,w) gibt.

Mit dem Makro

forall_adj_edges(e, w) { ... }

wird über alle zum Knoten w adjazenten Kanten e iteriert. Im Falle eines gerichteten graph sind das alle e, deren Quelle w ist, für die es also einen Knoten v und eine Kante (w,v) im Graphen gibt. Im ungerichteten Fall sind es alle e, deren Quelle oder Ziel w ist.

Für einen gerichteten graph gibt es darüber hinaus noch folgende Makros: Hinter

forall_out_edges(e, w) { ... }

verbirgt sich eine schnellere Version von forall_adj_edges(e,w).

forall_in_edges(e, w) { ... }

iteriert über alle zu w inzidenten Kanten, also über die Kanten, deren Ziel w ist. Und schließlich iteriert

forall_inout_edges(e, w) { ... }

zuerst (sic!) über alle Kanten in out_edges(w), und dann über alle Kanten in in_edges(w).

Navigieren

Die wohl wichtigste Methode zum Navigieren in einem graph ist opposite(). Nach einem Aufruf

node w = G.opposite(e,v);

ist w der von v verschiedene Endpunkt der Kante e. Diese Methode, zusammen mit den obigen Iterationsmakros, reicht in den meisten Problemstellungen aus, um in einem Graphen geeignet zu navigieren, d. h. entlang eines gewünschten Pfades von Knoten zu Knoten zu springen.

Neben opposite() gibt es auch noch die expliziten Methoden

G.source(e);
G.target(e);

die zu einer Kante e die Quelle bzw. das Ziel liefern.

Ein Beispiel

Als Beispiel für die bisher vorgestellten Möglichkeiten der Iteration und Navigation wollen wir den Graphen aus Abbildung 5.5 erzeugen, darüber iterieren und darin navigieren.

Das folgende Programm gibt zunächst für jeden Knoten dessen Ausgangsgrad und alle adjazenten Kanten aus. Danach gibt es für jeden Knoten den Eingangsgrad und alle inzidenten Kanten aus. Dann startet es im Knoten 0 und läuft immer weiter, so lange es vom aktuellen Knoten aus zu einem Knoten mit größerer Nummer springen kann (der erste solche wird ausgewählt). Zum Schluss bewegt es sich vom Knoten 2 aus entlang einer Kante rückwärts, so lange es zu einem Knoten mit kleinerer Nummer springen kann (wiederum wird der erste solche ausgewählt).

Filename: IteratingNavigatingGraphs.C
#include <LEDA/graph.h>
#include <LEDA/string.h>
#include <iostream>

using leda::GRAPH;
using leda::node;
using leda::edge;
using leda::string;
using std::cout;
using std::endl;


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

  node v0 = G.new_node(0);
  node v1 = G.new_node(1);
  node v2 = G.new_node(2);

  edge a = G.new_edge(v0, v1, "a");
  edge b = G.new_edge(v1, v2, "b");
  edge c = G.new_edge(v0, v2, "c");
  edge d = G.new_edge(v0, v1, "d");
  edge e = G.new_edge(v2, v2, "e");

  cout << "Adjacent edges (out_edges):" << endl;
  node v;
  forall_nodes(v,G) {
    cout << "Node " << G.inf(v) << ": ";
    cout << "Outdegree=" << G.outdeg(v) << ". ";
    edge e;
    forall_out_edges(e,v) { // same as forall_adj_edges(e,v)
      node s = G.source(e);
      node t = G.target(e);
      cout << G[e] << "=(" << G[s] << "," << G[t] << ") ";
    }
    cout << endl;
  }

  cout << "\nIncident edges:" << endl;
  forall_nodes(v,G) {
    cout << "Node " << G.inf(v) << ": ";
    cout << "Indegree=" << G.indeg(v) << ". ";
    edge e;
    forall_in_edges(e,v) {
      node s = G.source(e);
      node t = G.target(e);
      cout << G[e] << "=(" << G[s] << "," << G[t] << ") ";
    }
    cout << endl;
  }

  cout << "\nNavigating from node 0 to nodes with higher number:\n";
  v = v0;
  while(1) {
    cout << "Reached node " << G.inf(v) << endl;
    node v_old = v;
    node w;
    forall_adj_nodes(w,v)
      if(G.inf(w) > G.inf(v)) {
        v = w;
        break;
      }
    if(v_old == v) 
      break;
  }

  cout << "\nNavigating backwards from node 2 ";
  cout << "to nodes with lower number:\n";
  v = v2;
  while(1) {
    cout << "Reached node " << G.inf(v) << ". ";
    node v_old = v;
    edge e;
    forall_in_edges(e,v) {
      node s = G.opposite(e,v);
      if(G.inf(s) < G.inf(v)) {
        v = s;
        cout << "Traversing edge " << G.inf(e) << " backwards." << endl;
        break;
      }
    }
    if(v_old == v) 
      break; 
  }
  cout << endl;
}

Das Programm gibt Folgendes aus:

Adjacent edges (out_edges):
Node 0: Outdegree=3. a=(0,1) c=(0,2) d=(0,1)
Node 1: Outdegree=1. b=(1,2)
Node 2: Outdegree=1. e=(2,2)

Incident edges:
Node 0: Indegree=0.
Node 1: Indegree=2. a=(0,1) d=(0,1)
Node 2: Indegree=3. b=(1,2) c=(0,2) e=(2,2)

Navigating from node 0 to nodes with higher number:
Reached node 0
Reached node 1
Reached node 2

Navigating backwards from node 2 to nodes with lower number:
Reached node 2. Traversing edge b backwards.
Reached node 1. Traversing edge a backwards.
Reached node 0.

Die Methode outdeg() liefert zu einem Knoten den Ausgangsgrad, die Methode indeg() den Eingangsgrad. degree() liefert den Grad, also die Summe von Eingangsgrad und Ausgangsgrad. Im ungerichteten Fall sollte nur degree() benutzt werden.

Die Reihenfolge in in_edges(v) und out_edges(v) beeinflussen

In manchen Algorithmen ist es wichtig, die von und zu einem Knoten ausgehenden und inzidenten Kanten in einer bestimmten Reihenfolge um diesen herum anzuordnen und sie in dieser Reihenfolge zu durchwandern. Wir stellen hier einige Beispiele für einen gerichteten graph vor.

Ein Aufruf

edge f = G.new_edge(e, w);

erzeugt eine neue Kante f=(Quelle(e),w), die dieselbe Quelle wie die Kante e hat und das Ziel w. Sie wird in out_edges(Quelle(e)) hinter e eingeordnet. Anders ausgedrückt: Es wird eine neue Kante f erzeugt, die das Ziel w hat, vom selben Knoten wie e ausgeht und in der Reihenfolge der zu Quelle(e) adjazenten Kanten hinter e eingefügt wird. Wird als drittes Argument leda::before angegeben, wird sie vor e eingefügt.

Ein Aufruf

edge f = G.new_edge(w,e);

vertauscht die Rolle von w: w wird nun als Quelle aufgefasst und eine neue Kante f=(w,Ziel(e)) erzeugt. Sie wird in in_edges(Ziel(e)) hinter e eingeordnet. Wird als drittes Argument leda::before angegeben, wird sie vor e eingefügt.

Mit einem Aufruf

edge f = G.adj_succ(e);

kann die in der Liste adj_edges(Quelle(e)) (das ist im gerichteten Fall dieselbe wie out_edges(Quelle(e))) zur Kante e unmittelbar nachfolgende Kante f bestimmt werden. Die Methode liefert nil, wenn e schon die letzte Kante ist. Dadurch kann die Stelle eines Iterationsschrittes genauer festgelegt werden als durch die Iterationsmakros. Dem entsprechend gibt es die Methode adj_pred(), die den Vorgänger in der Adjazenzliste liefert

Die Methoden cyclic_adj_succ() und cyclic_adj_pred() arbeiten entsprechend, nur fassen sie die Adjazenzlisten als zirkuläre Listen auf (und liefern daher immer einen Vorgänger bzw. Nachfolger.)

Kanten zwischenzeitlich verbergen

Manchmal ist es angebracht, Kanten zwischenzeitlich aus einem Graphen zu entfernen und sie später wieder einzublenden. Ein Aufruf

G.hide_edge(e);

entfernt die Kante e temporär aus G, bis sie durch einen Aufruf von

G.restore_edge(e);

wieder eingeblendet wird. Ein Aufruf von restore_all_edges() blendet alle verborgenen Kanten wieder ein.

Die Methode

G.hidden_edges();

liefert eine Liste aller augenblicklich verborgenen Kanten. Mit

G.is_hidden(e);

kann abgefragt werden, ob die Kante e gerade verborgen ist.

Graph-Iteratoren

Iteratoren sind ein mächtiges Konzept im objekt-orientierten Programmier-Paradigma und stellen ein grundlegendes Entwurfsmuster dar, s. [15]. Grob gesagt ist ein Iterator ein kleines Objekt, das zu einer bestimmten linearen Abfolge assoziiert ist, etwa der Abfolge der aus einem Knoten v ausgehenden Kanten in der Liste out_edges(v). Ein Iterator wird dazu benutzt, die Elemente dieser Folge nach und nach zu durchlaufen.

Wir stellen hier kurz einige Iteratoren-Klassen von LEDA vor, mit denen über die Knoten und Kanten eines Graphen iteriert und die inzidenten und ausgehenden Kanten eines Knotens traversiert werden können. Iteratoren stellen somit eine Alternative zu den oben vorgestellten forall-Makros dar.

Beispielsweise ist das Makro forall_nodes(v,G) äquivalent zum folgenden Gebrauch eines Iterators der Klasse NodeIt:

for(NodeIt it(G); it.valid(); it++) { ... }

Hier wird ein Knoten-Iterator it, ein Objekt der Klasse NodeIt, auf dem Graphen G definiert. Solange dieser Iterator noch gültig ist, d. h., solange er noch nicht alle Knoten des Graphen durchlaufen hat, wird der Rumpf der Schleife durchlaufen. Am Ende jedes Schleifendurchlaufs wird der Iterator durch it++ um eine Position in der Folge weitergeschoben.

Iteratoren können überall dort benutzt werden, wo ein entsprechendes Item vom Typ node bzw. edge auch benutzt werden darf. So geschieht z. B. der Zugriff auf die in einem GRAPH zu einem Knoten v assoziierte Information, wenn der Iterator it in der Iterationsreihenfolge gerade auf diesem v steht, durch

G[it];

Wir sehen, dass hiermit der Iterationsprozess wesentlich feiner gesteuert werden kann als durch das entsprechende Makro: Das Weiterschieben des Iterators ist an beliebigen Stellen möglich und nicht an den Schleifenkopf gebunden, der Iterator kann durch it-- wieder zurückgeschoben werden, und die Gültigkeitsbedingung kann durch jede andere Bedingung ersetzt werden. Zudem können iteratoren-basierte Implementierungen leicht in Programme eingepasst werden, die gemäß des STL-Stils für Iteratoren implementiert sind. (Dieser Stil wurde für die C++-Standard-Bibliothek übernommen.) Allerdings wächst auch die Komplexität des Codes, wie wir gleich an einem Beispiel sehen werden.

Um Graph-Iteratoren benutzen zu können, muss die Header-Datei graph_iterator.h eingebunden werden. Wir stellen daraus die wichtigsten Iteratoren-Klassen kurz vor:

Mit einem NodeIt kann, wie wir schon gesehen haben, über alle Knoten eines Graphen iteriert werden. Entsprechend kann mit einem Kanten-Iterator vom Typ EdgeIt über alle Kanten iteriert werden.

Mit einem OutAdjIt kann über alle von einem Knoten ausgehenden Kanten iteriert werden, mit einem InAdjIt über alle zu einem Knoten inzidenten, und mit AdjIt über alle adjazenten Kanten. Ein solcher Iterator it muss zuerst initialisiert werden; dabei ist der Graph G und der Knoten v in G festzulegen, über dessen ausgehenden und/oder eingehenden Kanten it iterieren soll. Dies geschieht durch

it.init(G, v);

Das folgende Programm ist eine Neuformulierung des gerade vorgestellten Programms zur Durchwanderung des Graphen aus Abbildung 5.5; die hier gezeigte Version arbeitet ausschließlich mit Iteratoren, um sich im Graphen zu bewegen. Der Leser möge die Komplexität des Codes mit der des obigen Programms vergleichen.

Filename: IteratingNavigatingGraphsWithIterators.C
#include <LEDA/graph.h>
#include <LEDA/graph_iterator.h>
#include <LEDA/string.h>
#include <iostream>

using leda::GRAPH;
using leda::node;
using leda::edge;
using leda::NodeIt;
using leda::OutAdjIt;
using leda::InAdjIt;
using leda::string;
using std::cout;
using std::endl;


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

  node v0 = G.new_node(0);
  node v1 = G.new_node(1);
  node v2 = G.new_node(2);

  edge a = G.new_edge(v0, v1, "a");
  edge b = G.new_edge(v1, v2, "b");
  edge c = G.new_edge(v0, v2, "c");
  edge d = G.new_edge(v0, v1, "d");
  edge e = G.new_edge(v2, v2, "e");

  cout << "Adjacent edges (out_edges):" << endl;
  for (NodeIt n_it(G); n_it.valid(); n_it++) {
    cout << "Node " << G.inf(n_it) << ": ";
    cout << "Outdegree=" << G.outdeg(n_it) << ". ";
    for(OutAdjIt out_it(G, n_it); out_it.valid(); out_it++) {
      node s = G.source(out_it);
      node t = G.target(out_it);
      cout << G[out_it] << "=(" << G[s] << "," << G[t] << ") ";
    }
    cout << endl;
  }

  cout << "\nIncident edges:" << endl;
  for (NodeIt n_it(G); n_it.valid(); n_it++) {
    cout << "Node " << G.inf(n_it) << ": ";
    cout << "Indegree=" << G.indeg(n_it) << ". ";
    for(InAdjIt in_it(G, n_it); in_it.valid(); in_it++) {
      node s = G.source(in_it);
      node t = G.target(in_it);
      cout << G[in_it] << "=(" << G[s] << "," << G[t] << ") ";
    }
    cout << endl;
  }

  
  cout << "\nNavigating from node 0 to nodes with higher number:\n";
  NodeIt v_it;
  v_it.init(G, v0);
  while(1) {
    cout << "Reached node " << G.inf(v_it) << endl;
    NodeIt v_it_old = v_it;
    for(OutAdjIt out_it(G, v_it); out_it.valid(); out_it++) {
      NodeIt w_it;
      w_it.init(G, G.opposite(v_it, out_it));
      if(G.inf(w_it) > G.inf(v_it)) {
        v_it = w_it;
        break;
      }
    }
    if(v_it_old == v_it) 
      break;    
  }
  
  
  cout << "\nNavigating backwards from node 2 ";
  cout << "to nodes with lower number:\n";
  v_it.init(G, v2);
  while(1) {
    cout << "Reached node " << G.inf(v_it) << ". ";
    NodeIt v_it_old = v_it;
    for(InAdjIt in_it(G, v_it); in_it.valid(); in_it++) {
      NodeIt w_it;
      w_it.init(G, G.opposite(v_it, in_it));
      if(G.inf(w_it) < G.inf(v_it)) {
        v_it = w_it;
        cout << "Traversing edge " << G.inf(in_it);
        cout << " backwards." << endl;
        break;
      }
    }
    if(v_it_old == v_it) 
      break; 
  }
  cout << endl;
  
}

Übungen

Übung 51.

Formulieren Sie obige Programme so, dass sie nach einem make_undirected() auf dem ungerichteten Graphen aus Abbildung 5.6 laufen.

Übung 52.

Ein gerichteter Graph heißt regulär vom Grad r, wenn alle Knoten denselben Ausgangsgrad r haben.

Schreiben Sie eine Funktion Is_Regular(), die testet, ob ein Graph regulär ist und im Falle der Regularität den Grad r berechnet.

Übung 53.

Schreiben Sie Ihre eigene Version von TOPSORT(), die in dem Fall, dass keine Topologische Sortierung möglich ist, auch noch einen Zyklus entdeckt und ausgibt. Schreiben Sie eine Version mit und eine ohne Graph-Iteratoren.

Übung 54.

In einer Kunstausstellung führen Gänge (Kanten) an den Exponaten vorbei. Die Gänge stoßen an bestimmten Kreuzungspunkten (Knoten) aufeinander. Auf beiden Seiten eines Ganges steht ein Exponat; daher wäre es wünschenswert, dass die Besucher so durch die Ausstellung geleitet werden, dass sie vom Eingang aus jeden Gang einmal in jeder der beiden Richtungen durchlaufen und am Schluss wieder zum Eingang zurückkehren.

Die Problemstellung lautet abstrahiert: Finde in einem ungerichteten Graphen von einem bestimmten Knoten s aus einen Pfad, der jede Kante einmal in beiden Richtungen durchläuft und wieder bei s endet. (Diese Problemstellung darf nicht mit der Frage nach einer Euler-Tour verwechselt werden, bei der jede Kante genau einmal durchlaufen werden soll. Wie Leonhard Euler 1736 bewiesen hat, existiert eine solche Tour genau dann, wenn jeder Knoten einen geraden Grad hat. Seine Beschäftigung mit diesem Problem gilt als Geburtsstunde der Graphentheorie.)

Ein solcher Pfad kann im Gegensatz zu einer Euler-Tour immer wie folgt konstruiert werden: Wir laufen von s aus eine beliebige Kante e entlang zu einem Knoten a und merken uns dort, dass wir als erstes über e zu a gekommen sind. Von a aus laufen wir weiter, immer die Kante f markierend, über die wir als erste zu einem Knoten v gekommen sind. Jeder Knoten v darf durchaus mehrmals besucht werden, auch s. Jedes Mal, wenn wir nach v kommen, wählen wir eine andere Kante, um v wieder zu verlassen. Die ursprüngliche Kante f dürfen wir erst wieder zum Verlassen verwenden, wenn wir alle anderen Kanten schon benutzt haben.

Überlegen Sie sich, warum dieses Verfahren alle Kanten des Graphen genau einmal in jeder der beiden Richtungen durchläuft und wieder im Startknoten s endet.

Implementieren Sie dieses Verfahren mit Hilfe der bisher eingeführten Datenstrukturen und Makros für Graphen. Prägen Sie sich das Verfahren ein für den Fall, dass Sie einmal in einem Labyrinth oder einer Höhle gefangen sind.




Imprint-Dataprotection