Introduction

Iterators

Iterators are a powerful technique in object-oriented programming and one of the fundamental design patterns [35]. Roughly speaking, an iterator is a small, light-weight object, which is associated with a specific kind of linear sequence. An iterator can be used to access all items in a linear sequence step-by-step. In this section, different iterator classes are introduced for traversing the nodes and the edges of a graph, and for traversing all ingoing and/or outgoing edges of a single node.

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 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:

• 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 [63], (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.

Handles and 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^10.1.

An example shows how iterators can be used as handles:

    NodeIt it(G);
    while (it.valid()) { 
     cout << "current node " << index(it) << endl; }

STL Iterators

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

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

Data accessor is a design pattern[] that decouples data access from underlying implementation. Here, the pattern is used to decouple data access in graph algorithms from how data is actually stored outside the algorithm.

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 $\rightarrow$ T). An attributed set A = (S, a₁,..., a_m) consists of a set S and attributes a₁,..., 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 graphs:

• Classes GRAPH and UGRAPH (sects. Parameterized Graphs and  Parameterized Ugraphs) 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.

Graphiterator Algorithms

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

1. algorithms are instances of classes
2. algorithm instances have the ability to ``advance''
3. 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.