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:

• No macros are used.
• 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.
• The safe iterator classes (see the graph iterator LEDA extension package - they are documented here) provide a safe access to the nodes and edges of a graph. This means that the behavior of an iterator is well-defined even if its node or edge is removed through another 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.