Typunabhängiges Traversieren

G_forAllVertices (G_graph g, G_vertex v) { statements }  

Führt für jeden Knoten des Graphen g die Anweisungen statements aus. Der aktuelle Knoten steht dabei jeweils in der Variablen v. Die Reihenfolge entspricht der Folge aller Knoten des Graphen Vseq.

Beispiel:

Durch folgendes Beispiel wird process() für alle Knoten des Graphen aufgerufen:

G_forAllVertices (g, v)
{
  process (g, v);
}

Bemerkungen:

Im Gegensatz zu Methoden muß bei Makros der Graph explizit angegeben werden.

Innerhalb der Schleife darf die Folge aller Knoten Vseq nicht durch Erzeugen, Löschen oder Umordnen von Knoten verändert werden. Sie wird mit den Methoden  firstVertex() und  nextVertex() realisiert.

Aufwand:

Jeder Knoten wird einmal bearbeitet: O(|Vseq|)

G_forAllEdges (G_graph g, G_edge e) { statements }  

Führt für jede Kante des Graphen g die Anweisungen statements aus. Die aktuelle Kante steht dabei jeweils in der Variablen e. Die Reihenfolge entspricht der Folge aller Kanten des Graphen Eseq.

Bemerkungen:

Im Gegensatz zu Methoden muß bei Makros der Graph explizit angegeben werden.

Innerhalb der Schleife darf die Folge aller Kanten Eseq nicht durch Erzeugen, Löschen (auch indirekt durch Löschen eines Knotens) oder Umordnen von Kanten verändert werden. Die Schleife wird mit den Methoden  firstEdge() und  nextEdge() realisiert.

Aufwand:

Jede Kante wird einmal bearbeitet: O(|Eseq|)

G_forAllIncidentEdges (G_graph g, G_vertex v, G_edge e) { statements }  

Führt für jede mit dem Knoten v inzidente Kante des Graphen g die Anweisungen statements aus. Die aktuelle Kante steht dabei jeweils in der Variablen e. Die Reihenfolge, in der die Kanten bearbeitet werden, entspricht $\Lambda(v)$. Schlingen werden zweimal, nämlich für beide Orientierungen bearbeitet.

Bemerkungen:

Im Gegensatz zu Methoden muß bei Makros der Graph explizit angegeben werden.

In der Schleife darf die Folge $\Lambda(v)$ der zu v inzidenten Kanten nicht durch Hinzufügen, Löschen (auch indirekt durch Löschen eines Knotens) oder Umordnen von Kanten verändert werden. Die Schleife wird mit den Methoden  first() und  next() realisiert.

Aufwand:

Jede zu v inzidente Kante wird einmal bearbeitet: $O(\vert\Lambda(v)\vert)$

G_forAllInEdges (G_graph g, G_vertex v, G_edge e) { statements }  

Führt für jede in-Kante des Knotens v die Anweisungen statements aus. Die aktuelle Kante steht dabei jeweils in der Variablen e. Die Reihenfolge, in der die Kanten bearbeitet werden, entspricht $\Lambda^-(v)$.

Bemerkungen:

Im Gegensatz zu Methoden muß bei Makros der Graph explizit angegeben werden.

In der Schleife darf die Folge $\Lambda(v)$ der zu v inzidenten Kanten nicht durch Hinzufügen, Löschen (auch indirekt durch Löschen eines Knotens) oder Umordnen von Kanten verändert werden. Die Schleife wird mit den Methoden  firstIn() und  nextIn() realisiert.

Aufwand:

Es wird über alle inzidenten Kanten gesucht: $O(\vert\Lambda(v)\vert)$

G_forAllOutEdges (G_graph g, G_vertex v, G_edge e) { statements }  

Führt für jede out-Kante des Knotens v die Anweisungen statements aus. Die aktuelle Kante steht dabei jeweils in der Variablen e. Die Reihenfolge, in der die Kanten bearbeitet werden, entspricht $\Lambda^+(v)$.

Bemerkungen:

Im Gegensatz zu Methoden muß bei Makros der Graph explizit angegeben werden.

In der Schleife darf die Folge $\Lambda(v)$ der zu v inzidenten Kanten nicht durch Hinzufügen, Löschen (auch indirekt durch Löschen eines Knotens) oder Umordnen von Kanten verändert werden. Die Schleife wird mit den Methoden  firstOut() und  nextOut() realisiert.

Aufwand:

Es wird über alle inzidenten Kanten gesucht: $O(\vert\Lambda(v)\vert)$

G_vertex G_graph::firstVertex () const  

Liefert den ersten Knoten aus der Knotensequenz des Graphen.

Rückgabewert:

Wenn kein Knoten vorhanden ist, wird G_VertexBottom geliefert.

Aufwand:

O(1), inline

G_vertex G_graph::nextVertex (G_vertex v) const  

Liefert den Knoten, der in der Knotensequenz des Graphen unmittelbar hinter v steht.

Rückgabewert:

Wenn es hinter v keine weiteren Knoten mehr gibt, wird G_VertexBottom zurückgegeben.

Fehlerfälle:

Es wird G_VertexBottom zurückgegeben und folgende Meldung ausgegeben.

grf007

Der Knoten v existiert nicht.

Aufwand:

O(1), inline

G_edge G_graph::firstEdge () const  

Liefert die erste Kante aus der Kantensequenz des Graphen.

Rückgabewert:

Wenn keine Kante vorhanden ist, wird G_EdgeBottom geliefert.

Aufwand:

O(1), inline

G_edge G_graph::nextEdge (G_edge e) const  

