Iterators

Iterators are an alternative to the iteration macros introduced in sect. Graphs.3.(i). For example, consider the following iteration pattern:

node v; forall_nodes (n, G) { ... }Using the class

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

The crucial differences are:

- Iterators provide an intuitive means of
movement through the topology of a graph.
- Iterators are not bound to a loop, which means that the user has finer
control over the iteration process. For example, the continuation condition
*it.valid()*in the above loop could be replaced by another condition to terminate the loop once a specific node has been found (and the loop may be re-started at the same position later on). - The meaning of iteration may be modified seamlessly. For example, the
filter iterators defined in sect. Filter Node Iterator
restrict the iteration to a subset that is specified by an
arbitrary logical condition (
*predicate*). In other words, the nodes or edges that do not fulfill this predicate are filtered out automatically during iteration. - The functionality of iteration may be extended seamlessly. For example,
the observer iterators defined in sect. Observer Node Iterator
can be used to record details of the
iteration. A concrete example is given in sect. Observer Node Iterator:
an observer iterator can be initialized such that it records the number of
iterations performed by the iterator.
- Iterator-based implementations of algorithms can be easily
integrated into environments that are implemented according to the STL
style [69], (this style has been adopted for the standard C++
library). For this purpose, sect. STL Iterator Wrapper define adapters,
which convert graph iterators into STL iterators.

Iterators can be used whenever the corresponding handle can be used.
For example, node iterators can be used where a node is requested
or edge iterators can be used where an edge is requested.
For adjacency iterators, it is possible to use them whenever
an edge is requested^{14.1}.

An example shows how iterators can be used as handles:

NodeIt it(G); leda::node_array<int> index(G); leda::node v; int i=0; forall_nodes(v,G) index[v]=++i; while (it.valid()) { cout << "current node " << index(it) << endl; }

Those who are more used to STL may take advantage from the following
iterator classes: `NodeIt_n`, `EdgeIt_e`, `AdjIt_n`,
`AdjIt_e`, `OutAdjIt_n`, `OutAdjIt_e`, `InAdjIt_n`,
`InAdjIt_e`. The purpose of each iterator is the same as in
the corresponding standard iterator classes `NodeIt`, `EdgeIt` ...
The difference is the interface, which is exactly that of
the STL iterator wrapper classe (see sect. stlwrap for more
information).

An example shows why these classes are useful (remember the example from the beginning):

NodeIt_n base(G); for(NodeIt_n::iterator it=base.begin();it!=base.end(); ++it) { cout << "current node " << index(*it) << endl; }

As in STL collections there are public type definitions in all
STL style graph iterators. The advantage is that algorithms can
be written that operate independingly of the underlying type
(note: `NodeIt_n` and `NodeIt_n::iterator` are equal types).

Circulators differ from Iterators in their semantics. Instead of becoming invalid at the end of a sequence, they perform cyclic iteration. This type of ''none-ending-iterator`` is heavily used in the CGAL .

Data Accessors

Generally, an attributed graph consists of a (directed or undirected) graph and an arbitrary number of node and edge attributes. For example, the nodes of a graph are often assigned attributes such as names, flags, and coordinates, and likewise, the edges are assigned attributes such as lengths, costs, and capacities.

More formally, an *attribute* *a* of a set *S* has a certain type *T*
and assigns a value of *T* to every element of *S* (in other words, *a*
may be viewed as a function
*a* : *S* *T*). An *attributed set*
*A* = (*S*, *a*_{1},..., *a*_{m}) consists of a set *S* and attributes
*a*_{1},..., *a*_{m}.
An attributed graph is a (directed or undirected) graph *G* = (*V*, *E*) such that
the node set *V* and the edge set *E* are attributed.

Basically, LEDA provides two features to define attributes for graph:

- Classes
*GRAPH*and*UGRAPH*(sects. Parameterized Graphs and Parameterized Ugraph) are templates with two arguments,*vtype*and*etype*, which are reserved for a node and an edge attribute, respectively. To attach several attributes to nodes and edges,*vtype*and*etype*must be instantiated by structs whose members are the attributes. - A
*node array*(sect. Node Arrays) or*node map*(sect. Node Maps) represents a node attribute, and analogously,*edge arrays*(sect. Edge Arrays) and*edge maps*(sect. Edge Maps), represent edge attributes. Several attributes can be attached to nodes and edges by instantiating several arrays or maps.

