5.2.4. Iterating over nodes and edges and navigating in graphs

Learning objectives

The methods sort_nodes(), bucket_sort_nodes(), sort_edges(), and bucket_sort_edges()
Macros for iterating over edges and nodes
The methods opposite(), source(), and target() for navigating
Arranging edges around nodes in a certain order
Hiding edges temporarily with hide_edge() and restore_edge()
Graph iterators

Navigare necesse est”. It is unavoidable to navigate, in daily life as well as in a graph. This section describes the different possibilities to iterate over the nodes and edges of a graph and to traverse a graph from node to node.

Iterating over all nodes and edges

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) { ... }

Iterating over adjacent edges and nodes

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).

Navigating

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.

An example

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).

Filename: IteratingNavigatingGraphs.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#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.

Influencing the order in in_edges(v) and out_edges(v)

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.)

Hiding edges temporarily

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.

Graph iterators

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.

Filename: IteratingNavigatingGraphsWithIterators.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#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;
  
}

Exercises

Exercise 52.

Rephrase the programs above so that they run on the undirected graph from Figure 5.7 after a make_undirected().

Exercise 53.

A directed graph is called regular of degree r if all nodes have the same out-degree r.

Write a function Is_Regular() that tests whether a graph is regular and that, in the case of regularity, calculates the degree of r.

Exercise 54.

Write your own version of TOPSORT() that, in case no topological sorting is possible, finds a cycle and returns it. Write a version with and a version without graph iterators.

Exercise 55.

In an art exhibition, the corridors (edges) lead along the exhibits. The corridors meet at certain crosspoints (nodes). On both side of a corridor stands an exhibit; therefore it is desirable to guide the visitors through the exhibition such that they pass every corridor once in both directions, starting from the entrance and returning back to the entrance in the end.

The problem definition in an abstract form reads as follows: Find a path from a certain node s that traverses every edge once in both directions and that ends in s again. (This problem definition must not be mixed up with the quest for a Euler tour, in which every edge is to be traversed exactly once. As Leonhard Euler proved in 1736, such a tour exists if and only if every node has an even degree. His reflection on this problem is regarded as the birth hour of graph theory.)

In contrast to a Euler tour, such a path can always be created as follows: From s, we walk along an arbitrary edge e to a node a and memorize there that we have reached a first via e. From a, we walk on, always marking the edge f that has been the first to lead us to a node v. Every node v may well be visited several times, so may s. Every time we arrive at v, we choose a different edge to leave v again. We may reuse the initial edge f for leaving v not until we have used all other edges.

Think over why this method traverses all edges of the graph exactly once in both directions and then stops at s again.

Implement this method with the help of the data structures and macros for graphs introduced until now. Memorize the method for the case that you are captured in a labyrinth or a cave.




Imprint-Dataprotection