node v;
forall_nodes (n, G) { ... }
Using the class NodeIt introduced in sect. Node Iterators, this
iteration can be re-written as follows:
for (NodeIt it (G); it.valid(); ++it) { ... }
The crucial differences are:
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).
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:
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.