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.
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 outdegree for every node and all adjacent edges. Then it outputs the indegree 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: 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.
The methods
G.indeg(v); G.outdeg(v);
return the indegree and the outdegree of a node v, respectively.
G.degree(v);
returns the degree, that is, the sum of indegree and outdegree. 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);
Iterators are a powerful concept in the objectoriented 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, iteratorbased 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; }
Exercise 52.  Rephrase the programs above so that they run on the
undirected graph from Figure 5.7 after
a 
Exercise 53.  A directed graph is called regular of degree r if all nodes have the same outdegree r. Write a
function 
Exercise 54.  Write your own version of

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. 