Data accessors provide a uniform interface to access attributes, and the concrete organization of the attributes is hidden behind this interface. Hence, if an implementation of an algorithm does not access attributes directly, but solely in terms of data accessors, it may be applied to any organization of the attributes (in contrast, the algorithms in sect. Graph Algorithms require an organization of all attributes as node and edge arrays).

Every data accessor class *DA* comes with a function template * get*:

T get(DA da, Iter it);

This function returns the value of the attribute managed by the data accessor
*da* for the node or edge marked by the iterator *it*. Moreover,
most data accessor classes also come with a function template *set*:

void set(DA da, Iter it, T value);

This function overwrites the value of the attribute managed by the data
accessor *da* for the node or edge marked by the iterator *it* by
*value*.

The data accessor classes that do not provide a function template * set* realize attributes in such a way that a function *set* does
not make sense or is even impossible. The *constant accessor* in
sect. Constant Accessors is a concrete example: it realizes an attribute
that is constant over the whole attributed set and over the whole time
of the program. Hence, it does not make sense to provide a function * set*. Moreover, since the constant accessor class organizes its attribute
in a non-materialized fashion, an overwriting function *set* is even
impossible.

**Example:** The following trivial algorithm may serve as an example to
demonstrate the usage of data accessors and their interplay with various
iterator types. The first, nested loop accesses all edges once. More
specifically, the outer loop iterates over all nodes of the graph, and the
inner loop iterates over all edges leaving the current node of the outer loop.
Hence, for each edge, the value of the attribute managed by the data accessor
*da* is overwritten by *t*. In the second loop, a linear edge iterator
is used to check whether the first loop has set all values correctly.

template <class T, class DA> void set_and_check (graph& G, DA da, T t) { for (NodeIt nit(G); nit.valid(); ++nit) for (OutAdjIt oait(nit); oait.valid(); ++oait) set (da, eit, t); for (EdgeIt eit(G); eit.valid(); ++eit) if (get(da,it) != t) cout << "Error!" << endl; }

To demonstrate the application of function *set_and_check*, we first
consider the case that *G* is an object of the class *GRAPH* derived
from *graph* (sect. Graphs), that the
template argument *vtype*
is instantiated by a struct type *attributes*, and that the ` int`-member *my_attr* of *attributes* shall be
processed by * set_and_check* with value 1. Then *DA* can be instantiated as a
*node_member_da*:

node_member_da<attributes,int> da (&attributes::my_attr); set_and_check (G, da, 1);

Now we consider the case that the attribute to be processed is stored in an
*edge_array<int>* named *my_attr_array*:

node_array_da<int> da (my_attr_array); set_and_check (G, da, 1);

Hence, all differences between these two cases are factored out into a single declaration statement.

Several basic graph algorithms were re-implemented to use only graph iterators and data accessors. Moreover they share three design decisions:

**algorithms are instances**of classes- algorithm instances have the
**ability to ``advance''** - algorithm instances provide
**access to their internal states**

An example for an algorithm that supports the first two decisions is:

class Algorithm { int state, endstate; public: Algorithm(int max) : endstate(max), state(0) { } void next() { state++; } bool finished() { return state>=endstate; } };

With this class `Algorithm` we can easily instantiate an
algorithm object:

Algorithm alg(5); while (!alg.finished()) alg.next();

This small piece of code creates an algorithm object and invokes ``next()'' until it has reached an end state.

An advantage of this design is that we can write basic algorithms, which can be used in a standardized way and if needed, inspection of internal states and variables can be provided without writing complex code. Additionally, it makes it possible to write persistent algorithms, if the member variables are persistent.

Actually, those algorithms are quite more flexible than ordinary written algorithm functions:

template<class Alg> class OutputAlg { Alg alg; public: OutputAlg(int m) : alg(m) { cout << "max state: " << m << endl; } void next() { cout << "old state: " << alg.state; alg.next(); cout << " new state: " << alg.state << endl; } bool finished() { return alg.finished(); } };

This wrapper algorithm can be used like this:

OutputAlg<Algorithm> alg(5); while (!alg.finished()) alg.next();

In addition to the algorithm mentioned earlier this wrapper writes the internal states to the standard output.

This is as efficient as rewriting the ```Algorithm`''-class
with an output mechanism, but provides more flexibility.