Liefert die Kante, die in der Kantensequenz des Graphen unmittelbar hinter e steht.

Rückgabewert:

Wenn es hinter e keine weiteren Kanten mehr gibt, wird G_EdgeBottom zurückgegeben.

Fehlerfälle:

Es wird G_EdgeBottom zurückgegeben und folgende Meldung ausgegeben.

grf008

Die Kante e existiert nicht.

Aufwand:

O(1), inline

G_edge G_graph::first (G_vertex v) const  

Liefert die erste Kante aus der Kantensequenz des Knotens v.

Rückgabewert:

Wenn keine Kante vorhanden ist, wird G_EdgeBottom geliefert.

Fehlerfälle:

Es wird G_EdgeBottom zurückgegeben und folgende Meldung ausgegeben.

grf007

Der Knoten v existiert nicht.

Aufwand:

O(1), inline

G_edge G_graph::next (G_edge e) const  

Liefert die Kante, die in der Kantensequenz des Knotens thisV(e) unmittelbar hinter e steht.

Rückgabewert:

Wenn es hinter e keine weiteren Kanten mehr gibt, wird G_EdgeBottom zurückgegeben.

Fehlerfälle:

Es wird G_EdgeBottom zurückgegeben und folgende Meldung ausgegeben.

grf008

Die Kante e existiert nicht.

Aufwand:

O(1), inline

G_edge G_graph::getNthEdge (G_vertex v, int n) const  

Liefert die n'te Kante, aus der Kantensequenz des Knotens v.

Rückgabewert:

Wenn es weniger als n inzidente Kanten gibt, wird G_EdgeBottom geliefert.

Fehlerfälle:

Es wird G_EdgeBottom zurückgegeben und eine der folgenden Meldungen ausgegeben.

grf007

Der Knoten v existiert nicht.

grf060

Es gibt zu wenig zu v inzidente Kanten.

Aufwand:

Die Kantensequenz des Knotens v wird sequentiell durchsucht: $O(\vert\Lambda(v)\vert)$

G_edge G_graph::firstIn (G_vertex v) const  

Liefert die erste in den Knoten v einlaufende Kante.

Rückgabewert:

Wenn keine Kante vorhanden ist, wird G_EdgeBottom geliefert.

Fehlerfälle:

Es wird G_EdgeBottom zurückgegeben und folgende Meldung ausgegeben.

grf007

Der Knoten v existiert nicht.

Aufwand:

Da in der Liste der inzidenten Kanten die erste eingehende Kante gesucht wird: $O(\vert\Lambda(v)\vert)$

G_edge G_graph::nextIn (G_edge e) const  

Liefert die nächste in den Knoten omega(e) einlaufende Kante.

Rückgabewert:

Wenn es hinter e keine weiteren Kanten mehr gibt, wird G_EdgeBottom zurückgegeben.

Fehlerfälle:

Es wird G_EdgeBottom zurückgegeben und folgende Meldung ausgegeben.

grf008

Die Kante e existiert nicht.

Aufwand:

Da in der Liste der inzidenten Kanten die nächste eingehende Kante gesucht wird: $O(\vert\Lambda(\omega(e))\vert)$

G_edge G_graph::getNthInEdge (G_vertex v, int n) const  

Liefert die n'te in den Knoten v einlaufende Kante.

Rückgabewert:

Wenn es weniger als n einlaufende Kanten gibt, wird G_EdgeBottom geliefert.

Fehlerfälle:

Es wird G_EdgeBottom zurückgegeben und eine der folgenden Meldungen ausgegeben.

grf007

Der Knoten v existiert nicht.

grf060

Es gibt zu wenig zu v inzidente Kanten.

Aufwand:

Die Kantensequenz des Knotens v wird sequentiell durchsucht: $O(\vert\Lambda(v)\vert)$

G_edge G_graph::firstOut (G_vertex v) const  

Liefert die erste vom Knoten v ausgehende Kante.

Rückgabewert:

Wenn keine Kante vorhanden ist, wird G_EdgeBottom geliefert.

Fehlerfälle:

Es wird G_EdgeBottom zurückgegeben und folgende Meldung ausgegeben.

grf007

Der Knoten v existiert nicht.

Aufwand:

Da in der Liste der inzidenten Kanten die erste ausgehende Kante gesucht wird: $O(\Lambda(v))$

G_edge G_graph::nextOut (G_edge e) const  

Liefert die nächste vom Knoten alpha(e) ausgehende Kante.

Rückgabewert:

Wenn es hinter e keine weiteren Kanten mehr gibt, wird G_EdgeBottom zurückgegeben.

Fehlerfälle:

Es wird G_EdgeBottom zurückgegeben und folgende Meldung ausgegeben.

grf008

Die Kante e existiert nicht.

Aufwand:

Da in der Liste der inzidenten Kanten die nächste ausgehende Kante gesucht wird: $O(\vert\Lambda(\alpha(e))\vert)$

G_edge G_graph::getNthOutEdge (G_vertex v, int n) const  

Liefert die n'te vom Knoten v ausgehende Kante.

Rückgabewert:

Wenn es weniger als n ausgehende Kanten gibt, wird G_EdgeBottom geliefert.

Fehlerfälle:

Es wird G_EdgeBottom zurückgegeben und eine der folgenden Meldungen ausgegeben.

grf007

Der Knoten v existiert nicht.

grf060

Es gibt zu wenig zu v inzidente Kanten.

Aufwand:

Die Kantensequenz des Knotens v wird sequentiell durchsucht: $O(\vert\Lambda(v)\vert)$