We already got to know the macros

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

which can be used to iterate over all nodes and edges of a graph G. The nodes and edges are part of a list V and E, respectively; these macros and the following macros iterate over these lists. Furthermore, we already introduced the possibility to sort these lists. There are three possibilities for doing this (here we deal only with the possibilities for the node list V):

A call

G.sort_nodes(order);

with a node array node_array<T> order that is valid on G sorts the nodes in V in the order given by order. Here T has to be a numeric type.

A call

G.sort_nodes(cmp);

with a pointer to a comparison function for nodes

int (*cmp)(node, node);

sorts the nodes in V in the order given by cmp.

Finally, a call

G.bucket_sort_nodes(f);

executes bucket sort with the distribution function f(). With respect to this, the same holds what we said about bucket sort on linear lists in Section 2.3.4.

With the macro

forall_rev_nodes(v, G) { ... }

the list V can be traversed from behind to the front. Correspondingly, the list E can be traversed with the macro

forall_rev_edges(e, G) { ... }

The macro

forall_adj_nodes(v, w) { ... }

iterates over all nodes v that are adjacent to the node w. In the case of a directed graph, these are all v for which there is an edge (w,v) in the graph. In the undirected case, these are all v for which there is an edge (w,v) or an edge (v,w).

The macro

forall_adj_edges(e, w) { ... }

iterates over all edges e that are adjacent to the node w. In the case of a directed graph, these are all e whose source is w, that is, for which there is a node v and an edge (w,v) in the graph. In the undirected case, these are all e whose source or target is w.

For a directed graph, there are the following additional macros:

forall_out_edges(e, w) { ... }

is a faster version of forall_adj_edges(e,w).

forall_in_edges(e, w) { ... }

iterates over all edges that are incident to w, that is, the edges whose target is w.

Finally,

forall_inout_edges(e, w) { ... }

iterates first (sic!) over all edges in out_edges(w), and then over all edges in in_edges(w).

The most important method for navigating in a graph is probably opposite(). After a call

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

w is the endpoint of the edge e that is different from v. This method, in combination with the iteration macros above, is sufficient in most problems for navigating conveniently in a graph, that is, for jumping from node to node along a designated path.

Apart from opposite(), there are also the explicit methods

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

which return the source and the target of an edge e, respectively.

As an example for the possibilities of iteration and navigation that have been presented until now we want to create the graph from Figure 5.6, iterate over it, and navigate in it.

The following program first outputs the out-degree for every node and all adjacent edges. Then it outputs the in-degree for every node and all incident edges. Then it starts from node 0 and keeps on visiting nodes as long as it is able to jump from the current node to a node with a higher number (the first such node is chosen). Finally, it moves backwards from node 2 along an edge as long as it is able to jump to a node with a lower number (again, the first such node is chosen).

#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;
}

The program outputs the following:

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

Incident edges:
Node 0: In-degree=0.
Node 1: In-degree=2. a=(0,1) d=(0,1)
Node 2: In-degree=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.

The methods

G.indeg(v);
G.outdeg(v);

return the in-degree and the out-degree of a node v, respectively.

G.degree(v);

returns the degree, that is, the sum of in-degree and out-degree. In the undirected case, only degree() should be used.

In some algorithms, it is important to arrange the edges that leave a node and that are incident to a node in a certain order around this node, and to traverse the edges in this order. Here we give some examples for a directed graph.

A call

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

creates a new edge f=(source(e),w) that has the same source as edge e and that has the target w. It is arranged behind e in out_edges(source(e)). In other words: A new edge f is created that has the target w, that starts from the same node as e, and that is inserted behind e in the order of edges that are adjacent to source(e). If leda::before is given as a third argument, the edge f is inserted in front of e.

A call

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

changes the role of w: now w is interpreted as a source, and a new edge f=(w,target(e)) is created. It is arranged behind e in in_edges(target(e)). If leda::before is given as a third argument, it is inserted in front of e.

A call

edge f = G.adj_succ(e);

determines the edge f that immediately follows the edge e in the list adj_edges(source(e)) (in the directed case, this is the same list as out_edges(source(e))). The method returns nil if e is already the last edge. With this, the position of an iteration step can be specified more accurately than with the iteration macros. Correspondingly, there is the method adj_pred(), which returns the predecessor in the adjacency list.

The methods cyclic_adj_succ() and cyclic_adj_pred() work correspondingly; they interpret the adjacency lists as circular lists, though (and therefore always return a predecessor and a successor, respectively.)

Sometimes it is convenient to remove edges temporarily from a graph and to unhide them again later. A call

G.hide_edge(e);

removes the edge e temporarily from G until it is unhidden again with

G.restore_edge(e);

A call restore_all_edges() unhides all hidden edges.

The method

G.hidden_edges();

returns a list of all currently hidden edges.

With

G.is_hidden(e);

one can inquire whether an edge e is currently hidden.

Iterators are a powerful concept in the object-oriented programming paradigm, and they are a basic design pattern, see [15]. In few words, an iterator is a small object that is associated to a certain linear sequence, for example, to the sequence of the edges that leave the node v, which are held in the list out_edges(v). An iterator is used to traverse these elements of the sequence one after the other.

Here we introduce shortly to some iterator classes of LEDA that can be used to iterate over the nodes and edges of a graph and to traverse the edges incident to and leaving a node. Thus, iterators are an alternative to the forall macros introduced above.

For example, the macro forall_nodes(v,G) is equivalent to the following use of an iterator of the class NodeIt:

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

Here a node iterator it, an object of class NodeIt, is defined on the graph G. As long as this iterator is valid, that is, as long as the iterator has not traversed all nodes of the graph, the body of the loop is executed. At the end of every iteration, the iterator is advanced by one position in the sequence with the increment operator it++.

Iterators can be used wherever a corresponding item of type node or edge can be used. So, for example, the information associated to a node v in a GRAPH is accessed with

G[it];

if the iterator it is standing on v in the iteration sequence.

We see that an iterator allows to steer the iteration process much more accurately than the corresponding macro: Advancing the iterator is possible at any position and is not restricted to the head of the loop, the iterator can be positioned back again with it--, and the validity constraint can be replaced by any other constraint. Furthermore, iterator-based implementations can be easily fit into programs that are implemented according to the STL style for iterators. (This style was adopted for the C++ standard library.) Unfortunately, also the complexity of the code grows, as we will see immediately in an example.

To use graph iterators, the header file graph_iterator.h has to be included. We introduce briefly to the most important iterator classes declared in this file:

All nodes of a graph can be iterated over with a NodeIt, as we have already seen. Correspondingly, all edges can be iterated over with an edge iterator of type EdgeIt.

With an OutAdjIt, all edges that leave a node can be iterated over, with an InAdjIt all edges that are incident to a node, and with an AdjIt all adjacent edges. Such an iterator it first has to be initialized. The initialization step has to specify the graph G and the node v in G over whose incident and/or adjacent edges it is to iterate. This is done with

it.init(G, v);

The following program is a rephrasing of the program just introduced for traversing the graph from Figure 5.6; the version shown here works exclusively with iterators to move in the graph. The reader may compare the complexity of the code with that of the program above.

#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;
  
}